C++ 如何为地图创建自己的比较器？

How can I create my own comparator for a map?

提问by Xitrum

typedef map<string, string> myMap;

When inserting a new pair to myMap, it will use the key stringto compare by its own string comparator. Is it possible to override that comparator? For example, I'd like to compare the key stringby its length, not by the alphabet. Or is there any other way to sort the map?

当向 插入新对时myMap，它将使用键string通过自己的字符串比较器进行比较。是否可以覆盖该比较器？例如，我想string通过长度而不是字母来比较密钥。或者有没有其他方法可以对地图进行排序？

回答by Georg Fritzsche

std::maptakes up to four template type arguments, the third one being a comparator. E.g.:

std::map最多需要四个模板类型参数，第三个是比较器。例如：

struct cmpByStringLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

// ...
std::map<std::string, std::string, cmpByStringLength> myMap;

Alternatively you could also pass a comparator to maps constructor.

或者，您也可以将比较器传递给maps 构造函数。

Note however that when comparing by length you can only have one string of each length in the map as a key.

但是请注意，当按长度进行比较时，您只能将映射中每个长度的一个字符串作为键。

回答by honk

Since C++11, you can also use a lambda expressioninstead of defining a comparator struct:

从C++11 开始，您还可以使用lambda 表达式而不是定义比较器结构：

auto comp = [](const string& a, const string& b) { return a.length() < b.length(); };
map<string, string, decltype(comp)> my_map(comp);

my_map["1"]      = "a";
my_map["three"]  = "b";
my_map["two"]    = "c";
my_map["fouuur"] = "d";

for(auto const &kv : my_map)
    cout << kv.first << endl;

Output:

输出：

1
two
three
fouuur

1
2
3个
fouuur

I'd like to repeat the final note of Georg's answer: When comparing by length you can only have one string of each length in the map as a key.

我想重复 Georg 回答的最后一个注释：按长度进行比较时，地图中每个长度只能有一个字符串作为键。

Code on Ideone

Ideone 上的代码

回答by John Dibling

Yes, the 3rd template parameter on mapspecifies the comparator, which is a binary predicate. Example:

是的，第三个模板参数 onmap指定比较器，这是一个二元谓词。例子：

struct ByLength : public std::binary_function<string, string, bool>
{
    bool operator()(const string& lhs, const string& rhs) const
    {
        return lhs.length() < rhs.length();
    }
};

int main()
{
    typedef map<string, string, ByLength> lenmap;
    lenmap mymap;

    mymap["one"] = "one";
    mymap["a"] = "a";
    mymap["fewbahr"] = "foobar";

    for( lenmap::const_iterator it = mymap.begin(), end = mymap.end(); it != end; ++it )
        cout << it->first << "\n";
}

回答by yyFred

Specify the type of the pointer to your comparison function as the 3rd type into the map, and provide the function pointer to the map constructor:
map<keyType, valueType, typeOfPointerToFunction> mapName(pointerToComparisonFunction);

将指向比较函数的指针类型指定为映射中的第三种类型，并将函数指针提供给映射构造函数：
map<keyType, valueType, typeOfPointerToFunction> mapName(pointerToComparisonFunction);

Take a look at the example below for providing a comparison function to a map, with vectoriterator as key and intas value.

看看下面的例子，它为 a 提供了一个比较函数map，vector迭代器作为键和int值。

#include "headers.h"

bool int_vector_iter_comp(const vector<int>::iterator iter1, const vector<int>::iterator iter2) {
    return *iter1 < *iter2;
}

int main() {
    // Without providing custom comparison function
    map<vector<int>::iterator, int> default_comparison;

    // Providing custom comparison function
    // Basic version
    map<vector<int>::iterator, int,
        bool (*)(const vector<int>::iterator iter1, const vector<int>::iterator iter2)>
        basic(int_vector_iter_comp);

    // use decltype
    map<vector<int>::iterator, int, decltype(int_vector_iter_comp)*> with_decltype(&int_vector_iter_comp);

    // Use type alias or using
    typedef bool my_predicate(const vector<int>::iterator iter1, const vector<int>::iterator iter2);
    map<vector<int>::iterator, int, my_predicate*> with_typedef(&int_vector_iter_comp);

    using my_predicate_pointer_type = bool (*)(const vector<int>::iterator iter1, const vector<int>::iterator iter2);
    map<vector<int>::iterator, int, my_predicate_pointer_type> with_using(&int_vector_iter_comp);


    // Testing 
    vector<int> v = {1, 2, 3};

    default_comparison.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    default_comparison.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    default_comparison.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    default_comparison.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << default_comparison.size() << endl;
    for (auto& p : default_comparison) {
        cout << *(p.first) << ": " << p.second << endl;
    }

    basic.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    basic.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    basic.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    basic.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << basic.size() << endl;
    for (auto& p : basic) {
        cout << *(p.first) << ": " << p.second << endl;
    }

    with_decltype.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    with_decltype.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    with_decltype.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    with_decltype.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << with_decltype.size() << endl;
    for (auto& p : with_decltype) {
        cout << *(p.first) << ": " << p.second << endl;
    }

    with_typedef.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    with_typedef.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    with_typedef.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    with_typedef.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << with_typedef.size() << endl;
    for (auto& p : with_typedef) {
        cout << *(p.first) << ": " << p.second << endl;
    }
}