C++ Std::Set Update Is Tedious: I Can't Change an Element in Place

C++ std::set update is tedious: I can't change an element in place

set returns const_iterators (the standard says set<T>::iterator is const, and that set<T>::const_iterator and set<T>::iterator may in fact be the same type - see 23.2.4/6 in n3000.pdf) because it is an ordered container. If it returned a regular iterator, you'd be allowed to change the items value out from under the container, potentially altering the ordering.

Your solution is the idiomatic way to alter items in a set.

How to update an existing element of std::set?

Since val is not involved in comparison, it could be declared mutable

struct Foo {
  Foo(int i, int j) : id(i), val(j) {}
  int id;
  mutable int val;
  bool operator<(const Foo& other) const {
    return id < other.id;
  }
};

This implies that the value of val may change in a logically-const Foo, which means that it shouldn't affect other comparison operators etc.

Or you could just remove and insert, that takes O(1) additional time (compared to accessing and modifying) if insertion uses the position just before just after the old one as the hint.

Something like:

bool alreadyThere = !p.second; // you forgot the !
if (alreadyThere)
{
    Set::iterator hint = p.first;
    hint++;
    s.erase(p.first);
    s.insert(hint, f);
}

Modifying elements in std::set

Elements of a std::set are const. If you want to mutate the elements you need to do insertions and removals to put the container in the state you want.

In your code example:

for (auto item : s)

gets translated into something like:

for (auto iter = s.begin(); iter != s.end(); ++iter)
{
    auto item = *iter; // Copy!
    // loop body
}

The loop induction variable item is a copy of the element from the set, not a reference to the actual element in the set. As a result, the set is not changed. To change a set you need to call a member function of set, e.g. insert or erase.

Changing item to &item won't help here; if you do this you'll get a compile-time error because the elements of the set are const, so you can't apply reverse to them.

How can i replace element in set?

You have got to erase() one element and insert() the new one. replace is not defined for std::set. See http://www.cplusplus.com/reference/set/set/

what happens when you modify an element of an std::set?

You should not edit the values stored in the set directly. I copied this from MSDN documentation which is somewhat authoritative:

The STL container class set is used
for the storage and retrieval of data
from a collection in which the values
of the elements contained are unique
and serve as the key values according
to which the data is automatically
ordered. The value of an element in a
set may not be changed directly.
Instead, you must delete old values
and insert elements with new values.

Why this is is pretty easy to understand. The set implementation will have no way of knowing you have modified the value behind its back. The normal implementation is a red-black tree. Having changed the value, the position in the tree for that instance will be wrong. You would expect to see all manner of wrong behaviour, such as exists queries returning the wrong result on account of the search going down the wrong branch of the tree.

Change a object by iterator

The iterator for an std::set is const, since modifying the entry can impact the ordering.

To get around this, either :

• choose a different container
• do a delete+add operation (ie. remove the item from the set, modify it, and then add it into the set again)
• use mutable on the fields modified by setCount (if appropriate)
• use const_cast to cast away the constness of the item before calling setCount (as a last resort)

For the latter two options, make sure that setCount does not modify anything that changes the ordering of Item objects though.

---

Related Topics