2

A part of the source code for a project I'm working on, which is responsible for compressing a sequence of 'events', looks like this:

#include <iterator>
#include <list>

typedef int Event;

typedef std::list<Event> EventList;

struct Compressor {
    // Returns an iterator behind the last element which was 'eaten'
    virtual EventList::const_iterator eatEvents( const EventList &l ) = 0;
};

// Plenty of Compressor subclasses exist

void compressAndCopyEatenEvents( Compressor &c ) {
    EventList e;
    e.push_back( 1 );
    EventList::const_iterator newEnd = c.eatEvents( e );

    EventList eatenEvents;
    std::copy( e.begin(), newEnd, std::back_inserter( eatenEvents ) ); // barfs
}

The issue here is that the compressAndCopyEatenEvents function has a non-const list of events; this list os passed to the eatEvents methods, which takes a reference-to-const and yields a const_iterator. Now the compressAndCopyEatenEvenst function would like to copy the range of eaten events away, so it decides to use some algorithm (std::copy here, which of course could just as well be replaced with the right std::list constructor call - the point is that this problem exists with all kinds of ranges).

Unfortunately(?) many (if not all?) ranges need to be composed from the same iterator type. However, in the above code, 'e.begin()' yields an EventList::iterator (because the object is not const) but 'newEnd' is an EventList::const_iterator.

Is there a design weakness here which causes this mess? How would you tackle it?

2
  • Do you need the non-const iterators? If not, then you should make all your code work with const iterators only.
    – PlasmaHH
    Feb 1, 2012 at 11:07
  • I guess EventList::const_iterator begin = e.begin(); and passing that in is too much? I can't see a way around due to your consume method...
    – Nim
    Feb 1, 2012 at 11:15

4 Answers 4

4

In C++03 the only possible way is to cast. (which is ugly, which is a design flaw, yes).

std::copy( static_cast<EventList::const_iterator>e.begin(), newEnd, std::back_inserter( eatenEvents ) );

or have another named variable:

EventList::const_iterator constBegin = e.begin();
std::copy(constBegin , newEnd, std::back_inserter( eatenEvents ) );

In C++11 you have cbegin and cend functions (that always return const_iterators) so you'd do simply

std::copy( e.cbegin(), newEnd, std::back_inserter( eatenEvents ) );
1
  • You could assign e to a const EventList& object, which would automatically produce the desired const_iterator.
    – Peter Wood
    Mar 17, 2013 at 20:34
2

Consider using

EventList::const_iterator b = e.begin();
std::copy( b, newEnd, std::back_inserter( eatenEvents ) );

This will cause the correct list::begin() overload to be called, and for std::copy to compile cleanly.

1

See what the master says:

Scot Meyers in Effective STL

Item 26. Prefer iterator to const iterator, reverse_iterator, and const_reverse_iterator. Though containers support four iterator types, one of those types has privileges the others do not have. That type is iterator, iterator is special. the conversions that exist among iterator types.

typedef deque<int> IntDeque; //STL container and
typedef lntDeque::iterator Iter; // iterator types are easier
typedef lntDeque::const_iterator ConstIter; // to work with if you
// use some typedefs
Iter i;
ConstIter ci;
… //make i and ci point into
// the same container
if (i == ci ) ... //compare an iterator
// and a const_iterator

Item 27. Use distance and advance to convert a container's const_iterators to iterators.

typedef deque<int> IntDeque; //convenience typedefs
typedef lntDeque::iterator Iter;
typedef lntDeque::const_iterator ConstIter;
ConstIter ci; // ci is a const_iterator
…
Iter i(ci); // error! no implicit conversion from
// const_iterator to iterator
Iter i(const_cast<Iter>(ci)); // still an error! can't cast a
// const_iterator to an iterator

What works is advance and distance

typedef deque<int> IntDeque; //as before
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
IntDeque d;
ConstIter ci;
… // make ci point into d
Iter i(d.begin()); // initialize i to d.begin()
Advance(i, distance(i, ci)) //move i up to where ci is
// (but see below for why this must
// be tweaked before it will compile)
2
  • 1
    +1 for mentioning Effective STL - I have that at home, but I didn't think of consulting it. I'll read up on this! Feb 1, 2012 at 12:45
  • Always prefer STL!! as algorithms are far more efficient than hand written loops!! Feb 3, 2012 at 4:45
0

You could add a second overload of eatEvents, so the compiler will automatically pick the right one so as to preserves const-ness:

virtual EventList::iterator eatEvents( EventList &l ) = 0;

(One or both of them could be non-virtual and implemented in terms of a single underlying function.)

Sometimes that works well, although I'm not convinced it's the perfect thing here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.