How do I escape the const_iterator trap when passing a const container reference as a parameter

Question

I generally prefer constness, but recently came across a conundrum with const iterators that shakes my const attitude annoys me about them:

MyList::const_iterator find( const MyList & list, int identifier )
{
    // do some stuff to find identifier
    return retConstItor; // has to be const_iterator because list is const
}

The idea that I'm trying to express here, of course, is that the passed in list cannot/willnot be changed, but once I make the list reference const I then have to use 'const_iterator's which then prevent me from doing anything with modifing the result (which makes sense).

Is the solution, then, to give up on making the passed in container reference const, or am I missing another possibility?

This has always been my secret reservation about const: That even if you use it correctly, it can create issues that it shouldn't where there is no good/clean solution, though I recognize that this is more specifically an issue between const and the iterator concept.

Edit: I am very aware of why you cannot and should not return a non-const iterator for a const container. My issue is that while I want a compile-time check for my container which is passed in by reference, I still want to find a way to pass back the position of something, and use it to modify the non-const version of the list. As mentioned in one of the answers it's possible to extract this concept of position via "advance", but messy/inefficient.

Answer 1

If you're going to return a non-const accessor to the container, make the function non-const as well. You're admitting the possibility of the container being changed by a side effect.

This is a good reason the standard algorithms take iterators rather than containers, so they can avoid this problem.

Answer 2

Rather than trying to guarantee that the list won't be changed using the const keyword, it is better in this case to guarantee it using a postcondition. In other words, tell the user via comments that the list won't be changed.

Even better would be using a template that could be instantiated for iterators or const_iterators:

template <typename II> // II models InputIterator
II find(II first, int identifier) {
  // do stuff
  return iterator;
}

Of course, if you're going to go to that much trouble, you might as well expose the iterators of MyList to the user and use std::find.

Answer 3

If you're changing the data directed by the iterator, you're changing the list.

The idea that I'm trying to express here, of course, is that the passed in list cannot/willnot be changed, but once I make the list reference const I then have to use 'cons_iterator's which then prevent me from doing anything with the result.

What is "dong anything"? Modifying the data? That's changing the list, which is contradictory to your original intentions. If a list is const, it (and "it" includes its data) is constant.

If your function were to return a non-const iterator, it would create a way of modifying the list, hence the list wouldn't be const.

Answer 4

If I understand what you're saying correctly, you're trying to use const to indicate to the caller that your function will not modify the collection, but you want the caller (who may have a non-const reference to the collection) to be able to modify the collection using the iterator you return. If so, I don't think there's a clean solution for that, unless the container provides a mechanism for turning a const interator into a non-const one (I'm unaware of a container that does this). Your best bet is probably to have your function take a non-const reference. You may also be able to have 2 overloads of your function, one const and one non-const, so that in the case of a caller who has only a const reference, they will still be able to use your function.

Answer 5

Although I think your design is a little confusing (as others have pointed iterators allow changes in the container, so I don't see your function really as const), there's a way to get an iterator out of a const_iterator. The efficiency depends on the kind of iterators.

#include <list>

int main()
{
  typedef std::list<int> IntList;
  typedef IntList::iterator Iter;
  typedef IntList::const_iterator ConstIter;

  IntList theList;
  ConstIter cit = function_returning_const_iter(theList);

  //Make non-const iter point to the same as the const iter.
  Iter it(theList.begin());
  std::advance(it, std::distance<ConstIter>(it, cit));

  return 0;
}

Answer 6

It's not a trap; it's a feature. (:-)

In general, you can't return a non-const "handle" to your data from a const method. For example, the following code is illegal.

class Foo
   {
      public:
         int& getX() const {return x;}
      private:
         int x;
   };

If it were legal, then you could do something like this....

   int main()
   {
      const Foo f;
      f.getX() = 3; // changed value of const object
   }

The designers of STL followed this convention with const-iterators.

---

In your case, what the const would buy you is the ability to call it on const collections. In which case, you wouldn't want the iterator returned to be modifiable. But you do want to allow it to be modifiable if the collection is non-const. So, you may want two interfaces:

MyList::const_iterator find( const MyList & list, int identifier )
{
    // do some stuff to find identifier
    return retConstItor; // has to be const_iterator because list is const
}

MyList::iterator find( MyList & list, int identifier )
{
    // do some stuff to find identifier
    return retItor; 
}

Or, you can do it all with one template function

template<typename T>    
T find(T start, T end, int identifier);

Then it will return a non-const iterator if the input iterators are non-const, and a const_iterator if they are const.

Answer 7

What I've done with wrapping standard algorithms, is have a metaobject for determining the type of container:

namespace detail
{
    template <class Range>
    struct Iterator
    {
        typedef typename Range::iterator type;
    };

    template <class Range>
    struct Iterator<const Range>
    {
        typedef typename Range::const_iterator type;
    };
}

This allows to provide a single implementation, e.g of find:

template <class Range, class Type>
typename detail::Iterator<Range>::type find(Range& range, const Type& value)
{
    return std::find(range.begin(), range.end(), value);
}

However, this doesn't allow calling this with temporaries (I suppose I can live with it).

In any case, to return a modifiable reference to the container, apparently you can't make any guarantees what your function does or doesn't do with the container. So this noble principle indeed breaks down: don't get dogmatic about it.

I suppose const correctness is more of a service for the caller of your functions, rather that some baby-sitting measure that is supposed to make sure you get your simple find function right.

---

Another question is: how would you feel if I defined a following predicate and then abused the standard find_if algorithm to increment all the values up to the first value >= 3:

bool inc_if_less_than_3(int& a)
{
    return a++ < 3;
}

(GCC doesn't stop me, but I couldn't tell if there's some undefined behaviour involved pedantically speaking.)

1) The container belongs to the user. Since allowing modification through the predicate in no way harms the algorithm, it should be up to the caller to decide how they use it.

2) This is hideous!!! Better implement find_if like this, to avoid this nightmare (best thing to do, since, apparently, you can't choose whether the iterator is const or not):

template <class Iter, class Pred>
Iter my_find_if(Iter first, Iter last, Pred fun)
{
    while (first != last 
       && !fun( const_cast<const typename std::iterator_traits<Iter>::value_type &>(*first)))
        ++first;
    return first;
}

Answer 8

You are thinking about your design in the wrong way. Don't use const arguments to indicate what the function does - use them to describe the argument. In this case, it doesn't matter that find() doesn't change the list. What matters is that find() is intended to be used with modifiable lists.

If you want your find() function to return a non-const iterator, then it enables the caller to modify the container. It would be wrong for it to accept a const container, because that would provide the caller with a hidden way of removing the const-ness of the container.

Consider:

// Your function
MyList::iterator find(const MyList& list, int identifier);

// Caller has a const list.
const MyList list = ...
// but your function lets them modify it.
*( find(list,3) ) = 5;

So, your function should take a non-const argument:

MyList::iterator find(MyList& list, int identifier);

Now, when the caller tries to use your function to modify her const list, she'll get a compilation error. That's a much better outcome.