'STL vector vs list: Most efficient for graph adjacency lists?
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?
Solution 1:[1]
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.
Solution 2:[2]
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.
Solution 3:[3]
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...
Solution 4:[4]
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
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Sandeep |
| Solution 2 | Tim Sylvester |
| Solution 3 | maxim1000 |
| Solution 4 | mLstudent33 |