45

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.

atomicpirate
  • 657
  • 5
  • 12
  • I've explained this in detail, here: [error: passing xxx as 'this' argument of xxx discards qualifiers](http://stackoverflow.com/questions/5973427/error-passing-xxx-as-this-argument-of-xxx-discards-qualifiers) – Nawaz Aug 04 '16 at 13:23
  • If you really want to modify an element of a `std::set`, in place, you can use `const_cast`. Just be _really sure_ that the modification doesn't alter the order of the element within the set or you will run into undefined behavior. This is very unsafe, which is why you have to go _way_ out of your way to do it. – gnzlbg Aug 05 '16 at 23:32

5 Answers5

55

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.

nate
  • 1,771
  • 12
  • 17
  • 3
    I see that, but I may be modifying something in the set element which does not modify its sorting order in the set; [http://www.cplusplus.com/reference/set/set/begin](http://www.cplusplus.com/reference/set/set/begin) claims that a non-const set will return a non-const iterator from begin() – atomicpirate Aug 04 '16 at 13:24
  • 6
    The std::set can't know that so it makes everything `const` to be safe. If your structure has mutable data, and some immutable key fields, then maybe you should use a map with the with a structure as the value, and a copy of the immutable key fields as the key. You could always const_cast away the const if you know your are not changing the ordering of the values, but I would think the map approach is cleaner. – nate Aug 04 '16 at 13:27
  • 5
    According to http://en.cppreference.com/w/cpp/container/set while `begin` does return `iterator` that iterator is an alias for `const_iterator` since C++11 – nate Aug 04 '16 at 13:33
  • Ok so iterator is really const_iterator--well it makes sense I suppose in this context, although I would have just said that std::set::begin always returns a const_iterator and do away with the "pretend" non-const iterator version. :) – atomicpirate Aug 04 '16 at 13:41
  • 2
    I believe the alias is there to fulfill the general container interface where all containers have a both `iterator` and `const_iterator`. This could come into play with templates that are not aware of the details of a `std::set` – nate Aug 04 '16 at 13:44
  • 2
    Which is a good reason for template code to use `auto` everywhere, or at least to const-qualify references that it doesn't intend to modify. If the questioner were writing some template code with `Container::value_type &` in the place where it currently has `Int &`, then the template needlessly fails to instantiate for a set. – Steve Jessop Aug 04 '16 at 13:59
  • absolutely, though my gut tells me there is a rational beyond backward compatibility for the alias to exist. – nate Aug 04 '16 at 14:03
12

std::set uses the contained values to form a fast data structure (usually, a red-black tree). Changing a value means the whole structure needs to be altered. So, forcing constness, std::set prevents you from pushing it into a non-usable state.

lisyarus
  • 15,025
  • 3
  • 43
  • 68
11

From the cpp reference:

In a set, the value of an element also identifies it (the value is itself the key, of type T), and each value must be unique. The value of the elements in a set cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.

Ohad Eytan
  • 8,114
  • 1
  • 22
  • 31
6

The behaviour is by design.

Giving you a non-const iterator could inspire you to change the element in the set; the subsequent iterating behaviour would then be undefined.

Note that the C++ standard says that set<T>::iterator is const so the old-fashioned pre C++11 way still wouldn't work.

Fitzwilliam Bennet-Darcy
  • 1,332
  • 8
  • 18
0

Adding on nate's answer:

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.

With C++17 there is the new extract member function, so an alternative to const_cast could be:

#include <iostream>
#include <string_view>
#include <set>

struct S
{
  int used_for_sorting;
  bool not_used_for_sorting;

  bool operator<(const S &rhs) const
  { return used_for_sorting < rhs.used_for_sorting; }
};

void print(std::string_view comment, const std::set<S> &data)
{
  std::cout << comment;
  for (auto datum : data)
    std::cout << " {" << datum.used_for_sorting
              << ',' << datum.not_used_for_sorting
              << '}';

  std::cout << '\n';
}

int main()
{
  std::set<S> cont = {{1, false}, {2, true}, {3, false}};

  print("Start:", cont);

  // Extract node handle and change key
  auto nh = cont.extract({1, false});
  nh.value().not_used_for_sorting = true;

  print("After extract and before insert:", cont);

  // Insert node handle back
  cont.insert(std::move(nh));

  print("End:", cont);
}

Probably useful as hot-fix. In general it's hard to see any advantage over a std::map.

manlio
  • 18,345
  • 14
  • 76
  • 126