STD::设置用户定义类型,如何确保不重复

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

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

std::set<RouteElem, mycomparefunction> myset; 

请注意,无法将比较函数与排序函数分开。 STD::设置 是二叉树,如果二叉树中的元素不大于或小于特定元素,则应位于同一位置。它在查找位置的算法中执行类似的操作:

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

rlbond的比较器不阻止插入比较相等的元素。显然,考虑到字符限制,很难在注释中证明这一点,因为rlbond似乎认为std::set保证它永远不会包含 !compare(a,b) && !compare(b,a) 他的比较器。但是,RLBoin的比较器没有定义严格的顺序,因此对于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) 为false,因为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::排序使用内省排序。

如果你有,根据这个计划你可以使用 unordered_set 而不是 set 做最初的解谜。因为散列只需要依赖于x和y,所以它应该比插入一个集合所需的o(log n)比较快。

编辑:只是注意到你说你想“保持”排序顺序,而不是你想一批处理所有的东西。很抱歉。如果您希望在添加元素时有效地维护顺序并排除重复项,那么我建议您根据位置使用上面定义的集合或无序集合,并且 std::multiset<RouteElem> ,它将保持 operator< 秩序。对于每个新元素,请执行以下操作:

if (routeset.insert(elem).second) {
    routemultiset.insert(elem);
}

但请注意,这并不能提供例外保证。如果第二个insert抛出,则routeset已被修改,因此状态不再一致。所以我想你真的需要:

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类,则会更加冗长,但如果有很多重复,则会更好。

小心这件事的后果。看起来你在做类似于*的事情,如果你试图插入一个“副本”,它将被忽略,即使有一个“更好”的路线。

注意:此解决方案不起作用,请参阅下面的逐个解释

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;