Modify key of std::map

std map change second
modify value in std map
c++ map<key type
std::map erase
c map::extract
std::map constructor
std::map upsert
c++ map change value

Is there a way to modify the key of a std::map or ? This example shows how to do so with rebalancing the tree. But what if I provide some guarantees that the key won't need to be rebalanced?

#include <vector>
#include <iostream>
#include <map>


class Keymap
{
private:    
    int key; // this key will be used for the indexing
    int total;
public:
    Keymap(int key): key(key), total(0)
    {}
    bool operator<(const Keymap& rhs) const{
        return key < rhs.key;
    }
    void inc()
    {
        total++;
    }
};
std::map<Keymap, int> my_index;



int main (){
    std::map<Keymap, int> my_index;
    Keymap k(2);
    my_index.insert(std::make_pair(k, 0));

    auto it = my_index.begin();

    it->first.inc(); // this won't rebalance the tree from my understanding
    return 0;
}

The modification won't compile because of the constness of it->first

Is there any way to override this behavior?

You could make inc const and total mutable

class Keymap
{
private:    
    int key; // this key will be used for the indexing
    mutable int total;
public:
    Keymap(int key): key(key), total(0)
    {}
    bool operator<(const Keymap& rhs) const{
        return key < rhs.key;
    }
    void inc() const
    {
        total++;
    }
};

But you do need to ask yourself why you are doing this, mutable isn't used much.

You're right that no rebalancing is going to happen.

