實戰c++中的vector系列--vector的遍歷(stl算法、vector迭代器(不要在循環中判斷不等於end())、operator[])

實戰c++中的vector系列--vector的遍歷(stl算法、vector迭代器(不要在循環中判斷不等於end())、operator[])

遍歷一個vector容器有很多種方法，使用起來也是仁者見仁。

通過索引遍歷：

for (i = 0; i

迭代器遍歷：

for (vInt::const_iterator iter = v.begin(); iter != v.end();iter++)
{
    cout << *iter << " ";
}

算法遍歷：

copy(v.begin(), v.end(), ostream_iterator(cout, " "));

很多書上推薦的是使用算法進行遍歷。寫了一個簡單的程序對上面的三種方法進行了比較：

#include
#include
#include
#include
#include
#include
using namespace std;
typedef vector vInt;
void print_vec_operator(const vInt & v)//方法一，采用下標訪問
{
    int i;
    for (i = 0; i(cout, " "));
    cout << endl;
}

int main()
{
    vInt v;
    int i;
    for (i = 0; i<100000; i++)
    {
        v.push_back(i);
    }
    int start_time_print_vec1 = GetTickCount();
    print_vec_operator(v);
    int end_time_print_vec1 = GetTickCount();


    int start_time_print_vec2 = GetTickCount();
    print_vec_iterator(v);
    int end_time_print_vec2 = GetTickCount();


    int start_time_print_vec3 = GetTickCount();
    print_vec_algorithm(v);
    int end_time_print_vec3 = GetTickCount();

    std::cout << (end_time_print_vec1 - start_time_print_vec1) << endl;
    std::cout << (end_time_print_vec2 - start_time_print_vec2) << endl;
    std::cout << (end_time_print_vec3 - start_time_print_vec3) << endl;

    return 0;
}

當vector初始化10000個元素時，三種方法的效率不相上下，運行幾次時間相差無幾：
//輸出：
//1718 operator[]
//1735 iterator
//1797 algorithm

但是當把veector初始化100000的時候，三種方法的效率就有了較大的差距：
//輸出：
//20016 operator[]
//32172 iterator
//62468 algorithm

再寫一個vector裡放一個類：

#include
#include
#include
#include 
#include 
#include

class AAA
{
public:
    void MakeFull2()
    {
    }
};

int main()
{
    int nCount = 1000000;
    std::vector< AAA* > vAAA;
    vAAA.resize(nCount);
    for (int i = 0; i < nCount; ++i)
    {
        vAAA[i] = new AAA;
    }

    // 時間
    int start, end;

    // 測試成員函數調用(std::vector下標訪問方式)
    start = GetTickCount();
    size_t count = vAAA.size();
    for (size_t i = 0; i < count; ++i)
        vAAA[i]->MakeFull2();
    end = GetTickCount();
    std::cout << end - start << std::endl;


    // 測試成員函數調用(STL算法方式)
    start = GetTickCount();
    std::for_each(vAAA.begin(), vAAA.end(),
        std::mem_fun(&AAA::MakeFull2));
    end = GetTickCount();
    std::cout << end - start << std::endl;

    // 測試成員函數調用(STL迭代器方式)
    start = GetTickCount();
    std::vector< AAA* >::iterator itr_end = vAAA.end();
    for (std::vector< AAA* >::iterator itr = vAAA.begin(); itr != itr_end; ++itr)
        (*itr)->MakeFull2();
    end = GetTickCount();
    std::cout << end - start << std::endl;

    // 測試成員函數調用(STL迭代器方式)
    start = GetTickCount();
    for (std::vector< AAA* >::iterator itr = vAAA.begin(); itr != vAAA.end(); ++itr)
        (*itr)->MakeFull2();
    end = GetTickCount();
    std::cout << end - start << std::endl;
    return 0;
}
//輸出：
//313 oprator[]
//62  algorithm
//422 iterator
//922  iterator

再運行一次，結果為：
//296
//63
//594
//1672

這個時候使用algorithm+functional進行遍歷效率最高。
個人覺得下標索引的方式總是會效率高於迭代器方式。

下面分析一下兩種迭代器方式，為何相差不小呢：

這就要看一下std::vector::end()的原型了：

iterator end() _NOEXCEPT
{   // return iterator for end of mutable sequence
    return (iterator(this->_Mylast(), &this->_Get_data()));
}

就是每次判斷itr != vAAA.end()的時候，都要進行重新構造一個迭代器並進行返回，這樣當然降低的效率。