C++ STL Vector 容器封装与安全：避免越界访问及迭代器失效

C++ STL Vector 容器封装与安全

了解 vector 常用接口

vector 是 C++ 标准模板库中的部分内容，它是一个多功能的、能够操作多种数据结构和算法的模板类和函数库。简单来说，vector 是一个能够存放任意类型的动态数组，能够增加和压缩数据。

常见构造

构造函数声明	接口说明
vector()（重点）	无参构造
vector(size_type n, const value_type& val = value_type())	构造并初始化 n 个 val
vector(const vector& x)（重点）	拷贝构造
vector(InputIterator first, InputIterator last)	使用迭代器进行初始化构造

迭代器

iterator 的使用	接口说明
begin + end（重点）	获取第一个数据位置的 iterator/const_iterator，获取最后一个数据的下一个位置的 iterator/const_iterator
rbegin + rend	获取最后一个数据位置的 reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

容量操作

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变 vector 的 size
reserve（重点）	改变 vector 的 capacity

修改操作

vector 增删查改	接口说明
push_back（重点）	尾插
pop_back（重点）	尾删
find	查找。（注意这个是算法模块实现，不是 vector 的成员接口）
insert	在 position 之前插入 val
erase	删除 position 位置的数据
swap	交换两个 vector 的数据空间
operator[]（重点）	像数组一样访问

vector 实现

底层结构

在 C 语言实现当中，vector 实现中并没有迭代器的支持，因此底层结构设计并不复杂。

typedef struct SeqList {
    SLDataType* arr;
    int size; //有效数据个数
    int capacity; //空间大小
} SL;

为了提供迭代器的支持，可以像指针一样遍历数组，因此对 vector 的底层封装采用如下。

template<class T> class vector {
public:
    typedef T* iterator;
    typedef const T* const_iterator;
    //...
private:
    //给缺省值
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end_of_storage = nullptr;
};

迭代器

iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

memcpy 拷贝问题

void reserve(size_t n) {
    if (n > capacity()) {
        size_t oldsize = size();
        T* tmp = new T[n];
        memcpy(tmp, _start, sizeof(T) * oldsize);
        delete[] _start;
        _start = tmp;
        _finish = _start + oldsize;
        _end_of_storage = _start + n;
    }
}

实际上，上面这段程序在内置类型是不会出问题的，但是针对一些场景（如自定义类型）会报错。

如果 vector 中存的是自定义类型：

会导致多次析构；
一个数据的修改会影响另一个；
memcpy 则只能拷贝每个 string，但还是同样指向同一个串。

为了防止浅拷贝问题，如下程序是针对自定义类型的优化。

void reserve(size_t n) {
    if (n > capacity()) {
        size_t oldsize = size();
        T* tmp = new T[n];
        //memcpy(tmp, _start, sizeof(T) * oldsize); //err 只能针对内置类型
        for (size_t i = 0; i < oldsize; ++i) {
            tmp[i] = _start[i]; //内置类型不会有问题
                              //自定义类型调用其=运算符重载函数走深拷贝，防止 memcpy 出现的问题
        }
        delete[] _start;
        _start = tmp;
        _finish = _start + oldsize;
        _end_of_storage = _start + n;
    }
}

结论： 如果对象中涉及到资源管理时，千万不能使用 memcpy 进行对象之间的拷贝，因为 memcpy 是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

迭代器失效问题

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

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

void insert(iterator pos, const T& x) {
    assert(pos < _finish);
    assert(pos >= _start);
    if (size() == capacity()) {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
    }
    iterator it = _finish - 1;
    while (it >= pos) {
        *(it + 1) = *it;
        --it;
    }
    *pos = x;
    ++_finish;
}

在上面这段程序中，由于容量满了需要进行扩容，开辟一段新空间，将旧空间的元素拷贝到新空间上来，并更新_start，_finish，_end_of_storage。但如果迭代器 it 指向旧空间上的开始位置，此时进行 *it 会导致野指针解引用问题，这也就是所谓的迭代器失效了。

那该如何解决呢？更新迭代器指向的位置。

void insert(iterator pos, const T& x) {
    assert(pos < _finish);
    assert(pos >= _start);
    //防止迭代器失效
    if (size() == capacity()) {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = _start + len;
    }
    //...
}

更新了迭代器位置后，解引用还是会报错，这是为什么呢？这里看似解决了问题，但是别忘了形参的改变并不能影响实参，即实参中的迭代器依然指向旧空间的位置，依旧会使迭代器失效。那我让形参的改变影响实参可行吗，即加上引用呢？

void insert(iterator& pos, const T& x)

而我们设计初心是想要 pos 可以随意访问数组中的元素，当想访问数组中的第三个元素时

v.insert(v.begin()+3, 3);

由于是左值引用右值，需要是 const 左值引用才能引用右值，那么再进行更改。

void insert(const iterator& pos, const T& x)

这里会发现由于 const 的修饰，会导致 insert 函数内部是无法修改迭代器 pos 位置的，因此这种方案也是不可取的。

总之，insert 以后，默认迭代器都失效了（尽管在 insert 函数里修复了迭代器指向位置，但由于形参并不会实参）。

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

void erase(iterator pos) {
    assert(pos < _finish);
    assert(pos >= _start);
    iterator it = pos + 1;
    while (it < _finish) {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;
}

这里的删除依然存在着一个隐秘的问题。erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 就失效了（即 it 和_finish 刚好错过了，循环判断依然成立，此时继续执行会出现错误）。

按照上面的说法，那么改下判断条件不就能使 it 等于_finish 了吗？但运行之后依然会报错，这是因为删除 vector 中任意位置上元素时，Visual Studio 环境下检查严格。即在 VS 下检查严格。（Linux 下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有 VS 下极端）

auto it = v1.begin();
while (it != v1.end()) {
    if (*it % 2 == 0) {
        v1.erase(it);
    } else {
        ++it;
    }
}

因此，使用 erase 接口时并不能依赖于编译器，应注意需要手动更新迭代器防止迭代器失效问题。

在 stl 库中也是这么解决的。

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

auto it = v1.begin();
while (it != v1.end()) {
    if (*it % 2 == 0) {
        it = v1.erase(it);
    } else {
        ++it;
    }
}

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

总的来说：vector 特别需要注意的是在使用 insert 和 erase 接口应注意迭代器失效问题，这样才能让我们在使用 stl 库接口时应对自如。

initializer_list 实现

void push_back(const T& x) {
    if (size() == capacity()) {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
    }
    *_finish = x;
    _finish++;
}
vector(initializer_list<T> il) {
    reserve(il.size());
    for (auto& ch : il) {
        push_back(ch);
    }
}

C++ STL Vector 容器封装与安全：避免越界访问及迭代器失效