C++ Primer Plus 學習筆記：STL 迭代器完整指南

為什麼需要迭代器？

模板使算法獨立於數據類型，而迭代器則使算法獨立於容器類型。這是 STL 實現泛型編程的核心機制之一——算法只需與迭代器交互，而不關心底層容器的具體實現。

迭代器的五大類型

根據功能強弱，迭代器分為五類，形成嚴格的層次結構：

1. 輸入迭代器：支援單向讀取，如 istream_iterator
2. 輸出迭代器：支援單向寫入，如 ostream_iterator
3. 正向迭代器：可多次讀寫，單向移動，如 forward_list
4. 雙向迭代器：可雙向移動，如 list、set、map
5. 隨機訪問迭代器：支援任意跳躍，如 vector、deque、數組指針

層次結構與算法適用性

高層迭代器包含低層迭代器的所有功能。編寫算法時，應盡可能使用要求最低的迭代器，以擴大適用容器範圍：

• find() 只需輸入迭代器，故適用於所有可讀容器
• sort() 需隨機訪問迭代器，故僅適用於 vector、deque 等

注意：迭代器類型是概念而非具體類型，任何滿足需求的類型（如原始指針）皆可作為迭代器使用。

迭代器實戰示例

1. 指針作為迭代器

#include <iostream>
#include <algorithm>
using namespace std;

#define SIZE 100
int iarray[SIZE];

int main() {
    iarray[20] = 50;
    int* ip = find(iarray, iarray + SIZE, 50);
    if (ip == iarray + SIZE)
        cout << "50 not found in array" << endl;
    else
        cout << *ip << " found in array" << endl;
    return 0;
}

2. 流迭代器與 copy 算法

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

void Display(vector<int>& v, const char* s) {
    cout << endl << s << endl;
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, "\t"));
    cout << endl;
}

int main() {
    vector<int> collection(10);
    for (int i = 0; i < 10; ++i)
        collection[i] = rand() % 10000;

    Display(collection, "Before sorting");
    sort(collection.begin(), collection.end());
    Display(collection, "After sorting");
    return 0;
}

3. 插入迭代器：front_inserter、back_inserter、inserter

#include <iostream>
#include <algorithm>
#include <list>
#include <iterator>
using namespace std;

int iArray[5] = {1, 2, 3, 4, 5};

void Display(list<int>& v, const char* s) {
    cout << s << endl;
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}

int main() {
    list<int> iList;
    copy(iArray, iArray + 5, front_inserter(iList));  // 反序插入
    Display(iList, "Before find and copy");

    auto p = find(iList.begin(), iList.end(), 3);
    copy(iArray, iArray + 2, inserter(iList, p));  // 在 3 前插入 1,2
    Display(iList, "After find and copy");
    return 0;
}

4. 容器迭代器典型用法

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> intVector(100);
    intVector[20] = 50;
    auto intIter = find(intVector.begin(), intVector.end(), 50);
    if (intIter != intVector.end())
        cout << "Vector contains value " << *intIter << endl;
    else
        cout << "Vector does not contain 50" << endl;
    return 0;
}

總結

迭代器是 STL 算法與容器之間的橋樑，理解其分類、層次結構及使用場景，是掌握 STL 泛型編程的關鍵。實際開發中，優先選擇 auto 推導迭代器類型，善用 begin()/end()、cbegin()/cend() 及各類插入迭代器，能顯著提升代碼的通用性與可維護性。