What Is the Fastest Way to Change a Key of an Element Inside Std::Map

What is the fastest way to change a key of an element inside std::map

In C++17, the new map::extract function lets you change the key.

Example:

std::map<int, std::string> m{ {10, "potato"}, {1, "banana"} };
auto nodeHandler = m.extract(10);
nodeHandler.key() = 2;
m.insert(std::move(nodeHandler)); // { { 1, "banana" }, { 2, "potato" } }

Modify key of std::map

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.

How to modify key values in std::map container

Looks like you are better off building a new map and swapping it afterward. You'll have only n insert operations instead of n deletions and n insertions.

How to change some keys in a std::map using extract and insert

The vector type is simple to address, since std:map specializations expose a type alias.

std::vector<std::map<K,V>::node_type> tmp;

The more involved point is the iteration. You cannot use a simple range-based for. That is because node extraction invalidates iterators to the extracted element. And that includes the iterator used behind the scenes for iteration. Instead, a more appropriate loop would be

for (auto it = myMap.begin() ; it != myMap.end();) {
    if(it->second->needsToBeModified()){
      auto out = it++;
      tmp.push_back(myMap.extract(out));
    }
    else
      ++it;
}

Insertion while iterating is possible (since it doesn't invalidate iterators). But if the iteration order is important (even if only for debuggability), I think an auxiliary vector like you use is appropriate.

How to get an element in a map and change it

map<char, int>::iterator it = m.find('a'); 
if (it != m.end() {
    it->second = 105;

updating the value of a key in a std::map

If you are sure that y does not participate in the "logical state" of your class and is merely an implementation detail, then you could declare it mutable:

struct T
{
  int x;
  mutable int y;
  bool operator<(const T& rhs) const { return x < rhs.x; }
};

Now you ought to be able to change y:

for (auto it = m.begin(); it != m.end(); ++it)
{
  it->first.y = -2; // ouch? But it won't invalidate the map's invariants.
}

How to change the key in an unordered_map?

You can use unordered_map::erase and unordered_map::insert to update a key. The average time complexity is O(1)(BTW, the worst is O(n)). If you are using C++17, you can also use unordered_map::extract to update a key. The time complexity is the same.

However, since you only need a set of number, I think unordered_set is more suitable for your algorithm.

---

Related Topics