【C++】—— list迭代器

前言

​ C++ 中的 STL（标准模板库）为我们提供了多种容器，vector、list以及stack等；

​ 对于这些容器STL提供了统一的遍历方法，那就是迭代器——可以高效地进行插入和删除操作。迭代器是遍历这些容器的重要工具，本篇文章将详细讲解 C++ STL 中 list 容器的迭代器（iterator）使用方式、类型以及相关的注意事项。

1、list容器

​ list 是一个双向链表容器，和 vector 和 string 不同，它不是基于连续内存的数组结构，而是基于节点（node）的链表。每个节点包含一个数据元素以及指向前后节点的指针。由于这种结构，list 在中间进行插入或删除元素时效率极高，但随机访问性能较差。因此，list 适合需要频繁插入和删除的场景。

2、迭代器

​ 在 C++ STL 中，迭代器（iterator）是用于遍历容器元素的对象。你可以将迭代器类比为一个指针，它指向容器中的元素。通过迭代器，我们能够对容器中的元素进行遍历、读取、修改等操作。

在 list 容器中，迭代器类型主要有以下几种：

• 双向迭代器（Bidirectional Iterator）：list 支持双向迭代器，意味着我们可以从前向后遍历，也可以从后向前遍历。
• 常量迭代器（const_iterator）：用来指向常量的迭代器，不能通过它修改所指向的元素。
• 逆向迭代器（reverse_iterator）：用于从容器的尾部向头部遍历。
• 常量逆向迭代器（const_reverse_iterator）：不能修改元素的逆向迭代器。

3、迭代器基本用法

在 C++ 中，我们可以使用 begin() 和 end() 方法获取 list 的迭代器。这些迭代器可以用来遍历 list 中的所有元素。

3.1、获取迭代器

• list<T>::begin()：返回指向容器第一个元素的迭代器。
• list<T>::end()：返回指向容器尾后元素的迭代器（该位置之后没有元素）。
• list<T>::rbegin()：返回指向最后一个元素的逆向迭代器。
• list<T>::rend()：返回指向第一个元素之前位置的逆向迭代器。

3.2、使用迭代器遍历

通过 begin() 和 end() 获取的迭代器可以在循环中进行遍历：

#include <iostream>
#include <list>

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

    // 正向遍历
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it) {
        std::cout << *it << " ";  // 输出迭代器指向的值
    }
    std::cout << std::endl;

    // 逆向遍历
    for (std::list<int>::reverse_iterator rit = mylist.rbegin(); rit != mylist.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，我们首先正向遍历了 list，输出 1 2 3 4 5。接着使用逆向迭代器 rbegin() 和 rend() 逆向遍历，输出 5 4 3 2 1。

3.3、修改元素

通过非 const 的迭代器，可以修改 list 中的元素。例如：

std::list<int>::iterator it = mylist.begin();
*it = 10;  // 将第一个元素修改为10

如果是 const_iterator，则无法修改所指向的元素，编译时会报错。

4、迭代器属性

4.1、双向迭代器

list 的迭代器是 双向迭代器，这意味着你可以使用 ++ 运算符向前移动迭代器，使用 -- 运算符向后移动迭代器。

++it;  // 向前移动到下一个元素
--it;  // 向后移动到前一个元素

但是，由于 list 不是随机访问的容器，所以 list 的迭代器不支持随机访问运算符（如 it + 1 是非法操作）。

4.2、迭代器失效问题

4.2.1、插入元素与迭代器失效

list 的一个重要特性是，它的迭代器在元素的插入和删除过程中相对稳定。也就是说，插入和删除操作不会使已有的迭代器失效（指向已删除元素的迭代器除外）。例如：

#include <iostream>
#include <list>

int main() {
    std::list<int> mylist = {1, 2, 3, 4, 5};
    std::list<int>::iterator it = mylist.begin();
    ++it;  // it 指向第二个元素（2）

    mylist.insert(it, 10);  // 在第二个元素前插入10

    // 插入后，it 仍然有效，指向原来的第二个元素（现在是3）
    std::cout << *it << std::endl;  // 输出3

    return 0;
}

如上所示，插入元素并不会使迭代器失效。

4.2.2、删除元素与迭代器失效

删除元素后，指向被删除元素的迭代器会失效，因此在删除元素时要特别注意迭代器的使用。通常，删除操作后需要更新迭代器：

it = mylist.erase(it);  // 删除it指向的元素，并返回下一个有效的迭代器

5、常见迭代器操作

5.1、插入元素

可以使用 insert() 方法在指定迭代器位置插入元素：

mylist.insert(it, value);  // 在it指向的位置之前插入value

5.2、删除元素

使用 erase() 方法删除指定位置的元素：

it = mylist.erase(it);  // 删除it指向的元素，并返回指向下一个元素的迭代器

5.3、清除数据

使用 clear() 清空整个 list，此操作后所有迭代器都会失效：

mylist.clear();

6、总结

​ C++ STL 中的 list 迭代器是操作 list 容器的关键工具，通过它我们可以进行遍历、插入、删除等操作。由于 list 是双向链表结构，它的迭代器支持双向遍历，但不支持随机访问。在进行插入和删除操作时，迭代器的使用需要格外小心，确保不使用失效的迭代器。

通过合理使用迭代器，你可以高效地操作 list 容器，实现高效的数据处理和管理。

使用时注意：

• 不要使用失效的迭代器：指向被删除元素或超过容器范围的迭代器是无效的，访问它们可能导致未定义行为。
• 随机访问不可用：与 vector 不同，list 迭代器不支持随机访问，因此不能使用 it + n 这样的操作。
• 使用 erase 和 insert 时需更新迭代器：当你在遍历 list 时删除元素，要确保正确地更新迭代器以避免访问无效位置。