前言

能夠在運行時高效地存放各種類型的動態數組vector！

Vector定義

#include <Vector> 
using namespace std;
void init() {
    //空對象
    vector<int> v1;
    //元素個數為5，每個int元素都為0
    vector<int> v2(5);
    //元素個數為5，每個int元素都為3
    vector<int> v3(5, 3);
    //手動賦初值，共五個元素，元素值為指定的內容
    vector<int> v4{1, 2, 3, 4, 5};
}

Vector常規操作

C++中文在線手冊：https://zh.cppreference.com/

訪問Vector中的任意元素或從末尾添加元素的時間複雜度是O(1)，而查找特定值的元素所處的位置或是在Vector中插入元素則是線性時間複雜度，即O(n)。

增加元素

下標插入

Vector是動態數組，是支持隨機訪問的，也就是直接用下標取值。

但是如果是直接用下標賦值，當下標超出了容器的超出了容量，會無法插入，而且此時是不會報錯。

/*
 * 聲明了一個對象，初始是兩個元素，容量為2
 * 當直接修改下標沒有超過容量，會直接修改元素
 * 當直接修改下標查過了容量，會沒有變化，因為容器內不存在超過容量的元素，被認為是無效操作。
 * */
void add1(){
    vector<int> demo{1, 2};
    demo[1]=3;//{1,3}
    demo[10]=3;//{1,3}
}

所以建議使用自帶的插入函數。

insert插入

允許多個元素的插入，使用疊代器指定位置。

注意：是在疊代器 pos 位置之前插入！

注意：因為需要調用類的構造函數和移動構造函數，所以較慢，但是適用性很棒！

void add2(){
    vector<int> demo{1, 2};
    //在第一個元素後面插入3
    demo.insert(demo.begin() + 1, 3);//{1,3,2}
    //在末尾插入2個5
    demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
    //插入其他容器的部分序列
    set<int> setTemp{7, 8, 9};
    demo.insert(demo.end(), ++setTemp.begin(), --setTemp.end()); //{1,3,2,5,5,8}
    //插入初始化列表
    demo.insert(demo.end(), {10, 11}); //{1,3,2,5,5,7,8,9,10,11}
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

emplace插入

注意是每次只能插入一個，而且是只有構造函數，效率高！

void add3() {
    vector<int> demo{1, 2};
    demo.emplace(demo.begin(), 3);//{3,1,2}
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

push_back插入

vector底層是用數組實現的，每次執行push_back操作，在底層實現時，是會判斷當前元素的個數是否等於容量大小，如果沒有就直接插入，否則就要擴容了。

void add4() {
    vector<int> demo{1, 2};
    demo.push_back(3);//{3,1,2}
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

換句話說，擴容時是要重新分配大小的，先free掉原來的存儲空間，後重新malloc。非常耗費時間！

void
vector<_Tp, _Allocator>::push_back(const_reference __x)
{
    if (this->__end_ != this->__end_cap())
    {
        __construct_one_at_end(__x);
    }
    else
        __push_back_slow_path(__x);
}

遍曆元素

下標遍歷1

/*
 * 直接for循環，用下標取元素即可
 * */
void search1() {
    vector<int> demo{1, 2};
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

下標遍歷2

/*
 * 直接用下標取值，超過容量會報錯
 * */
void search3() {
    vector<int> demo{1, 2};
    cout <<demo.at(1);
    // cout <<demo.at(1);// 會報錯
    cout << endl;
}

疊代器遍歷

/*
 * 直接用疊代器，注意const_iterator還是iterator
 * */
void search2() {
    vector<int> demo{1, 2};
    // 如果參數為const vector<int> 需要用const_iterator
    // vector<int>::const_iterator iter=v.begin();
    for (vector<int>::iterator it = demo.begin(); it != demo.end(); ++it) {
        cout << (*it) << " ";
    }
    cout << endl;
}

刪除元素

/*
 * 刪除有兩種方式，
 * clear一個是直接清空
 * erase是刪除指定疊代器範圍內的數字
 * pop_back是刪除最後一個
 * */
void del() {
    vector<int> demo{1, 2, 3, 4, 5};
    //清空
    demo.clear();//{}
    if (demo.empty()) {//判斷Vector為空則返回true
        demo.insert(demo.end(), {6, 7, 8, 9, 10, 11});//{ 6, 7, 8, 9, 10, 11 }
        //刪除第一個元素
        demo.erase(demo.begin());//{7, 8, 9, 10, 11 }
        //刪除前三個
        demo.erase(demo.begin(), demo.begin() + 3); //{ 10, 11 }
        //刪除最後一個
        demo.pop_back();//{10}
    }
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

原理

內存擴展方式

當調用插入函數，卻發現空間不夠的時候，會進行擴容：

尋找原來的capacity的兩倍空間；
將原數據複製過去；
釋放原空間三部曲。

每次配置新空間時都有留下一些數據空間，可以保證常數的時間複雜度

三大特性

嚴格的線性順序排序。
支持動態內存分配
支持隨機訪問元素，並操供了在尾部添加和刪除操作

size和capacity的區別

size則代表了對象內元素的個數

capacity代表了能夠存放多少個元素的閥值。

一旦超過閥值capacity，容器會花費大量時間重新配置內部的存儲器，並導致vector元素相關的所有reference、pointers、iterator都會失效。

感謝

示例文件

gitee：https://gitee.com/JunKuangKuang/KeenCPPTest-all/blob/ac9971df11109470fbaf708ba2977ca593d92292/STL/vector/vector_test.cpp

github.com：https://github.com/JunKuangKuang/KeenCPPTest-all/blob/main/STL/vector/vector_test.cpp

感謝

感謝現在的好奇，為了能成為更好的自己。

離線下載連結

vector 類中的 push_back( ) 函數

C++ STL vector插入元素

Cpp淺析系列-STL之vector

前言