前言

上篇博客簡述了string類，實際上就是一個用來裝字符的容器，后面我會整理其他的容器，首先這篇我介紹的是向量類std::vector，在使用之前需要引入向量庫vector，

vector的理解

vector可以看做一個可以按照需要自動增長和縮短的動態陣列
內部機理
實際上，vector內部就是用陣列存盤地址的，我們知道陣列是需要在創建的時候指定大小，但是std::vector不需要，這里有一個概念，我們把內部陣列能夠存放元素的最大數量稱為容器容量(capacity)，實際元素數量(size)超過容量時，就需要繼續申請擴充容量，然而陣列無法在末尾直接增加記憶體的，所以我們需要申請一塊更大的連續記憶體，并把舊記憶體的資料復制到新記憶體里面，這個復制操作的時間復雜度很明顯就是O(n),隨后舊記憶體被釋放，
值得注意的是
擴容時一般會申請適量多的記憶體
利：以一定記憶體來換取大幅度提高插入元素時的速度
原因：
當容量大于元素數量時：
插入1個新元素的時間復雜度為O( 1 ),
插入n個新元素的時間復雜度為O（n），
當容量小于元素數量時：
插入1個新元素的時間復雜度為O( n ),
插入n個新元素的時間復雜度為O（n*n），
但是還有一種容器既不會浪費記憶體也可以快速插入就是list

vector的成員型別

由于vector是一個后來人們撰寫的類，所以具體的內部代碼主要由寫庫的人決定(如擴充容量的多少)，不過C++是有標準的（為了達到每個人寫的代碼可以進行交流），只要按照標準寫代碼庫，這些新宣告與定義的型別都可以找到底層型別，例如size_type的底層代碼通常是size_t（C++標準中的無符號的整數型別），

在使用上，完整的vector型別： std:vecter<存放的元素的型別>
在使用上，完整的成員型別:std:vecter<存放的元素的型別>：上面的成員型別

vector的創建

1.vector<資料型別> v;//<>尖括號是用來指定容器存放的元素的資料型別，也就是說容器只能存放一種資料型別
例：vector<int>v；

2.vectorc資料型別> v(size_type count);//
例：vector<int> v(50);

3.vector<資料型別> v(size_type count，資料的型別value);
例：vector<int> v(10，1);
4.vector<資料型別>v(任意型別的輸入迭代器 first，任意型別的輸入送代器 last)
例：string str=“woaini”;
.vector<char>v(str.begin()，str.end();

創建時間復雜度

1. O(1)
2. O(n)（與 count 成線性）
3. O(n)（與 count 成線性）
4. 4.O(n)（與 first 到 last 的距離成線性）

vector的迭代器

時間復雜度:O(1)
1 vector<int>::iterator it=v.begin();
2. vector<int>::const_iterator const it =v.begin();
3. vector<int>::reverse_iterator rbegin();
4. vector<int>::const_reverse_iterator const rbegin();

vector的容量

1 bool flag=v.empty();// 判斷容器是否為空O(1)
2.size_type size=size() ; //回傳容器中的元素數量O(1),內部實作`

std::distance(begin(),end())//了解更多推薦看候捷的《STL原始碼剖析》

3.size_type capacity=capacity() ; 獲取容器的容量O(1),擴充多少不確定，
4.void reserve(size_type n); 預留容量(與容器的size()成線性)

 vector<int> v;
 v.reserve(1);
 v.phsh_back(1);//直接插入而不需要擴容

**如果 n<=capacity()，則函式沒有操作;
如果 n>capacity()，則容器重新分配記憶體,來擴充容量，
注意：
重新分配記憶體后，由于記憶體地址已經發生了改變，這就導致了之前保存下來的這個容器的所有迭代器全部都會失效，不能再使用，如果需要使用迭代器的話，就必須重新通過成員函式begin()和end()獲取，
時間復雜度
1-3.O(1);
4.與容器的size()成線性

vector元素訪問

時間復雜度都是O(1)
1.中括號[]//獲取相應位置的參考
例：v[3]=222;
2.reference at(size_type pos);//同上，但是會判斷是否越界
例：v.at(3)=666;
3.reference front(); 獲取容器第1個元素的參考
例：cout<<v.front()<<endl;
4.reference back(); 獲取容器最后1個元素的參考
例：cout<<v.back()<<endl;
5.int* data(); 獲取容器底層陣列的首地址
例：int*p=data();
合法范圍：[data(),data()+size()]

vector的元素修改

void push_back(const value_type & value);
例：v.push_back(222);
時間復雜度：雖然有可能出現時間復雜度O()的擴容操作，但是由于時間均攤給每一步，時間復雜度還是O(1)
void pop_back();
例：v.pop_back();
注意：
1.first和last不能是物件自身的迭代器，否則是未定義行為
2. 如果新的 size()大于舊的 capacity()，則該容器物件所有迭代器和參考都會失效,在插入新元素后，由于原來插入位置的元素及其后面的元素移位，導致原來插入位置及其后面的迭代器和參考全部失效，
iterator insert(iterator pos. const value_type & value);//在pos前一位插入value
void insert(iterator pos. size_type count, const value_type & value);//在pos前插入count個value
void insert(iterator pos.任意型別的輸入送代器first任意型別的輸入迭代器 last);//插入指定迭代器first到last之間的元素
iterator erase(iterator pos);
例：

string str ="happynewyear"
vector<char> v(str.begin(),str.end());
v.erase(v.begin()+5);

iterator erase(iterator first, iterator last);

v.erase(v.begin()+1,v.begin()+3);//洗掉2，3, 4

void clear();//清空容器，容器容量不變；
例v.clear();
void resize(size_type count);//定義容量
例：v.size(5)；
void resize(size_type count, const value_type & value);//定義容量
例：resize(5,666)；
如果當前大小大于count，則減少到count個元素如果當前大小小于count
則：
1 后附額外的默認插入的元素
2. 后附額外的 value 的副本時間復雜度O(n)，與元素的數量成線性

◆◆◆◆◆◆◆◆◆◆◆◆◆◆感謝您對這篇文章的閱讀，感恩一見三連哦~?◆◆◆◆◆◆◆◆◆◆◆◆◆◆