C++ Comparator 函数指定映射的特定键顺序？

Question

问题：您将如何编写函数来为地图构造函数执行自定义比较器以创建特定的键顺序？

我有以下字符串键：

"a", "d", "i", "n", "ns", "ne", "vl", "rr"

我正在使用地图为这些键写入值。但我需要按照上述确切顺序订购它们。地图通常创建顺序：

a d i n ne ns rr vl

如何编写可以发送到地图构造函数的比较器函数，以便我可以保留此顺序？

这是我目前使用的方法

vector<pair<string, string>>({ { "a","" },{ "d","" },{ "i","" },{ "n","" },{ "ns","" },{ "ne","" },{ "vl","" },{ "rr","" }, { "","" } });

...然后我打了一堆 find_if 电话。如果找到，我将值添加到该对中。如果没有，我创建一对新的（在开始时）。我在一开始就这样做，所以如果密钥不存在，我可以 return "" 。好吧，除了我需要对上面没有列出的键进行排序外，这一切都有效，因为可以添加任何键。此外，当我尝试添加一个不存在的密钥时，我的程序崩溃了。必须调试它......但是这种方式令人困惑。使用带有一些特定排序的地图将非常适合我的需要（在运行时添加的任何键都应该通过默认比较进行排序以及维护顺序。这些 "unknown" （未来添加的）键可以排序然而）。

我 "want this" 的原因（在评论中询问）：我需要在程序的最后一步输出这样的字符串：

",a=legato,d=dn,i=12,n=A3"

等它们需要按特定顺序排列，因为我稍后需要使用正则表达式（在单独的程序中）来操作此字符串。顺序对于指定的键很重要。对于未指定的键，顺序也必须固定...因为正则表达式。

Answer 1

您指定映射用于排序键的比较器作为模板参数。所以你的地图声明看起来像：

std::map<string, value_type, my_comparator> my_map;

比较器是您可以定义的东西，它接受两个 key_type 参数 a 和 b，如果 a 出现在 [ 之前，则 returns 为真=15=]（否则为假）。这方面的一个例子是：

struct my_comparator {
    bool operator()(const string &a, const string &b) {
        // Return true if a comes before b.
    }
}

要实现您在问题中指定的顺序，您可以按照以下方式进行操作。我已经使用 std::tuple 来确保满足严格的订购标准。

bool operator()(const string &a, const string &b) {
    auto a_tuple = std::make_tuple(a == "a", a == "d", a == "i", ..., a);
    auto b_tuple = std::make_tuple(b == "a", b == "d", a == "i", ..., a);

    return a_tuple < b_tuple;
}

因为这在元组的最后一个元素中有 a 和 b，如果它与您的预定义字符串之一不匹配，它将按这些排序。

Answer 2

查看对解释为什么需要这样做的问题的编辑，我建议改为使用默认排序的 map，然后在您想要输出值时参考不同的列表：

std::vector<std::string> ordering = { "a", "d", "i", "n", "ns", "ne", "vl", "rr" };
for (const auto& key : ordering)
    ...output the_map[key]...

无论如何，如果您坚持使用不同顺序的 map，您可以根据需要进行特殊处理：

struct WeirdLess
{
    bool operator<(const std:string& lhs, const std::string& rhs) const
    {
        if (lhs == "ne" && rhs == "ns" ||
            lhs == "ns" && rhs == "ne" ||
            lhs == "rr" && rhs == "vl ||
            lhs == "vl" && rhs == "rr")
            return rhs < lhs;
        return lhs < rhs;
    }
};

std::map<std::string, std::string, WeirdLess> my_map;

虽然它的可扩展性不是很好，如果您最终在 map 中有数百个条目并且其中一半需要特殊外壳。尝试提出一些逻辑来捕捉为什么特定字符串较早 - 或者至少是识别它们的启发式 - 这可能是一个更好的主意。例如：

    bool operator<(const std:string& lhs, const std::string& rhs) const
    {
        if (lhs.size() == 2 && rhs.size() == 2 && lhs[0] == rhs[0])
            return rhs < lhs;
        return lhs < rhs;
    }

Answer 3

根据持有键顺序的向量对向量对进行排序

这不是原问题的答案，而是描述问题的解决方案。有关此概念的更快版本，请参阅我的其他答案。

