跳至主要内容

走進 STL：快速導覽 C++ 標準模板庫的核心要素

STL 是什麼？​

STL(Standard Template Library) 是 C++ 程式設計語言中一個非常重要和強大的函式庫，它提供了一系列資料結構，如向量(vector)、列表(list)和雜湊表(map)，以及搜尋、排序等演算法和通用函式，可用於大幅簡化 C++ 程式開發。 STL 遵循泛型程式設計(Generic Programming) 的理念， 基於模板(Template) 來實作各種資料結構與演算法，這使得 STL 可以處理任何符合特定需求的資料類型，而不局限於特定的類型。這種泛型性增加了 STL 的可重用性和靈活性。

STL 的核心主要由以下幾大組建所組成：

  • 容器 Container
  • 演算法 Algorithms
  • 迭代器 Iterator
  • 仿函數 Functor
  • 適配器 Adaptor

容器 Container​

容器(Container)是 STL 中用於存放資料的資料結構類別模板，每種容器都提供了特定資料結構的功能。

容器類型​

STL 提供了以下幾種類型的容器：

  • 序列容器（Sequence Containers）
    • vector：表示可動態調整大小的陣列。支持快速隨機存取，但在中間插入或刪除元素可能會比較慢。
    • deque：和 vector 相似，但設計上支持在頭部和尾部高效插入和刪除。
    • list：雙向鏈表，支持在任何位置快速插入和刪除，但不支持快速隨機存取。
    • forward_list：僅支持向前遍歷的鏈表，相比 list 更節省空間。
  • 關聯容器（Associative Containers）
    • set：基於紅黑樹實現的集合，元素唯一，自動排序。
    • multiset：與 set 相似，但元素可以重複。
    • map：鍵-值對的集合，其中的鍵唯一，基於紅黑樹。
    • multimap：與 map 相似，但一個鍵可以關聯多個值。
  • 無序關聯容器（Unordered Associative Containers）
    • unordered_set：基於哈希表的集合，元素唯一，不自動排序，提供快速查找。
    • unordered_multiset：與 unordered_set 相似，但元素可以重複。
    • unordered_map：基於哈希表的鍵-值對集合，提供快速查找。
    • unordered_multimap：與 unordered_map 相似，但一個鍵可以關聯多個值。

容器操作方法​

所有 STL 容器都提供了一些共通的操作，如：

  • size()：返回容器中元素的數量。
  • empty()：判斷容器是否為空。
  • insert()：插入元素到容器中。
  • erase()：刪除容器中的元素。
  • clear()：移除容器中所有元素。

如何使用容器​

STL 容器的使用方式非常簡單。要使用 STL 容器，我們首先需要包含 STL 標頭檔。例如，要使用向量資料結構，我們需要包含以下標頭檔：

#include <vector>

包含標頭檔後，我們就可以使用 STL 中提供的資料結構、演算法和函式。例如，以下程式碼使用向量資料結構來存放一組整數：

#include <vector>

int main() {
  std::vector<int> numbers = {1, 5, 3, 4, 3};

  // 迭代器
  for (auto it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }

  // 演算法
  std::sort(numbers.begin(), numbers.end());

  // 函式
  std::cout << std::count(numbers.begin(), numbers.end(), 3) << std::endl;

  return 0;
}

// 1 5 3 4 3
// 1 3 3 4 5
// 2

迭代器 Iterator​

迭代器(Iterator)在 STL 中是一種可以用於訪問、遍歷和操作容器中元素的物件。迭代器是一種廣義的指針，大多數的時候，我們可以把它視為指向容器中元素的普通指針來使用，但它具有比普通指針更強大的功能。

以下整理迭代器的幾個特點：

  • 可以指向容器中的元素。
  • 可以遞增或遞減，以訪問序列中的相鄰元素。
  • 可以比較兩個迭代器，以確定它們指向的元素的位置。
  • 可以用於將各種 STL 算法套用在 STL 容器上，例如 std::sort 和 std::find。

標準容器迭代器的運算符​

以下是一些常見的標準容器迭代器運算符：

  • *iter : 解引用迭代器，獲取其指向的元素的值。
  • iter->member: 如果迭代器指向的是結構體或類型的物件，則可以使用此運算符訪問其成員。
  • iter++ or ++iter: 將迭代器遞增，指向序列中的下一個元素。
  • iter-- or —-iter: 將迭代器遞減，指向序列中的前一個元素(僅限雙向和隨機存取迭代器)。
  • iter1 - iter2 or iter1 + iter2: 對迭代器進行算術運算，返回距離(僅限隨機存取迭代器)。
  • iter1 == iter2: 比較兩個迭代器，確定它們是否指向相同的元素。
  • iter1 != iter2: 比較兩個迭代器，確定它們是否指向不同的元素。

