Why adding a number to an associative container's iterator is not possible?

Question

I have an std::set and I wanted to iterate trough the element pairs in the set so I wrote 2 for loops like this:

for(std::set<T>::iterator i=mySet.begin();i!=mySet.end();++i)
{
    for(std::set<T>::iterator j=i+1;j!=mySet.end();++j)
    {
        // do something
    }
}

The compiler told me that I can't add numbers to iterator. However I can increment and decrement them. A workaround I find that I can skip the first iteration:

for(std::set<T>::iterator i=mySet.begin();i!=mySet.end();++i)
{
    std::set<T>::iterator j=i;
    for(++j;j!=mySet.end();++j)
    {
        // do something
    }
}

Why I can't just add a number why I have to increment?

score 5 · Accepted Answer · edited May 23 '17 at 10:26

5

you can do this only with random access iterator, so the reasons are the same as for not having an indexoperator on containers when it would be slow. See also Why isn't there an operator[] for a std::list?

edited May 23 '17 at 10:26

Community

1
1

answered Nov 26 '10 at 10:29

DaVinci

1,391
2
12
27

This is a conscious design decision from the STL guys. Rather than hiding the cost, they prefer you to use the more verbose form `std::advance(j, n);` so that it LOOKS slower. This is a hint (if you often need to increment by more than 1) that you should change your data structure :) – Matthieu M. Nov 26 '10 at 17:06

score 2 · Answer 2 · answered Nov 26 '10 at 10:56

As usual, Boost has a solution:

for(std::set<T>::iterator i=mySet.begin();i!=mySet.end();++i)
{
    for(std::set<T>::iterator j=boost::next(i);j!=mySet.end();++j)
    {
        // do something
    }
}

Of course you could also consider

for(std::set<T>::iterator i=mySet.begin();i!=mySet.end();/* NOTHING */)
{
    std::for_each(++i, mySet.end(), /* do something*/ );
}

score 0 · Answer 3 · answered Nov 26 '10 at 10:30

0

Because set only supports bidirectional iterator, that only allows increments and decrements.

Set is usually a tree structure therefore these are the only operations that make sense.

answered Nov 26 '10 at 10:30

Šimon Tóth

35,456
20
106
151

score 0 · Answer 4 · answered Nov 26 '10 at 10:34

0

Look here at the definition of iterators. The method which you are looking for is defined only for iterators of containers which allows random access which set doesn't support.

answered Nov 26 '10 at 10:34

Gaim

6,734
4
38
58

score 0 · Answer 5 · answered Nov 26 '10 at 10:57

0

Your question was already answered, but note that you can shorten your code like this:

for(std::set<T>::iterator i=mySet.begin();i!=mySet.end();++i)
{
    for(std::set<T>::iterator j=i;++j!=mySet.end();)
    {
        // do something
    }
}

answered Nov 26 '10 at 10:57

Yakov Galka

70,775
16
139
220

Why adding a number to an associative container's iterator is not possible?

5 Answers5