为什么 std::set 允许我插入重复的（非唯一的）自定义元素？

Question

我需要创建一组自定义项目：

1. 按优先级排序
2. 不能有重复的名字。

在这个例子中，我使用std::set和一个重载的operator<( )。据我所知，std::set使用operator<( )进行排序和唯一性检查。但是我的代码失败了，因为我能够插入具有重复名称的项目：

#include <iostream>
#include <set>



struct Item
{
    std::string name;
    int priority;
};



bool operator<( const Item& a, const Item& b ) 
{
    // Always returns false if names are equal.
    // Set should consider elements equal when a < b is false and b < a is also false.
    if( a.name == b.name )
        return false;

    return ( a.priority < b.priority );
}



int main()
{
    Item a  { "a", 3000 };
    Item b  { "b", 4000 };
    Item c  { "c", 2000 };
    Item a2 { "a", 5000 };


    std::set<Item> pool;


    pool.insert( a );
    pool.insert( b );
    pool.insert( c );
    pool.insert( a2 );


    for( const auto& item : pool )
        std::cout << item.name << ": " << item.priority << std::endl;


    return 0;
}

在 onlinegdb.com 中编译它给了我下面的结果。

名称为“a”的两个元素都插入到std::set 中。

c: 2000
a: 3000
b: 4000
a: 5000

我究竟做错了什么？

我应该使用不同的容器吗？

编辑：

更改插入顺序会使代码按预期工作。

    pool.insert( a );
    pool.insert( a2 );
    pool.insert( b );
    pool.insert( c );

正确结果为：

c: 2000
a: 3000
b: 4000

Answer 1

我究竟做错了什么？

您的比较函数未能强加严格的弱排序。这是Compare概念的要求，是标准集的要求。违反该要求会导致未定义的行为。

严格的弱排序关系必须是可传递的（对于 S 中的所有 x、y、z，如果 x < y 和 y < z 则 x < z）。您的比较函数没有此属性。

那么， std::set 如何确定元素是唯一的？

等价性由 确定!comp(a, b) && !comp(b, a)。

我可以覆盖它以检查项目名称吗？

影响等价关系的唯一方法是改变比较函数。无法使用标准集将唯一性约束与排序约束分开。

我应该使用不同的容器吗？

是的。

我有什么建议可以用 STL 容器解决这个问题吗？

没有一个标准容器是合适的。您需要的是一个多索引容器。Boost 库集合有一个实现。