C++ Primer：vector插入元素时迭代器失效问题

╰+攻爆jí腚メ 2023-05-28 05:05 36阅读 0赞

### vector插入元素时迭代器失效问题 ###

*  1. capacity()不足，在末尾添加元素
 *  2. capacity()充足，在末尾添加元素
 *  3. capacity()充足，在中间添加元素
 *  4. capacity()充足，在首部添加元素
 *  5. 总结

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

**提示：以下所有程序是使用MinGW编译运行的。若使用VS的MSVC运行，程序会报错，因为MSVC无法解引用失效迭代器或尾后迭代器。**

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

# 1. capacity()不足，在末尾添加元素 #

#include <iostream>
    #include <vector>
    using namespace std;
    //输出
    void show(vector<int> &v);
    //迭代器
    vector<int>::iterator i1, i2, i3;
    
    int main()
    {
        vector<int> vi{1, 2};
        i1 = vi.begin();
        i2 = ++vi.begin();
        i3 = vi.end();
        //输出
        show(vi);
        //在末尾插入
        vi.push_back(3);
        //输出
        show(vi);
    
        return 0;
    }
    
    void show(vector<int> &v)
    {
        cout << "size:     " << v.size() << endl;
        cout << "capaticy: " << v.capacity() << endl;
        cout << "vector:   ";
    
        for (auto &a : v)
        {
            cout << a << "(" << &a << ")"
                 << "\t";
        }
        cout << endl
             << "iterate:  ";
    
        cout << *i1 << "(" << &(*i1) << ")"
             << "\t";
        cout << *i2 << "(" << &(*i2) << ")"
             << "\t";
        cout << *i3 << "(" << &(*i3) << ")" //解引用尾后迭代器的行为是未定义的
             << "\t";
        cout << endl
             << endl;
    }

![运行结果][format_png_pic_center]  
![插入元素前后比较图][format_png_pic_center 1]  
分析：

1.  因为size()==capacity()，故插入元素后，vector被重新分配内存。vi原先从0x3a0f88开始，插入元素后，vi从0x3a0f98开始。
2.  插入元素前，i1指向vi首元素，i2指向vi中的第2个元素，i3指向不存在的尾后元素，\*i3是未定义的。
3.  插入元素后，vector被重新分配内存，i1、i2和i3指向未知的内存区域，故i1、i2和i3已失效。

# 2. capacity()充足，在末尾添加元素 #

#include <iostream>
    #include <vector>
    using namespace std;
    //输出
    void show(vector<int> &v);
    //迭代器
    vector<int>::iterator i1, i2, i3;
    
    int main()
    {
         vector<int> vi{1, 2};
         //扩充存储空间
         vi.reserve(4);
         //迭代器
         i1 = vi.begin();
         i2 = ++vi.begin();
         i3 = vi.end();
         //输出
         show(vi);
         //在末尾插入
         vi.push_back(3);
         //输出
         show(vi);
    
         return 0;
    }
    
    void show(vector<int> &v)
    {
         cout << "size:     " << v.size() << endl;
         cout << "capaticy: " << v.capacity() << endl;
         cout << "vector:   ";
    
         for (auto &a : v)
         {
              cout << a << "(" << &a << ")"
                   << "\t";
         }
         cout << endl
              << "iterate:  ";
    
         cout << *i1 << "(" << &(*i1) << ")"
              << "\t";
         cout << *i2 << "(" << &(*i2) << ")"
              << "\t";
         cout << *i3 << "(" << &(*i3) << ")" //解引用尾后迭代器的行为是未定义的
              << "\t";
         cout << endl
              << endl;
    }

![运行结果][format_png_pic_center 2]

![插入元素前后比较图][format_png_pic_center 3]

分析：

1.  因为size()<capacity()，故插入元素后，vector的内存地址不变。
2.  插入元素前后，i1始终指向vi首元素，i2始终指向vi中的第2个元素，且其值并未改变。故i1和i2仍有效。
3.  插入元素前，i3指向vi不存在的尾后元素，\*i3是未定义的；插入元素后，\*i3=3，不再指向尾后元素，故i3失效。

# 3. capacity()充足，在中间添加元素 #

