Thursday, July 9, 2009

Feature collision

One thing the C++ community is pretty proud of is that, in contrast to C, C++ supports const correctness. Turns out that const correctness clashes with STL containers.
Today Roker pointed me to a poor guy from #c++@freenode with the following problem:

#include <iostream>
#include <list>

typedef std::list<int> list_t;

list_t::const_iterator find_first_odd(const list_t & list)
  for (list_t::const_iterator i = list.begin(); i != list.end(); ++i)
    if (*i % 2 != 0) return i;

  return list.end();

int main()
  list_t list;

  list_t::const_iterator odd_i = find_first_odd(list);

  if (odd_i != list.end())
    // Error. Can not use const_iterator with 'std::list::erase'

  return 0;

For the sake of const correctness the function find_first_odd expects a constant reference to the list because it is not going to modify it. But as a result the function can only return a const_iterator, because there is no way to get a non-const iterator from the constant list.
So the caller of find_first_odd ends up with a const_iterator which is useless for modifying operations such as erase. And for him it is also impossible to turn the const_iterator into a non-const iterator. The two types have no relation to each other, so casting does not work. And there are no conversion functions in the STL either. So the only way out here is to sacrifice const correctness and pass a non-const reference to find_first_odd.
According to Roker nobody on #c++ had a better solution. And according to Scott Meyers' article Three Guidelines for Effective Iterator Usage there is none. const_iterators can not be easily transformed into iterators. What you can do is nasty and rather inefficient.
Here it comes:

template <class Container>
typename Container::iterator convert(typename Container::const_iterator in, Container& container)
    typename Container::iterator out(container.begin());
    std::advance(out, std::distance<typename Container::const_iterator>(out, in));
    return out;

If the container does not support random access, this conversion is O(n). Furthermore it can only be done, if the container object is at hand. Finally note, that this function violates const correctness, because the container object which is not altered by the function is not passed as const&. The reason is that the begin() function of a constant container returns a const_iterator which you can not convert into the output non-const iterator. In case you are confused, try this illustration.

No comments:

Post a Comment