《C++ Primer》筆記 第9章 順序容器

1. 順序容器型別

2. string和vector將元素保存在連續的記憶體空間中，由元素的下標來計算其地址是非常快速的，但在中間位置添加或洗掉元素就會非常耗時，list和forward_list兩個容器的設計目的是令容器任何位置的添加和洗掉操作都很快速，作為代價，這兩個容器不支持元素的隨機訪問，并且相比vector、deque、array，這兩個容器的額外記憶體開銷也很大，deque支持快速的隨機訪問，在deque的兩端添加或洗掉元素都是很快的，與list或forward_list添加洗掉元素的速度相當，array物件的大小是固定的，因此，array不支持添加和洗掉元素以及改變容器大小的操作，forward_list的設計目標是達到與最好的手寫的單向鏈表資料結構相當的性能，因此，forward_list沒有size操作，因為保存或計算其大小就會比手寫鏈表多出額外的開銷，對其他容器而言，size保證是一個快速的常量時間的操作，
3. 以下是一些選擇容器的基本原則：
   • 除非你有很好的理由選擇其他容器，否則應使用vector，
   • 如果你的程式有很多小的元素，且空間的額外開銷很重要，則不要使用list或forward_list，
   • 如果程式要求隨機訪問元素，應使用vector或deque，
   • 如果程式要求在容器的中間插入或洗掉元素，應使用list或forward_list，
   • 如果程式需要在頭尾位置插入或洗掉元素，但不會在中間位置進行插入或洗掉操作，則使用deque，
   • 如果程式只有在讀取輸入時才需要在容器中間位置插入元素，隨后需要隨機訪問元素，則
     • 首先，確定是否真的需要在容器中間位置添加元素，當處理輸入資料時，通常可以很容易地向vector追加資料，然后再呼叫標準庫的sort函式來重排容器中的元素，從而避免在中間位置添加元素，
     • 如果必須在中間位置插入元素，考慮在輸入階段使用list，一旦輸入完成，將list中的內容拷貝到一個vector中，
4. 如果你不確定應該使用哪種容器，那么可以在程式中只使用vector和list公共的操作：使用迭代器，不使用下標操作，避免隨機訪問，這樣，在必要時選擇使用vector或list都很方便，
5. 容器型別上的操作形成了一種層次：
   • 某些操作是所有容器型別都提供的，
   • 另外一些操作僅針對順序容器、關聯容器或無序容器，
   • 還有一些操作只適用于一小部分容器，
6. 順序容器建構式的一個版本接受容器大小引數，它使用了元素型別的默認建構式，但某些類沒有默認建構式，我們可以定義一個保存這種型別物件的容器，但我們在構造這種容器時不能只傳遞給它一個元素數目引數：

     // 假定noDefault是一個沒有默認建構式的型別
     vector<noDefault> v1(10, init); // 正確：提供了元素初始化器
     vector<noDefault> v2(10); // 錯誤：必須提供一個元素初始化器
   

7. 容器操作：

8. forward_list迭代器不支持遞減運算子（--），

9. 一個迭代器范圍由一對迭代器表示，兩個迭代器分別指向同一個容器中的元素或者是尾元素之后的位置，

10. 迭代器范圍中的元素包含first所表示的元素以及從first開始直至last（但不包含last）之間的所有元素，左閉合區間：[left, right)，

11. 如果滿足如下條件，兩個迭代器begin和end構成一個迭代器范圍：

    • 它們指向同一個容器中的元素，或者是容器最后一個元素之后的位置，且
    • 我們可以通過反復遞增begin來到達end，換句話說，end不在begin之前，

12. 標準庫使用左閉合范圍是因為這種范圍有三種方便的性質，假定begin和end構成一個合法的迭代器范圍，則

    • 如果begin與end相等，則范圍為空
    • 如果begin與end不等，則范圍至少包含一個元素，且begin指向該范圍中的第一個元素
    • 我們可以對begin遞增若干次，使得begin==end

13. 這些性質意味著我們可以用回圈來處理一個元素范圍，

    while (begin != end)
    {
        *begin = val; // 正確：范圍非空，因此begin指向一個元素
        // 在while回圈中，可以安全地解參考begin，因為begin必然指向一個元素，
        ++begin; // 移動迭代器，獲取下一個元素
    }
    

14. 反向迭代器就是一種反向遍歷容器的迭代器，與正向迭代器相比，各種操作的含義也都發生了顛倒，例如，對一個反向迭代器執行++操作，會得到上一個元素，

