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

## 實戰c++中的vector系列--vector的遍歷(stl算法、vector迭代器(不要在循環中判斷不等于end())、operator[]) 遍歷一個vector容器有很多種方法，使用起來也是仁者見仁。通過索引遍歷： ~~~ for (i = 0; i<v.size(); i++) { cout << v[i] << " "; } ~~~ 迭代器遍歷： ~~~ for (vInt::const_iterator iter = v.begin(); iter != v.end();iter++) { cout << *iter << " "; } ~~~ 算法遍歷： ~~~ copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); ~~~ 很多書上推薦的是使用算法進行遍歷。寫了一個簡單的程序對上面的三種方法進行了比較： ~~~ #include<iostream> #include<vector> #include<iterator> #include<algorithm> #include<time.h> #include<windows.h> using namespace std; typedef vector<int> vInt; void print_vec_operator(const vInt & v)//方法一，采用下標訪問 { int i; for (i = 0; i<v.size(); i++) { cout << v[i] << " "; } cout << endl; } void print_vec_iterator(const vInt &v)//方法二，采用迭代器訪問 { for (vInt::const_iterator iter = v.begin(); iter != v.end();iter++) { cout << *iter << " "; } cout << endl; } void print_vec_algorithm(const vInt &v)//方法三，將容器的內容復制到cout綁定的迭代器 { copy(v.begin(), v.end(), ostream_iterator<int>(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<iostream> #include<vector> #include<iterator> #include <algorithm> #include <functional> #include<windows.h> 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<void, AAA>(&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()的時候，都要進行重新構造一個迭代器并進行返回，這樣當然降低的效率。