【C++】迭代器详解与失效机制

1. 迭代器详解

1.1 迭代器类型

• begin()/end()：正向迭代器

• cbegin()/cend()（C++11）：常量正向迭代器

• rbegin()/rend()：反向迭代器

• crbegin()/crend()（C++11）：常量反向迭代器

1.2 迭代器失效规则

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。

对于 vector 可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back 等。

#include <iostream> 
using namespace std; 
#include <vector> 
int main() 
{  
    vector<int> v{1,2,3,4,5,6};  
    auto it = v.begin();    
    // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容  
    // v.resize(100, 8);    
    // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变  
    // v.reserve(100);    
    // 插入元素期间，可能会引起扩容，而导致原空间被释放  
    // v.insert(v.begin(), 0);  
    // v.push_back(8);    
    // 给vector重新赋值，可能会引起底层容量改变  
    v.assign(100, 8);    
    /*  
    出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉， 
    而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的 
    空间，而引起代码运行时崩溃。  
    解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新 
    赋值即可。  
    */  
    while(it != v.end()) 
     {  
        cout<< *it << " " ;  
        ++it; 
     }  
    cout<<endl;  
    return 0; 
}

比如：

2.指定位置元素的删除操作-erase

#include <iostream> 
using namespace std; 
#include <vector> 
int main() 
{  
    int a[] = { 1, 2, 3, 4 }; 
    vector<int> v(a, a + sizeof(a) / sizeof(int));  
    
    // 使用find查找3所在位置的iterator  
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);  
    
    // 删除pos位置的数据，导致pos迭代器失效。  
    v.erase(pos);  
    cout << *pos << endl; // 此处会导致非法访问  
    return 0; 
}

erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 就失效了。因此删除 vector 中任意位置上元素时，vs 就认为该位置迭代器失效了。

以下代码的功能是删除 vector 中所有的偶数，请问那个代码是正确的，为什么？

#include <iostream> 
using namespace std; 
#include <vector> 
int main() 
{  
    vector<int> v{ 1, 2, 3, 4 };  
    auto it = v.begin();  
    while (it != v.end()) 
     {  
        if (*it % 2 == 0)  
        v.erase(it);  
        ++it; 
     }    
    return 0; 
} 

int main() 
{  
    vector<int> v{ 1, 2, 3, 4 };  
    auto it = v.begin();  
    while (it != v.end()) 
     {
         if (*it % 2 == 0)  
            it = v.erase(it);  
        else  
            ++it; 
     } 
    return 0; 
}

第二个代码是正确的，第一个代码存在逻辑错误，会导致迭代器失效和未定义行为。

核心原因：vector 的 erase 操作会导致迭代器失效

vector::erase(it) 执行后，会删除 it 指向的元素，并且：

• 原 it 迭代器会失效（指向已被释放的内存）

• erase 会返回指向被删除元素下一个位置的新迭代器

第一个代码的问题在于：当删除元素后，it 已经失效，继续对其进行 ++ 操作会导致程序异常。

第二个代码的正确之处在于：

• 删除元素时，通过 it = v.erase(it) 接收新的有效迭代器，避免失效问题

• 不删除元素时，才执行 ++it 移动到下一个元素

这种写法确保了迭代器始终有效，能够正确遍历并删除所有偶数元素。

示例执行过程（第二个代码）

以 v = {1,2,3,4} 为例

1. 初始 it 指向 1（非偶数）→ ++it → 指向 2

2. it 指向 2（偶数）→ erase(it) 返回指向 3 的迭代器 → it 现在指向 3

3. it 指向 3（非偶数）→ ++it → 指向 4

4. it 指向 4（偶数）→ erase(it) 返回指向 end() 的迭代器 → 循环结束

最终 vector 变为 {1,3}，符合预期。

erase 会返回被删除 it 的下一个位置的迭代器，在使用 vector::erase 时，必须通过其返回值更新迭代器。

3.与 vector 类似，string 在插入+扩容操作+erase 之后，迭代器也会失效

#include <string> 
void TestString()
{  
    string s("hello");  
    auto it = s.begin();  
    // 放开之后代码会崩溃，因为resize到20会string会进行扩容  
    // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了  
    // 后序打印时，再访问it指向的空间程序就会崩溃  
    //s.resize(20, '!');  
    while (it != s.end()) 
     {  
        cout << *it;  
        ++it; 
     } 
    cout << endl;  
    it = s.begin();  
    while (it != s.end()) 
     {  
        it = s.erase(it); 
         // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后  
        // it位置的迭代器就失效了  
        // s.erase(it);   
        ++it; 
     } 
}

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

2.Vector 与其他容器比较

2.1 容器特性对比表

2.2 容器选择指南

• 需要随机访问：vector， deque， array

• 频繁在头部插入删除：deque， list

• 频繁在中间插入删除：list

• 内存紧凑性重要：vector， array

• 需要异常安全：list（所有操作提供强异常保证）

• C 风格接口兼容：vector（可使用 data（）获取原始指针）