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

Question

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

然后我意识到，根据另一个参数以某种方式对地图进行排序对我来说会更有用，所以我在我的键中添加了一个称为优先级的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::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

现场示例

我认为你的问题不容易用std::map解决.可能的解决方案是使用带有地址的boost::multi_index作为一个索引，将优先级用作另一个索引。更改现有元素的优先级boost::multi_index提供了替换数据的方法。

Answer 2

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

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

为您节省十几行。

---

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