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

Question

I find the update operation on std::set tedious since there's no such an API on cppreference. So what I currently do is something like this:

//find element in set by iterator
Element copy = *iterator;
... // update member value on copy, varies
Set.erase(iterator);
Set.insert(copy);

Basically the iterator return by Set is a const_iterator and you can't change its value directly.

Is there a better way to do this? Or maybe I should override std::set by creating my own (which I don't know exactly how it works..)

Answer 1

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.

Answer 2

C++17 introduced extract, see Barry's answer.

---

If you're stuck with an older version, there are 2 ways to do this, in the easy case:

• You can use mutable on the variable that are not part of the key
• You can split your class in a Key Value pair (and use a std::map)

Now, the question is for the tricky case: what happens when the update actually modifies the key part of the object ? Your approach works, though I admit it's tedious.

Answer 3

In C++17 you can do better with extract(), thanks to P0083:

// remove element from the set, but without needing
// to copy it or deallocate it
auto node = Set.extract(iterator);
// make changes to the value in place
node.value() = 42;
// reinsert it into the set, but again without needing 
// to copy or allocate
Set.insert(std::move(node));

This will avoid an extra copy of your type and an extra allocation/deallocation, and will also work with move-only types.

You can also extract by key. If the key is absent, this will return an empty node:

auto node = Set.extract(key);
if (node) // alternatively, !node.empty()
{
    node.value() = 42;
    Set.insert(std::move(node));
}

Answer 4

Update: Although the following is true as of now, the behavior is considered a defect and will be changed in the upcoming version of the standard. How very sad.

---

There are several points that make your question rather confusing.

1. Functions can return values, classes can't. std::set is a class, and therefore cannot return anything.
2. If you can call s.erase(iter), then iter is not a const_iterator. erase requires a non-const iterator.
3. All member functions of std::set that return an iterator return a non-const iterator as long as the set is non-const as well.

You are allowed to change the value of an element of a set as long as the update doesn't change the order of elements. The following code compiles and works just fine.

#include <set>

int main()
{
    std::set<int> s;
    s.insert(10);
    s.insert(20);

    std::set<int>::iterator iter = s.find(20);

    // OK
    *iter = 30;

    // error, the following changes the order of elements
    // *iter = 0;
}

If your update changes the order of elements, then you have to erase and reinsert.

Answer 5

You may want to use an std::map instead. Use the portion of Element that affects the ordering the key, and put all of Element as the value. There will be some minor data duplication, but you will have easier (and possibly faster) updates.

Answer 6

I encountered the very same issue in C++11, where indeed ::std::set<T>::iterator is constant and thus does not allow to change its contents, even if we know the transformation will not affect the < invariant. You can get around this by wrapping ::std::set into a mutable_set type or write a wrapper for the content:

  template <typename T>
  struct MutableWrapper {
    mutable T data;
    MutableWrapper(T const& data) : data(data) {}
    MutableWrapper(T&& data) : data(data) {}
    MutableWrapper const& operator=(T const& data) { this->data = data; }
    operator T&() const { return data; }
    T* operator->() const { return &data; }
    friend bool operator<(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data < b.data;
    }   
    friend bool operator==(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data == b.data;
    }   
    friend bool operator!=(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data != b.data;
    }   
  };

I find this much simpler and it works in 90% the cases without the user even noticing there to be something between the set and the actual type.

Answer 7

This is faster in some cases:

std::pair<std::set<int>::iterator, bool> result = Set.insert(value);
if (!result.second) {
  Set.erase(result.first);
  Set.insert(value);
}

If the value is usually not already in the std::set then this can have better performance.