运行: https://ideone.com/8ICRwZ

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// create vector holding desired ordering
vector<string> order({ "a", "d", "i", "n", "ns", "ne", "vl", "rr" });

// create sort function for vector of pairs
bool comparator(const pair<string, string> &s1, const pair<string, string> &s2) {
    // find() - it.begin() gives you the index number. 
    int a = find(order.begin(), order.end(), s1.first) - order.begin();
    int b = find(order.begin(), order.end(), s2.first) - order.begin();
    return a < b; // lower index < higher index
};

int main() {
    // create the map
    map<string,string> MyMap = { { "a","legato" }, { "vl","3" }, {"i", "3"}, { "rr","2" } };

    // convert map into vector of pairs
    vector<pair<string,string>> vp;
    for (auto& it : MyMap) vp.push_back({ it.first, it.second });

    // sort the vector
    sort(vp.begin(), vp.end(), comparator);

    // put the vector pairs into a string format
    for (auto& it : vp) cout << it.first << "=" << it.second << " ";

    return 0;
}

输出：a=legato i=3 vl=3 rr=2

Answer 4

这就是您如何为地图创建比较器函数来为多个键创建特定的排序顺序。

其他答案的启发使我能够写出自己的答案，以尽可能最好的方式（IMO）准确地解决我的问题。

运行: https://ideone.com/7H5CZg

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// create vector holding desired ordering
vector<string> order({ "a", "d", "i", "n", "ns", "ne", "vl", "rr" });

// create sort function for map   
struct my_comparator {
    bool operator()(const string &s1, const string &s2) {
        // find() - it.begin() gives you the index number. 
        int a = find(order.begin(), order.end(), s1) - order.begin();
        int b = find(order.begin(), order.end(), s2) - order.begin();
        return a < b; // lower index < higher index
    }
};

int main() {
    // create the map
    map<string,string, my_comparator> MyMap = { { "a","legato" }, { "i","3" }, { "vl","3" }, { "rr","2" } };

    // output map
    for (auto& it : MyMap) cout << it.first << "=" << it.second << "  ";

    return 0;
}

输出：a=legato i=3 vl=3 rr=2

更新：这通常会更快，它使用映射而不是向量来查找键顺序。

您也可以将这种做事方式应用到其他答案中。

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// using a map is faster in most cases (with more keys and such)
map<string, int> maporder({ {"a", 1}, {"d", 2}, {"i", 3}, {"n", 4}, {"ns", 5}, {"ne", 6}, {"vl", 7}, {"rr", 8} });

// create sort function for map   
struct mapcomp {
    bool operator()(const string &s1, const string &s2) {
         // compares ints by looking them up with the input string
        return maporder[s1] < maporder[s2];
    }
};

int main() {
    // create the map
    map<string,string, mapcomp> MyMap = { { "a","legato" }, { "i","3" }, { "vl","3" }, { "rr","2" } };

    // output map
    for (auto& it : MyMap) cout << it.first << "=" << it.second << "  ";

    return 0;
}

Answer 5

此函数根据输入向量对集合进行排序

一位好朋友和伟大的程序员为我写了这个答案。根据 ideone.com，这是最有效的解决方案。这不是原始问题的答案，但是实际问题的答案。

//first param is the container you want to sort
//second param is the container that holds the order of things
vector<pair<string,string>> KeySort(map<string,string> s, const vector<string>& order){
    vector<pair<string,string>> res;
    for (const auto& it : order) {
        auto needle = s.find(it);
        if (needle != s.end()) {
            res.emplace_back(move(*needle));
            s.erase(needle);
        }
    }
    for (auto&& it : s) res.emplace_back(move(it));
    return res;
}

ideone 基准测试：https://ideone.com/GYsiM8

ideone 示例使用：https://ideone.com/eAU5US

// create vector holding desired ordering
vector<string> ord({ "a", "d", "i", "n", "ns", "ne", "vl", "rr" });

// create the map
map<string,string> MyMap = { {"a","legato"}, {"vl","4"}, 
{"i","2"}, {"rr","3"}, {"z","unspecified1"}, {"b","unspecified2"}};

// sort the vector
vector<pair<string,string>> out = KeySort(MyMap, ord);

输出：a=legato i=2 vl=4 rr=3 b=unspecified2 z=unspecified1

C++ Comparator 函数指定映射的特定键顺序？

C++ Comparator function to specifiy specific key ordering for map?

c++

dictionary

comparator