STL庫：C++數據結構與演算法

一、STL概述

C++ STL（Standard Template Library）是C++標準庫的重要組成部分，它是一組通用的模板類和函數，實現了大量的常用數據結構和演算法，為我們提供了高效、可靠和安全的工具，簡化了程序設計和開發。STL庫中包含了以下容器：

• 容器（Containers）
• 迭代器（Iterators）
• 演算法（Algorithms）
• 函數對象（Function Objects）
• 適配器（Adapters）

STL庫的設計理念是以泛型編程為基礎，將數據類型和演算法分開設計，使得數據結構和演算法可以獨立地發展和變換，從而實現代碼的可重用性和可擴展性。

二、容器

容器是用於存儲和管理數據的類模板，它們定義了一系列與數據操作有關的成員函數，可以快速地對數據進行插入、刪除、查找等操作。常用的STL容器有以下幾種：

1. vector

vector是一種動態數組，可以根據需要自動調整容量，實現高效的隨機訪問和插入/刪除操作。例如：

#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  return 0;
}

輸出結果為：1 2 3

2. list

list是一種雙向鏈表，可以在任何位置進行插入和刪除操作，但不支持隨機訪問。例如：

#include <iostream>
#include <list>
using namespace std;
int main() {
  list<int> l;
  l.push_back(1);
  l.push_back(2);
  l.push_back(3);
  for (auto iter = l.begin(); iter != l.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：1 2 3

3. map

map是一種關聯容器，可以將鍵值對（Key-Value）組合存儲，支持按照鍵值進行查找和刪除等操作。例如：

#include <iostream>
#include <map>
using namespace std;
int main() {
  map<string, int> m;
  m["apple"] = 1;
  m["banana"] = 2;
  m["orange"] = 3;
  for (auto iter = m.begin(); iter != m.end(); iter++) {
    cout << iter->first << " " << iter->second << endl;
  }
  return 0;
}

輸出結果為：

apple 1
banana 2
orange 3

三、迭代器

迭代器是一種通用的數據訪問方式，可以方便地遍歷STL容器中的元素，常用的迭代器類型有以下幾種：

1. Input Iterator

Input Iterator是一個只讀的迭代器，它可以對容器中的數據進行遍歷和讀取，例如：

#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<int> v = {1, 2, 3};
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：1 2 3

2. Output Iterator

Output Iterator是一個只寫的迭代器，它可以向容器中寫入數據，例如：

#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<int> v = {1, 2, 3};
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    *iter *= 2;
  }
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：2 4 6

3. Forward Iterator

Forward Iterator是一種單向的迭代器，它支持遞增和取值操作，例如：

#include <iostream>
#include <forward_list>
using namespace std;
int main() {
  forward_list<int> flist = {1, 2, 3};
  for (auto iter = flist.begin(); iter != flist.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：1 2 3

4. Bidirectional Iterator

Bidirectional Iterator是一種雙向的迭代器，它可以向前和向後遍歷容器中的元素，例如：

#include <iostream>
#include <list>
using namespace std;
int main() {
  list<int> l = {1, 2, 3};
  for (auto iter = l.rbegin(); iter != l.rend(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：3 2 1

5. Random Access Iterator

Random Access Iterator是一種隨機訪問的迭代器，可以快速定位到容器中的任意位置，並進行讀寫操作，例如：

#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<int> v = {1, 2, 3};
  cout << v[1] << endl; // 輸出 2
  v[1] = 4;
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：1 4 3

四、演算法

演算法是STL庫中非常重要的一部分，提供了大量的常用演算法，包括查找、排序、遍歷、合併等操作。

1. 查找

STL庫中提供了多種查找演算法，包括二分查找、線性查找、查找最大/最小值等。

例如，使用二分查找演算法：（前提是數據序列已經排好序）

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  int a[] = {1, 2, 3, 4, 5};
  cout << binary_search(a, a + 5, 4) << endl; // 輸出 1
  return 0;
}

2. 排序

STL庫中提供了多種排序演算法，包括快速排序、歸併排序、堆排序等，其中最常用的是快速排序。

例如，使用快速排序演算法：（vector會使用快排）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
  vector<int> v = {3, 1, 4, 2, 5};
  sort(v.begin(), v.end());
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：1 2 3 4 5

3. 遍歷

STL庫中提供了多種遍歷演算法，包括for_each、transform等，這些演算法可以對容器中的元素進行操作並輸出。

例如，使用for_each演算法將vector中的每個元素乘以2並輸出：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int n) {
  cout << n * 2 << " ";
}
int main() {
  vector<int> v = {1, 2, 3};
  for_each(v.begin(), v.end(), print);
  return 0;
}

輸出結果為：2 4 6

4. 合併

STL庫中提供了多種合併演算法，包括merge、set_union等，這些演算法可以將多個有序的序列合併成一個有序的序列。

例如，使用merge演算法將兩個vector合併成一個有序的序列並輸出：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
  vector<int> v1 = {1, 3, 5};
  vector<int> v2 = {2, 4, 6};
  vector<int> v3(v1.size() + v2.size());
  merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
  for (auto iter = v3.begin(); iter != v3.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：1 2 3 4 5 6

五、函數對象

函數對象是STL庫中的一種概念，是一種重載了運算符()的類，可以像函數一樣進行調用，可以用於演算法中的比較、計算等操作。

1. 比較函數對象

比較函數對象是一種用於比較兩個元素大小的函數對象，常用於sort、max_element等演算法中。

例如，比較函數對象的實現：

struct cmp {
  bool operator()(int a, int b) const {
    return a < b;
  }
};

使用比較函數對象對vector進行排序：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct cmp {
  bool operator()(int a, int b) const {
    return a < b;
  }
};
int main() {
  vector<int> v = {3, 1, 4, 2, 5};
  sort(v.begin(), v.end(), cmp());
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

輸出結果為：1 2 3 4 5

2. 計算函數對象

計算函數對象是一種用於計算表達式的函數對象，常用於accumulate等演算法中。

例如，計算函數對象的實現：

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