【C++ STL】vector

文章目录

• vector
• • 1. vector的接口
  • • 1.1 默认成员函数
    • 1.2 容量操作
    • 1.3 访问操作
    • 1.4 修改操作
    • 1.5 vector与常见的数据结构的对比
  • 2. vector的模拟实现
  • • 2.1 类的定义
    • 2.2 默认成员函数
    • • 迭代器的分类
    • 2.3 容量接口
    • • memcpy 浅拷贝问题
      • 内存增长机制
      • reserve和resize的区别
    • 2.4 修改接口
    • • 迭代器失效问题
  • 3. vector的oj题

vector

vector是动态空间，随着元素的加入它内部机制会自行空充空间以容纳新元素。vector维护了一个连续的线性空间，普通指针就可以满足要求作为vector的迭代器，随机访问迭代器。vector里面其实有三个迭代器，分别是指向空间头部的iterator，指向空间尾部的iterator和指向可用空间的iterator。当有新的元素插入时，如果当前容量够就直接插入，如果容量不够则扩容至两倍或1.5倍，如果两倍不足，则扩容至足够大的空间。由于扩充过程不是在原有的空间后面追加，而是重新申请一块新的连续内存，所以所有迭代器都会失效。

template < 
	class T, // 元素类型
	class Alloc = allocator<T> > // 空间配置器类型

class vector; // 类模板声明

1. vector的接口

1.1 默认成员函数

1.2 容量操作

v.reserve(100);   // 扩容到100
v.resize(100, 1); // 有效元素个数变为100,新增元素初始化为1
v.resize(10);     // 有效元素个数变为10

由图可知，vs下vector按1.5倍增容。

1.3 访问操作

[]重载和at的区别是，[]越界会断言报错，at是抛异常。

[]重载就已经能方便的访问 vector，但并不意味着放弃迭代器。大部分容器都支持迭代器访问，且迭代器使用简单规范统一。

STL 中容器的迭代器区间都是采用 [ f i r s t , l a s t ) [first,last) [first,last) 左闭右开的方式。

//[]
for (size_t i = 0; i < v.size(); i++) {
    v1[i] += 1;
}

//iterator
vector<int>::iterator it = v.begin();
while (it != v.end()) {
    cout << *it << " ";
    it++;
}

for (auto e : v) {
    cout << e << " ";
}

1.4 修改操作

v.insert(ret, 30);
v.insert(ret, 2, 30);
v.insert(ret, v2.begin(), v2.end());
v1.erase(pos);
v1.erase(v1.begin(), v1.end());

#include <algorithm>
// 查找接口
template <class InputIter, class T>
   InputIter find (InputIter first, InputIter last, const T& val);

1.5 vector与常见的数据结构的对比

大伙们看看它们的主要特性和区别如下：

以下是 vector和array对比表格:

以下是 vector 和 list 的对比表格：

以下是 vector 和 list 在常见操作的时间复杂度对比：

2. vector的模拟实现

vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。如图：

2.1 类的定义

template <class T, class Alloc = alloc>
class vector {
public:
    typedef T* iterator;
    // ...
private:
    iterator start;
    iterator finish;
    iterator end_of_storage;
}

这个结构和顺序表结构稍有不同，但本质是一样的。只是将容量和元素个数的变量用指向对应位置的迭代器代替。

class Seqlist {
    T* _a;            /* start */
    size_t _size;     /* finish - start */
    size_t _capacity; /* end_of_storage - start */
}

2.2 默认成员函数

//default constructor
vector()
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{}
//fill constructor
vector(size_t n, const T& val = T()) // 引用临时对象可延长其声明周期
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    resize(n, val);  
}
//copy constructor
vector(const vector<T>& v)
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    _start = new T[v.capacity()];
    for (size_t i = 0; i < v.capacity(); i++)
    {
        _start[i] = v._start[i];
    }
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();
}

//range constructor
template <class InputIterator>
vector(InputIterator first, InputIterator last) 
    : _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first != last) 
	{
		push_back(*first++);
    }
}
//destructor
~vector() 
{
    delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
}

// 现代写法
//copy constructor
vector(const vector<T>& v) 
    : _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}
//operator=
vector<T>& operator=(vector<T> v)  /* pass by value */
{
    swap(v);
    return *this;
}

从范围构造可以看出类模板中的函数也可以是函数模板。

迭代器的分类

函数模板的模板参数要传迭代器区间时，命名是有规定的，范围构造中的InputIterator就是一种指定的迭代器类型。因容器的结构各有不同，迭代器分为五种类型：

可以看出，下方的迭代器类型是上方的父类，也就是说下方迭代器满足上方的所有要求。

划分出不同的迭代器类型，是为了限制传入的迭代器，因为其必须满足要求才能完成接下来的函数。

函数指明迭代器为InputIterator，意味着满足要求的迭代器都可以传入，起提示的作用。

当然，模版不区分类型，语法上所有迭代器都可以传入，但可能无法完成编译。

2.3 容量接口

memcpy 浅拷贝问题

vector<string> v;
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111"); // 增容浅拷贝

出现问题是因为正好数组需要增容。模拟实现的reserve函数使用memcpy将原空间的内容按字节拷贝至新空间。

1. 若 vector 存储的是内置类型，则浅拷贝没问题。
2. 若 vector 存储的是自定义类型，浅拷贝使得新旧变量指向同一块空间。深拷贝调用拷贝构造或者赋值重载。

