用vector :: iterator或at()迭代STL矢量,哪个速度会更快? - 小众知识

用vector :: iterator或at()迭代STL矢量,哪个速度会更快?

2013年01月27日 14:18:05 苏内容
  标签: vector/速度
阅读:649

就性能而言,什么工作更快?有什么不同吗?它依赖于平台吗?

//1. Using vector<string>::iterator:vector<string> vs = GetVector();for(vector<string>::iterator it = vs.begin(); it != vs.end(); ++it){
   *it = "Am I faster?";}//2. Using size_t index:for(size_t i = 0; i < vs.size(); ++i){
   //One option:
   vs.at(i) = "Am I faster?";
   //Another option:
   vs[i] = "Am I faster?";}

为什么不写一个测试并找出答案?

#include <vector>#include <iostream>#include <ctime>using namespace std;int main() {
    const int BIG = 20000000;
    vector <int> v;
    for ( int i = 0; i < BIG; i++ ) {
        v.push_back( i );
    }

    int now = time(0);
    cout << "start" << endl;
    int n = 0;
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        n += *it;
    }

    cout << time(0) - now << endl;
    now = time(0);
    for(size_t i = 0; i < v.size(); ++i) {
        n += v[i];
    }
    cout << time(0) - now << endl;

    return n != 0;}

使用迭代器会导致递增指针。 使用索引时,递增应该同样快,但查找元素需要添加(数据指针+索引)并取消指向该指针,但差异应该是非常小的。 at()还检查索引是否在边界内,因此可能会变慢。

基准测试结果为500M迭代,向量大小为10,使用gcc 4.3.3(-O3),linux 2.6.29.1 x86_64 

  at() :9158ms 

  operator[]:4269ms

  iterator:3914ms



vector和iterator及collection

Collection是所有集合的最上层接口,它里面定义了所有集合对象都可以进行的操作;它有两个子接口,分别是List和Set。List会记录放在其中元素的放入顺序,形象地说,可以认为是一个传送带,它上面所有的东西都有一个放置顺序。而Set要求放置在其中的元素必须不能重复,它与数学上集合的概念完全一致。

Iterator又称迭带器,能对Collection进行顺序遍历。

Vector是List接口的一个具体实现,支持列表元素的顺序访问,大小可以随着元素的增加二而增加,同时是线程安全的。也正为要求线程安全,所以访问的性能比较差。自Java1.2以后,已经不推荐使用。Java1.2推荐使用ArrayList和LinkedList。他们都不是线程安全的,所以性能较好。其中ArrayList随机访问速度快,而LinkedList在表中间 插入的速度快。

 

vector对象的定义和初始化

vector类定义了好几种构造函数,用来定义和初始化vector对象。

vector<T> v1;

vector保存类型为T的对象。默认构造函数v1为空。

vector<T> v2(v1);

v2是v1的一个副本。

vector<T> v3(n, i);

v3包含n个值为i的元素。

vector<T> v4(n);

v4含有值初始化的元素的n个副本。

vector的操作

vector标准库提供许多类似于string对象的操作,下表列出了几种最重要的vector操作。

v.empty()

如果v为空,则返回true,否则返回false。

v.size()

返回v中元素的个数。

v.push_back(t)

在v的末尾增加一个值为t的元素。

v[n]

返回v中位置为n的元素。

v1 = v2

把v1的元素替换为v2中元素的副本。

v1 == v2

如果v1与v2相等,则返回true。

!=, <, <=, >, >=

保持这些操作符惯有的含义。

向vector添加元素

push_back()操作接受一个元素值,并将它作为一个新的元素添加到vector对象的后面,也就是“插入(push)”到vector对象的“后面(back)”:

vector迭代器

除了使用下标来访问vector对象的元素外,标准库还提供了另一种检测元素的方法:使用迭代器(iterator)。迭代器是一种允许程序员检查容器内元素,并实现元素遍历的数据类型。

标准库为每一种标准容器(包括vector)定义了一种迭代器类型。迭代器类型提供了比下标操作更一般化的方法:所有的标准库容器都定义了相应的迭代器类型,而只有少数的容器支持下标操作。因为迭代器对所有的容器都适用,现代C++程序更倾向于使用迭代器而不是下标操作访问容器元素,即使对支持下标操作的vector类型也这样。 容器的iterator类型

每种容器类型都定义了自己的迭代器类型,如vector:

vector<int>::iterator iter;

这条语句定义了一个名为iter的变量,它的数据类型是由vector<int>定义的iterator类型。每个标准库容器类型都定义了一个名为iterator的成员,这里的iterator与迭代器实际类型的含义相同。

不同的容器类定义了自己的iterator类型,用于访问容器内的元素。换句话说,每个容器定义了一种名为iterator的类型,而这种类型支持(概念上的)迭代器的各种行为。

begin和end操作

每种容器都定义了一对命名为begin和end的函数,用于返回迭代器。如果容器中有元素的话,由begin返回的迭代器指向第一个元素:

vector<int>::iterator iter = ivec.begin();

上述语句把iter初始化为由名为begin的vector操作返回的值。假设vector不空,初始化后,iter即指该元素为ivec[0]。

由end操作返回的迭代器指向vector的“末端元素的下一个”。通常称为超出末端迭代器(off-the-end iterator),表明它指向了一个不存在的元素。如果vector为空,begin返回的迭代器与end返回的迭代器相同。

由end操作返回的迭代器并不指向vector中任何实际的元素,相反,它只是起一个哨兵(sentinel)的作用,表示我们已处理完vector中所有元素。

vector迭代器的自增和解引用运算

迭代器类型定义了一些操作来获取迭代器所指向的元素,并允许程序员将迭代器从一个元素移动到另一个元素。

迭代器类型可使用解引用操作符(*操作符)来访问迭代器所指向r 元素:

*iter = 0;

解引用操作符返回迭代器当前所指向的元素。假设iter指向vector对象ivec的第一个元素,那么*iter和ivec[0]就是指向同一个元素。上面这个语句的效果就是把这个元素的值赋为0。

迭代器使用自增操作符向前移动迭代器指向容器中下一个元素。从逻辑上说,迭代器的自增操作和int型对象的自增操作类似。对int对象来说,操作结果就是把int型值“加1”,而对迭代器对象则是把容器中的迭代器“向前移动一个位置”。因此,如果iter指向第一个元素,则++iter指向第二个元素。

由于end操作返回的迭代器不指向任何元素,因此不能对它进行解引用或自增操作。


扩展阅读
© CopyRight 2010-2021, PREDREAM.ORG, Inc.All Rights Reserved. 京ICP备13045924号-1