C++ - std::set 构造函数有时效率很低？

Question

我正在尝试以下列方式构造一个集合:

    std::set<SomeType> mySet(aVector.begin(), aVector.end());

该行的性能在大多数情况下非常高效。 10% 的情况下，我会遇到运行时间过长的情况(在某些情况下超过 600 毫秒!)。为什么会这样？每次输入都非常相似( vector 大部分已排序)。有什么想法吗？

Answer 1

我看到三种可能的可能性:

1. operator<因为你的结构没有实现 strict weak ordering ，这是 std::set 正常工作所必需的。请记住，如果您的 double 值曾经是 NaN ，你打破了这个假设(在一个花了很长时间查看是否有 NaN 的集合上)。

2. 有时，您的数据没有很好地排序。尝试始终先对 vector 执行 std::sort 并查看性能是否趋于平缓——默认构造集合，然后使用带有两个参数的 std::set::insert ，第一个是要比较的元素的提示反对第一(如果你能提供一个很好的提示)。这将使您无需求助即可构建集合。如果这解决了尖峰问题，您就知道数据的初始排序是原因。

3. 您的堆分配器偶尔会执行一项操作，使其花费比正常时间长得多的时间。它可能正在拆分或连接 block 以在花费更长时间的特定 std::set() 调用上找到空闲内存。您可以尝试使用替代分配器(如果您的程序是多线程的，您可以尝试 Google's tcmalloc )。如果您有一个显示在分配器中花费的时间的分析器，则可以排除这种情况，但大多数都缺少此功能。另一种选择是 to use a boost::intrusive_set ，这将避免在将项目存储在集合中时进行分配。