Stl迭代器

[TOC]

1. STL 迭代器

在 C++ 的标准模板库（STL）中，迭代器是用来遍历或访问容器中元素的对象，类似于指针。它们提供了一种通用的方法来访问容器的内容，无论容器的底层实现是什么样的。¹

1.1 迭代器的作用

1. 访问容器元素：迭代器提供了一种方法来按顺序访问容器中的元素，而不必知道容器的内部结构。
2. 容器与算法的桥梁：STL 中的算法，如 sort, find, accumulate 等，通常通过迭代器与容器进行交互。
3. 支持泛型编程：迭代器使得编写可用于不同类型容器的通用代码成为可能。

1.2 为什么需要迭代器，即使有指针

虽然指针可以用于类似的目的，但迭代器更加通用和灵活。迭代器不仅仅局限于数组或类似线性存储结构，它们也适用于如树、图这样的复杂数据结构。此外，迭代器可以为容器提供更丰富的操作集合，而指针的操作通常非常基础。

迭代器和指针都用于访问和遍历数据结构中的元素，但迭代器提供了比指针更多的功能和灵活性。让我们通过比较在不同场景下使用迭代器和指针来理解这一点：

(1) 示例 1：使用指针访问数组

#include <iostream>

int main() {
    int arr[] = {1, 2, 3, 4, 5};

    // 使用指针遍历数组
    for (int* ptr = arr; ptr < arr + 5; ++ptr) {
        std::cout << *ptr << " ";
    }

    return 0;
}

在这个例子中，我们使用指针来遍历数组。这是指针的典型应用场景，但它仅限于线性数据结构，如数组。

(2) 示例 2：使用迭代器访问 STL 容器

#include <iostream>
#include <vector>
#include <list>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> lst = {1, 2, 3, 4, 5};

    // 使用迭代器遍历 vector
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用迭代器遍历 list
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，我们使用迭代器来遍历 std::vector 和 std::list。迭代器提供了一种统一的方式来访问不同的容器，无论它们的内部实现如何。同样的迭代器接口可以用于数组、链表、树、图等多种不同的数据结构，这是指针无法做到的。

1.3 为什么选择迭代器

• 通用性：迭代器提供了一种统一的接口来访问多种不同的容器，包括那些不能使用普通指针访问的容器（如标准库中的 std::set、std::map）。
• 安全性：迭代器可以被设计为更安全，例如，通过检查迭代器是否失效来避免潜在的运行时错误。
• 扩展性：迭代器可以提供比指针更多的操作，如反向遍历（使用反向迭代器）等。

总之，迭代器之所以重要，是因为它们提供了一种比指针更灵活、更安全、更通用的方法来访问和操作各种数据结构。

1.4 迭代器何时失效

迭代器可能在容器结构改变时失效。具体来说：

• 在向 vector 或 deque 添加元素时，如果发生内存重新分配，所有指向该容器元素的迭代器都将失效。
• 在删除元素时，指向被删除元素的迭代器以及该元素之后的所有迭代器都将失效。
• 对于 list 和 forward_list，迭代器只有在指向被删除元素时才失效。
• 对于关联容器如 set 和 map，通常只有指向被删除元素的迭代器会失效。

1.5 如何使用迭代器删除元素

在使用迭代器删除元素时，要特别注意更新迭代器，以防止使用失效的迭代器。下面是一个例子，展示如何使用迭代器从 std::vector 中删除元素：

#include <iostream>
#include <vector>

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

    for (auto it = vec.begin(); it != vec.end(); /* no increment here */) 
    {
        if (*it % 2 == 0) 
        {  // 删除偶数元素
            it = vec.erase(it);
        } 
        else 
        {
            ++it;
        }
    }

    // 打印剩余元素
    for (int val : vec) 
    {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，vec.erase(it) 删除了当前迭代器 it 指向的元素，并返回指向下一个元素的迭代器。这就是为什么在删除元素时不需要在循环中递增迭代器。如果在删除时递增了迭代器，就有可能跳过一些元素或尝试访问失效的迭代器。

但是上述代码会显得逻辑复杂，且容易出错，因此建议使用 erase-remove 来去除特定元素。

2. std 迭代器函数

std::next()

将迭代器前进到指定位置并返回指针

std::set<T>::iterator it = std::next(vec.begin(), 3);

std::advance()

将迭代器推进到指定位置（可前可后）

std::set<T>::iterator it = set.begin();
std::advance(it, 3);  // it本身被修改  

std::prev()

与上面的std::next()成一对，用于返回之前的位置。

auto it = std::prev(vec.begin(), 4);

参考文章²

1. 每天学点设计模式——迭代器模式 ↩︎

2. 来源：ChatGPT ↩︎