15. begin和end有多個版本：帶r的版本回傳反向迭代器；以c開頭的版本則回傳const迭代器；不以c開頭的函式都是被多載過的，一個是const成員，回傳容器的const_iterator型別；另一個是非常量成員，回傳容器的iterator型別，當我們對一個非常量物件呼叫這些成員時，得到的是回傳iterator的版本，只有在對一個const物件呼叫這些函式時，才會得到一個const版本，與const指標和參考類似，可以將一個普通的iterator轉換為對應的const_iterator，但反之不行，

16. 當auto與begin或end結合使用時，獲得的迭代器型別依賴于容器型別，與我們想要如何使用迭代器毫不相干，但以c開頭的版本還是可以獲得const_iterator的，而不管容器的型別是什么，當不需要寫訪問時，應該使用cbegin和cend，

17. 容器定義和初始化

18. 當將一個容器初始化為另一個容器的拷貝時，兩個容器的容器型別和元素型別都必須相同，但當傳遞迭代器引數來拷貝一個范圍時，就不要求容器型別是相同的了，而且，新容器和原容器中的元素型別也可以不同，只要能將要拷貝的元素轉換為要初始化的容器的元素型別即可（建構式只是讀取范圍中的元素并進行拷貝），

    // 每個容器有三個元素，用給定的初始化器進行初始化
    list<string> authors = {"Milton", "Shakespeare", "Austen"};
    vector<const char*> articles = {"a", "an", "the"};
    
    list<string> list2(authors); // 正確：型別匹配
    deque<string> authList(authors); // 錯誤：容器型別不匹配
    vector<string> words(articles); // 錯誤：容器型別必須匹配
    // 正確：可以將const char*元素轉換為string
    forward_list<string> words(articles.begin(),articles.end());
    

19. 如果元素型別是內置型別或者是具有默認建構式的型別別，可以只為建構式提供一個容器大小引數，如果元素型別沒有默認建構式，除了大小引數外，還必須指定一個顯示的元素初始值，

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class A
    {
    private:
        vector<int> data;
    
    public:
        A(vector<int>::iterator beg, vector<int>::iterator end)
        {
            data.assign(beg, end);
        }
        void display()
        {
            for (auto i : data)
                cout << i << " ";
            cout << endl;
        }
    };
    
    int main()
    {
        vector<int> iv{1, 2, 3};
        vector<A> one(5, A(iv.begin(), iv.end()));
        for (auto i : one)
            i.display();
        cout << endl;
        return 0;
    }
    

20. 只有順序容器的建構式才接受大小引數，關聯容器并不支持，

21. 標準庫array的大小也是型別的一部分，當定義一個array時，除了指定元素型別，我們必須同時指定元素型別和大小，

    array<int, 42> // 型別為：保存42個int的陣列
    array<string, 10> // 型別為：保存10個string的陣列
    
    array<int, 10>::size_type i; // 陣列型別包括元素型別和大小
    array<int>::size_type j; // 錯誤：array<int>不是一個型別
    

22. 一個默認構造的array是非空的：它包含了于其大小一樣多的元素，這些元素都被默認初始化，就像一個內置陣列中的元素那樣，如果我們對array進行串列初始化，初始值的數目必須等于或小于array的大小，如果初始值數目小于array的大小，則它們被用來初始化array中靠前的元素，所有剩余元素都會進行值初始化，在這兩種情況下，如果元素型別是一個型別別，那么該類必須有一個默認建構式，以使值初始化能夠進行，

    array<int, 10> ia1; // 10個默認初始化的int
    array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; // 串列初始化
    array<int, 10> ia3 = {42}; // ia3[0]為42，剩余元素為0
    
    int digs[10] = {0,1,2,3,4,5,6,7,8,9};
    int cpy[10] = digs; // 錯誤：內置陣列不支持拷貝或賦值
    array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
    array<int, 10> copy = digits; // 正確：只要陣列型別匹配即合法
    

23. 與其他容器一樣，array也要求初始值的型別必須與要創建的容器型別相同，此外，array還要求元素型別和大小也都一樣，因為大小是array型別的一部分，

24. 與賦值相關的運算子可用于所有容器，賦值運算子將其左邊容器中的全部元素替換為右邊容器中元素的拷貝，如果兩個容器原來大小不同，賦值運算后兩者的大小都與右邊容器的原大小相同，

    c1 = c2; // 將c1的內容替換為c2中元素的拷貝
    c1 = {a,b,c}; // 賦值后，c1大小為3
    

