C++ std::set comparator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// SetBug.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
#include <iso646.h>
using namespace std;

typedef string Item;

// order items by decreasing frequency
struct decreasing_order_comparator {
    bool operator() (const pair<uint64_t, Item>& lhs, const pair<uint64_t, Item>& rhs) const
    {
        //uint64_t是long long 型，用lld或I64d不同系统不一样.data函数的使用
        printf("%lld %s  %lld %s\n", lhs.first, lhs.second.data(), rhs.first, rhs.second.data());
        //printf("%s\n", lhs.second.data());
        //cout << lhs.second << ' ' << rhs.second << endl;
        return (lhs.first > rhs.first) or (not(lhs.first > rhs.first) and lhs.second < rhs.second);
    }
};
set<pair<uint64_t, Item>, decreasing_order_comparator> items_ordered_by_frequency;

int main()
{
    //调试了一晚上，到了第二天早晨才恍然大悟。发现VS编译器真的规范，用CB运行直接忽略debug assertion failed。
    /*原因：不影响结果，忽略即可。首先插入5B，当3A插入的时候，会判断3 <= 5 and A < B，所以返回true，即3A > 5B。但是，如果首先插
    入3A，当5B插入时，会判断5 > 3，所以返回true，即5B > 3A。前后结果矛盾，所以导致set无法确定插入位置，因此
    当有多个变量的时候，最好使用multiset或者需要给前后两个变量都添加判断，不能产生歧义。*/
    items_ordered_by_frequency.insert({ 5, "B" });
    items_ordered_by_frequency.insert({ 3, "A" });

    items_ordered_by_frequency.insert({ 2, "H" });
    items_ordered_by_frequency.insert({ 1, "T" });
    set<pair<uint64_t, Item>, decreasing_order_comparator>::iterator it = items_ordered_by_frequency.begin();
    cout << it->first << ' ' << it->second << endl;
    return 0;
}

注意C/C++可以直接使用and、or、not运算符，添加iso64.h头文件即可。

使用时，正常插入没问题，查找时遇到invalid comparator问题。
原因是comparator不符合规定。

comparator需要时strict weak ordering，需要注意的是，comparator(x,x)必须返回false。
invalid comparator问题
参考：
[1].https://stackoverflow.com/questions/9648100/using-own-comparator-operator-for-map-giving-error-in-case-if-key-not-found
[2].https://stackoverflow.com/questions/32263560/errorinvalid-comparator-when-sorting-using-custom-comparison-function