Why the libc++ std::vector internally keeps three pointers instead of one pointer and two sizes?

by

It’s because the rationale is that performance should be optimized for iterators, not indices.
(In other words, performance should be optimized for begin()/end(), not size()/operator[].)
Why? Because iterators are generalized pointers, and thus C++ encourages their use, and in return ensures that their performance matches those of raw pointers when the two are equivalent.

To see why it’s a performance issue, notice that the typical for loop is as follows:

for (It i = items.begin(); i != items.end(); ++i)
    ...

Except in the most trivial cases, if we kept track of sizes instead of pointers, what would happen is that the comparison i != items.end() would turn into i != items.begin() + items.size(), taking more instructions than you’d expect. (The optimizer generally has a hard time factoring out the code in many cases.) This slows things down dramatically in a tight loop, and hence this design is avoided.

(I’ve verified this is a performance problem when trying to write my own replacement for std::vector.)

Edit: As Yakk pointed out in the comments, using indices instead of pointers can also result in the generation of a multiplication instruction when the element sizes aren’t powers of 2, which is pretty expensive and noticeable in a tight loop. I didn’t think of this when writing this answer, but it’s a phenomenon that’s bitten me before (e.g. see here)… bottom line is, in a tight loop everything matters.

More Related Contents:

  1. Erasing elements from a vector
  2. Thou shalt not inherit from std::vector
  3. Why can’t I make a vector of references?
  4. What’s the most efficient way to erase duplicates and sort a vector?
  5. Concatenating two std::vectors
  6. vector vs. list in STL
  7. How do I sort a std::vector by the values of a different std::vector?
  8. When vectors are allocated, do they use memory on the heap or the stack?
  9. Is it safe to assume that STL vector storage is always contiguous?
  10. Efficient way of reading a file into an std::vector?
  11. Looking for C++ STL-like vector class but using stack storage
  12. How to initialize std::vector from C-style array?
  13. Appending a vector to a vector [duplicate]
  14. Sorting a vector in descending order
  15. Why is it OK to return a ‘vector’ from a function?
  16. How to use std::sort with a vector of structures and compare function?
  17. std::vector, default construction, C++11 and breaking changes
  18. Initial capacity of vector in C++
  19. std::vector iterator invalidation
  20. STL vector and thread-safety
  21. Sorting a std::vector by the string?
  22. How do you copy the contents of an array to a std::vector in C++ without looping?
  23. How to make elements of vector unique? (remove non adjacent duplicates)
  24. Why would I prefer using vector to deque
  25. std::vector removing elements which fulfill some conditions
  26. Can std::vector emplace_back copy construct from an element of the vector itself?
  27. iterator for 2d vector
  28. C++ template function compiles in header but not implementation
  29. vector and const
  30. How to get the address of the std::vector buffer start most elegantly?

Leave a Comment