std::list和std::vector是C++中的兩種常見數(shù)據(jù)結構，它們在不同的使用場景下各有優(yōu)勢。

• std::vector的內(nèi)部實現(xiàn)是動態(tài)數(shù)組，它在連續(xù)的內(nèi)存塊中存儲數(shù)據(jù)。這使得std::vector在訪問元素時具有非常高的效率，因為可以直接通過索引來訪問元素，時間復雜度為O(1)。然而，std::vector在插入和刪除元素時可能需要移動大量的元素，特別是在非尾部進行插入或刪除操作時，時間復雜度為O(n)。
• std::list的內(nèi)部實現(xiàn)是雙向鏈表，它在非連續(xù)的內(nèi)存塊中存儲數(shù)據(jù)。這使得std::list在插入和刪除元素時具有非常高的效率，因為你只需要修改相關節(jié)點的指針，無需移動其他元素，時間復雜度為O(1)。然而，std::list在訪問元素時可能需要遍歷整個鏈表，時間復雜度為O(n)。

如果主要的操作是插入元素insert操作，那么使用std::list會比使用std::vector更高效。

list插入元素和vector插入元素對比案例

leetcode406.根據(jù)身高重建隊列

vector的做法

class Solution {
public:
    //注意cmp接收的是兩個一維數(shù)組，而不是二維數(shù)組
    static bool cmp(vector<int>& P1,vector<int>& P2){
        if(P1[0]>P2[0])  return true;//整體降序
        if(P1[0]==P2[0]){
            if(P1[1]<P2[1]) 
                return true;//p1[0]相同的時候按照p1[1]升序
        }
        return false;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //先對所有的hi降序排序，因為本題的people中的變量是{a,b}，所以需要自定義sort cmp
        sort(people.begin(),people.end(),cmp);
        //定義新的二維數(shù)組作為輸出
        vector<vector<int>>result;
        //開始遍歷排序后的people
        for(int i=0;i<people.size();i++){
            //因為此時已經(jīng)排序完畢，所以[6,1]直接插入到下標為1的地方，[5,0]直接插入下標為0的地方
            int position=people[i][1];//people[i][1]就代表著第i個集合people的第二個元素！
            //元素放到對應的二維結果數(shù)組里
            result.insert(result.begin()+position,people[i]);
        }
        return result;

    }
};

list優(yōu)化的做法

class Solution {
public:
    static bool cmp(vector<int>& P1,vector<int>& P2){
        if(P1[0]>P2[0])  return true;
        if(P1[0]==P2[0]){
            if(P1[1]<P2[1]) 
                return true;
        }
        return false;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        //結果數(shù)組類型修改為list<vector<int>>
        list<vector<int>>result;
        
        //遍歷排序后的people
        for(int i=0;i<people.size();i++){
            int position=people[i][1];
            //找到position位置之后，定義迭代器再插入
            list<vector<int>>::iterator it = result.begin();
            //注意這里insert的寫法,先尋找插入位置
            while(position--){
                it++;
            }
            //while結束之后找到插入位置
            result.insert(it,people[i]);
        }
        //把結果轉(zhuǎn)換為vector<vector<int>>，相當于構造新的二維vector
        return vector<vector<int>>(result.begin(),result.end());

    }
};

其直觀上來看數(shù)組的insert操作是O(n)的，整體代碼的時間復雜度是O(n^2)。
鏈表的insert查找+插入也是O(n)，整體代碼時間復雜度是一樣的。

為什么時間復雜度相同還會有性能差異

對于普通數(shù)組，一旦定義了大小就不能改變，例如int a[10];，這個數(shù)組a至多只能放10個元素，改不了的。

對于動態(tài)數(shù)組，就是可以不用關心初始時候的大小，可以隨意往里放數(shù)據(jù)，那么耗時的原因就在于動態(tài)數(shù)組的底層實現(xiàn)。

那么動態(tài)數(shù)組為什么可以不受初始大小的限制，可以隨意push_back數(shù)據(jù)呢？

首先vector的底層實現(xiàn)也是普通數(shù)組。

vector的大小有兩個維度一個是size一個是capicity，size就是我們平時用來遍歷vector時候用的，例如：

for (int i = 0; i < vec.size(); i++) {

}

而capicity是vector底層數(shù)組（就是普通數(shù)組）的大小，capicity不一定=size。

當insert數(shù)據(jù)的時候，如果已經(jīng)大于capicity，capicity會成倍擴容，但對外暴漏的size其實僅僅是+1。

那么既然vector底層實現(xiàn)是普通數(shù)組，怎么擴容的？

就是重新申請一個二倍于原數(shù)組大小的數(shù)組，然后把數(shù)據(jù)都拷貝過去，并釋放原數(shù)組內(nèi)存。

舉一個例子，如圖：

原vector中的size和capicity相同都是3，初始化為1 2 3，此時要push_back一個元素4。

那么底層其實就要申請一個大小為6的普通數(shù)組，并且把原元素拷貝過去，釋放原數(shù)組內(nèi)存，注意圖中底層數(shù)組的內(nèi)存起始地址已經(jīng)變了。

同時也注意此時capicity和size的變化，是成倍改變的！

而在本案例中，我們使用vector來做insert的操作，此時大家可會發(fā)現(xiàn)，雖然表面上復雜度是O(n2)，但是，其底層都不知道額外做了多少次全量拷貝了，所以算上vector的底層拷貝，整體時間復雜度可以認為是O(n^2 + t × n)級別的，t是底層拷貝的次數(shù)。

所以，雖然插入操作的理論時間復雜度沒有改變，但 在實踐中，由于std::list不需要移動元素，所以實際運行時間會更短。這就是為什么使用std::list后代碼運行時間減少的原因。

參考：
代碼隨想錄-vector和list差別解釋文章來源地址http://www.zghlxwxcb.cn/news/detail-535533.html

到了這里，關于list和vector容器的插入與訪問操作區(qū)別的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！