vector迭代器失效解决方法及内存原理

朱雀 2022-09-26 03:14 233阅读 0赞

### 迭代器失效,有两个层面的意思: ###

1. 无法通过迭代器++,--操作遍历整个stl容器。记作: 第一层失效。
    2. 无法通过迭代器存取迭代器所指向的内存。  记作: 第二层失效。

### vector是个连续内存存储的容器，如果vector容器的中间某个元素被删除或从中间插入一个元素， 有可能导致内存空间不够用而重新分配一块大的内存。 ###

### 这个动作将导致先前获取的迭代器,，第一层和第二层均失效。 ###

### **造成失效的两个函数**: ###

*  insert（i, value）  
    在迭代器i前插入一个元素value, 返回指向value迭代器
 *  erase(i)  
    删除迭代器i位置的元素， 返回指向后一个元素的迭代器

### **避免失效的方法**： ###

*  i = insert（i, value）
 *  i = erase(i)

### 造成失效的原因是因为**内存的重新分配, 保留下来的迭代器不再指向容器中原来的元素**… ###

### 下面我们来看一下执行这两个操作时内存分配的具体情况: ###

# 1. erase操作 #

//erase操作
    #include<vector>
    #include<iostream>
    using namespace std;
    int main(){
        vector<int>q{
       1,2,3,4,5,6,7,8,9,10};
        int cnt = 0;
        int flag = 0;
        for(vector<int>::iterator i = q.begin(); i != q.end(); ++i){
            ++cnt;
            if(cnt > 15){
                cout<<"gg"<<endl;
                break;
            }
            if(*i == 3)              //删除第三个
               i = q.erase(i);
            cout << *i << endl;
            cout << &(*i) << endl;
        }
        return 0;
    }

## output: ##

1
      0xc72158
      2
      0xc7215c
      4
      0xc72160
      5
      0xc72164
      6
      0xc72168
      7
      0xc7216c
      8
      0xc72170
      9
      0xc72174
      10
      0xc72178

## 输出结果分析: ##

### 当删除第3个元素以后我们发现第四个元素是紧邻第二个元素的（刚好差一个int的内存） ###

### 也就是说vector执行erase（i）后会将迭代器i之后的元素**逐个向前移动一个type单位** ###

### 这也就是i及i之后所有迭代器失效的原因… ###

--------------------

# 2. insert操作（内存不足时） #

//insert操作
    //内存不够情况
    #include<vector>
    #include<iostream>
    using namespace std;
    int main(){
    
        vector<int>q{
       1,2,3,4,5,6,7,8,9,10};                                 //  c++11列表初始化
        vector<int>::iterator j = q.begin();
        j++;
        cout<<"第二个元素:"<<*j<<endl;
        cout<<"第二个元素地址:"<<&(*j)<<endl;
        cout<<"初始vector分配的容量:"<<q.capacity()<<endl;                  //  有多少元素即分配多少内存
        int cnt = 0;
        int flag = 0;  //flag保证只插入一次
    
    
        for(vector<int>::iterator i = q.begin(); i != q.end(); ++i){
            ++cnt;
            if(cnt > 15){
                cout<< "gg" <<endl;
                break;
            }
            if(*i == 3&&!flag){
                flag = 1;
                i = q.insert(i,22);
                cout<<"\n插入后第二个元素:"<<*j<<endl;
                cout<<"插入后第二个元素地址:"<<&(*j)<<endl;
                cout<<"插入元素后vector分配的容量:" <<q.capacity() <<endl;
            }
            cout << *i << endl;
            cout << &(*i) << endl;
        }
        return 0;
    }

## output: ##

第二个元素:2
      第二个元素地址:0xe5215c
      初始vector分配的容量:10
      1
      0xe52158
      2
      0xe5215c
    
      插入后第二个元素:15007936
      插入后第二个元素地址:0xe5215c
      插入元素后vector分配的容量:20
      22
      0xe52190
      3
      0xe52194
      4
      0xe52198
      5
      0xe5219c
      6
      0xe521a0
      7
      0xe521a4
      8
      0xe521a8
      9
      0xe521ac
      10
      0xe521b0

## 输出结果分析: ##

### vector内存分配策略为 **二倍扩容** , 每次当内存不够的情况下vector会将容量扩展为当前的两倍. ###

### 那这些新分配的会在原内存的后面吗？ 根据输出结果显然不是的。 ###

### 上例代码在插入元素22 后, 新的3号元素内存位置距离上一个元素不是4byte(1个int单位), 也就是说 ###

### **当vector扩容时, 会在另一个内存分配一段新的内存**(原内存的二倍). 并把原内存中的元素全部拷贝到新内存中… ###

### 指向二号元素的迭代器在插入操作之后指向的值由2变成了15007936,也验证了上述结论. ###

--------------------

# 3. insert操作（内存充足时） #

//insert操作
    //内存充足情况
    #include<vector>
    #include<iostream>
    using namespace std;
    int main(){
    
        vector<int>q{
       1,2,3,4,5,6,7,8,9,10};                             
        q.push_back(11);
        cout<<"初始vector分配的容量:"<<q.capacity()<<endl;                  
        int cnt = 0;
        int flag = 0;  //flag保证只插入一次
    
    
        for(vector<int>::iterator i = q.begin(); i != q.end(); ++i){
            ++cnt;
            if(cnt > 15){
                cout<< "gg" <<endl;
                break;
            }
            if(*i == 3&&!flag){
                flag = 1;
                i = q.insert(i,22);
                cout<<"插入元素后vector分配的容量:" <<q.capacity() <<endl;
            }
            cout << *i << endl;
            cout << &(*i) << endl;
        }
        return 0;
    }

## output: ##

初始vector分配的容量:20
      1
      0x1f2188
      2
      0x1f218c
      插入元素后vector分配的容量:20
      22
      0x1f2190
      3
      0x1f2194
      4
      0x1f2198
      5
      0x1f219c
      6
      0x1f21a0
      7
      0x1f21a4
      8
      0x1f21a8
      9
      0x1f21ac
      10
      0x1f21b0
      11
      0x1f21b4

## 输出结果分析: ##

### 很显然当内存充足的情况下, 执行insert操作只会将迭代器**i及i之后的的所有元素向后移动一个type单位**.所以这种情况下即使没有使用返回值也**不会发生迭代器失效** ###