I agree with ApochPiQ: If the order of your elements don't matter, use a vector and swap-and-pop.
ApochPiQ, what about the fact that I'm going to add to the list at any time? I don't see a performance hit with the list, but with the vector I'll hit the resize & copy routines regularly.
First, if you're using C++11, you'd hit the resize and move your elements regularly (make sure your move-constructors are labeled noexcept, or you will in-fact copy). Second, your elements are pointers (so a move vs a copy isn't any different). Copying a range of pointers is as fast as copying a range of integers. It's a single memcpy() for the entire vector of pointers - very fast.
You can reserve() the amount of memory you're likely to need in advance, but even if you fail to reserve() you'll likely rarely need many actual reallocations.
Swapping and popping is very very fast also - no reallocation required. When you later push_back() a new element, you still won't need to reallocate, because your previous 'pop' (from the swap-and-pop) didn't reallocate, and so still has the not-yet-filled capacity.
I like having a SwapAndPop() templated function that I can pass a lambda to:
#include <iostream>
#include <algorithm> //For std::swap
#include <memory> //For std::unique_ptr
#include <vector>
//std::make_unique implementation (it was forgotten in the C++11 standard, and will be added later).
//Once it's added, I can just remove this from here.
template<typename T, typename ...Args>
std::unique_ptr<T> make_unique( Args&& ...args )
{
return std::unique_ptr<T>( new T( std::forward<Args>(args)... ) );
}
//Swaps and pops every element in 'container', for which the callback function 'predicate(element)' returns true.
//This is faster than std::remove_if(), but does not preserve the order of the elements like 'remove_if()' does.
template<typename ContainerType, typename FunctionType>
void SwapAndPop(ContainerType &container, FunctionType predicate)
{
for(typename ContainerType::iterator it = container.begin(); it != container.end();)
{
if(predicate(*it))
{
//Swap the value of the current element with the element at the back of the container.
std::swap(*it, container.back());
//Pop the back of the container.
container.pop_back();
if(container.empty())
{
break;
}
}
else
{
++it;
}
}
}
class Object
{
static unsigned nextID;
public:
Object() : timeToDelete(++nextID % 3), id(nextID) { }
bool timeToDelete = false;
size_t id = 0;
public:
typedef std::unique_ptr<Object> uPtr;
};
unsigned Object::nextID = 0;
int main()
{
const size_t NumObjectsForTest = 40;
std::vector<Object::uPtr> objects;
//Create all the objects.
for(size_t i = 0; i < NumObjectsForTest; ++i)
{
objects.push_back(make_unique<Object>());
}
//Print all the objects.
for(const auto &object : objects)
{
std::cout << "Object " << object->id << ": " << (object->timeToDelete? "[Time to delete]":"[Still alive]") << std::endl;
}
std::cout << "------------------------------------\n"
<< "Calling SwapAndPop...\n"
<< "------------------------------------\n";
SwapAndPop(objects, [](Object::uPtr &objectPtr) -> bool { return objectPtr->timeToDelete; });
//Print all the objects again.
for(const auto &object : objects)
{
std::cout << "Object " << object->id << ": " << (object->timeToDelete? "[Time to delete]":"[Still alive]") << std::endl;
}
return 0;
}
[run the code]
If you're likely to add/erase alot of objects of the exact same type (and if you find that this area of code is actually a bottleneck), you might even want to just 'swap', but leave the pointer and the memory hanging around so you can re-use it without the overhead of another call to 'new'.