迭代器類型​

STL 提供了五種基本的迭代器類型：

迭代器類型迭代器功能範例
輸入迭代器 Input iterator允許讀取序列中的元素，只能單向移動。istream
輸出迭代器 Output iterator允許寫入序列中的元素，也只能單向移動。ostream, inserter
前向迭代器 Forward iterator支持單向訪問和修改forward_list
雙向迭代器 Bidirectional iterator除了前向迭代器的功能外，還可以向後移動。list, set, multiset, map, multimap
隨機迭代器 Random access iterator提供直接訪問任意元素的能力，功能最強。vector, deque, array, string

其他迭代器​

除了基本的迭代器類型外，STL 也提供了一些特殊用途的迭代器：

迭代器類型迭代器功能範例
逆向迭代器 Reverse iterator允許以相反的順序遍歷容器。vector, list, deque
插入迭代器 Insert iterator專為在容器中插入元素而設計，不進行元素訪問。inserter, back_inserter, front_inserter
流迭代器 Stream iterator用於從流中讀寫數據。istream_iterator, ostream_iterator
移動迭代器 Move iterator允許元素的移動而非複製，用於優化性能。make_move_iterator

使用範例​

下面提供一個使用迭代器的範例遍歷與操作容器元素的範例:

#include <vector>
#include <list>
#include <iostream>
#include <iterator> // 為了使用 inserter 和 fill_n

using namespace std;

int main() {
    // 遍歷vector
    vector<int> v = {1, 2, 3, 4, 5};
    for(auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " "; // 輸出: 1 2 3 4 5
    }
    cout << endl;

    // 反向遍歷
    for(auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " "; // 輸出: 5 4 3 2 1
    }
    cout << endl;

    // 修改list中的元素
    list<string> lst = {"apple", "banana", "orange"};
    auto it = lst.begin();
    *it = "pear"; // lst變為 {"pear", "banana", "orange"}

    // 使用inserter插入元素
    vector<int> v2;
    fill_n(inserter(v2, v2.begin()), 5, 100); // v2變為{100, 100, 100, 100, 100}

    return 0;
}

演算法 Algorithms​

STL 提供了豐富的演算法函數,能夠在各種容器上執行不同的操作。這些演算法函數定義在 <algorithm> 和 <numeric> 標頭檔案中。

根據功能，演算法大致上可以分為以下幾類：

非變動序列操作​

這些演算法不會修改操作對象,通常用於查詢或條件測試。

演算法功能範例時間複雜度
all_of檢查範圍內的所有元素是否都滿足某個條件all_of(v.begin(), v.end(), pred)O(n)
any_of檢查範圍內是否至少有一個元素滿足某個條件any_of(v.begin(), v.end(), pred)O(n)
none_of檢查範圍內是否沒有元素滿足某個條件none_of(v.begin(), v.end(), pred)O(n)
find在範圍內尋找第一個等於特定值的元素find(v.begin(), v.end(), value)O(n)
find_if在範圍內尋找第一個滿足條件的元素find_if(v.begin(), v.end(), pred)O(n)
count計算範圍內等於特定值的元素數量count(v.begin(), v.end(), value)O(n)
count_if計算範圍內滿足某個條件的元素數量count_if(v.begin(), v.end(), pred)O(n)
equal檢查兩個範圍內的元素是否全部相等equal(v1.begin(), v1.end(), v2.begin())O(n)
search在範圍內尋找第一次出現的另一個範圍的序列search(v.begin(), v.end(), subv.begin(), subv.end())O(n*m)

變動序列操作​

這些演算法會修改操作對象。

