为什么在std :: set上进行迭代比在std :: vector上进行迭代慢得多？

Question

在优化性能关键代码时，我注意到在std :: set上进行迭代有点慢。

然后，我编写了一个基准测试程序，并通过迭代器（auto it : vector）测试了向量的迭代速度，通过迭代器对集合进行了迭代，并通过索引（int i = 0; i < vector.size(); ++i）对向量进行了迭代。

容器的构造相同，具有1024个随机整数。（当然，由于我们正在使用集合，因此每个int都是唯一的）。然后，对于每次运行，我们循环遍历容器并将其int求和为long int。每次运行都有1000次迭代进行求和，并且对1000次运行进行了平均测试。

这是我的结果：

Testing vector by iterator
?           
Maximum duration: 0.012418
Minimum duration: 0.007971
Average duration: 0.008354

Testing vector by index
?           
Maximum duration: 0.002881
Minimum duration: 0.002094
Average duration: 0.002179

Testing set by iterator
?           
Maximum duration: 0.021862
Minimum duration: 0.014278
Average duration: 0.014971

如我们所见，通过迭代器对集合进行迭代比通过向量进行迭代慢1.79倍，而通过索引进行迭代的速度比向量慢6.87倍。

这里发生了什么？集合不仅是一种结构化的向量，可以检查每个项目在插入时是否唯一吗？为什么要这么慢？

编辑：谢谢您的答复！很好的解释。根据要求，这是基准代码。

#include <chrono>
#include <random>
#include <string>
#include <functional>
#include <set>
#include <vector>

void benchmark(const char* name, int runs, int iterations, std::function<void(int)> func) {
    printf("Testing %s\n", name);

    std::chrono::duration<double> min = std::chrono::duration<double>::max();
    std::chrono::duration<double> max = std::chrono::duration<double>::min();
    std::chrono::duration<double> run = std::chrono::duration<double>::zero();
    std::chrono::duration<double> avg = std::chrono::duration<double>::zero();

    std::chrono::high_resolution_clock::time_point t1;
    std::chrono::high_resolution_clock::time_point t2;

    // [removed] progress bar code
    for (int i = 0; i < runs; ++i) {
        t1 = std::chrono::high_resolution_clock::now();

        func(iterations);

        t2 = std::chrono::high_resolution_clock::now();

        run = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);

        // [removed] progress bar code

        if (run < min) min = run;
        if (run > max) max = run;   
        avg += run / 1000.0;
    }
    // [removed] progress bar code

    printf("Maximum duration: %f\n", max.count());
    printf("Minimum duration: %f\n", min.count());
    printf("Average duration: %f\n", avg.count());

    printf("\n");
}

int main(int argc, char const *argv[]) {
    const unsigned int arrSize = 1024;

    std::vector<int> vector; vector.reserve(arrSize);
    std::set<int> set;

    for (int i = 0; i < arrSize; ++i) {
        while (1) {
            int entry = rand() - (RAND_MAX / 2);
            auto ret = set.insert(entry);
            if (ret.second) {
                vector.push_back(entry);
                break;          
            }
        }
    }

    printf("Created vector of size %lu, set of size %lu\n", vector.size(), set.size());

    benchmark("vector by iterator", 1000, 1000, [vector](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (auto it : vector) {
                sum += it;
            }
        }
    });

    benchmark("vector by index", 1000, 1000, [vector, arrSize](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (int j = 0; j < arrSize; ++j) {
                sum += vector[j];
            }
        }
    });

    benchmark("set by iterator", 1000, 1000, [set](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (auto it : set) {
                sum += it;
            }
        }
    });

    return 0;
}

我正在使用O2发布结果，但是我试图使编译器避免优化总和。

Answer 1

集合不仅是一种结构化的向量，可以检查每个项目在插入时是否唯一吗？

不，到目前为止还没有。这些数据结构完全不同，这里的主要区别是内存布局：std::vector将其元素放入内存中的连续位置，而这std::set是基于节点的容器，其中每个元素都被单独分配并驻留在内存中的不同位置，可能彼此之间相距很远，并且肯定以某种方式无法为处理器预取数据以进行快速遍历。这是完全相反的std::vector-因为下一个元素总是恰好在当前元素“旁边”，CPU会将元素加载到其缓存中，并且在实际处理这些元素时，它只需要进入缓存即可。检索值- 与RAM访问相比非常快。

请注意，通常需要具有排序的唯一数据集，这些数据集连续地排列在内存中，并且C ++ 2a或之后的版本实际上可能附带a flat_set，请查看P1222。

Matt Austern的“为什么不应该使用set（以及应该使用什么）”也是一个有趣的读物。

Answer 2

最主要的原因是，当我们通过遍历std::vector该存储其在一个连续的内存卡盘元素，你基本上做到：

++p;

其中p是一个T*原始指针。Stl代码是：

 __normal_iterator&
 operator++() _GLIBCXX_NOEXCEPT
 {
    ++_M_current;                            // <--- std::vector<>: ++iter
    return *this;
 }

对于a std::set，底层对象更加复杂，并且在大多数实现中，您会在树状结构上进行迭代。最简单的形式是：

p=p->next_node;

p树节点结构上的指针在哪里：

struct tree_node {
   ...
   tree_node *next_node;
};

但实际上，“真实的” stl代码要复杂得多：

_Self&
operator++() _GLIBCXX_NOEXCEPT
{
    _M_node = _Rb_tree_increment(_M_node);   // <--- std::set<> ++iter
    return *this;
}

// ----- underlying code \/\/\/

static _Rb_tree_node_base*
local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
  if (__x->_M_right != 0) 
    {
      __x = __x->_M_right;
      while (__x->_M_left != 0)
        __x = __x->_M_left;
    }
  else 
    {
      _Rb_tree_node_base* __y = __x->_M_parent;
      while (__x == __y->_M_right) 
        {
          __x = __y;
          __y = __y->_M_parent;
        }
      if (__x->_M_right != __y)
        __x = __y;
    }
  return __x;
}

_Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
  return local_Rb_tree_increment(__x);
}

const _Rb_tree_node_base*
_Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
{
  return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
}

（请参阅：bits / stl_tree.h中的_Rb_tree_increment的定义是什么？）