Modifying the value of a user defined type in `std::set`

Question

Consider the case where I have a user defined type with say a id() member function which returns a unique std::string.

I want a container of this objects, where the id() uniquely identifies the elements, but I want to "use" the objects to do other things which may modify their members.

I am currently constructing the objects.by calling std::set::emplace and capturing the returned iterator, bool pair.

But I am then not allowed to modify it's value as the iterator is const.

Is there a good way to do what I want? The only two I can think of are:

1. Store unique_ptrs to the object in the set, this way the pointer value is what differentiates it rather than the name and the object pointed to can be modified.
2. Store a map using the id() as the Key, but this means I have duplicated the keys.

I am happy to use well adopted and modern libraries, such as boost, if they have the right container for my problem.

Answer 1

Is there a good way to do what I want?

No not really. The granularity of std::set is at object level. There is no way to express that a portion of an object contributes to the key.

Some people recommend declaring all non-key members mutable. This is wrong, as mutable is meant for things that are hidden from the public interface of the object (e.g. a mutex).

The "official" way is to take the object out the set, modify it and put it back in. C++17 has set::extract which helps to improve performance of this task a bit (which of course remains inefficient if you never modify the key, since the tree still has to be checked/rebalanced).

I want to "use" the objects to do other things which may modify their members.

If you're absolutely sure you never modify the object key, just cast away constness. From a legal point of view it is OK to cast away constness from objects that were not born const. For extra safety you can wrap the key into another, const member:

struct Element {
    const Key key;
    Value value;
};

This won't help if you have a data cube with multiple sets each using its own "view" on the key.

1. Store unique_ptrs to the object in the set

This would be a pessimization due to extra indirection. Since the elements are on the heap, you will take an extra cache miss. And again end up with UB if you accidentally modify the key.

2. Store a map using the id() as the Key

Yes, different variations of this approach are possible, but you must still ensure to never modify the key.

For example you could store a key + pointer to data. This approach is often combined with a dense_hash_set with linear probing for best performance. Since the value is accessed only once after the element is found, it doesn't really matter that it is located elsewhere.

Answer 2

I would suggest using Boost.MultiIndex as a drop-in replacement for std::set, as it adds the modify method which allows modification of an element, checking whether the position within the container has changed:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>

struct S { /* ... */ };
boost::multi_index_container<S> t; // default configuration emulates std::set<S>
auto [it, inserted] = t.emplace(...);
t.modify(it, [&](S& s) {
    // modify s here
    // if the key is unchanged, s does not move
    // the iterator `it` remains valid regardless
});

Example.

There is a small overhead in checking that the key is indeed unchanged, but this should be minimal compared to the rest of the program and should optimize and predict well.

Answer 3

std::set maintains its elements sorted, and the keys the elements are sorted by, correspond to the elements themself. As a result, the elements in the std::set are const qualified to prevent the user from modifying the elements (i.e., the keys) and thus breaking the std::set order.

Traditionally, if you wanted to modify an element of an std::set, you would have first to remove the element object you wish to modify from the std::set, modify it, and insert it into the std::set again. The problem is that this results in the allocation of an std::set internal node.

Since C++17 you can remove and reinsert an element into the std::set without allocating an std::set internal node thanks to std::set::extract(). This member function returns the node handle corresponding to the requested element. After modifying the element through this returned node, you can reinsert the node with the corresponding insert() overload. No node allocation takes place as you are reusing an already allocated node.

The drawback to these approaches – regardless of whether or not allocation occurs – is that reinserting the element into the std::set takes logarithmic time in the size of the set (unless you can take advantage of the hint to insert()).

Casting away constness and modifying std::set elements

You can still cast const away from an element of the std::set and modify its data members, as long as your std::set's comparison function doesn't take into account the data members you change. That is, if you only modify data members of an element belonging to an std::set whose comparison function doesn't consider, the order won't break.