1. vector的特點
內存特點： 內存空間連續(xù)爬橡，隨機訪問效率高莉擒。
插入刪除：插入或者刪除某個元素，需要將現有元素進行復制恋博，移動齐佳。
如果vector中存儲的對象很大，或者構造函數復雜交播，則在對現有元素進行拷貝時開銷較大重虑，因為拷貝對象要調用拷貝構造函數。對于簡單的小對象秦士，vector的效率優(yōu)于list缺厉。vector在每次擴張容量的時候，將容量擴展2倍隧土，這樣對于小對象來說提针，效率是很高的。
應用場景：vector適用于對象數量少曹傀，簡單對象辐脖，隨機訪問元素頻繁。支持高效的隨機訪問和尾端插入皆愉、刪除操作嗜价，其它位置的插入、刪除效率低下幕庐。
2. list
內存特點：內存空間不連續(xù)久锥，依靠指針來連接。具有雙鏈表結構异剥，每個元素維護一個前向和后向指針瑟由，因此支持前向、后向遍歷冤寿。
插入刪除：支持高效的隨機插入歹苦、刪除操作，但隨機訪問效率低下督怜，且需要額外維護指針殴瘦，開銷也較大。
應用場景： list適用于對象數量變化大亮蛔，對象復雜痴施，插入和刪除頻繁。
3. deque
內存特點：內存空間連續(xù)，與vector類似辣吃，不同之處在于deque提供了兩級數據結構动遭，
- 第一級完全類似于vector，代表實際容器
- 另一級維護容器的首位地址神得。
插入刪除：支持高效的首端 尾端 插入/ 刪除操作厘惦。其它位置的插入、刪除效率低下哩簿。
4. vector宵蕉、list、deque比較
- 隨機訪問操作节榜，選擇vector
- 若已知存儲元素size羡玛，選擇vector
- 需要隨機 插入 刪除，（不僅僅在兩端）宗苍，選擇list
- 只有需要在首端進行插入稼稿、刪除操作的時候，才選擇deque讳窟，否則選擇vector
- 若既需要隨機插入让歼、刪除，又需要隨機訪問丽啡，則需要在vector和list之間做折中谋右。
- 當要存儲的是大型的數據類對象時，list要優(yōu)于vector补箍。
（也可以使用vector來存儲指向對象的指針改执，同樣會取得較高的效率，但是指針的維護容易出錯坑雅，不推薦）
5. capacity vs size
- capacity是容器需要增長之前天梧，能夠盛的元素總數；只有連續(xù)存儲的容器才有capacity的概念（例如vector霞丧，deque，string）冕香，list不需要capacity蛹尝。
- size是容器當前存儲的元素的數目。
- vector默認的容量初始值悉尾，以及增長規(guī)則是依賴于編譯器的突那。
6. 用vector存儲自定義類對象時，自定義類對象須滿足：
- 有可供調用的無參構造函數
- 有可用的拷貝賦值函數
7. 迭代器 iterator
- vector與deque的迭代器支持算術運算
- list的迭代器只能進行++/--操作构眯，不支持普通的算數運算愕难。
vector 詳細介紹
1. vector剖析：
vector 的數據安排以及操作方式，與 array 非常像似。兩者的唯一差別在于空間的運用彈性猫缭。
- array是靜態(tài)空間
- vector 是動態(tài)空間葱弟，隨著元素的加入，它的內部機制會自行擴充空間以容納新元素猜丹。
因此芝加，vector 的運用對于內存的樽節(jié)與運用彈性有很大的幫助，我們再也不必因為害怕空間不足而一開始就要求一個大塊頭 array 了射窒，我們可以安心使用vector藏杖，吃多少用多少。
vector 的使用技術脉顿，關鍵在于其對大小的控制以及重新配置時的數據搬移效率蝌麸。
一旦 vector 舊有空間滿載，如果客端每新增一個元素艾疟，vector 內部只是擴充元素的空間来吩，實為不智，因為所謂擴充空間（不論多大）汉柒，在創(chuàng)建一個vector 后误褪，它會自動在內存中分配一塊連續(xù)的內存空間進行數據存儲，初始的空間大小可以預先指定也可以由vector 默認指定碾褂，這個大小即capacity （）函數的返回值兽间。當存儲的數據超過分配的空間時vector 會重新分配一塊內存塊，但這樣的分配是很耗時的正塌，在重新分配空間時它會做這樣的動作：
首先嘀略，vector 會申請一塊更大的內存塊；(2的指數級增長)
然后乓诽，將原來的數據拷貝到新的內存塊中帜羊；
其次，銷毀掉原內存塊中的對象（調用對象的析構函數）鸠天；
最后讼育，將原來的內存空間釋放掉。
2. vector 的特點：
指定一塊如同數組一樣的連續(xù)存儲稠集，但空間可以動態(tài)擴展奶段。即它可以像數組一樣操作，并且可以進行動態(tài)操作剥纷。通常體現在push_back()pop_back() 痹籍。
隨機訪問方便，它像數組一樣被訪問晦鞋，即支持[ ] 操作符和vector.at()
節(jié)省空間蹲缠，因為它是連續(xù)存儲棺克，在存儲數據的區(qū)域都是沒有被浪費的，但是要明確一點vector 大多情況下并不是滿存的线定，在未存儲的區(qū)域實際是浪費的娜谊。
在內部進行插入、刪除操作效率非常低渔肩，這樣的操作基本上是被禁止的因俐。Vector 被設計成只能在后端進行追加和刪除操作，其原因是vector 內部的實現是按照順序表的原理周偎。
只能在vector 的最后進行push 和pop 抹剩，不能在vector 的頭進行push 和pop 。
當動態(tài)添加的數據超過vector 默認分配的大小時要進行內存的重新分配蓉坎、拷貝與釋放澳眷，這個操作非常消耗性能。 所以要vector 達到最優(yōu)的性能蛉艾，最好在創(chuàng)建vector 時就指定其空間大小钳踊。
Vectors 包含著一系列連續(xù)存儲的元素,其行為和數組類似。訪問Vector中的任意元素或從末尾添加元素都可以在常量級時間復雜度內完成勿侯，而查找特定值的元素所處的位置或是在Vector中插入元素則是線性時間復雜度
3 vector的函數
- 1.Constructors 構造函數
vector<int> v1; //構造一個空的vector
vector<int> v1( 5, 42 ); //構造了一個包含5個值為42的元素的Vector
3.2.Operators 對vector進行賦值或比較
C++ Vectors能夠使用標準運算符: ==, !=, <=, >=,<, 和 >.
要訪問vector中的某特定位置的元素可以使用 [] 操作符.
兩個vectors被認為是相等的,如果:
- 1.它們具有相同的容量
- 2.所有相同位置的元素相等.
vectors之間大小的比較是按照詞典規(guī)則.
- 3.assign() 對Vector中的元素賦值
語法：
void assign( input_iterator start, input_iterator end );
// 將區(qū)間[start, end)的元素賦到當前vector
void assign( size_type num, const TYPE &val );
// 賦num個值為val的元素到vector中,這個函數將會清除掉為vector賦值以前的內容.
4.at() 返回指定位置的元素
語法：
TYPE at( size_type loc );//差不多等同v[i];但比v[i]安全;,到后邊有例子說明
5.back() 返回最末一個元素
6.begin() 返回第一個元素的迭代器
7.capacity() 返回vector所能容納的元素數量(在不重新分配內存的情況下）
8.clear() 清空所有元素
9.empty() 判斷Vector是否為空（返回true時為空）
10.end() 返回最末元素的迭代器(譯注:實指向最末元素的下一個位置)
11.erase() 刪除指定元素
語法：
iterator erase( iterator loc );//刪除loc處的元素
iterator erase( iterator start, iterator end );//刪除start和end之間的元素
那好,既然刪除了元素,那我們來看看他的空間是不是也縮小了或者他的大小
void main( )
{
vector<int> vec1;
vec1.push_back(1);
vec1.push_back(2);
vec1.push_back(3);
cout<<vec1.capacity()<<","<<vec1.size()<<endl;
vec1.erase(vec1.begin());
cout<<vec1.capacity()<<","<<vec1.size()<<endl;
vec1.erase(vec1.begin());
cout<<vec1.capacity()<<","<<vec1.size()<<endl;
cout<<vec1[2];//在這里我們應該看到了拓瞪，如果用vec1.at(2)訪問肯定是非法的數據
}
從這個簡單的例子說明了一個問題，在erase刪除元素的時候助琐，并不會回收capacity容量的大小的祭埂，只是將元素向前移位，并且修改了size的大小兵钮，并不是真正意義上的刪除蛆橡，另外為了安全的訪問最好使用at()函數而不是下標訪問。
12.front() 返回第一個元素的引用
13.get_allocator() 返回vector的內存分配器
14.insert() 插入元素到Vector中
語法：
iterator insert( iterator loc, const TYPE &val );
//在指定位置loc前插入值為val的元素,返回指向這個元素的迭代器,
void insert( iterator loc, size_type num, const TYPE &val );
//在指定位置loc前插入num個值為val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
//在指定位置loc前插入區(qū)間[start, end)的所有元素
15.max_size() 返回Vector所能容納元素的最大數量（上限）
16.pop_back() 移除最后一個元素
17.push_back() 在Vector最后添加一個元素
18.rbegin() 返回Vector尾部的逆迭代器
19.rend() 返回Vector起始的逆迭代器
20.reserve() 設置Vector最小的元素容納數量
補充說明：
-
1. 內存管理效率
四個內存相關函數：
size()：容器中實際容納了多少元素
告訴你容器中有多少元素掘譬。它沒有告訴你容器為它容納的元素分配了多少內存泰演。capacity()：容器最大可容納的元素，如果超過此值葱轩，需要重新動態(tài)分配一塊1.5至2倍大小的內存睦焕，將現有元素賦值過去，然后銷毀之前的內存靴拱。
告訴你容器在它已經分配的內存中可以容納多少元素复亏。那是容器在那塊內存中總共可以容納多少元素，而不是還可以容納多少元素缭嫡。如果你想知道一個vector或string中有多少沒有被占用的內存，你必須從capacity()中減去size()抬闷。如果size和capacity返回同樣的值妇蛀，容器中就沒有剩余空間了耕突，而下一次插入（通過insert或push_back等）會引發(fā)上面的重新分配步驟。resize(): 強制容器容納N個元素
強制把容器改為容納n個元素评架。調用resize之后眷茁，size將會返回n。如果n小于當前大小纵诞，容器尾部的元素會被銷毀上祈。如果n大于當前大小，新默認構造的元素會添加到容器尾部浙芙。如果n大于當前容量登刺，在元素加入之前會發(fā)生重新分配。reserve(): 強制將容量改為N
強制容器把它的容量改為至少n嗡呼，提供的n不小于當前大小纸俭。這一般強迫進行一次重新分配，因為容量需要增加南窗。（如果n小于當前容量揍很，vector忽略它，這個調用什么都不做万伤，string可能把它的容量減少為size()和n中大的數窒悔，但string的大小沒有改變。在我的經驗中敌买，使用reserve來從一個string中修整多余容量一般不如使用“交換技巧”简珠，那是條款17的主題。）
增加效率的方法：
- 使用reserve()函數提前設定容量大小放妈，避免多次容量擴充操作導致效率低下北救。
說明：在通過 reserve() 來申請?zhí)囟ù笮〉臅r候總是按指數邊界來增大其內部緩沖區(qū)。當進行insert或push_back等增加元素的操作時芜抒，如果此時動態(tài)數組的內存不夠用珍策，就要動態(tài)的重新分配當前大小的1.5~2倍的新內存區(qū)，再把原數組的內容復制過去宅倒。所以攘宙，在一般情況下，其訪問速度同一般數組拐迁，只有在重新分配發(fā)生時蹭劈，其性能才會下降。
vector v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i)
v.push_back(i);
- 使用“交換技巧”來修整vector過氏哒伲空間/內存
vector(ivec).swap(ivec);
有一種方法來把它從曾經最大的容量減少到它現在需要的容量铺韧。
- 使用swap方法強行釋放STL vector 所占內存
template < class T>
void ClearVector( vector& v )
{
vector vtTemp;
vtTemp.swap( v );
}
//如
vector v ;
nums.push_back(1);
nums.push_back(3);
nums.push_back(2);
nums.push_back(4);
vector().swap(v);
/* 或者v.swap(vector()); */
/*或者{ std::vector tmp = v; v.swap(tmp); }; //加大括號{ }是讓tmp退出{ }時自動析構*/
