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

Question

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

然后我意识到，根据另一个参数以某种方式对 map 进行排序对我来说会更有用，所以我添加了一个名为 priority 的 int 来帮助我与订购。这个想法是我遍历 map 并首先处理优先级较高的项目。我现在将以下用户定义的 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);
    }
};

map 排序似乎工作正常，添加新项目时，如果您要遍历 map ，它们会自动输入到预期位置。例如对于 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" }

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

在这种情况下，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");

在如上所述的问题 2 之后，我将一个新项目添加到 map 中，该项目具有与现有项目相同的 addr。新项目似乎已添加到基于新的(修改后的)priority 的预期位置，但要更新的现有项目保持原样。所以我最终在 map 中找到了 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" }

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

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

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

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

Answer 1

问题是你的比较运算符实现不正确，它没有提供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 提供了替换数据的方法。