25. 與內置陣列不同，標準庫array型別允許賦值，賦值號左右兩邊的運算物件必須具有相同的型別，由于右邊運算物件的大小可能與左邊運算物件的大小不同，因此array型別不支持assign，也不允許用花括號包圍的值串列進行賦值，

    array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
    array<int, 10> a2 = {0}; // 所有元素值均為0
    a1 = a2; // 替換a1中的元素
    a2 = {0}; // 錯誤：不能將一個花括號串列賦予陣列
    

26. 賦值相關運算會導致指向左邊容器內部的迭代器、參考和指標失效，而swap操作將容器內容交換不會導致指向容器的迭代器、參考和指標失效（容器型別為array和string的情況除外），

27. 順序容器的assign成員允許我們從一個不同但相容的型別賦值，或者從容器的一個子序列賦值，assign操作用引數所指定的元素（的拷貝）替換左邊容器中的所有元素，

    list<string> names;
    vector<const char*> oldstyle;
    names = oldstyle; // 錯誤：容器型別不匹配
    // 正確：可以將const char*轉換為string
    names.assign(oldstyle.cbegin(), oldstyle.cend());
    

28. 由于其舊元素被替換，因此傳遞給assign的迭代器不能指向呼叫assign的容器，

29. 除array外，swap不對任何元素進行拷貝、洗掉或插入操作，因此可以保證在常數時間內完成，

30. 除string外，指向容器的迭代器、參考和指標在swap操作之后都不會失效，它們仍指向swap操作之前所指向的那些元素，但是，在swap之后，這些元素已經屬于不同的容器了，對一個string呼叫swap會導致迭代器、參考和指標失效，

31. swap兩個array會真正交換它們的元素，因此，交換兩個array所需的時間與array中元素的數目成正比，

32. 對于array，在swap操作之后，指標、參考和迭代器所系結的元素保持不變，但元素值已經與另一個array中對應元素進行了交換，

33. 在標準庫中，容器既提供成員函式版本的swap，也提供非成員版本的swap，非成員版本的swap在泛型編程中是非常重要的，統一使用非成員版本的swap是一個好習慣，

34. 成員函式size回傳容器中元素的數目；empty當size為0時回傳布林值true，否則回傳false；max_size回傳一個大于或等于該型別容器所能容納的最大元素數的值，forward_list支持max_size和empty，但不支持size，

35. 每個容器型別都支持相等運算子（==和!=）；除了無序關聯容器都支持關系運算子（>、>=、<、<=），關聯運算子左右兩邊的運算物件必須是相同型別的容器，且必須保存相同型別的元素，

36. 比較兩個容器實際上是進行元素的逐對比較，這些運算子的作業方式與string的關系運算類似，

    • 如果兩個容器具有相同大小且所有元素都兩兩對應相等，則這兩個容器相等；否則兩個容器不等，
    • 如果兩個容器大小不同，但較小容器中每個元素都等于較大容器中的對應元素，則較小容器小于較大容器，
    • 如果兩個容器都不是另一個容器的前綴子序列，則它們的比較結果取決于第一個不相等的元素的比較結果，

37. 只有當其元素型別也定義了相應的比較運算子時，我們才可以使用關系運算子來比較兩個容器，

38. 容器的相等運算子實際上是使用元素的==運算子實作比較的，而其他關系運算子是使用元素的<運算子，如果元素型別不支持所需運算子，那么保存這種元素的容器就不能使用相應的關系運算，

39. 向一個vector、string或deque插入元素會使所有指向容器的迭代器、參考和指標失效，

40. 不同容器使用不同的策略來分配元素空間，而這些策略直接影響性能，

41. 當我們用一個物件來初始化容器時，或將一個物件插入到容器中時，實際上放入到容器中的是物件的一個拷貝，而不是物件本身，就像我們將一個物件傳遞給非參考引數一樣，容器中的元素與提供值的物件之間沒有任何關聯，隨后對容器中元素的任何改變都不會影響到原始物件，反之亦然，

42. 通過使用insert的回傳值，可以在容器中一個特定位置反復插入元素：

    list<string> lst;
    auto iter = lst.begin();
    while (cin >> word)
    	iter = lst.insert(iter, word); // 等價于呼叫push_front
    

43. emplace_front、emplace和emplace_back這些操作構造而不是拷貝元素，

