Quote:Original post by Wiggin
Each partition only belongs to one list (anything else would be horrid to work with). Actually, I only have two lists: One for partitions with moving objects within, and one for those without. The partitioning is updated every frame.
Zahlmans code absolutely solved the problem as stated, but not fast enough for my purpose.
Oh. Well, that makes things MUCH clearer then. :)
Don't move things about between two lists at all. Instead, partition a single list, remembering (by storing an iterator) where one partition ends and the next begins. (Yeah, partitioning a list of partitions... oh dear, name overload!)
#include <algorithm>#include <list>bool hasMovingObject(const Partition& p) { // logic here...}class World { // ... std::list<Partition> partitions; std::list<Partition>::iterator firstWithoutMovingObjects; // ... void update() { // ... // Re-partition the list firstWithoutMovingObjects = std::partition(partitions.begin(), partitions.end(), hasMovingObject); // ... updatePartitionsWithMovingObjects(partitions.begin(), firstWithoutMovingObjects); updatePartitionsWithoutMovingObjects(firstWithoutMovingObjects, partitions.end()); // ... }};
Quote:
I've considered using arrays, but that entails a whole host of other issues.
The best part about the standard library algorithms is that you are insulated against changes to your container types (given a few careful typedefs). They even work on plain arrays :)
