目前正在使用 set 处理算法问题。
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
"(())()","()()()","()()()"
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;
}
};
比较器模板参数(默认为std::less<T>
)必须表示其域中值之间的严格弱排序关系。
这种关系有一些要求:
- 它不是自反的(
x < x
产生错误) - 它是不对称的(
x < y
暗示y < x
是假的) - 它是可传递的(
x < y && y < z
意味着x < z
)
更进一步,我们可以根据这种关系定义值之间的等价性,因为如果!(x < y) && !(y < x)
那么它必须保持该x == y
。
在你的情况下,你有这样的∀ x, y
,这样x.size() == y.size()
,那么两个comp(x,y) == false && comp(y,x) == false
,所以由于没有x
或y
小于另一个,那么它们必须是相等的。
此等效性用于确定两个项目是否相同,从而忽略示例中的第二次插入。
要解决此问题,您必须确保您的比较器永远不会为comp(x,y)
和comp(y,x)
返回 false 如果您不想考虑x
等于y
,例如通过
auto cmp = [](const string& a, const string& b) {
if (a.size() != b.size())
return a.size() > b.size();
else
return std::less()(a, b);
}
因此,对于相同长度的输入,您可以回退到正常的词典顺序。
这是因为元素的相等性是由比较器定义的。一个元素被视为等于另一个元素当且仅当!comp(a, b) && !comp(b, a)
。
由于"(())()"
的长度不大于也不小于"()()()"
的长度,因此您的比较器认为它们相等。std::set
中只能有唯一的元素,一个等效的对象将覆盖现有的对象。
默认比较器使用operator<
,在字符串的情况下,执行字典顺序。
我尝试使用多集,但它附加重复项。
多集确实允许重复。因此,尽管长度相同,但两个字符串都将被包含。
>size_comp只考虑字符串的长度。默认比较运算符使用字典比较,它根据字符串的内容和长度进行区分。