c++ - std::set 中的顺序和 std::unordered_set 的差异

Question

我希望 std::set 的顺序与 std::list 或 std::vector 一致，只是不会第二次附加值。 MSVC 110 证明我错了。我预计以下代码会产生如下所示的结果，在 ideone ( http://ideone.com/e47GwQ ) 上运行代码时就是这种情况(尽管不确定他们使用哪个编译器和版本)。

#include <iostream>
#include <set>

template <typename C>
int insert_get_index(C& container, typename C::value_type value)
{
    typename C::iterator it = container.insert(value).first;
    return std::distance(container.begin(), it);
}

int main()
{
    int a = 3, b = 1, c = 9;
    std::set<int*> set;

    std::cout << insert_get_index(set, &a) << "\n";
    std::cout << insert_get_index(set, &b) << "\n";
    std::cout << insert_get_index(set, &c) << "\n";
    std::cout << insert_get_index(set, &a) << "\n";
    std::cout << insert_get_index(set, &b) << "\n";
    std::cout << insert_get_index(set, &c) << "\n";

    return 0;
}

0
1
2
0
1
2

在 Visual Studio 2012 中运行代码会产生如下所示的结果。

0
0
2
1
0
2

现在，为什么我要细化 std::set 的行为如上所述？因为 cplusplus.com 指出

Sets are containers that store unique elements following a specific order.

此外，还有 std::unordered_set。

1. 我对文档的理解有误吗，std::set 是 value ordered？
2. 那么 std::unordered_set 是干什么用的？
3. 是否有其他标准库容器可以满足我的要求？

Answer 1

Did I understand the documentation incorrectly and std::set is instead value ordered?

确实是按值排序的。除非您提供自己的比较器，否则它们是通过使用 std::less 进行比较来排序的。 .对于大多数类型，这使用 < .对于指针(通常不能以明确定义的方式与 < 进行比较)，它定义了一个未指定但一致的顺序。 (在具有线性地址空间的常见平台上，这可能只是比较地址值；但您不能依赖它)。

因此在这种情况下，存储指向局部变量的指针取决于编译器选择为每个变量分配存储的位置，这可能因编译器而异。

And what's std::unordered_set for then?

当您不关心顺序时，这可以提供更好的性能。它使用哈希表进行恒定时间查找，而 set使用搜索树(或类似的东西)进行对数时间查找。

Is there a different standard library container that fulfils my requirements?

不，没有容器既能维护插入顺序，又能提供快速的基于值的查找。根据您的具体要求，您可以使用 vector维护顺序，并使用 std::find 进行线性时间查找;或者您可以使用两个容器，一个用于维护顺序，一个用于提供快速查找，并使用谨慎的逻辑来保持它们的一致性。