演算法功能範例時間複雜度
copy複製範圍內的元素到另一範圍copy(v.begin(), v.end(), dest.begin())O(n)
copy_n複製指定數量的元素到另一範圍copy_n(v.begin(), n, dest.begin())O(n)
copy_if根據條件複製元素到另一範圍copy_if(v.begin(), v.end(), dest.begin(), pred)O(n)
copy_backward反向複製元素到另一範圍copy_backward(v.begin(), v.end(), dest.end())O(n)
move移動範圍內的元素到另一範圍move(v.begin(), v.end(), dest.begin())O(n)
move_backward反向移動元素到另一範圍move_backward(v.begin(), v.end(), dest.end())O(n)
swap交換兩個元素的值swap(a, b)O(1)
transform將範圍內的元素轉換後存儲到另一範圍transform(v.begin(), v.end(), dest.begin(), op)O(n)
remove移除等於特定值的所有元素remove(v.begin(), v.end(), value)O(n)
remove_if移除滿足條件的所有元素remove_if(v.begin(), v.end(), pred)O(n)
fill將範圍內的所有元素設置為特定值fill(v.begin(), v.end(), value)O(n)
fill_n將指定數量的元素設置為特定值fill_n(v.begin(), n, value)O(n)
replace替換所有等於特定值的元素replace(v.begin(), v.end(), old_val, new_val)O(n)
replace_if根據條件替換元素replace_if(v.begin(), v.end(), pred, new_val)O(n)
unique移除連續重複的元素並返回結束迭代器unique(v.begin(), v.end())O(n)
reverse反轉範圍內的元素順序reverse(v.begin(), v.end())O(n)
rotate將範圍內的元素循環左移rotate(v.begin(), v.middle(), v.end())O(n)
random_shuffle隨機重排範圍內的元素random_shuffle(v.begin(), v.end())O(n)

分割操作​

這些演算法會將序列中的元素重新排列。

演算法功能範例時間複雜度
is_partitioned檢查範圍內的元素是否符合某個條件，已分割成兩部分is_partitioned(v.begin(), v.end(), pred)O(n)
partition根據條件將範圍內的元素重新排列，滿足條件的元素排在前面partition(v.begin(), v.end(), pred)O(n)
stable_partition根據條件分割元素，保持相對順序不變stable_partition(v.begin(), v.end(), pred)O(n log n)
partition_copy根據條件分割元素到兩個不同的容器partition_copy(v.begin(), v.end(), dest1.begin(), dest2.begin(), pred)O(n)
partition_point返回一個迭代器，指向分割後第二部分的開始位置partition_point(v.begin(), v.end(), pred)O(log n)

排序操作​

這些演算法用於對容器中的元素進行排序。

演算法功能範例時間複雜度
sort對範圍內的元素進行排序sort(v.begin(), v.end())O(n log n)
stable_sort對範圍內的元素進行穩定排序，保持相等元素的順序stable_sort(v.begin(), v.end())O(n log n)
partial_sort對範圍內的部分元素進行排序，使得指定的部分是已排序的partial_sort(v.begin(), v.middle(), v.end())O(n log k)
nth_element重新排列範圍內的元素，使得第n個元素會在它的最終排序位置上nth_element(v.begin(), v.nth(), v.end())O(n)

二分搜尋操作​

二分搜尋相關的演算法需要對操作的序列進行排序，通常搭配 sort 使用。

演算法功能範例時間複雜度
lower_bound找到範圍內第一個大於或等於指定值的元素位置lower_bound(v.begin(), v.end(), value)O(log n)
upper_bound找到範圍內第一個大於指定值的元素位置upper_bound(v.begin(), v.end(), value)O(log n)
equal_range同時獲得lower_bound和upper_bound，返回一對迭代器equal_range(v.begin(), v.end(), value)O(log n)
binary_search檢查一個已排序範圍是否包含某個元素binary_search(v.begin(), v.end(), value)O(log n)

合併操作​

合併相關的演算法需要對操作的序列進行排序，通常搭配 sort 使用。

演算法功能範例時間複雜度
merge合併兩個已排序的序列，結果也是排序的merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin())O(n + m)
inplace_merge在序列中合併兩個連續的已排序範圍inplace_merge(v.begin(), v.middle(), v.end())O(n log n)
includes檢查一個已排序範圍是否包含另一個已排序範圍的所有元素includes(v1.begin(), v1.end(), v2.begin(), v2.end())O(n + m)
set_union合併兩個已排序範圍，結果集包含每個範圍中的每個元素，不重複set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin())O(n + m)
set_intersection獲得兩個已排序範圍的交集set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin())O(n + m)
set_difference獲得兩個已排序範圍的差集，即存在於第一個範圍但不在第二個範圍的元素set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin())O(n + m)

堆操作​

這些演算法用於在向量上執行堆操作

演算法功能範例時間複雜度
make_heap建立一個 heap，將範圍內的元素重新排列成 heap 的形式make_heap(v.begin(), v.end())O(n)
sort_heap對一個 heap 進行排序，將 heap 轉換成一個有序的序列sort_heap(v.begin(), v.end())O(n log n)
push_heap將新元素加入到 heap 中並保持 heap 的特性v.push_back(value); push_heap(v.begin(), v.end())O(log n)
pop_heap從 heap 中移除最大元素（或最小元素），並保持 heap 的特性pop_heap(v.begin(), v.end()); v.pop_back()O(log n)