#include <iostream>
    #include <vector>
    using namespace std;
    //输出
    void show(vector<int> &v);
    //迭代器
    vector<int>::iterator i1, i2, i3;
    
    int main()
    {
        vector<int> vi{1, 2};
        //扩充存储空间
        vi.reserve(4);
        //迭代器
        i1 = vi.begin();
        i2 = ++vi.begin();
        i3 = vi.end();
        //输出
        show(vi);
        //在第2个元素之前插入
        vi.insert(i2, 3);
        //输出
        show(vi);
    
        return 0;
    }
    
    void show(vector<int> &v)
    {
        cout << "size:     " << v.size() << endl;
        cout << "capaticy: " << v.capacity() << endl;
        cout << "vector:   ";
    
        for (auto &a : v)
        {
            cout << a << "(" << &a << ")"
                 << "\t";
        }
        cout << endl
             << "iterate:  ";
    
        cout << *i1 << "(" << &(*i1) << ")"
             << "\t";
        cout << *i2 << "(" << &(*i2) << ")"
             << "\t";
        cout << *i3 << "(" << &(*i3) << ")" //解引用尾后迭代器的行为是未定义的
             << "\t";
        cout << endl
             << endl;
    }

![运行结果][format_png_pic_center 4]

![插入元素前后比较图][format_png_pic_center 5]

分析：

1.  因为size()<capacity()，故插入元素后，vector的内存地址不变。
2.  插入元素前后，i1始终指向vi首元素，且其值并未改变。故i1仍有效。
3.  插入元素前，i2指向vi的第2个元素，\*i2=2；插入元素后，i2仍指向vi的第2个元素，但\*i2=3，故i2已失效。
4.  插入元素前，i3指向vi不存在的尾后元素，\*i3是未定义的；插入元素后，\*i3=2，不再指向尾后元素，故i3失效。

# 4. capacity()充足，在首部添加元素 #

#include <iostream>
    #include <vector>
    using namespace std;
    //输出
    void show(vector<int> &v);
    //迭代器
    vector<int>::iterator i1, i2, i3;
    
    int main()
    {
         vector<int> vi{1, 2};
         //扩充存储空间
         vi.reserve(4);
         //迭代器
         i1 = vi.begin();
         i2 = ++vi.begin();
         i3 = vi.end();
         //输出
         show(vi);
         //在第1个元素之前插入
         vi.insert(i1, 3);
         //输出
         show(vi);
    
         return 0;
    }
    
    void show(vector<int> &v)
    {
         cout << "size:     " << v.size() << endl;
         cout << "capaticy: " << v.capacity() << endl;
         cout << "vector:   ";
    
         for (auto &a : v)
         {
              cout << a << "(" << &a << ")"
                   << "\t";
         }
         cout << endl
              << "iterate:  ";
    
         cout << *i1 << "(" << &(*i1) << ")"
              << "\t";
         cout << *i2 << "(" << &(*i2) << ")"
              << "\t";
         cout << *i3 << "(" << &(*i3) << ")" //解引用尾后迭代器的行为是未定义的
              << "\t";
         cout << endl
              << endl;
    }

![运行结果][format_png_pic_center 6]

![插入元素前后比较图][format_png_pic_center 7]

分析：

1.  因为size()<capacity()，故插入元素后，vector的内存地址不变。
2.  插入元素前后，i1始终指向vi首元素，但\*i1从1变成3。故i1失效。
3.  插入元素前后，i2始终指向vi的第2个元素，但\*i2从2变成1。故i2失效。
4.  插入元素前，i3指向vi不存在的尾后元素，\*i3是未定义的；插入元素后，\*i3=2，不再指向尾后元素，故i3失效。

# 5. 总结 #

**1. 当size()==capacity()，插入元素时vector会被重新分配内存，指向元素的迭代器都会失效。**  
**2. 当size()<capacity()，插入元素时vector不会被重新分配内存。此时，若迭代器指向插入位置之前的元素，它仍有效；若迭代器指向插入位置之后的元素，它将会失效。**

[format_png_pic_center]: /images/20230528/466d277e2e2f4fd79975b2aad7666ecf.png
[format_png_pic_center 1]: /images/20230528/5c958940656b42ca9f51903e1a649b8d.png
[format_png_pic_center 2]: /images/20230528/9dd13acf917c49aeb0335a82603fda51.png
[format_png_pic_center 3]: /images/20230528/04db5cccb3284eba9d78ed7ebdad3a59.png
[format_png_pic_center 4]: /images/20230528/dc41c881bc6547a6a2fa828f9aa713e5.png
[format_png_pic_center 5]: /images/20230528/48261cefdd7c4e8bbcdb390070222c14.png
[format_png_pic_center 6]: /images/20230528/1ac247df3df04011972124b1daa3c0eb.png
[format_png_pic_center 7]: /images/20230528/f8d080d2fafa4df8b2ab4e556a4c8a0d.png