技術文章 » C++ STL標準模板庫

C++ STL標準模板庫

2020-07-16 10:04:41
除了執行時庫之外，C++ 還提供了一個模板庫。標準模板庫（STL）包含許多用於實現資料型別和演算法的模板。

STL 中最重要的資料結構是容器和疊代器。容器是一種儲存資料並以某種方式組織資料的類。疊代器是一個像指標一樣工作的物件，允許存取儲存在容器中的專案。

順序容器

STL 中有兩種型別的容器類：順序容器和關聯容器。順序容器以序列的形式儲存專案，這意味著按照專案在容器內的位置以自然方式排序專案。陣列就是順序容器的一個範例。

STL提供了如表 1 所示的 3 個順序容器。

表 1 STL順序容器
容器名稱 描 述
vector 作為一個陣列實現的一系列專案，在程式執行期間可以根據需要自動增長。專案可以高 效地從向量末尾新增或刪除。從向量的中間或開始位置插入或刪除專案的效率不高
deque 一系列具有頭部和尾部的專案：專案可以有效地從頭部和尾部新增或刪除。在雙端佇列（deque）的中間插入和刪除專案的效率都很低
list 允許從任意位置快速新增和刪除的一系列專案

因為順序容器按順序組織它儲存的專案，所以可稱它有一個頭部和一個尾部。如果可以指定容器中某個專案的位置，然後直接跳轉到該專案，而不必遍歷容器中該專案之前的所有專案，則稱該容器提供了對其內容的隨機存取方式。

隨機存取中使用的位置通常是通過給定一個整數指定的，該整數指定了容器內所需專案的位置。該整數指定的位置可以相對於容器的頭部、末尾或相對於其他位置。陣列和向量都是提供隨機存取的順序容器範例。

關聯容器

順序容器使用序列中的專案位置來存取其資料。相反，關聯容器將一個鍵（Key）與儲存的每個專案相關聯，然後使用該鍵來檢索儲存的專案。電話簿是關聯容器的一個範例，它儲存的值是電話號碼，每個電話號碼都與一個名稱相關聯。該名稱稍後可以用作查詢或 檢索電話號碼的鍵。

STL 提供了 4 個關聯容器，如表 2 所示。

表 2 STL關聯容器
容器名稱 描 述
set 儲存一組鍵。不允許重複的值
multiset 儲存一組鍵。允許重複的值
map 將一組鍵對映到資料元素。每個鍵都與唯一的資料元素相關聯，並且不允許使用重複的鍵
multimap 將一組鍵對映到資料元素。相同的鍵可以關聯多個值

map 是一個容器，要求每個儲存的值都與一個鍵相關聯。每個鍵可能只與一個值相關 聯。一旦使用了鍵，則不能將具有相同鍵的其他值新增到 map 中

multimap 和 map 相似，只不過其鍵則可以關聯多個值。

set 和 map 類似，只不過它僅儲存鍵，並不關聯值。沒有專案能在一個 set 中儲存兩次，也就是說，不允許重復專案。multiset 很像 set，只不過它允許重複。

疊代器

疊代器是像指標一樣的物件。它們可用於存取儲存在容器中的專案。典型的疊代器是在容器類中宣告的類的物件。疊代器可以過載指標運算子，如遞增運算子 ++、遞減運算子 -- 和解除參照運算子 * 等，以提供類似於指標的行為。

每個 STL 容器物件都提供成員函數 begin() 和 end()，它們返回物件的開始和結束疊代器。如果容器是非空的，則 begin() 疊代器將指向容器開始處的專案，而 end() 疊代器則指向剛剛超過容器尾部的地方。

表 3 顯示了可用於各種 STL 容器的不同型別的疊代器。

表 3 疊代器型別
疊代器型別 描 述
前向（Forward) 只能在容器中向前移動（使用++運算子）
雙向（Bidirectional) 可以在容器中前後移動（使用++和一運算子）
隨機存取（Random-Access) 可以在容器中前後移動，還可以直接跳轉到指定的資料專案
輸入（Input) 可以使用cin從輸入裝置或檔案讀取資訊
輸出（Output) 可以使用emit將資訊寫入輸出裝置或檔案

疊代器的使用

每個STL容器類都定義了一個名為 iterator 的內部類，可用於建立疊代物件。範例如下：

vector<int>::iterator list<string>::iterator

以上範例都是內部類，可以相應為 vector<int> 和 list<string> 型別的容器提供疊代器。以下範例演示了如何為 int 型別的向量和 string 列表定義疊代器，並將它們初始化為容器的開始位置。