44. emplace函式在容器中直接構造元素，傳遞給emplace函式的引數必須與元素型別的建構式相匹配，

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class A
    {
    private:
        vector<int> data;
    
    public:
        A(vector<int>::iterator beg, vector<int>::iterator end)
        {
            data.assign(beg, end);
        }
        void display()
        {
            for (auto i : data)
                cout << i << " ";
            cout << endl;
        }
    };
    
    int main()
    {
        vector<int> iv{1, 2, 3};
        vector<A> one(5, A(iv.begin(), iv.end()));
        for (auto i : one)
            i.display();
        cout << endl;
        
        vector<int> ivv{2, 3, 6};
        one.emplace_back(ivv.begin(), ivv.end());
        one.back().display();
        return 0;
    }
    

45. 包括array在內的每個順序容器都有一個front成員函式，而除forward_list之外的所有順序容器都有一個back成員函式，這兩個操作分別回傳首元素和尾元素的參考：

    // 在解參考一個迭代器或呼叫front或back之前檢查是否有元素
    if (!c.empty())
    {
    	// val和val2是c中第一個元素值的拷貝
    	auto val = *c.begin(), val2 = c.front();
    	// val3和val4是c中最后一個元素值的拷貝
    	auto last = c.end();
    	auto val3 = *(--last); // forward_list迭代器不能執行--操作
    	auto val4 = c.back(); // forward_list不支持
    }
    

46. 在呼叫front和back（或解參考begin和end回傳的迭代器）之前，要確保c非空，如果容器為空，if中操作的行為將是未定義的，

47. 對一個空容器呼叫front和back，就像使用一個越界的下標一樣，是一種嚴重的程式設計錯誤，

48. 在容器中訪問元素的成員函式（即，front、back、下標和at）回傳的都是參考，如果容器是一個const物件，則回傳值是const的參考，如果容器不是const的，則回傳值是普通參考，我們可以用來改變元素的值：

    if (!c.empty())
    {
    	c.front() = 42; // 將42賦予c中的第一個元素
    	auto &v = c.back(); // 獲得指向最后一個元素的參考
    	v = 1024; // 改變c中的元素
    	auto v2 = c.back(); // v2不是一個參考，它是c.back()的一個拷貝
    	v2 = 0; // 未改變c中的元素
        // 如果我們使用auto變數來保存這些函式的回傳值，并且希望使用此變數來改變元素的值，必須記得將變數定義為參考型別
    }
    

49. 洗掉deque中除首尾位置之外的任何元素都會使所有迭代器、參考和指標失效，指向vector或string中洗掉點之后位置的迭代器、參考和指標都會失效，
50. 洗掉元素的成員函式并不檢查其引數，在洗掉元素之前，程式員必須確保它（們）是存在的，
51. 在一個單向鏈表中，沒有簡單的辦法來獲取一個元素的前驅，因此，在一個forward_list中添加或洗掉元素的操作是通過改變給定元素之后的元素來完成的，為了支持這些操作，forward_list也定義了before_begin，它回傳一個首前迭代器（允許我們添加洗掉鏈表首元素）

// 示例代碼：
forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); // 表示flst的“首前元素”
auto curr = flst.begin(); // 表示flst中的第一個元素
while (curr != flst.end()) // 仍有元素要處理
{
	if (*curr % 2) // 若元素為奇數，也可以用*curr & 1
		curr = flst.erase_after(prev); // 洗掉它并移動curr
	else
	{
		prev = curr; // 移動迭代器curr，指向下一個元素，prev指向
		++curr; // curr之前的元素
	}
}

52. 如果resize縮小容器，則指向被洗掉元素的迭代器、參考和指標都會失效；對vector、string或deque進行resize可能導致迭代器、指標和參考失效，

53. 容器操作可能使迭代器失效，使用失效的迭代器、指標或參考是嚴重的運行時錯誤，

    • 在向容器添加元素后：
      • 如果容器是vector或string，且存盤空間被重新分配，則指向容器的迭代器、指標和參考都會失效，如果存盤空間未重新分配，指向插入位置之前的元素的迭代器、指標和參考仍有效，但指向插入位置之后元素的迭代器、指標和參考將會失效，
      • 對于deque，插入到除首尾位置之外的任何位置都會導致迭代器、指標和參考失效，如果在首尾位置添加元素，迭代器會失效，但指向存在的元素的參考和指標不會失效，
      • 對于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指標和參考仍有效，
    • 當我們從一個容器中洗掉元素后，指向被洗掉元素的迭代器、指標和參考一定會失效，畢竟，這些元素都已經被銷毀了，當我們洗掉一個元素后：
      • 對于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、參考和指標仍有效，
      • 對于deque，如果在首尾之外的任何位置洗掉元素，那么指向被洗掉元素外其他元素的迭代器、參考和指標也會失效，如果是洗掉deque的尾元素，則尾后迭代器也會失效，但其他迭代器、參考和指標不受影響；如果是洗掉首元素，這些也不會受影響，
      • 對于vector和string，指向被刪元素之前元素的迭代器、參考和指標仍有效，注意：當我們洗掉元素時，尾后迭代器總是會失效，

