Way to replace constant item in a map using iterator

Question

I have code like this:

std::map<int, const Data> all_data;
// ...
bool OldDataIsBetter(Data const& oldData, Data const& newData) {...}
// ...
void AddData(int key, Data&& newData)
{
    auto [it, ok] = all_data.try_emplace(key, std::move(newData));
    if (!ok)
    {
        if (OldDataIsBetter(*it, newData)) return;
        it->second = std::move(newData);
    }
}

This doesn't compile, because it->second refers to a const Data and so its assignment operator cannot be called. It works fine if const is removed.

The intent of the above is to insert_or_assign, except that if an item is already present then I need to compare the old and new items to see which one is "better".

The intent of declaring the map element type with const is that the data is supposed to be immutable once in the map -- the item as a whole can be replaced but not piecemeal modified.

I can "fix" the above by reassigning to the container instead:

all_data[key] = std::move(newData);

(Actually turns out that has the same problem with const.)

Or by erasing and retrying the emplace:

all_data.erase(it);
all_data.emplace(key, std::move(newData)); // should never fail

But neither of these seem elegant, since I already have an iterator pointing to the item that should be replaced, and both of the above forget that and go search again.

Is there a better way to accomplish this replacement?

---

TLDR from a chat thread brought up related questions:

• If extract can remove a node from a container, let you modify its otherwise-const key, and reinsert it -- all without any reallocations -- why is this not possible for a const mapped_value?
• Const objects can be destroyed. This should also apply to const objects inside containers -- and indeed that's what the erase/emplace variant might be doing if it happens to reuse the same storage for the node (either by coincidence or through a custom allocator). Why then isn't there a way to replace a const mapped_value with a different const mapped_value without reallocating the map node that contains it?

Answer 1

const means immutable, not partially mutable. If you use const on an object declaration (which is what you're doing when you stick const in that template parameter), C++ believes you mean it. And it will hold you to it.

So const Data is a non-starter.

From your question, I surmise that Data has some functions that set some parts of its state, and you do not want users to call said functions. But you want the user to be able to overwrite the value.

The way to do this is to provide an object type which wraps a Data instance, allowing assignment from a Data object. This wrapper will provide versions of the const accessors that Data provides. But the type does not otherwise provide non-const modifiers of Data.

Answer 2

In your case, what you really want to be able to do is conditionally overwrite the data element.

This strongly argues for a mutable data element.

In the general case, the container must have immutable elements, so you could provide a wrapper that provides const access unless mutable access is specifically requested:

#include <map>
#include <functional>

struct Data {};

struct MyDataMap
{
    using store_type = std::map<int, Data>;
    using iterator = store_type::const_iterator;

    template<class Condition>
    std::pair<iterator, bool> 
    replace_if(int key, Data&& value, Condition cond)
    {
        auto [it, inserted_or_replaced] = store_.try_emplace(key, std::move(value));
        if (!inserted_or_replaced && cond(it->second, value))
        {
            it->second = std::move(value);
            inserted_or_replaced = true;
        }
        return std::make_pair(it, inserted_or_replaced);
    }

    // other accessors as necessary

    iterator begin() const { return store_.cbegin(); }
    iterator end() const { return store_.cend(); }

private:

    store_type store_;
};

// ...
bool OldDataIsBetter(Data const& oldData, Data const& newData);
// ...

void test(MyDataMap& m, int k, Data newd)
{
    auto oldIsWorse = std::not_fn(OldDataIsBetter);
    auto [it, replaced] = m.replace_if(k, std::move(newd), oldIsWorse);    
}

Answer 3

After some further experimentation I think that the below is the best method currently available for this scenario:

it = all_data.erase(it);
all_data.emplace_hint(it, key, std::move(newData)); // should never fail

This still doesn't seem ideal to me as it will still reallocate the map node. This is not the end of the world but I'd like to find a way to avoid it if possible.