vector<int> vect;
list<string> myList;
vector<int>::iterator vIter = vect.begin();
list<string>::iterator listIter = myList.begin();

在 C++ 11 中，可以將疊代器的型別宣告為 auto，這樣編譯器將從容器的型別推斷出疊代器的正確型別，如下所示：

auto vIter = vect.begin();
auto listIter = myList.begin();

除此之外，C++ 還提供了 begin(c) 和 end(c) 函數，當它們應用於 STL 容器 c 時，將相應返回 c.begin() 和 c.end() 疊代器。

所以，上面的 2 個範例也可以改寫為以下形式：

auto vlter = begin(vect);
auto listlter = begin(myList);

begin(c) 和 end(c) 函數的好處是可以和陣列一起使用。在某些情況下，這允許程式設計師編寫能同時處理 STL 容器和陣列的程式碼。

疊代器可以像指標一樣工作，指示容器內的位置。如果 iter 是一個疊代器，則 *iter 就代表了在容器的疊代器位置中儲存的元素。此外，編寫 iter++ 將導致疊代器向前移動到容器的下一個位置。end() 疊代器始終指示超過容器最後一個元素的位置，所以它絕對不能被解除參照。end() 疊代器僅用作標記符號，以防止掉入容器的末尾。

例如，以下程式碼將列印程式碼中的所有值：
vector<int> vect { 10, 20, 30, 40, 50};
auto vIter = vect.begin();
while (iter != vect.end())
{
    //列印iter位置的元素並向前疊代
    cout << *iter << " ";
    iter ++;
}
下面的程式演示了如何使用上述概念知識來處理陣列和向量。它的主要思路是編寫如下模板函數：

template<typename T> void print(T begin_iter, T end_iter)

該函數釆用 T 型別形參。作為 T 傳遞的真實型別需要支援解除參照運算子 * 和字尾遞增運算子 ++。像這樣的型別進入某些 STL 容器中可以作為迭代器，或者進入陣列中作為指標。無論哪一種方式，都可以參照 T 作為迭代器型別。

請注意，begin_iter 和 end_iter 指定了某些容器中的開頭和末尾位置。遞增運算子 ++ 知道如何從容器中的一個位置移動到下一個位置。因此，無須第三個形參即可指定容器本身。在下面程式的程式碼清單中可以看到 print 函數的程式碼。

該程式的 main 函數演示了print函數的兩種用法，其中一個用於 string 陣列，另一個用於 int 型別的陣列。 
// This program demonstrates how iterators and related concepts can be used to write code that works with arrays and STL containers.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template<typename T>

void print(T begin_iter, T end_iter)
{
    auto iter = begin_iter;
    while (iter != end_iter)
    {
        cout << *iter << ";
        iter++;
    }
    cout << endl;
}
int main()
{
    // Print an array of strings
    string names[]{ "Anna", "Bob", "Chuck" };
    print(begin(names), end(names));
    // Print a vector of integers
    vector<int> vec{ 10, 20, 30 };
    print(begin(vec), end(vec));
    return 0;
}
程式輸出結果:

Anna Bob Chuck
10 20 30

vector容器

表 4 列出了向量類別範本的一些成員函數。其中一些接收疊代器作為形參，而另外一些則返回疊代器作為結果。

