Compare two consecutive elements in std::list

Question

I'd like to compare two consecutive elements in a std::list while iterating through the list. What is the proper way to access element i+1 while my iterator is at element i? Thanks Cobe

Answer 1

Boost has a utility called next (and its inverse, prior) for just that purpose.

*itr == *next(itr)

Edit: But, if we step back to look at the forest, the real question is, why custom-write your adjacent_find function? (I recommend Nicola Bonelli's answer to be accepted.) That's part of the STL, and doesn't require using Boost, if your code doesn't use Boost (thanks to the commenters for pointing this out).

Answer 2

The simplest way would be to hold two iterators (since you'll have to stop at the penultimate one anyway).

std::list<int>::const_iterator second = list.begin(),
                               end = list.end();

if ( second != end ) // Treat empty list
    for(std::list<int>::const_iterator first = second++; // Post-increment 
        second != end; 
        ++first, ++second)
    {
        //...
    }

Note that first is initialized with the post-incrementation of second so when the loop starts first is list.begin() and second is list.begin()+1.

Chris Jester-Young points out that boost has next and prior functions, although I am not familiar with these functions (for my sins) implementing them is trivial (especially considering that list has bidirectional iterators).

template <class Iterator>
Iterator next(Iterator i) // Call by value, original is not changed
{ 
    return ++i;
}
// Implementing prior is left as an exercise to the reader ;o)

My feeling is that use of next does not suite this problem as well as maintaining both iterators since you have to remember to make sure next(i) does not equal end() at every use.

---

Edits:

• Fixed bug if the list is empty thanks to Luc Touraille's comment.
• Add reference to next and why I think it doesn't fit this use-case.

Answer 3

STL provide the adjancent_find() algorithm that can be used to find two consecutive equal elements. There is also a version with a custom predicate.

These are the prototypes:

template <class ForwardIterator>
   ForwardIterator adjacent_find ( ForwardIterator first, ForwardIterator last );

template <class ForwardIterator, class BinaryPredicate>
   ForwardIterator adjacent_find ( ForwardIterator first, ForwardIterator last,
                                   BinaryPredicate pred );

Answer 4

List is a Reversible Container, so its iterators are Bidirectional Iterators, which is a model of Forward Iterator, which I'm pretty sure means you can do this (or something equivalent, if you're allergic to breaking out of the middle of a loop etc.):

if (!l.empty()) {
    for (list<T>::const_iterator i = l.begin();;) {
        const T &a = *i;
        ++i;
        if (i == l.end()) break;
        do_comparison(a, *i);
    }
}

You couldn't do that with an Input Iterator, because with those the values only "exist" as long as you have an iterator at them. But you can with a Forward Iterator.