C++ STL：標準庫中的容器類和演算法

一、STL簡介

STL（Standard Template Library）是C++標準庫的一部分，是一種基於模板的泛型編程技術，提供了一系列高效、可重用、通用的演算法、容器和函數對象。STL以一種通用且可擴展的方式提供了許多數據結構和演算法。STL的設計遵循了泛型編程的原則，可以輕鬆地擴展或修改數據結構與演算法，使得程序員可以快速地開發高質量、高效率的程序。

二、STL組成

STL主要由三個部分組成：容器、演算法和迭代器。

1. 容器

容器是存儲數據的對象，也稱為數據結構。STL庫提供了多種不同類型的容器，適合於不同的應用場景，包括：

• 序列容器（如vector、deque和list）：存儲線性數據，按照插入順序排列。
• 關聯容器（如set、map和multimap）：存儲按照一定規則排序的數據。
• 容器適配器（如stack、queue和priority_queue）：是實現特定數據結構的一種容器。

//示例代碼：vector容器使用
#include 
#include 
using namespace std;

int main(){
    // 定義一個整型vector，名為vec
    vector vec;
    vec.push_back(10); // 在vec的尾部插入10
    vec.push_back(20); // 在vec的尾部插入20
    vec.push_back(30); // 在vec的尾部插入30

    // 輸出vec的所有元素
    for(auto i : vec){
        cout << i << " ";
    }
    return 0;
}

2. 演算法

演算法是STL的核心部分，提供了一系列通用的演算法，包括搜索、排序、遍歷、拷貝、替換等。這些演算法都是基於迭代器實現的，使得很容易將它們與任意容器結合使用。

• 常用演算法：sort、find、count等。

//示例代碼：使用sort演算法對vector進行排序
#include 
#include 
#include 
using namespace std;

int main(){
    vector vec = {5, 3, 6, 2, 7, 1, 4};

    // 列印排序前的vector
    cout << "before sorting: ";
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;

    // 對vector進行排序
    sort(vec.begin(), vec.end());

    // 列印排序後的vector
    cout << "after sorting: ";
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

3. 迭代器

迭代器是一種抽象的訪問和遍歷容器（或其他數據序列）中的元素的對象。迭代器提供了一種通用的方法來遍歷容器內的元素，容器的具體實現方式對用戶是透明的。在STL中，迭代器被視為通用的介面，可以應用於所有容器類型，甚至是用戶自定義的容器類型或數據結構。

• 迭代器分類：輸入迭代器、輸出迭代器、正向迭代器、雙向迭代器、隨機訪問迭代器。

//示例代碼：迭代器遍歷vector
#include 
#include 
using namespace std;

int main(){
    vector vec{1, 2, 3, 4, 5};

    // 使用迭代器遍歷vec
    vector::iterator iter;
    for (iter = vec.begin(); iter != vec.end(); iter++) {
        cout << *iter << " ";
    }

    return 0;
}

三、C++11中新增容器

C++11標準中新增了多種容器類型，包括了更多的序列容器和關聯容器，有些容器實現類似於現有的容器，但還有一些提供了新的功能和更好的性能：

• array：固定大小的數組。
• forward_list：單向鏈表，相比於list，佔用更少的內存，但某些操作可能更慢。
• unordered_set和unordered_map：無序的關聯容器，通過哈希表實現，具有快速查詢的特點，但可能犧牲一定的空間。

//示例代碼：使用unordered_map容器存儲鍵值對
#include 
#include 
using namespace std;

int main(){
    // 創建一個空的unordered_map
    unordered_map mymap;

    // 向unordered_map中插入元素
    mymap.emplace("apple", 1);
    mymap.emplace("orange", 2);
    mymap.emplace("banana", 3);

    // 遍歷unordered_map中的元素
    for (auto& kv : mymap) {
        cout << kv.first << ": " << kv.second << '\n';
    }

    return 0;
}

四、STL的優點和缺點

1. 優點

• STL提供了大量的通用演算法和容器，可大大減少程序員的開發量，提高開發效率。
• STL使用模板技術，使得演算法和容器的實現與數據類型的無關，可重用性和可擴展性極高。
• STL的迭代器機制提供了一種通用的遍歷方式，使得任何容器類型都可以進行遍歷。

2. 缺點

• STL提供的通用演算法和容器並不一定是最高效的，程序員需要針對具體情況選擇合適的數據結構和演算法。
• STL的語法相對比較複雜，使用起來需要一定的學習成本。
• STL在處理大量數據時，可能出現內存佔用較高的情況。