STL iterators and 'const'

Question

I have a problem with what appears to be some sort of implicit casting to const when I use iterators. I'm not really sure which code is relevant (if I did I probably wouldn't be asking this question!) so I will try my best to illustrate my problem.

typedef set<SmallObject> Container;              //not const

void LargeObject::someFunction() {               //not const
    Container::iterator it;                      //not const
    for (it = c.begin(); it != c.end(); ++it) {  //assume c is a "Container"
        (*it).smallObjectFunction();             //not a const function
    }
}

However I always get the following error:

error: passing 'const SmallObject' as 'this' argument of 'int SmallObject::smallObjectFunction()' discards qualifiers

However, if I cast it as ((SmallObject)(*it).smallObjectFunction(); then I get rid of the error message.

The only thing I can figure is that somehow the definition of

bool operator< (const SmallObject &a) const;

is somehow causing the iterator to return const objects. Any help or explanation here?

Answer 1

Sets and maps keep the elements in order according to the sort condition. For user code not to break invariants, the key of the map and the whole element in the set must be constant. Your problem is that the stored element is not a SmallObject but a const SmallObject.

If this was not limited you could have:

int init[] = { 1, 2, 3, 4, 5 };
std::set<int> values( init, init+5 );
std::copy( values.begin(), values.end(), 
   std::ostream_iterator<int>(std::cout, " "));
   // 1 2 3 4 5
*(values.find(3)) = 5; // luckily this does not work!
std::copy( values.begin(), values.end(), 
   std::ostream_iterator<int>(std::cout, " "));
   // 1 2 5 4 5 -- not in order!!!

The problem there is not only that now the set element would not be in order, but that depending on how the tree was built there could be elements that are present in the set but cannot be found.

Answer 2

Your code is not stupid and could compile cleanly with a conformant STL implementation, depending on some design decisions that your STL implementation made. The C++03 Standard does not specify what the reference typedef should be for set::iterators (in my opinion, they should be non-constant references). So keep doing what you do, but insert a const_cast:

const_cast<SmallObject&>(*it).smallObjectFunction();

It is more efficient and much clearer than erasing and re-inserting. For a more extensive discussion of this problem, check out Item 8 in “More Exceptional C++” by Herb Sutter.

It is perfectly safe to do a const_cast in this situation and it is not bad style, just make sure that you do not change the value of the fields that determine the order. If the interface of the class makes it hard to verify that you do not change the order, then the interface is probably not well designed.