c++ : double iteration through map

Question

I would like to iterate through a map but the inner loop would just iterate through the upper part of the elements. With a vector it would look like that :

for(auto element1 = myVector.begin() ; element1 != myVector.end() ; ++element1){
    for(auto element2 = element1 + 1; element2 != myVector.end() ; ++element2){
         //my stuff
    }
}

But with a map element1 + 1 returns an error no operator matches this operand.. I believe it comes from the fact that the element are not ordered in a map.

So how could I do that properly ? I am currently using this messy workaround that requires a test in each loop :

for(auto element1 = myMap.begin() ; element1 != myMap.end() ; ++element1){
    for(auto element2 = element1; element2 != myMap.end() ; ++element2){
         if(element->first != element2->first)
         //my stuff
    }
}

Answer 1

You can use std::next to do this:

for(auto element1 = myMap.begin() ; element1 != myMap.end() ; ++element1) {
    for(auto element2 = std::next(element1) ; element2 != myMap.end() ; ++element2) {
        //my stuff
    }
}

Here is some additional background information about std::next. std::next has an optional second argument which is the number of elements to follow the passed iterator. For example std::next(element1, 2) would return an iterator for the 2nd element after element1. As has been pointed out in the comments, you must be careful when using std::next, especially in loops. If it points to the element before myMap.end(), then using std::next(it, 2) results in undefined behavior. You want to make sure that using this will never pass the end of the container.

You can think of std::next as if it were implemented like this:

// If distance is negative, then i must meet the requirements of BidirectionalIterator
// Otherwise, i must meet the requirements of ForwardIterator.
template<class ForwardIterator>
ForwardIterator next(ForwardInterator i, int distance) {
    for( ; distance < 0 ; ++distance) {
        --i;
    }
    for( ; distance > 0 ; --distance) {
        ++i;
    }

    return i;
}

Which can be equivalently implemented like this:

template<class ForwardIterator>
ForwardIterator next(ForwardIterator i, int distance) {
    std::advance(i, distance);
    return i;
}

Answer 2

Even if you didn't know about some of the newer C++ facilities like std::next() (which is a good way to solve this problem), this seems to be a rather basic problem to solve:

for(auto element1 = myMap.begin() ; element1 != myMap.end() ; ++element1){
    auto element2 = element1;
    ++element2;
    for(; element2 != myMap.end() ; ++element2){
         //my stuff
    }
}