tags:

views:

497

answers:

7

I'm trying to do a double-loop over a std::list to operate on each pair of elements. However, I'm having some trouble initialising the second iterator. The code I'd like to write is:

for(std::list<int>::iterator i = l.begin(); i != l.end(); ++i) {
    for(std::list<int>::iterator j = i+1; j != l.end(); ++j) {
        ...
    }
}

That doesn't work because list iterators aren't random-access, so you can't do +1. But I'm having some trouble finding a neat alternative; the compiler doesn't seem to be very happy with std::list<int>::iterator j(i)++; which I had some hope for. Achieving what I want seems like I'm going to have to have some awkward extra increment which won't fit the structure of the for loop nicely.

There are obvious alternatives (using a vector, for example!) but it seems to me that there should be some reasonably neat way of doing this which I'm just not seeing at the moment.

Thanks in advance for any help :)

+2  A: 
for(std::list<int>::iterator i = l.begin(); i != l.end(); ++i) {
    std::list<int>::iterator j = i; ++j;
    for(; j != l.end(); ++j) {
        ...
    }
}

Back in the game!

Actually, this a pretty common idiom in numerical algorithms, so I do not see it as ugly.

ebo
+7  A: 
for(std::list<int>::iterator i = l.begin(); i != l.end(); ++i) {
    std::list<int>::iterator j = i;
    for(std::advance(j, 1); j != l.end(); ++j) {
        ...
    }
}
dirkgently
`advance` has no return value, it modifies the first argument. (Which I personally dislike.) That said, it's easy to write an `advance_copy` function.
GMan
@GMan: Fixed. Ty!
dirkgently
No problem. I decided to go with my idea as an alternate answer.
GMan
+3  A: 

How about:

for (std::list<int>::iterator i = l.begin(); i != l.end(); ++i) {
    for (std::list<int>::iterator j = i; ++j != l.end(); ) {
        // ...
    }
}
Sean
+2  A: 

I'm just going off the idea I had in dirkgently's answer:

template <typename Iter, typename Dist>
Iter advance_copy(Iter pIter, const Dist& pOffset)
{
    std::advance(pIter, pOffset);

    return pIter;
}

// ...

typedef std::list<int> int_list;

for(int_list::iterator i = l.begin(); i != l.end(); ++i)
{
    for(int_list::iterator j = advance_copy(i, 1); j != l.end(); ++j)
    {
    }
}

You can make another class of utility functions too, to help make it concise:

// for consistency,
template <typename Iter>
void increment(Iter& pIter)
{
    ++pIter;
}

template <typename Iter>
Iter increment_copy(Iter pIter)
{
    return ++pIter;
}

// ...

typedef std::list<int> int_list;

for(int_list::iterator i = l.begin(); i != l.end(); ++i)
{
    for(int_list::iterator j = increment_copy(i); j != l.end(); ++j)
    {
    }
}
GMan
A: 

I'd go for Sean's suggestion, except make it a while loop:

for (std::list<int>::iterator i = l.begin(); i != l.end(); ++i) {
    std::list<int>::iterator j( i ); 
    while( ++j != l.end() ) {
        // ...
    }
}
anon
A: 

If you're already using Boost, then the easiest approach is to use boost::next.

for(std::list<int>::iterator i = l.begin(); i != l.end(); ++i)
    for(std::list<int>::iterator j = boost::next(i); j != l.end(); ++j)
avakar
You mean Boost stole my idea. :(
GMan
+1  A: 

The straightforward "neat" alternative can be based on the fact that list iterator is an object of user-defined type with overloaded operators (as opposed to a built-in type). (Of course, this is not formally guaranteed, but one can expect this based on the nature of the list container.) For this reason, it is possible to apply the overloaded prefix ++ operator to a temporary object of list iterator type.

To achieve what you want you just need to create a temporary copy of i, increment it using the prefix ++ and then use the resultant value to initialize j

for(std::list<int>::iterator i = l.begin(); i != l.end(); ++i) { 
  for(std::list<int>::iterator j = ++std::list<int>::iterator(i); j != l.end(); ++j) { 
    ... 
  } 
} 

And that's it. Note, that this trick is fairly popular and can be encountered in real code from time to time. Note also, that it will not generally work with std::vector because many implementations use ordinary built-in pointers as vector iterators, but it will normally work with std::list.

However, personally, I wouldn't really use this in my code. You have already received several good answers that do this by adding an extra line of code.

AndreyT