STL vector vs list: Most efficient for graph adjacency lists?

Question

Lists consume most of their time in allocating memory when pushing_back. On the other hand, vectors have to copy their elements when a resize is needed. Which container is, therefore, the most efficient for storing an adjacency list?

Hat

@quasiverse: the requirements on vector essentially require a copy as it grows. vectors are required to store their elements contiguously. As you add elements, you will eventually use up the allocated space, and on the next addition you're going to get a new memory allocation followed by a copy of the current elements to the new space, followed by a deallocation of the old space. – Obstreperous

Answer 1

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 instead¹. 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.}

Jacobsohn

Answer 2

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.

Neuburger

Answer 3

STL containers are not rigidly defined, so implementations vary. If you're careful you can write your code so that it doesn't care whether it's a vector or a list that's being used, and you can just try them to see which is faster. Given the complexity of cache effects, etc., it's nearly impossible to predict the relative speeds with any accuracy.

Azeotrope

Answer 4

You can add third option to this comparison: list with specialized allocator.

Using allocators for small objects of fixed size may greatly increase speed of allocation/deallocation...

Sluggard

Answer 5

This tutorial site recommends using an array of lists or I guess you can use a vector of list elements instead: array of lists adj list

Strepitous