表 4 vector 類的成員函數精選
成員函數 描 述
at(position) 返回向量中position位置的元素的值。範例：
x = vect.at(5);
該語句可以將向量中位置5的元素的值賦給變數x
back() 返回對向量中最後一個元素的參照。範例：
cout << vect.back() << endl;
begin() 返回指向向量第一個元素的疊代器。範例：
iter = vect.begin();
capacity () 返回在不分配額外記憶體的情況下，向量中可以儲存的元素的最大數量。它和 size 成員函數返回的值並不相同。範例：
x = vect.capacity();
該語句可以將向量的容量值賦給變數 x
clear() 清除向量中的所有元素。範例：
vect.clear();
該語句可以將 vect 向量中的元素全部刪除掉
empty() 如果向量為空則返回 true，否則返回 false。範例：
if (vect.empty())
cout<< "The vector is empty.";
end() 返回指向向量最後一個元素後面位置的疊代器。範例：
iter = vect.end();
erase(iter) 導致疊代器 iter 指向的向量元素被刪除。範例：
vect.erase(iter);
erase(iterl, iter2) 導致疊代器 iter1 和 iter2 指定的範圍中的所有向量元素都被刪除。範例：
vect.erase(iter1, iter2);
front() 返回對向量中第一個元素的參照。範例：
cout << vector.front() << endl;
insert(iter,value) 將一個元素插入到向量中。範例：
vect.insert(iter, x);
該語句可以將值 x 插入到由疊代器 iter 指向的元素的前面
insert(iter, n，value) 將 value 的 n 個副本插入到向量中。插入的位置就在由疊代器 iter 指向的位置前面。 範例：
vect.insert(iter, 7, x);
該語句可以將值 x 的 7 個副本插入到由疊代器 iter 指向的元素前面
pop_back() 從向量中刪除最後一個元素。範例：
vect.pop back();
該語句可以將 vect 向量的最後一個元素刪除掉，這也意味著其大小會被減去 1
push_back(value) 將 value 儲存為向量最後一個元素的新值。如果該向量的容量已經被填滿，那麼它會自動調整大小。範例：
vect.push back(7);
該語句可以將 vect 向量最後一個元素的值儲存為 7
reverse() 反轉向量中元素的順序。最後一個元素變成第一個元素，而第一個元素則變成最後 一個元素。範例：
vect.reverse();.
resize(n) resize(n,value) 調整向量的大小，使它擁有 n 個元素，其中 n 大於向量的當前大小。如果包含了可選的 value 引數，則每個新元素都將使用該值進行初始化。範例，假設 vect 向量當 前包含 4 個元素：
vect.resize(6,99);
該語句可以給向量新增 2 個元素，並且每個新元素都將被初始化為 99
size() 返回 vector 向量中元素的個數。範例：
cout << vector.size() << endl;
swap(vector2) 將當前向量的內容和 vectors 向量的內容交換。範例：
vectl.swap(vect2);
該語句可以交換向量 vect1 和 vect2 的內容

演算法

STL 提供的演算法被實現為函數模板，並可對容器的元素執行各種操作。在 STL 中有很多演算法，表 5 僅列出了其中的很少一部分（該表僅給出了一般說明）。

表 5 STL演算法
算 法 描 述
binary_search 對某個物件執行二分搜尋，如果找到物件則返回 true，否則返回 false。範例：
binary search(iter1, iter2, value);
在該語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一個 元素，iter2 指向範圍中最後一個元素之後）。語句對元素範圍執行二分搜尋，搜尋 value。binary_search 函數在找到元素的情況下返回 true，如果未找到元素則返回 false
count 返回一個值出現在一個範圍內的次數。範例：
number = count(iter1, iter2, value);
在該語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一個 元素，iter2 指向範圍中最後一個元素之後）。該語句返回 value 出現在元素範圍內的次數
for_each 為容器中的每個元素執行一個函數。範例：
for each(iter1, iter2, func);
在這個語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一 個元素，iter2 指向範圍中的最後一個元素之後）。第 3 個引數 func 是函數的名稱。 該語句為範圍中的每個元素呼叫函數 func，將該元素作為引數傳遞
find 在容器中查詢匹配值的第一個物件並返回一個疊代器。範例：
iter3 = find(iter1, iter2, value);
在該語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一個 元素，iter2 指向範圍中最後一個元素之後）。語句在元素範圍內搜尋 value。如果找到了該值，則函數將返回一個疊代器到包含它的元素，否則返回疊代器 iter2
max_element 返回範圍中最大物件的疊代器。範例：
iter3 = max element(iter1, iter2);
在該語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一個 元素，iter2 指向範圍中最後一個元素之後）。該語句返回範圍中包含最大值的元素的疊代器
min_element 返回範圍中最小物件的疊代器。範例：
iter3 = min element(iter1, iter2);
在該語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一個 元素，iter2 指向範圍中最後一個元素之後）。該語句返回範圍中包含最小值的元素的疊代器
random_shuffle 隨機重排容器中的元素。範例：
random shuffle(iter1, iter2);
在這個語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一 個元素，iter2 指向範圍中最後一個元素之後）。該語句可隨機地重新排列範圍中的元素
sort 對某個範圍中的元素進行排序。範例：
sort (iter1, iter2);
在這個語句中，iter1 和 iter2 定義了容器中的元素範圍（iter1 指向範圍中的第一 個元素，iter2 指向範圍中最後一個元素之後）。該語句將按升序對範圍中的元素進行排序。
注意，STL 演算法需要包含 algorithm 標頭檔案才能使用。