c++ - std::set 比较器函数如何工作？

Question

目前正在研究一个使用集合的算法问题。

set<string> mySet;
mySet.insert("(())()");
mySet.insert("()()()");

//print mySet: 
(())()
()()()

好的，正如预期的那样。

但是，如果我放置一个按长度对集合进行排序的 comp 函数，我只会返回 1 个结果。

struct size_comp
{
    bool operator()(const string& a, const string& b) const{
        return a.size()>b.size();
    }
};
set<string, size_comp> mySet;
mySet.insert("(())()");
mySet.insert("()()()");

//print myset
(())()

谁能给我解释一下为什么？

我尝试使用多集，但它附加了重复项。

multiset<string,size_comp> mSet;
mSet.insert("(())()");
mSet.insert("()()()");
mSet.insert("()()()");
//print mset
"(())()","()()()","()()()" 

Answer 1

std::set 仅存储唯一值。两个值 a,b 被认为是等价的当且仅当

!comp(a,b) && !comp(b,a)

或者在日常用语中，如果a不小于b并且b不小于a .特别地，只有这个标准用于检查是否相等，根本不考虑普通的operator==。

因此对于您的比较器，对于每个 n，该集合只能包含一个长度为 n 的字符串。

如果你想允许多个值在你的比较下是等价的，使用std::multiset .这当然也允许完全重复，同样，在您的比较器下，"asdf" 与 "aaaa" 等同于 "asdf"。

如果这对您的问题没有意义，您需要想出一个不同的比较器来引入适当的相等概念，或者使用其他数据结构。

---

获得您可能想要的行为的快速修复(如果我错了请纠正我)将引入一个次要比较标准，如普通 operator>。这样，我们首先按长度排序，但仍然能够区分相同长度的不同字符串。

struct size_comp
{
    bool operator()(const string& a, const string& b) const{
        if (a.size() != b.size())
            return a.size() > b.size();
        return a > b;
    }
};