What’s faster, iterating an STL vector with vector::iterator or with at()?

by

Using an iterator results in incrementing a pointer (for incrementing) and for dereferencing into dereferencing a pointer.
With an index, incrementing should be equally fast, but looking up an element involves an addition (data pointer+index) and dereferencing that pointer, but the difference should be marginal.
at() also checks if the index is within the bounds, so it could be slower.

Benchmark results for 500M iterations, vector size 10, with gcc 4.3.3 (-O3), linux 2.6.29.1 x86_64:
at(): 9158ms
operator[]: 4269ms
iterator: 3914ms

YMMV, but if using an index makes the code more readable/understandable, you should do it.

2021 update

With modern compilers, all options are practically free, but iterators are very slightly better for iterating and easier to use with range-for loops (for(auto& x: vs)).

Code:

#include <vector>

void iter(std::vector<int> &vs) {
    for(std::vector<int>::iterator it = vs.begin(); it != vs.end(); ++it)
        *it = 5;
}

void index(std::vector<int> &vs) {
    for(std::size_t i = 0; i < vs.size(); ++i)
        vs[i] = 5;
}

void at(std::vector<int> &vs) {
    for(std::size_t i = 0; i < vs.size(); ++i)
        vs.at(i) = 5;
}

The generated assembly for index() and at() is identical ([godbolt])(https://godbolt.org/z/cv6Kv4b6f), but the loop setup for iter() is three instructions shorter:

iter(std::vector<int, std::allocator<int> >&):
        mov     rax, QWORD PTR [rdi]
        mov     rdx, QWORD PTR [rdi+8]
        cmp     rax, rdx
        je      .L1
.L3:                              ; loop body
        mov     DWORD PTR [rax], 5
        add     rax, 4
        cmp     rax, rdx
        jne     .L3
.L1:
        ret
index(std::vector<int, std::allocator<int> >&):
        mov     rax, QWORD PTR [rdi]
        mov     rdx, QWORD PTR [rdi+8]
        sub     rdx, rax
        mov     rcx, rdx
        shr     rcx, 2
        je      .L6
        add     rdx, rax
.L8:                              ; loop body
        mov     DWORD PTR [rax], 5
        add     rax, 4
        cmp     rdx, rax
        jne     .L8
.L6:
        ret

More Related Contents:

  1. Is std::vector so much slower than plain arrays?
  2. Sorting a vector in descending order
  3. std::vector iterator invalidation
  4. What happens if you increment an iterator that is equal to the end iterator of an STL container
  5. iterator for 2d vector
  6. Erasing elements from a vector
  7. Why can’t I make a vector of references?
  8. Concatenating two std::vectors
  9. Why are Standard iterator ranges [begin, end) instead of [begin, end]?
  10. When vectors are allocated, do they use memory on the heap or the stack?
  11. Efficient way of reading a file into an std::vector?
  12. Why use non-member begin and end functions in C++11?
  13. Relative performance of std::vector vs. std::list vs. std::slist?
  14. What is the difference between const_iterator and non-const iterator in the C++ STL?
  15. vector or map, which one to use?
  16. Performance issue for vector::size() in a loop in C++
  17. std::vector, default construction, C++11 and breaking changes
  18. Custom Iterator in C++
  19. Initial capacity of vector in C++
  20. STL vector and thread-safety
  21. How do you copy the contents of an array to a std::vector in C++ without looping?
  22. How to make elements of vector unique? (remove non adjacent duplicates)
  23. Why would I prefer using vector to deque
  24. How to remove constness of const_iterator?
  25. std::vector removing elements which fulfill some conditions
  26. Do STL iterators guarantee validity after collection was changed?
  27. Incrementing iterators: Is ++it more efficient than it++? [duplicate]
  28. Can std::vector emplace_back copy construct from an element of the vector itself?
  29. Benefits of using reserve() in a vector – C++
  30. How to get the address of the std::vector buffer start most elegantly?

Leave a Comment