[C++ 面試基礎知識總結] 順序容器[C++ 面試基礎知識總結] 順序容器

參考書籍：《c++ primer》

<a href="#c-%e9%9d%a2%e8%af%95%e5%9f%ba%e7%a1%80%e7%9f%a5%e8%af%86%e6%80%bb%e7%bb%93-%e9%a1%ba%e5%ba%8f%e5%ae%b9%e5%99%a8">c 面試基礎知識總結 順序容器</a>

<a href="#%e7%9b%ae%e5%bd%95">目錄</a>

<a href="#%e9%a1%ba%e5%ba%8f%e5%ae%b9%e5%99%a8%e4%b8%8e%e9%80%89%e6%8b%a9">順序容器與選擇</a>

<a href="#%e8%bf%ad%e4%bb%a3%e5%99%a8">疊代器</a>

<a href="#%e5%ae%b9%e5%99%a8%e7%9a%84%e5%88%9d%e5%a7%8b%e5%8c%96%e5%92%8c%e8%b5%8b%e5%80%bc">容器的初始化和指派</a>

<a href="#%e9%a1%ba%e5%ba%8f%e5%ae%b9%e5%99%a8%e6%93%8d%e4%bd%9c">順序容器操作</a>

<a href="#%e6%b7%bb%e5%8a%a0%e5%85%83%e7%b4%a0">添加元素</a>

<a href="#%e8%ae%bf%e9%97%ae%e5%85%83%e7%b4%a0">通路元素</a>

<a href="#%e5%88%a0%e9%99%a4%e5%85%83%e7%b4%a0">删除元素</a>

<a href="#%e6%94%b9%e5%8f%98%e5%ae%b9%e5%99%a8%e5%a4%a7%e5%b0%8f">改變容器大小</a>

<a href="#%e8%bf%ad%e4%bb%a3%e5%99%a8%e5%a4%b1%e6%95%88">疊代器失效</a>

<a href="#vector%e5%af%b9%e8%b1%a1%e7%9a%84%e5%a2%9e%e9%95%bf">vector對象的增長</a>

<a href="#string-%e6%93%8d%e4%bd%9c">string 操作</a>

<a href="#%e6%94%b9%e5%8f%98string">改變string</a>

<a href="#%e6%90%9c%e7%b4%a2string">搜尋string</a>

<a href="#%e6%95%b0%e5%80%bc%e8%bd%ac%e6%8d%a2">數值轉換</a>

<a href="#%e5%ae%b9%e5%99%a8%e9%80%82%e9%85%8d%e5%99%a8">容器擴充卡</a>

<a href="#%e6%a0%88stack">棧stack</a>

<a href="#%e9%98%9f%e5%88%97queue">隊列queue</a>

順序容器類型：

vector 可變大小數組

deque 雙端隊列

list 雙向連結清單

forward_list 單向連結清單

array 固定大小數組

string 專門用于儲存字元的可變大小數組

選擇容器的基本原則：

1.預設情況用vector

2.小元素多，空間額外開銷重要的時候避免使用list或forward_list

3.要求随機通路元素時，用vector或deque

4.要求在容器中間插入或删除元素時，用list或forward_list

5.需要在頭尾插入或删除元素，但不會在中間進行次操作時，用deque

複合使用：如果一個程式隻有在讀取輸入時才需要在容器中間插入元素，随後需要随機通路元素，則可以在輸入階段使用list，一旦輸入完成後，将list中的内容拷貝到一個vector中。

begin和end操作生成指向容器中第一個元素和尾元素之後位置的疊代器。除forward_list以外的順序容器還支援按逆序尋址元素的疊代器<code>reverse_iterator</code>。采用rbegin和rend操作分别生成指向容器尾元素和收元素之前位置的疊代器。

建立一個容器為另一個容器的拷貝時，兩個容器的類型和其存放的元素類型都必須比對。用傳遞疊代器參數來拷貝一個範圍時，就不要求容器類型是相同的了，容器中的元素類型也可以不同，隻要是可以轉換的即可。

array的大小也是類型的一部分，當定義一個array時，除了指定元素類型，還要指定容器大小。

進行指派運算時，如果兩個容器原來大小不等，則讓兩個容器的大小都與右邊容器的原大小相等。

除array以外的順序容器都支援assign，assign可以将右邊運算對象的元素拷貝到左邊運算對象中，也可以指定數目且具有相同給定值的元素替換容器中的原有元素。

注意：使用一個對象來初始化容器或将一個對象插入到容器時，實際上放入容器中的是對象值的一個拷貝，而不是對象本身。容器中的元素與提供值得對象之間沒有任何關聯！

通路容器中的元素的主要方法：解引疊代器，調用front,back函數，使用下标。

注意：如果容器為空，調用front,back函數會發生嚴重錯誤。在使用下标時需要保證給定下标在有效範圍内，防止發生越界。在容器中通路成員函數傳回的都是引用，如果容器是一個const對象，則傳回值是const引用。如果容器不是const，則可以用傳回值來改變元素的值。

注意：删除元素的函數都不會檢查其參數，是以在删除元素之前，必須保證被删元素确實存在。

改變容器大小時，如果容器縮小，容器後部的元素會被删除，如果容器增大，會在容器後部添加新元素。

向容器中添加元素和從容器中删除元素的操作可能會使指向容器元素的指針，引用或疊代器失效。使用失效的指針，引用或疊代器是一種嚴重錯誤。當使用疊代器時，最好保證在每次改變容器的操作之後都正确地重新定位疊代器。

注意：end傳回的疊代器很容易失效，不要儲存end傳回的疊代器。

在有些程式設計環境下運作最後一條語句，輸出的v的容量也有可能是75，即系統自動為v重新配置設定的記憶體空間為原來的1.5倍。

string除了支援順序容器的通用操作外，還支援一些其他的操作。

注意：substr和replace函數的開始位置不能超出string的長度，操作長度最大值為string長度與開始位置之差。

注意：搜尋對大小寫敏感！

除了順序容器外，标準庫還定義了3個順序容器擴充卡:stack,queue和priority_queue。擴充卡可以接受一種已有的容器類型，使其行為看起來像一種不同的類型。所有擴充卡都要求容器具有添加，删除元素和通路尾元素的能力。是以array和<code>forward_list</code>無法用來構造擴充卡。

stack隻需要實作添加，删除，通路尾元素操作，是以可以用vector，list，deque來構造，預設情況下stack是基于deque構造的。

棧的基本操作

queue需要實作添加尾元素，删除首元素，通路首尾元素操作，是以隻能用list，deque來構造，預設情況下queue是基于deque構造的。

隊列的基本操作

priority_queue與queue的差別在于<code>priority_queue</code>，需要實作的是隊尾元素的添加删除和随機通路，是以隻能用vector和deque進行構造，預設情況是用vector構造<code>priority_queue</code>。且<code>priority_queue</code>的元素是按優先級排序的（queue是按入隊順序），可用<code>q.top()</code>傳回優先級最高的元素。