修改std::map的键

Question

修改std::map的键

8

有没有一种方法可以修改 std::map 或者的键？这个例子展示了如何通过重新平衡树来实现。但是，如果我能提供一些保证，说明键不需要重新平衡，那该怎么办呢？

#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;
}

由于it->first的常量性，这个修改无法编译。

是否有任何方法可以覆盖这种行为？

- Mini Fridge

1

你能给一个实际的例子来说明它的重要性吗？ - bobah

1

你是否被容器类型 std::map<Keymap, int> 所束缚，或者你可以使用类似于 struct Value { int total; int index; }; std::map<int, Value> 这样的东西？ - Caleth

@bobah 您可能遇到需要在对象之间进行映射的情况，其中键具有比文字地图键或具有类似属性的集合更多的功能。更确切地说，它肯定可以有其他成员，这些成员不会影响其排序顺序并且应该是可修改的。假设您有一个 std :: set <Cars，SortByLicensePlate> carsToInspect; ，在处理它们后要更改检查日期。您可以（可能应该）在此处使用 std :: vector，但是您明白了。 - Max Langhof

@MaxLanghof - 所有这类用例都是设计缺陷。在您的示例中，应该是 std::map<CarLicensePlate, Car> 或类似于 boost::multi_index 的东西，后者作为索引容器，具有一致的数据修改支持。 - bobah

@bobah，你说得很有道理，这可以被视为设计缺陷。然而，你所提出的解决方案要么是将“CarLicensePlate”移出“Car”类，要么是有一个重复的字段，这会浪费内存。因此，这完全取决于密钥与对象的关系。但我明白你的意思，这个问题很难辩解。在我的情况下，我想避免重构的成本来存储一些元数据。 - Mini Fridge

@MiniFridge - 明白了。关于数据重复的问题 - 大多数用作键的字符串可以通过使用 uint64_t 或 uint128_t 大小的 POD 来欺骗并存储，引用它们将与复制它们相同。此外，字符串键可以“内部化”为整数，并在周边停止。但这些最好在从头开始编写时完成，而不是在遗留代码中完成。 - bobah

4个回答

3

如果您无法更改设计并引入替代只读键，则最好选择使用Boost.MultiIndex容器（我不知道合理的替代方案）。它专门为此目的设计，并具有更新索引对象的一致内置支持，包括事务变量。文档和代码示例在这里。

通常，像将业务实体存储在自键集合中，具有可变键以提供额外功能（计数器等）等模式往往会对代码的可维护性、性能和可扩展性产生影响。

- bobah

1

你可以将键包装到一个允许修改const对象的类中。这样的一个类是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;
}

演示

需要注意的是，我们必须提供一个自定义的比较器对象，因为我们（大概）想按键值排序，而不是指针值。

需要明确的是，这不是unique_ptr的设计初衷，智能指针（遵循常规指针的语义）的const语义从这个角度来看有点反向（为什么我可以从const对象中获取非const引用？代码检查程序可能会抱怨这种使用方式...），但它在这里奏效了。当然，裸指针也可以实现同样的功能（其中T* const可以更改T的值，但不能更改指针位置，而const T*可以更改其位置，但不能更改T的值），但这模仿了您原始代码的所有权/生存期模型。

不用说，这打开了破坏映射不变式（通过键打破排序）的大门，因此在使用之前请三思。但与直接const_cast键不同，它是没有未定义行为的。

- Max Langhof

1

std::map和其他标准关联容器没有提供一种方法来做到这一点，而不需要移除和添加元素，可能会导致树重新平衡的副作用。您可以通过各种方式绕过映射键常量性（例如使用mutable成员），但是这完全取决于您确保不会实际破坏键排序。

如果您需要这种效率，但更安全一些，您可以考虑将容器更改为boost::multi_index_container。

std::map<K,V>类似于：

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>
>>>;

除了在multi_index_container中，整个元素始终为const。如果您想直接修改second成员，可以参考this boost page中提到的方法。

multi_index_container提供了两个标准关联容器没有的成员replace和modify。这两个成员都会检查修改后的元素是否按相同的排序顺序排列。如果是，则不进行重新平衡。

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

- aschepler

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- john · Accepted Answer

你可以将inc设为常量(const)，将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++;
    }
};

但是你需要问问自己为什么要这样做，mutable 没有被广泛使用。

你说得对，不会发生任何重新平衡。