Relative performance of std::vector vs. std::list vs. std::slist?

by

As usual the best answer to performance questions is to profile both implementations for your use case and see which is faster.

In general if you have insertions into the data-structure (other than at the end) then vector may be slower, otherwise in most cases vector is expected to perform better than list if only for data locality issues, this means that if two elements that are adjacent in the data-set are adjacent in memory then the next element will already be in the processor’s cache and will not have to page fault the memory into the cache.

Also keep in mind that the space overhead for a vector is constant (3 pointers) while the space overhead for a list is paid for each element, this also reduces the number of full elements (data plus overhead) that can reside in the cache at any one time.

More Related Contents:

  1. Efficiency of the STL priority_queue
  2. I wrote this method to delete duplicate elements of a linked list, but it shows segmentation fault, why? [closed]
  3. Is std::vector so much slower than plain arrays?
  4. How to overload std::swap()
  5. Why is std::map implemented as a red-black tree?
  6. Why does the C++ STL not provide any “tree” containers?
  7. Looking for C++ STL-like vector class but using stack storage
  8. Is there a way to access the underlying container of STL container adaptors?
  9. What’s faster, iterating an STL vector with vector::iterator or with at()?
  10. A proper way to create a matrix in c++
  11. vector or map, which one to use?
  12. How to choose between map and unordered_map?
  13. adding list items or nodes in linked list
  14. Performance of qsort vs std::sort?
  15. Order Statistic Tree in C++
  16. Erasing elements from a vector
  17. Concise explanation of reference collapsing rules requested: (1) A& & -> A& , (2) A& && -> A& , (3) A&& & -> A& , and (4) A&& && -> A&&
  18. Why are Standard iterator ranges [begin, end) instead of [begin, end]?
  19. Why do I get the same sequence for every run with std::random_device with mingw gcc4.8.1?
  20. Nice way to append a vector to itself
  21. Is inline assembly language slower than native C++ code?
  22. Why is value taking setter member functions not recommended in Herb Sutter’s CppCon 2014 talk (Back to Basics: Modern C++ Style)?
  23. Non-copyable elements in vector
  24. How to make elements of vector unique? (remove non adjacent duplicates)
  25. How does overloading of const and non-const functions work?
  26. Does boost have a datatype for set operations that is simpler than the STL?
  27. c++11 regex slower than python
  28. STL deque accessing by index is O(1)?
  29. Incrementing iterators: Is ++it more efficient than it++? [duplicate]
  30. Can std::vector emplace_back copy construct from an element of the vector itself?

Leave a Comment