内存增长机制

当空间不足以容纳数据时（例如使用 vec.push_back(val)），std::vector 会自动申请更大的内存空间，通常是当前大小的1.5倍或2倍（具体取决于编译器，例如GCC通常是2倍，而在VS下的MinGW是1.5倍）。然后，它会将原有数据拷贝到新的内存空间中，并释放原来的内存空间。

当你释放或清空数据（使用 vec.clear()）时，std::vector 的存储空间不会被释放，只是清空了数据元素。因此，对 std::vector 的任何操作，一旦触发了内存重新配置，会导致指向原 vector 的所有迭代器失效。

void reserve(size_t n) 
{
    if (n > capacity()) 
    {
        T* tmp = new T[n];
        size_t oldSize = size();
        
        if (_start) 
        {
            //memcpy(tmp, _start, size() * sizeof(T)); // err
            for (int i = 0; i < size(); i++) 
            {
                tmp[i] = _start[i];//_start指向的空间存任意类型都能完成深拷贝
            }
            
            delete[] _start;
        }
        
        _start = tmp;
        _finish = _start + oldSize;
        _end_of_storage = _start + n;
    }
}

void resize(size_t n, T val = T())
{
    if (n > size())
    {
        reserve(n);
        while (_finish != _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else
    {
        _finish = _start + n;
    }
}

reserve和resize的区别

reserve 是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化 push_back），可以提高效率，其次还可以减少多次要拷贝数据的问题。reserve 只是保证 vector 中的空间大小（capacity）最少达到参数所指定的大小 n，预留空间。

resize 可以改变有效空间的大小，也有改变默认值的功能。capacity 的大小也会随着改变。resize() 可以有多个参数。 resize() 改变了 vector 的 capacity 同时也增加了它的 size！

原因如下：

1. reserve 是容器预留空间，但在空间内不真正创建元素对象，所以在没有添加新的对象之前，不能引用容器内的元素。加入新的元素时，要调用 push_back()/insert() 函数。

2. resize 是改变容器的大小，且在创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用 operator[] 操作符，或者用迭代器来引用元素对象。此时再调用 push_back() 函数，是加在这个新的空间后面的。

可能大家平时用 reserve() 比较多，顾名思义，reserve 就是预留内存。为的是避免内存重新申请以及容器内对象的拷贝。说白了，reserve() 是给 push_back() 准备的！而 resize 除了预留内存以外，还会调用容器元素的构造函数，不仅分配了 N 个对象的内存，还会构造 N 个对象。

从这个层面上来说， resize() 在时间效率上是比 reserve() 低的。但是在多线程的场景下，用 resize 再合适不过。

2.4 修改接口

iterator insert(iterator pos, const T& val)
{
    assert(_start <= pos && pos <= _finish); // 检查pos位置是否合法
    // 增容
    if (_finish == _end_of_storage) 
    {
        size_t sz = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2); //增容会导致迭代器失效，迭代器位置陈旧
        pos = _start + sz; //增容后更新pos
    }
    
    // 后移 [pos,_finish)
    for (iterator end = _finish; end > pos; --end)
    {
        *end = *(end - 1);
    }
    
    // 插入
    *pos = val;
    ++_finish;
    return pos; //返回迭代器最新位置
}

• 增容改变_start，但迭代器pos并没有跟着改变，仍然指向原空间，也就是迭代器失效。
• 迭代器pos实参并没有改变仍然指向错误位置，故函数返回更新的pos。

iterator erase(iterator pos)
{
    assert(_start <= pos && pos < _finish);

    for (iterator begin = pos + 1; begin < _finish; begin++)
    {
        *(begin - 1) = *begin;
    }
    
    _finish--;
    return pos; //返回删除数据的下一个位置
}

• erase 挪动数据后 pos 指向元素会发生变化，同样会导致迭代器失效。
• 返回删除数据的下一个位置，通过返回值更新迭代器。

迭代器失效问题

1. 插入操作导致迭代器失效

当向 vector 中插入元素时，如果当前容量不足，vector 会重新分配内存，并将现有元素复制到新的内存空间中。这种内存重分配会导致所有之前获取的迭代器失效，因为它们仍然指向旧的内存地址，而不是新分配的地址。例如：

std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();  // 获取迭代器指向 vec 的第一个元素

vec.push_back(4);  // 插入元素导致内存重分配，it 指向的地址已经无效
// it 现在是一个悬空指针，不能再安全地使用

解决方法是，在插入操作之后重新获取迭代器，或者使用返回的插入位置迭代器。

2. 删除操作导致迭代器失效

删除 vector 中的元素会导致迭代器失效，特别是被删除元素之后的所有元素的位置都会向前移动。如果使用的是被删除元素的迭代器，那么在调用删除操作后，该迭代器就变得无效。例如：

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2;  // it 指向 vec 的第三个元素，值为 3

vec.erase(it);  // 删除元素 3

// 现在 it 指向的位置已经是无效的，应该重新赋值或者使用 erase 返回的迭代器

为了安全地进行删除操作，可以使用 erase 方法返回的迭代器，它指向被删除元素之后的下一个有效位置：

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2;  // it 指向 vec 的第三个元素，值为 3

it = vec.erase(it);  // 删除元素 3，并更新 it 为下一个有效迭代器

3. vector的oj题