遍歷統計操作​

這些演算法定義在 <numeric> 中

演算法功能範例時間複雜度
accumulate計算給定範圍內所有元素的總和或累積結果accumulate(v.begin(), v.end(), initial_value)O(n)
inner_product計算兩個範圍的內積，或進行對應元素的乘積和其後的累加操作inner_product(v1.begin(), v1.end(), v2.begin(), initial_value)O(n)
partial_sum計算給定範圍內各個子範圍的總和，並將中間結果存儲到另一個範圍partial_sum(v.begin(), v.end(), result.begin())O(n)
adjacent_difference計算連續元素之間的差異，並將結果存儲到另一個範圍adjacent_difference(v.begin(), v.end(), result.begin())O(n)
iota在範圍內填充連續遞增或遞減的值iota(v.begin(), v.end(), start_value)O(n)

仿函數 Functor​

仿函數(functor)又稱之為函數物件(function object)，泛指任何可以使用函數調用運算子 () 的物件。簡單來說來說，就是重載(overload)運算子 operator() 的 struct 或類別的實例。仿函數可以被當作函數來使用，與一般函數不同的是，仿函數可以擁有內部狀態和其他成員函數，通常用於封裝與特定操作相關的狀態或行為。

以下舉例一個簡單的仿函數:

struct Sum {
    int operator()(int a, int b) {
        return a + b;
    }
};

我們可以像呼叫一般函數一樣來使用它:

Sum add;
int result = add(3, 4); // result = 7

而且仿函數還可以有自己的內部狀態:

struct Multiplier {
    int factor;
    Multiplier(int f) : factor(f) {}
    int operator()(int a) {
        return a * factor;
    }
};

為什麼要使用仿函數呢？​

  1. 帶有記憶的功能：

  • 仿函數可以存儲狀態。比如，如果你想要一個可以記住之前加過的總和的加法器，仿函數就很方便。

  • 範例：創建一個計數器，每次調用時增加並記住總和。

    class Counter {
    public:
        Counter(): count(0) {}
        int operator()() { return ++count; }

    private:
        int count;
    };

    Counter counter;
    cout << counter(); // 輸出 1
    cout << counter(); // 輸出 2

  1. 靈活調整行為：

    • 你可以為不同的情況創建不同的仿函數物件，每個物件有自己的行為和狀態。
    • 範例：創建一個加法器，可以設定初始加數。
    class Adder {
    public:
        Adder(int number): number(number) {}
        int operator()(int x) const { return x + number; }

    private:
        int number;
    };

    Adder addFive(5);
    cout << addFive(3); // 輸出 8

  2. 易於與STL算法結合：

    • STL算法，如 sort,find_if 等，通常接受函數或仿函數作為參數，這使得使用仿函數可以更自然地與STL集成。
    • 範例：使用仿函數來自定義排序條件。
    std::vector<int> v = {1, 5, 3, 4, 2};
    std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // 用Lambda表達式，其實也是一種仿函數

適配器 Adaptor​

適配器(Adaptor)在程式設計中是一種結構型模式，它允許將一個類別的接口轉換成客戶端期望的另一個接口。適配器讓原本因介面不兼容而不能一起工作的類可以一起工作。在 STL 中，適配器用於變換容器、迭代器或函數等的行為。

適配器的類型​

在C++中，適配器主要有三種類型：

  1. 容器適配器：
    • 這些適配器將底層的容器類型轉換成提供特定接口的容器類型，例如 stack、queue 和 priority_queue 。
    • 例子：

      • stack適配器可以將vector、deque或list等類型作為其底層容器。

      • 使用stack適配器：

        std::stack<int> s;
        s.push(1);
        s.push(2);
        s.push(3);
        while (!s.empty()) {
            std::cout << s.top() << std::endl;
            s.pop();
        }
  2. 迭代器適配器：
    • 改變迭代器的行為，例如reverse_iterator、insert_iterator、stream_iterator等。
    • 例子：

      • 使用reverse_iterator來反向遍歷容器：

        std::vector<int> v = {1, 2, 3, 4, 5};
        for (auto it = v.rbegin(); it != v.rend(); ++it) {
            std::cout << *it << " ";
        }
  3. 函數適配器：
    • 這些適配器用來改變函數或者函數物件的呼叫方式，例如bind、function、not1/not2等。
    • 例子：

      • 使用bind來創建新的函數物件：

        auto adder = std::bind(std::plus<int>(), std::placeholders::_1, 100);
        std::cout << adder(5); // 輸出 105

Reference​