通过迭代器和运算符[]/index快速访问std :: vector？

Question

说,我有一个

std::vector<SomeClass *> v;

在我的代码中,我需要经常在程序中访问它的元素,向前和向后循环它们.

这两者之间的访问类型最快？

迭代器访问:

std::vector<SomeClass *> v;
std::vector<SomeClass *>::iterator i;
std::vector<SomeClass *>::reverse_iterator j;

// i loops forward, j loops backward
for( i = v.begin(), j = v.rbegin(); i != v.end() && j != v.rend(); i++, j++ ){
    // some operations on v items
}

下标访问(按索引)

std::vector<SomeClass *> v;
unsigned int i, j, size = v.size();

// i loops forward, j loops backward
for( i = 0, j = size - 1; i < size && j >= 0; i++, j-- ){
    // some operations on v items
}

而且,如果我不需要修改它们,const_iterator是否提供了访问向量元素的更快方法？

Answer 1

性能差异可能是可忽略的或没有(编译器可能将它们优化为相同); 你应该担心其他事情,比如你的程序是否正确(一个缓慢但正确的程序比快速和错误的程序更好).使用迭代器还有其他优点,例如能够将底层容器更改为一个operator[]而不需要修改循环.有关更多信息,请参阅此问

与普通迭代器相比,const_iterators很可能没有或可忽略的性能差异.它们旨在通过防止修改不应修改的内容而不是性能来提高程序的正确性.const一般来说,关键字也是如此.

简而言之,在发生两件事情之前,优化不应该是您的关注:1)您注意到它运行得太慢而且2)您已经描述了瓶颈.对于1),如果它比它运行慢十倍,但只运行一次并需要0.1ms,谁在乎呢？对于2),确保它绝对是瓶颈,否则优化它将对性能几乎没有可衡量的影响!

Answer 2

已经实现了一个简单的基于循环的基准测试.我使用VS 2010 SP1(发布配置).

1. 使用迭代器(*it =*it + 1;)
2. 使用指数(vs [i] = vs [i] + 1;)

在几十亿次迭代中,第二种方法变得更快,增加了1%.结果(索引比迭代器略快)是可重现的,但正如我所说,差异非常小.

Answer 3

如果速度很重要,那么你应该有时间并且会在其上运行一个分析器,看看哪种情况最适合你的情况.

如果没关系,那么你正在进行过早优化,应该停止这样做.

Answer 4

我昨天做了一个测试，使用 [] vs 迭代器，代码是创建一个包含一些元素的向量并从向量中删除一些元素。这是使用运算符 [] 访问元素的代码

  TimeSpent([](){
    std::vector<int> vt = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    for (int i = int(vt.size()) - 1; i >= 0; i--)
    {
      if (vt[i] % 2 == 0)
      {
        //cout << "removing " << vt[i] << endl;
        vt.erase(vt.begin() + i);
      }
    }
  });

以下代码是关于使用迭代器访问向量元素

  TimeSpent([](){
    std::vector<int> vt = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    for (std::vector<int>::iterator num = vt.begin(); num != vt.end();)
    {
      if (*num % 2 == 0)
      {
        num = vt.erase(num);
      }
      else
      {
        ++num;
      }
    }
  });

通过此函数分别调用它们进行测试

void TimeSpent(std::function<void()> func)
{
  const int ONE_MIL = 10000;
  long times = ONE_MIL;
  std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
  while (times > 0)
  {
    func();
    --times;
  }
  std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
  cout << "time elapsed : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << endl;
}

测试环境是visual studio 2013 pro。version 4.5.51650
结果是：
operator[] : 192
iterator : 212
总结：当我们访问vector容器时，operator[]比iterator快。