59

Can I do normal computations with iterators, i.e. just increment it by adding a number?

As an example, if I want to remove the element vec[3], can I just do this:

std::vector<int> vec;
for(int i = 0; i < 5; ++i){
      vec.push_back(i);
}
vec.erase(vec.begin() + 3); // removes vec[3] element

It works for me (g++), but I'm not sure if it is guaranteed to work.

Frank
  • 64,140
  • 93
  • 237
  • 324

4 Answers4

63

It works if the iterator is a random access iterator, which vector's iterators are (see reference). The STL function std::advance can be used to advance a generic iterator, but since it doesn't return the iterator, I tend use + if available because it looks cleaner.

C++11 note

Now there is std::next and std::prev, which do return the iterator, so if you are working in template land you can use them to advance a generic iterator and still have clean code.

Tuntuni
  • 481
  • 1
  • 7
  • 19
Todd Gardner
  • 13,313
  • 39
  • 51
  • 2
    Correct; added some documentation links that list which functions should be available to which types of iterators. – Todd Gardner Jun 23 '09 at 15:00
  • 2
    No, it doesn't. The + operator means "in one step, jump this far ahead" which a list iterator cannot do. Forward non-random-access iterators (like list iterators) support only support the increment (++) operator to advance one element at a time. As Todd said, you can use std::advance, which invokes the ++ operator repeatedly, to succinctly express the idea of moving a non-random iterator forward by a number of steps. – Tyler McHenry Jun 23 '09 at 15:02
  • 1
    Well, to be pedantic, it isn't guaranteed to work for bidirectional iterators like list, but I believe it isn't guaranteed to not work either; an implementation could add it. – Todd Gardner Jun 23 '09 at 15:03
  • 1
    @TylerMcHenry: I believe that `std::advance` exploits `+` for random access iterators (i.e. it doesn't always invoke `++` repeatedly). The [`std::advance` documentation](http://en.cppreference.com/w/cpp/iterator/advance) seems to agree. – Frerich Raabe Oct 18 '12 at 17:48
  • 2
    It's worth pointing out that the compilation error when using + with a std::list iterator is a *benefit* over std::advance in some situations. If you were advancing an arbitrary number of places in a vector (not just one place as here) and need to do it in constant time, then someone changes the container to a list, this might be an error you want to catch. Better to catch it at compilation time than when you notice the bad performance later (maybe on production!). Also, using + rather than std::advance documents the expectation that it's a constant-time operation. – Jim Oldfield Aug 19 '15 at 15:59
  • A point to note regarding std::advance and std::next. The std::advances takes an iterator by reference, so it will modify the iterator that you pass in. The std::next don't modify the input variable but will return the updated iterator. Whether you wish to modify your original iterator will influence which one to use. – nishant Jul 06 '18 at 21:40
4

A subtle point is that the operator+ takes a Distance; i.e., a signed integer. If you increment the iterator by an unsigned, you may lose precision and run into a surprise. For example on a 64 bit system,

std::size_t n = (1 << 64) - 2;
std::vector<double> vec(1 << 64);
std::vector<double> slice(vec.begin() + n, vec.end());

leads to implementation-defined behavior. With g++ or clang, you can ask the compiler to warn you about such undesired conversions with the warning flag -Wsign-conversion that is not part of the canonical -Wall or -Wextra.

A work-around is to work on the pointer directly

std::vector<double> slice(vec.data() + n, vec.data() + vec.size());

It's not pretty but correct. In some occasions, you need to construct the iterator manually, for example

std::vector<double>::iterator fromHere{vec.data() + n};
vec.erase(fromHere, vec.end());
Fred Schoen
  • 1,372
  • 13
  • 18
  • Is there any documentation on the constructors available for std::vector::iterator? – ghd Dec 29 '19 at 14:51
  • 1
    The example here involves implicit conversion of the value of `n` from unsigned (size_t) to signed (Distance) type. This leads to **implementation-defined** behavior when the value of `n` is too large to be represented by `Distance` data type. _It will never lead to undefined behavior_. – ghd Jan 02 '20 at 04:14
  • I know the differences are subtle. On https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior, I found a citation of the standard that `An example of undefined behavior is the behavior on integer overflow.`. I thought it would fall into that category. If it doesn't, can @ghd provide a statement from the C++ standard that it is implementation-defined? – Fred Schoen Jan 21 '20 at 09:56
  • In the example code snippet above, where is the possibility of integer overflow? The conversion of unsigned to signed is _not considered as overflow_ if the unsigned value cannot be represented as signed value. As per the C++17 working draft standard (N4659) **7.8**: _If the destination type is signed, the value is unchanged if it can be represented in the destination type; otherwise, the value is implementation-defined._ Only [overflow in signed arithmetic](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Overflows) can result in undefined behavior. – ghd Jan 24 '20 at 04:18
  • Updated the answer to use _implementation-defined_ , thanks @ghd A related note is https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#es106-dont-try-to-avoid-negative-values-by-using-unsigned – Fred Schoen Dec 15 '20 at 10:52
2

It works with random access iterators. In general you may want to look at std::advance which is more generic. Just be sure to understand performance implications of using this function template.

Nemanja Trifunovic
  • 24,346
  • 3
  • 50
  • 88
1

Number arithmetic is possible only with random access iterators such as those in std::vector and std::deque.

    std::vector<int>list={1,2,3,4,5,6,7,8};
    auto last_v=*(list.end()-1);
    auto third_last_v=*(list.end()-3);
    std::cout<<"Last & 3rd last entry for vector:"<<last_v<<","<<third_last_v<<std::endl;

will output 8 and 6, however for std::map, std::multimap, std::set, std::multiset having bidirectional iterator

    std::map<int,std::string> map_={{1,"one"},{2,"two"},{3,"three"}};
    auto last_mp=*(map_.end()-1);
    auto third_last_mp=*(map_.end()-3);
    std::cout<<"Last & 3rd last entry for map:("<<last_mp.first<<","<<last_mp.second<<") and ("<<third_last_mp.first<<","<<third_last_mp.second<<")"<<std::endl;

will result in error: no match for ‘operator-’ (operand types are ‘std::map, int>::iterator {aka std::_Rb_tree_iterator, int> >}’ and ‘int’)

For bidirectional iterator std::next(),std::prev or std::advance() works

    std::map<int,std::string> map_={{1,"one"},{2,"two"},{3,"three"}};
    auto last_mp=*std::prev(map_.end(),1);
    auto third_last_mp=*std::prev(map_.end(),3);
    std::cout<<"Last & 3rd last entry for map:("<<last_mp.first<<","<<last_mp.second<<") and ("<<third_last_mp.first<<","<<third_last_mp.second<<")"<<std::endl;

will output (3,three) and (1,one). On a similar note std::unordered_map has a forward iterator, so here std::next() makes sense to use.

Shantanu
  • 11
  • 2