【STL】序列式容器--vector

系统管理员 2022-06-13 01:36 267阅读 0赞

【STL】常用容器总结，带有复习性质的学习更有效率；

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

【vector】序列式动态增长的容器

**优点：**相比如array的数组，不拘泥于固定大小，可以动态增长，依然可以采用下标的方式随机访问，（未雨绸缪）提前根据需求调用API设置vector初始大小，这是因为vector存在的缺陷（见下）；

**缺点：**因为是固定位置的结构，所以避免不了的是挪动时的消耗，比如，删除一个元素，vector底层是将要删除的元素后面的元素统一向前挪动一个位置，覆盖要删除的元素，然后删除最后一个元素，不但耗时耗力，还存在迭代器失效的问题，还有扩容时需要 “配置新空间/数据移动/释放旧空间”，很费力的；

虽然vector存在这样的缺点，但是实际中，vector仍然是使用很频繁的容器，毕竟比自己去维护一个数组要方便的多；

**演示vector迭代器失效问题：**

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
        vector<int> v;
        for(int i = 0; i < 10; ++i)
        {
            v.push_back(i);
        }
    
        vector<int>::iterator it = v.begin();
        while(it != v.end())
        {
            if(*it == 5)
            {
                v.erase(it);
            }
            it++:
        }
        return 0;
    }

分析： 程序崩溃，因为操作了无效的迭代器，看过源码的同学都知道，erase是会返回一个有效的迭代器的，所以这里需要重新接受一下迭代器并且做一些代码处理：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
        vector<int> v;
        for(int i = 0; i < 10; ++i)
        {
            v.push_back(i);
        }
    
        vector<int>::iterator it = v.begin();
        while(it != v.end())
        {
            if(*it == 5)
            {
                it = v.erase(it);
            }
            else
            {
                it++;
            }
        }
        return 0;
    }

下面我们验证下一个问题，当我们erase一个或者多个元素时，vector的空间释放没有；

vector<int>::iterator it = v.begin();
        cout<<"vector capacity:"<<v.capacity()<<endl;
        v.erase(it);
        cout<<"vector capacity:"<<v.capacity()<<endl;

程序运行起来看看结果：  
![这里写图片描述][SouthEast]

从上面的容量查询结果可以看出来，删除元素的前后，容量的大小没有发生变化； 看来erase并不具备释放空间的能力，看一下源码的话就会发现，erase里面调用了全局的 destroy 函数， 跟进去看一下destroy函数又做了什么， 奥， 原来只是显示的调用了 对象的析构函数，那么vector的这段空间到底是如何释放的?

通过源码，我们可以看到vector的空间是通过空间配置器alloc开辟的，释放是通过deallocate 释放的；

那么除了扩容时可以释放原有的空间，开辟出一块更大的空间，或者vector的生命周期完成的时候可以释放这块原有的空间，还有其它的方法吗？

举个例子，我面试的时候被问到的问题：如何释放原有的空间？ 除了上述的方法；

即，现在我有一个 vector ,它的空间为10个int的大小，现在我想让它释放掉这段空间，并且不能增容，这个vector还能继续使用；

下面是我第一时间想到的解决方案：

vector<int> v;
        v.reserve(10);
        cout<<v.capacity()<<endl;
        v.clear();
        cout<<v.capacity()<<endl;

结果：  
![这里写图片描述][SouthEast 1]

分析： 如果看到这里的话，应该对这结果不出意外，就如同前面说的，看一下源码的话，就会发现clean只是调用了 destroy 函数，并没有调用deallocate, 所以，思考了一下就否决了这个方案；

那么，正确的方法应该是什么呢？ 其实，就是我们平时写代码经常用的方法，和临时变量交换；

代码：

vector<int> v;
        v.reserve(10);
    
        cout<<v.capacity()<<endl;
        vector<int>::iterator it = v.begin();
    
        if(1)
        {
            vector<int> tmp;
            v.swap(tmp);
        }
        cout<<v.capacity()<<endl;

结果：  
![这里写图片描述][SouthEast 2]

当然，insert之后，迭代器也会失效，不能再使用；

[SouthEast]: /images/20220613/5d010688945a4114a264eaa221ecc21f.png
[SouthEast 1]: /images/20220613/ff37829cc9a14591ac929881a46ec7cc.png
[SouthEast 2]: /images/20220613/c87201d856854906ad140836e473862d.png