1

我希望 的顺序std::set像std::listor一样一致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 声明

集合是按照特定顺序存储唯一元素的容器。

此外，还有std::unordered_set.

  1. 我是否错误地理解了文档，std::set而是按价值排序？
  2. 那有什么std::unordered_set用呢？
  3. 是否有其他标准库容器可以满足我的要求？
4

1 回答 1

3

我是否错误地理解了文档，而 std::set 是按值排序的？

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

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

那有什么std::unordered_set用呢？

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

是否有其他标准库容器可以满足我的要求？

不，没有容器既可以维护插入顺序，又可以提供基于值的快速查找。根据您的确切要求，您可以使用vector; 来维护订单，并忍受线性时间查找std::find；或者您可以使用两个容器，一个用于维护顺序，一个用于提供快速查找，并使用仔细的逻辑来保持它们的一致性。

于 2014-09-18T17:14:04.297 回答