Error: no matching member function for call to 'push_back'

Question

Why am I getting the error at the last two lines? The goal is to find the object in a set, and modify its content.

using namespace std;

struct mystruct {
  int id;
  vector<int> y;
  mystruct(const int id):id(id) {}
  bool operator<(const mystruct& x) const { return id < x.id; }
  bool operator==(const mystruct& x) const { return id == x.id; }
};

void test() {
  std::set<mystruct> sx;
  mystruct x(1);
  x.y.push_back(1); x.y.push_back(2);
  sx.insert(x);
  //
  set<mystruct>::iterator i = sx.find(1);
  const mystruct* x1 = &(*i);
  const mystruct x2 = *x1;
  cout << &(i->y) << endl;
  cout << &(x1->y) << endl;
  cout << x2.id << endl;
  x2.y.push_back(3);
  i->y.push_back(4);
}

It seems like the iterator returns a constant object, and doesn't let me use push_back() to modify the vector y. How can I overcome this?

Error:

test.cpp:27:8: error: no matching member function for call to 'push_back'
  x2.y.push_back(z);
  ~~~~~^~~~~~~~~
/opt/local/libexec/llvm-6.0/include/c++/v1/vector:688:36: note: candidate function not viable: 'this' argument has type 'const vector<int>', but method is not marked const
    _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
                                   ^
/opt/local/libexec/llvm-6.0/include/c++/v1/vector:691:36: note: candidate function not viable: 'this' argument has type 'const vector<int>', but method is not marked const
    _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
                                   ^

Answer 1

Since x2 is declared with a const qualifier, i.e. const mystruct x2, C++ compiler considers only const-qualified member functions for all invocations on x2 and any of its members. In particular, it is looking for void push_back (const int& val) const member function to invoke. Obviously, there is no such function, because push_back must modify the container, so the compiler produces an error explaining exactly what's going on:

candidate function not viable: 'this' argument has type 'const vector<int>', but method is not marked const

The only way to address this in your code is to remove const qualifier from x2's declaration.

Answer 2

The reason why you cannot modify x2 is that it is declared const, as has been pointed out by @dasblinkenlight. @songyuanyao's comment is right as for accessed to the object referenced by the iterator, but doesn't quite answer the question because it does not say why set iterators only allow const access.

The reason for this is that, as you know, a std::set is an ordered container whose structure is determined by comparing entries to one another using (by default) operator <. This means that there is a container invariant such that if an item a precedes another item b in the std::set, it follows that !(b < a). I put it like this because this also holds for std::multiset. Since, in a set, duplicates are not allowed, it follows that, actually, if a precedes b, then a < b. If this invariant were to be violated, then any set operation that requires the set to be sorted, such as find or insert, will have unexpected (to be precise, undefined) behavior.

Therefore, a std::set will not allow you to change an item using an iterator, because you could unwittingly change members of the item in a way that affect its proper place in the set, breaking the invariant and thereby causing undefined behavior.

Unfortunately, the compiler is not smart enough to understand that your comparison function only evaluates certain members, in this case, only id. If compiler and language were capable of analyzing and expressing this, they might figure that while i->id should be a reference to const, i->m for any other member m could safely be a reference to non-const.

There are at least four possible solutions to your problem:

1. The easiest but ugliest solution is to mark the members that you need to modify as mutable. Note that you must yourself ensure that changing them does not affect the sort order.
2. Another fairly ugly solution is the deliberate use of const_cast as in const_cast<mystruct &>(*i) where i is an iterator. Again, never change a member that has an effect on the sort order in this way.
3. A more elegant solution that, however, has additional run time overhead, is to add a level of pointer indirection (e.g. using std::unique_ptr) to properties that you want to modify. Note, however, that if you were to use the pointee in your comparison function, you would still run the risk of breaking the set invariant, only now the compiler and library will no longer prevent you from doing so!
4. The only way that works even if you want to change members affecting the sort order is to make a copy of the item, modify the copy, erase the old item, and then re-insert the copy. This allows the container to insert the copy at a different position if necessary.

Final notes:

• A hashed container such as std::unordered_set will have exactly the same issue, only in this case it is not the comparison function, but both the hash and equality functions that you have to consider.
• For the given reasons, a std::map or std::unordered_map may be a better match for your problem domain, as, in this case, the library knows that the mapped_type is not used to determine container structure. Note also how the value_type of a std::map or std::unordered_map is std::pair<const key_type, mapped_type> instead of std::pair<key_type, mapped_type> exactly for the same reason that changing the key could break the container invariants.