的std ::与用户定义类型，如何确保没有重复设置的std ::与用户定义类型，如何确保没有重复设置

所以，我有一个std ::一套需要保持特定的顺序，以及不允许定义的用户的副本（由我）型。 现在，我可以得到为了在我喜欢的类型重载“<”操作正常工作。 然而，集不适当地检测重复，说实话，我不是很确定它是如何做到这一点的内部。 我已经超载了“==”操作，但不知何故，林不知道这是一组实际使用？ 所以，问题是如何设置的确定重复，当你添加值？ 下面是相关的代码：

用户定义的类型：

//! 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被认为是等于当且仅当!(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:

rlbond的比较并不妨碍它比较了相同元素的插入。 显然，这是很难的意见，就证明了这给出的字符的限制，因为rlbond似乎认为的std ::一套保证它永远不会包含两个元素!compare(a,b) && !compare(b,a)为他比较。 然而，rlbond的比较没有定义严格的秩序，因此是不为std ::一套有效的参数。

#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“对于算法正确工作， 补偿具有诱导对值的严格的弱序”。

25.3：4” ...的要求是比较和当量均为传递关系：

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（平等）

Answer 4:

该STL集合实施做了概念上类似这样的检测平等：

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

也就是说，如果两个元素比其他两个不更小，则它们必须是相等的。 您可以在您的设置断点来检查这个operator==()方法和检查，看其是否曾经被调用的。

我通常会怀疑比较运算符检查完全不同的东西。 您的<运算符时的两件事情是从你如何单独定义的==操作符定义。 一般来说，你会希望这样的比较使用一致的信息。

Answer 5:

你可以尝试一些类似如下：

//! 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做初步uniqueifying。 由于散列将只需要依赖于x和y，它应该比O（日志N）的比较，以插入一组需要更快。

编辑：只注意到你说你要“保持”的排序顺序，不是说你想处理批量的一切。 对于那个很抱歉。 如果要有效地维持秩序，排除重复的同时加入的元素，然后我建议使用所述一组或无序集合I中定义，基于位置，并且还一个std::multiset<RouteElem>这将维持operator<顺序。 对于每一个新的元素，这样做：

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

虽然提防，这种不提供异常保证。 如果第二插入抛出，那么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类的地方，但更好，如果有太多的重复。

Answer 6:

谨防这种后果的。 它看起来像你正在尝试做一些像A *，如果你试图插入一个“重复”会被忽略，即使有一个“更好”的路线。

注意：此方法不起作用，请参阅下面onebyone的解释

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;

文章来源: std::set with user defined type, how to ensure no duplicates