vector的介紹

1.vector是可變大小數組的容器

2.像數組一樣，采用連續的空間存儲，也就意味著可以通過下標去訪問，但它的大小可以動態改變

3.每次的插入都要開空間嗎？開空間就要意味著先開臨時空間，然后在拷貝舊的到新的上面，在釋放原來的，就時間而言，這是一個相對代價很高的任務；顯然這是不行的，vector的分配策略：會分配一些而外的空間以適應可能的增長，例如我們平時說的以1.5或者2倍的方式增容，不同的庫選擇不同的策略權衡空間的使用和重新分配，以至于在插入一個元素時能在常數時間內插入；

vector的使用

構造函數：

?

注意：這里的allocator_type是空間配置器，與內存池相關，可以暫時忽略

? ? ? ? ? 這里的vector<int>要傳模板，指明你每個元素里面存的類型是什么?

第一個能構造一個空的vector數組

第二個能構造4個元素，每個元素里面存100的數組

第三個傳迭代器能根據迭代器構造出一個對象

第四個是拷貝構造函數?

如果第二個中我沒有指定每個元素為100，它會根據你傳的模板是什么初始化為啥，例如你傳int就初始化為0

3種遍歷方式

1.operator[]

因為底層是數組，所以重載了operator[]方便遍歷

for(size_t i=0;i<vt.size();i++)
{cout<<vt[i]<<" ";
}

2.迭代器遍歷

?

?可以看到vector容器提供了begin/end和rbegin/rend，這說明我們可以正反向遍歷?

vector<int>::iterator it=vt.begin();
while(it!=vt.end())
{cout<<*it;it++;
}vector<int>::reverse_iterator rit=rbegin();
while(it!=rbegin())
{cout<<*it;it++;
}

3.返回for遍歷：底層就是迭代器，只要能實現迭代器就能實現范圍for

for(auto&e:vt)
{cout<<e;
}

注意：如果你有一個函數，例如打印函數，你是不想修改數組里面元素的值，那傳參時需要傳const修飾的數組，此時你在打印函數中使用迭代器，只能用const迭代器?

迭代器分兩個版本，一個是const迭代器一個是普通迭代器

void Print(const vector<int>&vt)
{vector<int>::const_iterator it=vt.begin();while(it!=vt.end())
{
cout<<*it;
*it+=1;//這句是錯的，你傳了const就意味著你不能通過迭代器去修改
}
}

?capacity函數接口

size()：顧名思義就是返回數組的大小，這里的大小是有效元素的大小

capacity():是返回這里數組的容量，也就是你動態開辟出來的大小

empty():判斷是否為空；如果沒有元素即返回true，有就返回false

resize():改變數組的size

reserve()：改變數組的容量，如果提前知道空間可以減少增容的代價

注意：vs2022是以1.5倍增長，gcc是以兩倍增長，兩個用的STL版本不一樣，vs使用PJ版本，gcc是用SGI版本

Modifiers函數接口

數組當然實現的是尾插和尾刪，效率高，如果你有頭插和頭刪最好別選vector（后面會介紹list和vector的優缺點）

push_back()：尾插一個數據

pop_back():尾刪一個數據

insert():任意位置的插入，在pos位置之前插入

注意：這里傳迭代器?

erase():任意位置的刪除，刪除pos位置的元素，返回下一個元素的迭代器

注意：這里我們不知道要刪除的元素的位置該如何找到呢？vector沒有實現find

可以調用<algorithm>庫實現的find

找到返回pos位置的迭代器，找不到返回end();

?swap():交換兩個vector的數據空間

clear():清空元素，但開辟的空間沒有釋放

?重點談迭代器失效問題

迭代器的主要作用是讓算法不用關系底層數據結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態指針T*。因此，迭代器失效，實際就是迭代器底層對應的指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果就是程序崩潰（即如果繼續使用已經失效的迭代器，程序可能會崩潰）

第一種情況：

如果你先定義了迭代器vector<int>::iterator it=vt.begin();

然后在進行各種擴容操作reserve，resize，insert，assign，push_back等

然后在使用迭代器，那原來的指針it指向的的那塊空間已經被釋放了，因為你進行了擴容開辟了新空間，你在使用迭代器去解引用或者it！=vt.end()等操作都可能會造成程序崩潰

第二種情況：

比如你使用庫實現的find去查找某個元素，會返回一個迭代器類型，然后在釋放這個位置的元素

vector<int>::iterator pos=find(vt.begin(),vt.end(),3);
if(pos!=vt.end())
{erase(pos);
}
cout<<*pos<<;//此處會導致非法訪問

erase刪除pos位置之后，pos位置之后的元素會往前挪動，沒有導致底層空間的改變，理論上講迭代器是不會失效的，但是，如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，pos就會失效，因此刪除vector中任意位置的元素是，vs就認為該位置迭代器失效了?

動態二維數組的理解：

我們如何創建一個二維數組，可以想象每個vector的元素都是一個vector<int>

vector<vector<int>> vv(5);

這里可以想象一個一維數組，有五個元素，每個元素都是一個vector<int>?

那我們如何初始化呢?

?第一種：我們學過vector<int> v(3,5)//這是創建3個元素，每個元素都是5，因此我們可以這與初始化二維數組，rows是行，每個元素是vector<int>(cols),initial)

int main() {// 定義二維數組的行數和列數int rows = 3;int cols = 4;// 初始值int initialValue = 0;// 創建并初始化二維 vectorstd::vector<std::vector<int>> twoDArray(rows, std::vector<int>(cols, initialValue));// 輸出二維數組for (const auto& row : twoDArray) {for (int element : row) {std::cout << element << " ";}std::cout << std::endl;}return 0;
}

第二種：

可以創建好二維數組，在用循環依次填入數據?

int main() {// 定義二維數組的行數和列數int rows = 3;int cols = 4;// 初始值int initialValue = 0;// 創建空的二維 vectorstd::vector<std::vector<int>> twoDArray;// 逐行添加元素for (int i = 0; i < rows; ++i) {std::vector<int> row(cols, initialValue);twoDArray.push_back(row);}// 輸出二維數組for (const auto& row : twoDArray) {for (int element : row) {std::cout << element << " ";}std::cout << std::endl;}return 0;
}

?第三種：使用c++11的初始化列表進行初始化

int main() {// 使用列表初始化創建二維 vectorstd::vector<std::vector<int>> twoDArray = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};// 輸出二維數組for (const auto& row : twoDArray) {for (int element : row) {std::cout << element << " ";}std::cout << std::endl;}return 0;
}

注意：當我們創建好了之后，可以像一個二維數組一樣使用vv[i][j]去訪問每個元素

實質就是operator[]重載運算符，第一個[]先和vv結合，第二個后結合就可以訪問了?

?簡單模擬實現vector容器、

我已經把代碼上傳gitee，有需要可以自己拿

?June: 這里包含我的c++和Linux及數據結構https://gitee.com/taifanshu/day2.git