CODEWITHSUNDEEP
c++c++11dictionaryiteratorstd
Zebrafish
Zebrafish

Reputation: 13936

How can I go decrement the iterator of a std::map by a certain number?

With an std::vector I can do:

std::vector<int> h;
auto it = h.end() - 2;

But with the std::map I can't do:

std::map<int, int> h;
auto it = h.end() - 2;

I can only do:

auto it = --h.end();

This is for example if I want the member two from the end, or three from the end, or whatever.

Upvotes: 4

Views: 4247

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 310980

The template class std::vector has random access iterators for which the operation h.end() - 2 is defined.

On the other hand the template class std::map has bidirectional iterators for which the operation h.end() - 2 is not defined.

If you include the header <iterator> you can use standard functions std::next and std::prev as for random access iterators and for bidirectional iterators.

For example

#include <map>
#include <iterator>

//...

std::map<int, int> h;
//...
auto it = std::prev( h.end(), 2 );

and

#include <vector>
#include <iterator>

//...

std::vector<int> h;
//...
auto it = std::prev( h.end(), 2 );

Upvotes: 1

Arnav Borborah
Arnav Borborah

Reputation: 11789

On the other hand, you can also use std::prev, as follows:

auto it = std::prev(iter, 2);

Internally, this does the same thing as std::advance (using it, in fact), except it could be said that this is somewhat clearer.

If you were wondering why you couldn't subtract a map iterator unlike a vector iterator, the reason for this is because std::vector<T>::iterator is a RandomAccessIterator, meaning it "can be moved to point to any element in constant time"1 through addition/subtraction. On the other hand, std::map<T,U>::iterator is a BidirectionalIterator, which can go in either direction, but only in increments of one.

1 http://en.cppreference.com/w/cpp/concept/RandomAccessIterator

Upvotes: 7

Holt
Holt

Reputation: 37616

You can use std::advance:

auto it = h.end();
std::advance(it, -4);

Note that the complexity is linear in n (the second parameter) for std::map iterators (which are not random access iterators), meaning that there is no "magic" and a call to std::advance is equivalent to applying n times the increment/decrement operator on the iterator.

Upvotes: 9

Related Questions