本文原創(chuàng)發(fā)表地址為：http://www.shnenglu.com/kusamba/archive/2010/09/16/126786.html，轉(zhuǎn)載請(qǐng)保留原鏈接，謝謝！
std::vector作為順序容器，具有如下特點(diǎn)：
/************************************************************************* vector* 1, 順序存儲(chǔ)，內(nèi)部數(shù)據(jù)結(jié)構(gòu)為數(shù)組* 2, 使用之前調(diào)用reserve()預(yù)分配元素?cái)?shù)目，可提高性能* 3, insert/erase操作效率低，跟被操作元素在vector中的位置成正比* 在末尾增加或刪除元素所需時(shí)間與元素?cái)?shù)目無(wú)關(guān)，* 在中間或開頭增加或刪除元素所需時(shí)間隨元素?cái)?shù)目呈線性變化* 4, insert/erase操作將有可能導(dǎo)致vector內(nèi)存重新分配，iterator失效* 5, 時(shí)間復(fù)雜度：* 隨機(jī)索引訪問[index]: O(1)* 查找：O(n)* by Kusamba@126.com http://www.shnenglu.com/kusamba*/技術(shù)要點(diǎn)：
1，加載頭文件
#include <vector>
using namespace std;
2，預(yù)分配內(nèi)存, 調(diào)用reserve函數(shù)
3, 插入對(duì)象，使用push_back或[index]
4, insert/erase 如何避免iterator失效
代碼如下：
1 /************************************************************************
2 * vector
3 * 1, 順序存儲(chǔ)，內(nèi)部數(shù)據(jù)結(jié)構(gòu)為數(shù)組
4 * 2, 使用之前調(diào)用reserve()預(yù)分配元素?cái)?shù)目，可提高性能
5 * 3, insert/erase操作效率低，跟被操作元素在vector中的位置成正比
6 * 在末尾增加或刪除元素所需時(shí)間與元素?cái)?shù)目無(wú)關(guān)，
7 * 在中間或開頭增加或刪除元素所需時(shí)間隨元素?cái)?shù)目呈線性變化
8 * 4, insert/erase操作將有可能導(dǎo)致vector內(nèi)存重新分配，iterator失效
9 * 5, 時(shí)間復(fù)雜度：
10 * 隨機(jī)索引訪問[index]: O(1)
11 * 查找：O(n)
12 */
13
14 /**
15 * 謂詞表達(dá)式
16 */
17 struct sComplexObj
18 {
19 int nID;
20 char szNickName[32];
21 };
22 bool Equal_ID(sComplexObj obj)
23 {
24 return obj.nID == 4 ? true : false;
25 }
26
27 /**
28 * 測(cè)試代碼
29 */
30 void vector_test()
31 {
32 vector<int> vInt;
33
34 /**
35 * reserve : 預(yù)分配空間
36 * capacity: 獲取預(yù)分配空間數(shù)目
37 * size : 當(dāng)前元素個(gè)數(shù)
38 */
39 int nCapacity = 0, nSize = 0;
40 nCapacity = vInt.capacity();
41
42 vInt.reserve(10);
43 nSize = vInt.size();
44
45 /**
46 * insert
47 */
48 for (int i = 0; i < 10; ++i)
49 {
50 vInt.push_back(i + 1);
51 }
52 for (int i = 0; i < 10; ++i)
53 {
54 vInt[i] = vInt[i] * 2;
55 }
56
57 // insert: 在4倍數(shù)元素的后面插入一個(gè)元素，值為該元素的2倍
58
59 // 錯(cuò)誤的做法
60 ////for (vector<int>::iterator it = vInt.begin(); it != vInt.end(); ++it)
61 ////{
62 //// if (*it % 4 == 0)
63 //// {
64 //// vInt.insert(it, *it * 2);-->it失效
65 //// //重新分配了空間，it和begin(), end()均失效
66 //// }
67 ////}
68
69 // 利用計(jì)數(shù)插入
70 for (int i = 0; i < vInt.size(); ++i)
71 {
72 if (vInt[i] % 4 == 0)
73 {
74 vInt.insert(vInt.begin() + i + 1, vInt[i] * 2);
75 i += 1;
76 }
77 }
78 // 利用iterator以及insert返回的被插入元素的位置
79 for (vector<int>::iterator it = vInt.begin(); it != vInt.end(); ++it)
80 {
81 if (*it % 3 == 0)
82 {
83 it = vInt.insert(it + 1, *it * 2);//獲取當(dāng)前插入元素的位置
84 }
85 }
86
87 /**
88 * erase
89 */
90 for (vector<int>::iterator it = vInt.begin(); it != vInt.end(); )
91 {
92 if (*it % 2 == 0)
93 {
94 it = vInt.erase(it);//返回end()或后一個(gè)元素的新位置
95 }
96 else
97 {
98 ++it;
99 }
100 }
101
102 //使用謂詞 只能刪除一次
103 vInt.erase(remove(vInt.begin(), vInt.end(), 4));
104
105 //對(duì)于復(fù)雜對(duì)象，還可以使用remove_if算法
106 {
107 vector<sComplexObj> vComplexObj;
108 for (int i = 0; i < 10; ++i)
109 {
110 sComplexObj obj;
111 obj.nID = i;
112 sprintf_s(obj.szNickName, "ID_%06d", i);
113 vComplexObj.push_back(obj);
114 }
115 vComplexObj.erase(remove_if(vComplexObj.begin(), vComplexObj.end(), Equal_ID));
116 }
117
118 /**
119 * traverse
120 */
121 printf("print vInt method1: ");
122 for (int i = 0; i < vInt.size(); ++i)
123 {
124 printf("%d ", vInt[i]);
125 }
126 printf("\n");
127
128 printf("print vInt method2: ");
129 for (vector<int>::iterator it = vInt.begin(); it != vInt.end(); ++it)
130 {
131 printf("%d ", *it);
132 }
133 printf("\n");
134 }