Why does std::set seem to force the use of a const_iterator?

Question

Consider the simple program below, which attempts to iterate through the values of a set using NON-const references to the elements in it:

#include <set> #include <iostream>  class Int { public:    Int(int value) : value_(value) {}    int value() const { return value_; }    bool operator<(const Int& other) const { return value_ < other.value(); } private:    int value_; };  int main(int argc, char** argv) {    std::set<Int> ints;    ints.insert(10);    for (Int& i : ints) {       std::cout << i.value() << std::endl;    }    return 0; } 

When compiling this, I get an error from gcc:

test.c: In function ‘int main(int, char**)’: test.c:18:18: error: invalid initialization of reference of type ‘Int&’ from expression of type ‘const Int’   for (Int& i : ints) {                 ^   

Yes, I know I'm not actually trying to modify the elements in the for loop. But the point is that I should be able to get a non-const reference to use inside the loop, since the set itself is not const qualified. I get the same error if I create a setter function and use that in the loop.

Answer 1

A set is like a map with no values, only keys. Since those keys are used for a tree that accelerates operations on the set, they cannot change. Thus all elements must be const to keep the constraints of the underlying tree from being broken.