STL vector vs list: Most efficient for graph adjacency lists?
I don't think this can be answered with absolute certainty. Nonetheless, I'd estimate that there's at least a 90% chance that a vector
will do better. An adjacency list actually tends to favor a vector
more than many applications, because the order of elements in the adjacency list doesn't normally matter. This means when you add elements, it's normally to the end of the container, and when you delete an element, you can swap it to the end of the container first, so you only ever add or delete at the end.
Yes, a vector
has to copy or move elements when it expands, but in reality this is almost never a substantial concern. In particular, the exponential expansion rate of a vector
means that the average number of times elements get copied/moved tends toward a constant -- and in a typical implementation, that constant is about 3.
If you're in a situation where the copying honestly is a real problem (e.g., copying elements is extremely expensive), my next choice after vector
still wouldn't be list
. Instead, I'd probably consider using std::deque
instead1. It's basically a vector of pointers to blocks of objects. It rarely has to copy anything to do an expansion, and on the rare occasion that it does, all it has to copy is the pointers, not the objects. Unless you need the other unique capabilities of a deque
(insert/delete in constant time at either end), a vector
is usually a better choice, but even so a deque
is almost always a better choice than a list (i.e., vector
is generally the first choice, deque
a fairly close second, and list
quite a distant last).
1. One minor aside though: at least in the past, Microsoft's implementation of `std::deque` had what I'd consider sort of a defect. If the size of an element in the `deque` is greater than 16, it ends up storing pointers to "blocks" of only a single element apiece, which tends to negate much of the advantage of using `deque` in the first place. This generally won't have much effect on its use for an adjacency list though.
The answer depends on use-case. P.S. @quasiverse - vectors call realloc when the memory you "::reserve", implicitly or explicitly, runs out
If you have a constantly changing adjacency list (inserts and deletes), a list would be best. If you have a more or less static adjacency list, and most of the time you are doing traversals/lookups, then a vector would give you the best performance.