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)元素ab被认为是相等的!(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;