By Mini Fridge


2018-08-10 11:03:32 8 Comments

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?

4 comments

@bobah 2018-08-10 11:44:14

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.

@aschepler 2018-08-10 12:03:53

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(); });

@Max Langhof 2018-08-10 11:13:20

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.

@john 2018-08-10 11:23:45

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.

@rubenvb 2018-08-10 11:47:11

"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.

@Max Langhof 2018-08-10 11:50:45

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"...

Related Questions

Sponsored Content

12 Answered Questions

[SOLVED] std::wstring VS std::string

36 Answered Questions

[SOLVED] Why is "using namespace std" considered bad practice?

17 Answered Questions

[SOLVED] Concatenating two std::vectors

34 Answered Questions

[SOLVED] std::string formatting like sprintf

1 Answered Questions

[SOLVED] C++ passing std::unique_ptr as an argument

  • 2015-12-24 15:11:09
  • tomtom
  • 1081 View
  • 1 Score
  • 1 Answer
  • Tags:   c++ unique-ptr

16 Answered Questions

[SOLVED] Iteration over std::vector: unsigned vs signed index variable

11 Answered Questions

[SOLVED] How to find if a given key exists in a C++ std::map

  • 2009-12-21 12:55:03
  • There is nothing we can do
  • 372369 View
  • 320 Score
  • 11 Answer
  • Tags:   c++ dictionary stl

8 Answered Questions

[SOLVED] How to convert a std::string to const char* or char*?

  • 2008-12-07 19:30:56
  • user37875
  • 803719 View
  • 778 Score
  • 8 Answer
  • Tags:   c++ string char const

1 Answered Questions

[SOLVED] Failed to specialize function template

1 Answered Questions

[SOLVED] How to make plugable factory work with lua?

  • 2010-01-02 20:22:33
  • Nhu Phuong
  • 138 View
  • 0 Score
  • 1 Answer
  • Tags:   c++ lua

Sponsored Content