std ::用户定义types设置，如何确保没有重复
所以我有一个std :: set需要保持特定的顺序，以及不允许用户定义（我）types的重复。 现在，我可以通过重载我的types中的'<'运算符来正确工作。 然而，这套设备并没有适当地检测到重复的内容，老实说，我不完全确定它是如何做到这一点的。 我已经重载了'=='运算符，但不知何故我不知道这是什么设置实际使用？ 所以问题是当你添加值时，这个集合是如何确定重复的？ 这是相关的代码：
用户定义的types：
//! An element used in the route calculation. struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; 因此，当它们的位置相等时，这些元素是等价的，如果一个元素的组合函数小于另一个元素，则元素小于另一个元素。 sorting工作，但集合将接受相同位置的两个元素。
operator==不被std::set 。 !(a < b) && !(b < a)元素a和b被认为是相等的!(a < b) && !(b < a)
std::set支持指定一个比较函数。 缺省值将会使用operator <来检查相等性。 您可以定义自定义函数来检查相等性，然后使用该函数：
std::set<RouteElem, mycomparefunction> myset;
请注意，无法将比较function与sortingfunction分开。 std::set是一个二叉树，如果一个二叉树中的元素不大也不小于特定元素，它应该在同一个地方。 它在地点查找algorithm中做了这样的事情：
if (a < b) { // check the left subtree } else if (b < a) { // check the right subtree } else { // the element should be placed here. }
rlbond的比较器不会阻止插入比较相等的元素。 显然，在给定字符限制的情况下，很难在注释中certificate这一点，因为rlbond认为std :: set保证它永远不会包含两个元素，即!compare(a,b) && !compare(b,a) for比较。 但是，rlbond的比较器没有定义严格的顺序，因此不是std :: set的有效参数。
#include <set> #include <iostream> #include <iterator> #include <algorithm> struct BrokenOrder { int order; int equality; public: BrokenOrder(int o, int e) : order(o), equality(e) {} bool operator<(const BrokenOrder &rhs) const { return order < rhs.order; } bool operator==(const BrokenOrder &rhs) const { return equality == rhs.equality; } }; std::ostream &operator<<(std::ostream &stream, const BrokenOrder &b) { return stream << b.equality; } // rlbond's magic comparator struct LessThan : public std::binary_function<BrokenOrder, BrokenOrder, bool> { bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const { return !(lhs == rhs) && (lhs < rhs); } }; int main() { std::set<BrokenOrder,LessThan> s; for (int i = 0; i < 5; ++i) { s.insert(BrokenOrder(i,i)); } for (int i = 0; i < 5; ++i) { s.insert(BrokenOrder(10-i,i)); } std::copy(s.begin(), s.end(), std::ostream_iterator<BrokenOrder>(std::cout, "\n")); }
输出：
0 1 2 3 4 3 2 1 0
重复。 魔法比较失败。 集合中的不同元素具有相同的equality值，因此与operator==相同，因为在插入期间，集合从不将新元素与其重复进行比较。 被排除的唯一副本是4，因为这两个4已经排列了第4和第6的顺序。这使它们在一起足够靠近，以便相互比较。
从C ++标准：25.3：3“为了使algorithm正常工作， comp必须在值上导致严格的弱sorting”。
25.3：4“…要求是comp和equiv都是传递关系：
comp(a,b) && comp(b,c) implies comp(a,c)"
现在，考虑元素a = BrokenOrder(1,1) ， b = BrokenOrder(2,2)和c = BrokenOrder(9,1) ， comp当然等于魔法比较器。 然后：
-
comp(a,b)是真的，因为1！= 2（相等）和1 <2（order） -
comp(b,c)是真的，因为2！= 1（相等）和2 <9（order） -
comp(a,c)是错误的，因为1 == 1（相等）
STL集合的实现在概念上做了一些这样的检测：
bool equal = !(a < b) && !(b < a);
也就是说，如果两个元素都不小于另一个，那么它们必须是相等的。 您可以通过在您的operator==()方法上设置断点并检查它是否被调用来检查。
通常我会怀疑比较运算符检查完全不同的东西。 你的<运算符是根据与你的==运算符定义分开的两件事情来定义的。 通常你会希望这样的比较使用一致的信息。
你可以尝试如下的东西：
//! An element used in the route calculation. struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; struct CompareByPosition { bool operator()(const RouteElem &lhs, const RouteElem &rhs) { if (lhs.position.x != rhs.position.x) return lhs.position.x < rhs.position.x; return lhs.position.y < rhs.position.y; } }; // first, use std::set to remove duplicates std::set<RouteElem,CompareByPosition> routeset; // ... add each RouteElem to the set ... // now copy the RouteElems into a vector std::vector<RouteElem> routevec(routeset.begin(), routeset.end()); // now sort via operator< std::sort(routevec.begin(), routevec.end());
显然中间是副本，看起来很慢。 但是，任何按两个不同标准对项目进行索引的结构因此与一个集合相比，每个项目都会有一些额外的开销。 上面的代码是O（n log n），假设你的std :: sort实现使用introsort。
如果你有它，在这个scheme下，你可以使用unordered_set而不是set来做初始的唯一化。 由于散列只需要依赖于x和y，它应该比插入到集合所需的O（log N）比较更快。
编辑：只是注意到，你说你想“保持”sorting，而不是你想处理所有的一批。 对于那个很抱歉。 如果你想在添加元素的时候高效地维护顺序并排除重复项，那么我会build议使用上面定义的基于位置的set或unordered集合，以及一个std::multiset<RouteElem> ，它将维护operator< order 。 对于每个新元素，请执行：
if (routeset.insert(elem).second) { routemultiset.insert(elem); }
虽然要小心，这不提供例外保证。 如果第二个插入引发，则路由集已被修改，所以状态不再一致。 所以我想你真的需要：
if (routeset.insert(elem).second) { try { routemultiset.insert(elem); // I assume strong exception guarantee } catch(...) { routeset.erase(elem); // I assume nothrow. Maybe should check those. throw; } }
或者与RAII等价，如果你的代码中只有一个地方使用了RAII类，那么这将更加冗长，但是如果有很多重复的话，那么就更好了。
当心这个的后果。 它看起来像你正在尝试做一些像A *，如果你试图插入一个“重复”它将被忽略，即使有一个“更好”的路线。
注：此解决scheme不起作用，请参阅下面的一个人的解释
struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; struct RouteElemLessThan : public std::binary_function<RouteElem, RouteElem, bool> { bool operator()(const RouteElem& lhs, const RouteElem& rhs) const { return !(lhs == rhs) && (lhs < rhs); } }; std::set<RouteElem, RouteElemLessThan> my_set;
