I've been reading up about how linked lists are terrible for random access and cache locality, and how the inventor of the language Bjarne Stroustrup himself says you should always use vectors... but I think I have a special case.

I'm going to have a dynamically sized list of pointers. The only reason for keeping track of the set is so that I can iterate over it when my program closes and free up any of the pointers that haven't already been released. Other than that, I'll never iterate over the list. I'm only going to be adding to the end of it (it's doubly linked). I'm going to be deleting from anywhere within it at any time. Anyone who uses data from the set is going to get a pointer to the new element in the list to use directly, so again no iteration for access or deletion. Cache misses are still a concern, but since these are all pointers I don't think the vector really buys me anything.

Does anyone have an argument why a linked list in this instance isn't the best option?

Does anyone have an argument why a linked list in this instance isn't the best option?

It sounds like you're going to end up fragmenting your memory space with list nodes everywhere.

Really, the idea doesn't make any sense to me. What problem exactly is this list meant to solve?

Paradigm Shifter, that is blasphemy. I'm going to delete all my allocated memory before I leave. I'm never going to iterate in order to access an element, so the random access clause isn't an issue.

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.

Pink Horror, I'm going to fragment the memory regardless of whether I use a vector or a list, since the elements are pointers to dynamically allocated memory. This list is literally for managing a collection of pointers that I'll only need to iterate over when the program closes and I want to delete anything that's left over.

std::vector uses exponential growth so you don't actually hit the resize penalty frequently. However, if you are worried about it you can use std::deque.

Paradigm Shifter, I agree completely with that. I'll only iterate at termination, which is when I'm fine with taking that performance hit.

SiCrane, I don't think a deque would give me better performance over a linked list. I'm going to be removing elements from the middle of the list regularly.

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'.

http://www.adrinael.net/containerchoice.png

http://www.baptiste-wicht.com/2012/11/cpp-benchmark-vector-vs-list/

TLDR: A list is mostly slower, only exception is very large objects, but you want to save tiny pointers.