std :: set用户定义的类型,如何确保没有重复

Question

所以我有一个std :: set,它需要保持特定的顺序以及不允许用户定义(由我)类型的重复.现在我可以通过重载我的类型中的'<'运算符来使订单正常工作.但是,该集合没有适当地检测重复,并且说实话,我不完全确定它是如何在内部执行的.我已经重载'=='运算符,但不知何故我不确定这是该集实际使用的是什么？所以问题是当你添加值时,集合如何确定重复？这是相关代码:

用户定义的类型:

//! 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);
    }
};

因此,当元素的位置相等时,元素是等价的,如果元素的组合函数小于另一元素,则元素小于另一元素.排序工作,但该集将接受相同位置的两个元素.

Answer 1

operator==不被使用std::set.元素a和b被认为是相等的iff!(a < b) && !(b < a)

Answer 2

std::set支持指定比较功能.默认值是less将使用operator <检查平等.您可以定义一个自定义函数来检查相等性并使用它来代替:

std::set<RouteElem, mycomparefunction> myset; 

请注意,无法将比较功能与排序功能分开.std::set是二叉树,如果二叉树中的元素不大于特定元素,则它应该在同一个位置.它在地方寻找算法中做了类似的事情:

if (a < b) {
    // check the left subtree
} else if (b < a) {
    // check the right subtree
} else {
    // the element should be placed here.
}

Answer 3

STL 集实现在概念上执行类似以下操作来检测相等性：

bool equal = !(a < b) && !(b < a);

也就是说，如果两个元素都不小于另一个，那么它们一定相等。您可以通过在operator==()方法上设置断点并检查它是否被调用来检查这一点。

我通常会对检查完全不同的事物的比较运算符持怀疑态度。您的<运算符是根据与您的运算符的定义方式不同的两件事来定义的==。一般来说，您会希望此类比较使用一致的信息。

Answer 4

rlbond的比较器不会阻止插入比较相等的元素.显然,鉴于字符限制,很难在评论中证明这一点,因为rlbond似乎认为std :: set保证它永远不会包含两个元素!compare(a,b) && !compare(b,a)用于他的比较器.但是,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"为了使算法正常工作,comp必须在值上引入严格的弱排序".

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(顺序)以来是真的
• comp(b,c) 自2!= 1(相等)和2 <9(顺序)后为真
• comp(a,c) 因为1 == 1(相等)是假的