如何使用用户定义的键控制和修改 std::map 顺序

Question

我开始使用 std::string 作为我的地图键，因为我地图中的每个项目都可以单独由一个字符串唯一标识。

然后我意识到根据另一个参数以某种方式对地图进行排序对我来说会更有用，所以我在我的键中添加了一个名为 priority 的 int 来帮助订购。这个想法是我遍历地图并首先处理优先级较高的项目。我现在有以下用户定义的 struct 作为我的地图键：

struct MyKey {

    // key data
    std::string addr;
    int priority;

    // constructor
    MyKey(const std::string & s, const int p) 
        : addr(s), priority(p) {}

    // overloaded operator
    bool operator<(const MyKey &that) const {

        // same key if addr is the same
        if (that->addr == this.addr)
            return false;

        // not same key so look at priorities to determine order
        if (that.priority < this->priority)
            return true;
        if (that.priority > this->priority)
            return false;

        // priorities are the same so use the string compare
        return (that.addr > this->addr);
    }
};

地图排序似乎工作正常，添加新项目时，如果您要遍历地图，它们会自动输入到预期位置。例如，对于 std::string 个值的映射：

std::map<myKey, std::string> myMap;

myKey key1 = myKey(std::string("key1"), 1);
myKey key2 = myKey(std::string("key2"), 2);
myKey key3 = myKey(std::string("key3"), 3);
myKey key4 = myKey(std::string("key4"), 4);

myMap[key1] = std::string("value1");
myMap[key2] = std::string("value2");
myMap[key3] = std::string("value3");
myMap[key4] = std::string("value4");

将在各自的索引处产生以下映射键值对：

[0] { addr = "key4", priority = 4 }, { "value4" }
[1] { addr = "key3", priority = 3 }, { "value3" }
[2] { addr = "key2", priority = 2 }, { "value2" }
[3] { addr = "key1", priority = 1 }, { "value1" }

但是...我在修改映射中已存在的键的现有优先级时遇到问题。

在这种情况下，find() 和 []（相对于 std::map）无法正常工作：

myKey modified_key1 = myKey(std::string("key1"), 5);

// problem 1 - this does not return iterator to "key1", 
// but instead to end of the map
auto & foundKey = myMap.find(modified_key1);

// problem 2 - this adds a brand new item to the map
myMap[modified_key1] = std::string("value1");

在如上所述 problem 2 之后，我将一个新项目添加到地图中，该项目与现有项目相同 addr。根据新的（修改的）priority，新项目似乎已添加到预期位置，但要更新的现有项目保持原样。所以我最终在地图中得到 2 个项目，它们的键中有相同的 addr：

[0] { addr = "key1", priority = 5 }, { "value1" }
[1] { addr = "key4", priority = 4 }, { "value4" }
[2] { addr = "key3", priority = 3 }, { "value3" }
[3] { addr = "key2", priority = 2 }, { "value2" }
[4] { addr = "key1", priority = 1 }, { "value1" }

这对我来说是个问题，因为我仍想依赖地图项键的 addr 是唯一的概念。

我想要的是地图意识到它已经有一个具有相同键的项目（或更多到相同键addr）并相应地重新排序该项目。

我曾尝试将比较仿函数作为映射定义的一部分进行试验，并且还重载了键 == 运算符，但同样的问题仍然存在。

我错过了什么或者我应该以不同的方式处理这个问题吗？

Answer 1

您可以使用 std::tuple<int, std::string> 而不是 MyKey，它为您定义了关系运算符：

using MyKey = std::tuple<int, std::string>;

为您节省十几行。

您不能修改任何关联容器中元素的键。相反，您需要使用旧密钥删除元素并使用新密钥重新插入它。

Answer 2

问题是您的比较运算符实施不正确，它不提供 strict weak 排序，因此 std::map 的行为未定义，假设您有 3 个 MyKey 对象：

MyKey mk1{ "a",3 }, mk2{ "b", 2 }, mk3 { "a", 1 };
mk1 < mk2 -> true as 3 > 2
mk2 < mk3 -> true as 2 > 1
mk1 < mk3 -> false as addr is the same, but must be true

live example

我认为 std::map 无法轻松解决您的问题。可能的解决方案是使用 boost::multi_index，地址作为一个索引，优先级作为另一个索引。要更改现有元素的优先级 boost::multi_index 提供了替换数据的方法。

如何使用用户定义的键控制和修改 std::map 顺序

How to control and modify the std::map ordering using a user-defined key

c++

operator-overloading

stdmap

user-defined-types