Update a key value : map update « map multimap « C++ Tutorial, Update a key value : map update « map multimap « C++ Tutorial. Permission to copy, use, modify, sell and distribute this software * is granted provided <​string> using namespace std; int main() { /* create map / associative array * - keys are stocks["Siemens"] = 842.20; // print all elements StringFloatMap::iterator pos;  The problem with changing the key of a std::map (or the value of a std::set) Contrary to sequence containers such as std::vector, std::map and std::set offers 2 guarantees: they maintain their elements in sorted order, they ensure their elements are unique (except for std::multimap and std::multiset).

If you cannot change the design and introduce surrogate read-only keys, your best option is to use Boost.MultiIndex container (I am not aware of reasonable alternatives). It is designed specifically for this purpose and has consistent built-in support of updating the indexed object, including the transactional variant. Documentation and code examples are here.

Generally, patterns like storing business entities in a self-keyed sets, having mutable keys serving additional purpose (counters and whatnot), etc. tend to have impact on maintenability, performance, and scalability of the code.

std::map<Key,T,Compare,Allocator>::extract , std::map<Key,T,Compare,Allocator>::extract Standard Library Headers extract is the only way to change a key of a map element without  Is there a way to modify the key of a std::map or ? This example shows how to do so with rebalancing the tree. But what if I provide some guarantees that the key won't need to be rebalanced?

You could wrap your keys into a class that allows modification of const objects. One such class would be std::unique_ptr:

using KeymapPtr = std::unique_ptr<Keymap>;

struct PtrComp
{
    template<class T>
    bool operator()(const std::unique_ptr<T>& lhs, const std::unique_ptr<T>& rhs) const
    {
        return *lhs < *rhs;
    }
};

template<class V>
using PtrMap = std::map<KeymapPtr, V, PtrComp>;

int main (){
    PtrMap<int> my_index;
    KeymapPtr k = std::make_unique<Keymap>(2);
    my_index.emplace(std::move(k), 0);

    auto it = my_index.begin();

    it->first->inc(); // this won't rebalance the tree from my understanding
    return 0;
}

Demo

Note that we have to supply a custom comparator object since we (presumably) want to sort by the key values, not the pointer values.

To be clear, this is not what unique_ptr is meant for, and the const semantics of smart pointers (which follow those of regular pointers) are a bit backwards from this perspective (why can I get a non-const reference from a const object? A linter may complain about this kind of use...), but it does the trick here. The same would of course work with naked pointers (where a T* const can have the T value changed but not the pointer location, whereas a const T* can have its location changed but not the T), but this mimics the ownership/lifetime model of your original code.

Needless to say, this opens the door to breaking the map invariants (breaking the sortedness by keys) so think twice before using it. But unlike const_casting your key directly, it is free of UB.

map::operator[] - C++ Reference, If k matches the key of an element in the container, the function returns a reference <map> #include <string> int main () { std::map< char ,std::string> mymap; an element and returns a reference that can be used to modify its mapped value. Since the std::map data structure maps from keys to values in a way that the keys are always unique and sorted, it is of crucial value that users cannot modify the keys of map nodes that are already inserted. In order to prevent the user from modifying the key items of perfectly sorted map nodes, the const qualifier is added to the key type.

std::map and the other standard associative containers do not provide a way to do this without removing and adding an element, likely causing tree rebalancing side effects. You can go around the map key constness in various ways (e.g. using mutable members), but then it's entirely up to you to make sure you don't actually break the key ordering.

If you need this sort of efficiency but a bit more safety, you might consider changing the container to a boost::multi_index_container instead.

A std::map<K,V> is similar to:

namespace BMI = boost::multi_index;
using map_value_type = std::pair<K, V>;
using map_type = BMI::multi_index_container<
    map_value_type,
    BMI::indexed_by<BMI::ordered_unique<
        BMI::member<map_value_type, &map_value_type::first>
>>>;

except that in a multi_index_container, the entire element is always const. If you want to be able to directly modify the second members, a means for that is described on this boost page.

multi_index_container provides two members the standard associative containers do not, replace and modify. Both of these will check for whether the modified element is in the same sort order or not. If it is, no rebalancing is done.

auto it = my_index.begin();
auto pair = *it;
pair.first.inc();
my_index.replace(it, pair);

// OR

auto it = my_index.begin();
my_index.modify(it, [](auto& pair) { pair.first.inc(); });

map::at - C++ Reference, Returns a reference to the mapped value of the element identified with key k. #​include <map> int main () { std::map<std::string, int > mymap = { { "alpha" , 0 } is accessed (neither the const nor the non-const versions modify the container). No. This is why value_type of std::map<Key, Value> is std::pair<Key const, Value> (notice const applied to Key). @Joseph Yep, something like that. In C++11 you can use std::move to move the value instead of copying it if it is relatively expensive to copy.

STL Maps Container in C++, Maps contain sorted key-value pair, in which each key is unique and cannot be changed, #include <iostream> #include <map> using namespace std; int main that if the given key is already present in the map then its value is modified. The major profit of using boost::bimaps::bimap over std::map is that we can modify the keys/values in a boost::bimaps::bimap which is something IMPOSSIBLE with std::map. boost::bimaps supports two methods namely modify_key and modify_data which can be use to modify the key and values respectively in a given bimap.

The std::map subscript operator is a convenience, but a potentially , The std::map<K, V> class is an associative container of key/value pairs. It also provides a handy subscript operator [] that lets you access the  Here is the pseudo algorithm I have in mind: find the node in the tree whose key I want to change. detach if from the tree (don't deallocate) rebalance. change the key inside the detached node. insert the node back into the tree. rebalance.

map Class, Key The key data type to be stored in the map. Type The element data lookup by specifying the std::less<> predicate that has no type parameters. A type const_iterator cannot be used to modify the value of an element. std::map::find returns an iterator to the found element (or to the end() if the element was not found). So long as the map is not const, you can modify the element pointed to by the iterator:

Comments
  • Can you give a practical example where it matters?
  • Are you tied to the container type std::map<Keymap, int>, or can you instead use something like struct Value { int total; int index; }; std::map<int, Value>?
  • @bobah You can have situations where you want to map between objects where the key has more functionality than being a literal map key, or a set with similar properties. More precisely, it could definitely have other members that do not affect its sorting order and that should be modifiable. Say, you get a std::set<Cars, SortByLicensePlate> carsToInspect; where you want to change the inspection date after processing them. You could (and possibly should) use a std::vector here instead, but you get the point.
  • @MaxLanghof - all such use cases are design flaws. In your example it should either be std::map<CarLicensePlate, Car> or something similar to the boost::multi_index which, being an indexing container, has consistent support of data modification.
  • @bobah you have a valid point that this can be viewed as design flaw. However what you proposing you either have to move CarLicensePlate out of the Car class or have a duplicate field which is memory inefficient. So it all comes down how the key relates to the object. But I get your point it is hard to make a case with this one. In my case, I wanted to avoid the cost of refactoring to store some metadata.
  • "isn't used much" is not a reason to ask yourself why you are doing this. mutable has its uses and necessities. The present case is actually a valid use case for mutable, although one might argue it allows too much modification.
  • How can you determine that this a valid use case for mutable? We are not seeing how total is used and whether it has any externally observable effect (it currently doesn't, but it also serves no purpose whatsoever, so the example is clearly incomplete). You would need to make a very good case to use mutable, not just "it helps here"...