54. 當你使用迭代器（或指向容器元素的參考或指標）時，最小化要求迭代器必須保持有效的程式片段是一個好的辦法，由于向迭代器添加元素和從迭代器洗掉元素的代碼可能會使迭代器失效，因此必須保證每次改變容器的操作之后都正確地重新定位迭代器，這個建議對vector、string和deque尤為重要，

55. 程式必須保證每個回圈布中都更新迭代器、參考和指標：

    // 傻瓜回圈，洗掉偶數元素，復制每個奇數元素
    vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
    auto iter = vi.begin(); // 呼叫begin而不是cbegin，因為我們要改變vi
    while (iter != vi.end())
    {
    	if (*iter % 2)
    	{
    		iter = vi.insert(iter, *iter); // 復制當前元素
    		iter += 2; // 向前移動迭代器，跳過插入到它之前的元素以及當前元素
    	}
    	else
    	{
    		iter = vi.erase(iter); // 洗掉偶數元素
    		// 不應向前移動迭代器，iter指向我們洗掉的元素之后的元素
    	}
    }
    

56. 不要保存end回傳的迭代器，當我們添加、洗掉vector或string的元素后，或在deque中首元素之外任何位置添加、洗掉元素后，原來end回傳的迭代器總是會失效，因此，添加或洗掉元素的回圈程式必須反復呼叫end，而不能在回圈之前保存end回傳的迭代器，一直當作容器末尾使用，

57. reserve并不改變容器中元素的數量，它僅影響vector預先分配多大的記憶體空間，只有當需要的記憶體空間超過當前容量時，reserve呼叫才會改變vector的容量，如果需求大小大于當前容量，reserve至少分配與需求一樣大的記憶體空間（可能更大），如果需求大小小于或等于當前容量，reserve什么也不做，特別是，當需求大小小于當前容量時，容器不會退回記憶體空間，因此，在呼叫reserve之后，capacity將會大于或等于傳遞給reserve的引數，這樣，呼叫reserve永遠也不會減少容器占用的記憶體空間，類似的，resize成員函式只能改變容器中元素的數目，而不是容器的容量，我們同樣不能使用resize來減少容器預留的記憶體空間，

58. 每個vector實作都可以選擇自己的記憶體分配策略，但是必須遵守的一條原則是：只有當迫不得已（在執行insert操作時size與capacity相等，或者呼叫resize或reserve時給定的大小超過當前capacity）時才可以分配新的記憶體空間，

59. 在c++11中，vector 增加了data()的用法，它回傳內置vecotr所指的陣列記憶體的第一個元素的指標，

60. string搜索函式回傳string::size_type值，該型別是一個unsigned型別，因此，用一個int或其他帶符號型別來保存這些函式的回傳值不是一個好主意，

61. 指定在哪里開始搜索：

    string numbers("0123456789"), name("r2d2");
    string::size_type pos = 0;
    // 每步回圈查找name中下一個數
    while ((pos = name.find_first_of(numbers, pos)) != string::npos)
    {
    	cout << "found number at index: " << pos
    		<< " element is " << name[pos] << endl;
    	++pos; // 移動到下一個字符
    }
    

62. 配接器是標準庫中的一個通用概念，本質上，一個配接器是一種機制，能使某種事物的行為看起來像另外一種事物一樣，一個容器配接器接受一種已有的容器型別，是其行為看起來像一種不同的型別，

63. 默認情況下，stack和queue是基于deque實作的，priority_queue是在vector之上實作的，我們可以在創建一個配接器時將一個命名的順序容器作為第二個型別引數，來多載默認容器型別，

    // 從deq拷貝元素到stk
    stack<int> stk(deq);
    // 在vector上實作的空堆疊
    stack<string, vector<string>> str_stk;
    // str_stk2在vector上實作，初始化時保存svec的拷貝
    stack<string, vector<string>> str_stk2(svec); // svec是vector<string>型別
    

64. deque支持在容器頭尾位置的快速插入和洗掉，而且在兩端插入或洗掉元素都不會導致重新分配空間，

標籤：其他

上一篇：HashSet詳解

下一篇：1.Yolov5學習率調整策略