vector类的使用介绍及模拟实现

Vector

0. vector 的介绍

Vectors are sequence containers representing arrays that can change in size.

vector 是用数组实现的、可变长度的顺序容器。

template < class T, //元素类型class Alloc = allocator<T> //空间配置器类型     >class vector; //类模板的声明

从 vector 的声明可以看出，vector 其实就是一种类模板。

vector 的大小可以动态变化，它的大小会被容器自动处理。vector 的内部是用动态开辟的数组实现的，所以在插入元素时可能需要增容，也就是重新开辟一块空间并拷贝原空间的内容，而深拷贝消耗比较大。

和顺序表类似，vector 存在容量的概念，不会每次插入新元素都增容，而是按照一定规律来进行增容。因此，vector 与单纯的数组相比会占用更多的内存，能够换来更好的管理方式。

学习 string 的时候花了很长时间，但 vector 和 string 类似，所以完全可以将两者类比学习。vector 是适用于任意类型，string 是专门针对字符串设计的类，相当于 vector 的特殊化。虽然两者都是依托数组实现的，但仍不能相互替代。

1. vector 的使用

1.1 vector 的默认成员函数

利用迭代器区间进行构造对象时，可以使用任意类型变量的迭代器，因为这里的参数是迭代器模板，支持任意的迭代器。

template <class InputIterator> //迭代器模板vector (InputIterator first, InputIterator last);

析构函数通常不用手动调用。赋值重载的使用也很简单。

1.2 vector 的容量操作

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

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

1.3 vector 的访问操作

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

1.4 vector 的迭代器操作

有[]的重载我们就已经能方便快捷的访问操作 vector 的元素，但并不意味着就要放弃使用迭代器。因为容器的定义要保证规范性和统一性，大部分容器都支持迭代器访问，且迭代器使用简单统一。

STL 标准库中的任意容器针对迭代器操作的区间都是采用 $[first,last)$ 左开右闭的方式。

/* vector三种遍历方式 *///[]for (size_t i = 0; i < v1.size(); i++) {    v1[i] += 1;    cout << v1[i] << " ";}cout << endl;//iteratorvector<int>::iterator it = v1.begin();while (it != v1.end()) {    cout << *it << " ";    it++;}cout << endl;//for-loopfor (auto e : v1) {    cout << e << " ";}cout << endl;

1.5 vector 的修改操作

/* assign */template <class InputIterator> void assign (InputIterator first, InputIterator last);// range (1)void assign (size_type n, const value_type& val);     // fill (2)/* insert */iterator insert (iterator position, const value_type& val);  // single element (1)void insert (iterator position, size_type n, const value_type& val);// fill (2)template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);  // range (3)/* erase */iterator erase (iterator position);iterator erase (iterator first, iterator last);

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());

1.6 vector 的其他操作

查找接口 find

vector 库中没有像 string 库一样提供成员函数find接口。因为 vector 作为数组本身的查找需求比较简单，直接使用算法库中的find即可，而 string 对象需要实现正向反向查找字符或子串，才单独实现在类中。

#include template <class InputIterator, class T>    InputIterator find (InputIterator first, InputIterator last, const T& val) {    while (first != last) { if (*first == val) {     return first; } ++first;    }    return last;}

遍历对象寻找是否有和 val 相等的迭代器位置元素，有则返回迭代器位置，无则返回最后一个迭代器位置end()。

2. vector 的模拟实现

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 */}

是空间配置器（内存池）相关的东西，学习 vector 阶段不必过多了解。

2.2 默认成员函数

//default constructorvector()    : _start(nullptr)    , _finish(nullptr)    , _end_of_storage(nullptr){}//fill constructorvector(size_t n, const T& val = T())    : _start(new T[n])    , _finish(_start + n), _end_of_storage(_finish){memset(_start, val, sizeof(T) * n);}//copy constructorvector(const vector<T>& v)    : _start(new T[v.capacity()]), _finish(_start + v.size()), _end_of_storage(_start + v.capacity()){    memcpy(_start, v._start, sizeof(T) * v.size());}

• 默认构造、填充构造、拷贝构造三种构造函数的默认传统写法。都很类似地开空间再拷贝数据。

//range constructortemplate <class InputIterator>vector(InputIterator first, InputIterator last)     : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last) {push_back(*first++);    }}//copy constructorvector(const vector<T>& v)     : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){    vector<T> tmp(v.begin(), v.end());    swap(tmp);}

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

迭代器的分类

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

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

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

例如范围构造的参数指明迭代器类型为InputIterator，意思是满足输入迭代器的要求的迭代器都可以作此参数。故此处我们可以传入任意的迭代器。

一般像底层是数组连续空间实现的容器，例如 vector, string 等的迭代器类型都是随机迭代器。像双向链表这样的非连续空间的容器的迭代器类型是双向迭代器。

• 通过复用构造函数的范围构造重载版本可以实现拷贝构造的现代写法。记得要初始化一下指针不然构造出来的随机值会影响之后的释放。

//overload operator=vector<T>& operator=(vector<T> v)  /* pass by value */{    swap(v);    return *this;}//destructor~vector() {    delete[] _start;    _start = _finish = _end_of_storage = nullptr;}

• 赋值重载的现代写法都是这么写的，只要实现了拷贝构造就可以。

2.2 访问接口

//overload operator []T& operator[] (size_t pos) {    return *(_start + pos);}const T& operator[](size_t pos) const {    return *(_start + pos);}//iteratortypedef T* iterator;typedef const T* const_iterator;iterator begin() {    return _start;}iterator end() {    return _finish;}const_iterator begin() const {    return _start;}const_iterator end() const {    return _finish;}

反向迭代器的设计较为复杂，要单独设计类去封装，该类封装正向迭代器，然后重载其operator++，学到 list 会能更好的理解迭代器。

2.3 容量接口

void resize(size_t n, const T& val = T()) {    if (n > size()) { if (n > capacity()) {     reserve(n); } while (_finish != _start + n)  {     *_finish = val;     _finish++; }    }    //_finish = _start + n; //迭代器的遍历以达到更新_finish位置的效果。}

• 缺省值采用T()的形式，即用 T 类型的匿名对象作val的缺省值。T()是调用默认构造函数的初始化出的对象，得到的是 T 类型的空值。

模板泛型编程兴起时，C++ 为了让模板参数适用于所有类型，对内置类型也优化出了构造函数。

void reserve(size_t n){    if (n > capacity()) {    size_t oldSize = size(); //增容 T* tmp = new T[n]; if (_start) {     memcpy(tmp, _start, size() * sizeof(T));     delete[] _start; } // 更新迭代器位置 _start = tmp; _finish = _start + oldSize; _end_of_storage = _start + n;    }}

• 在_start更新前计算出有效元素个数oldSize，用于更新增容后的_finish的地址，等到_start被修改后才计算就无法得到正确的结果。

memcpy 浅拷贝问题

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

假如用 vector 数组存储 string 对象，四次尾插元素都没问题，当第五次尾插元素时出现了内存问题。

其实，第五次尾插出现问题，是因为第五次时正好数组已满需要增容。而模拟实现的reserve函数使用memcpy将原空间的内容按字节拷贝至新空间。

1. 若 vector 存储的是内置类型的数据，则浅拷贝至新空间没有问题。
2. 若 vector 存储的是自定义类型的数据，由于浅拷贝粗暴地复制变量后再释放原空间，使得新变量指向已释放的空间。

如图所示，将对象中的原变量浅拷贝一份，再释放原空间，导致拷贝来的新变量指向了已释放的空间。故应该改为深拷贝。深拷贝需要调用自定义类型的拷贝构造或者赋值重载。

模拟实现的 reserve 是从堆上直接用 new 开辟一块空间，顺带初始化该段空间，所以深拷贝调用赋值重载即可。库中的容器都是从内存池上开辟空间，则需要调用定位 new 初始化空间再调用拷贝构造去拷贝数据。

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

size_t size() const {    return _finish - _start;}size_t capacity() const {    return _end_of_storage - _start;}bool empty() const {    return _start == _finish;}

2.4 修改接口

void swap(vector<T> v) {    std::swap(start, x.start);    std::swap(finish, x.finish);    std::swap(end_of_storage, x.end_of_storage);}void assign(size_t n, const T& val) {    resize(n);    memset(_start, val, sizeof(T) * n); //出其他值Error}void clear() {    _finish = _start;}void push_back(const T& x) {    if (_finish == _end_of_storage) { //增容 reserve(capacity() == 0 ? 4 : capacity() * 2);    }    *_finish = x;    ++_finish;}void pop_back() {    assert(_finish > _start);    --_finish;}

上述接口没什么难度。

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)    iterator end = _finish;    while (end != pos) { *end = *(end - 1); --end;    }    // 插入    *pos = val;    ++_finish;    return pos; //返回迭代器最新位置}

• 插入元素必然考虑增容，增容后_start指向新空间，但迭代器位置pos并没有改变仍然指向原空间的某个位置，也就是迭代器失效。所以要在增容前计算pos相对_start的位置，待增容后更新pos使之指向对应的位置即可。
• insert函数内迭代器失效的问题解决了，但函数外的pos实参并没有改变仍然指向陈旧的错误位置，故将更新的pos迭代器作返回值返回。

vector<int>::iterator pos = find(v.begin(), v.end(), 2);if (pos != v.end()) {    pos = v.insert(pos, 20); // 更新 pos 实参}

只能采用返回值的形式，不可以通过传引用解决，因为可能会传入临时对象等。

iterator erase(iterator pos){    assert(_start <= pos && pos < _finish);    /*iterator begin = pos;    while (begin != _finish) { *begin = *(begin + 1); // 越界访问 -> begin=_finish-1时，begin+1 == _finish begin++;    }*/    iterator begin = pos + 1;    while (begin != _finish)    { *(begin - 1) = *begin; begin++;    }    _finish--;    return pos; //返回迭代器最新位置}

• 遍历循环的临界条件是下标!=尾元素的后一个位置（不可访问），则下标最终会遍历到尾元素，即访问范围已足够，因此不可在循环内使下标加值如：*(begin+1)。

vector<int>::iterator pos = v1.begin();while (pos != v1.end()) {    //删除所有偶数    if (*pos % 2 == 0) {  pos = v1.erase(pos);//删除后pos复位    }    else { ++pos;//不符合删除条件的才进位    }}

• erase同样有迭代器失效的问题，删除后 pos 就已经指向了下一个元素，再直接++pos会跳过该元素。须不符合删除条件时再 ++。
• pos=erase(pos)保证删除后 pos 的位置依然正确，避免有些少见的 STL 版本可能会缩容导致pos为野指针。

漏掉元素是 erase 删除元素出现的所有问题的根源。迭代器失效的问题只有在连续使用迭代器时才会出现。不光 vector 会迭代器失效，只要能够使用迭代器访问的容器，都可能发生迭代器失效的问题。

2.5 其他接口

bool operator==(vector<T> v) {    if (&x != this) { for (size_t i = 0; i < size(); i++) {     if ((*this)[i] != v[i]) {  return false;     } }    }    return true;}bool operator!=(vector<T> v) {    return !(*this == v);}bool operator< (vector<T> v) {    for (size_t i = 0; i < size(); i++) { if ((*this)[i] >= v[i]) {     return false; }    }    return true;}bool operator<=(vector<T> v) {    return *this < v || *this == v;}bool operator> (vector<T> v) {    return !(*this <= v);}bool operator>=(vector<T> v) {    return !(*this < v);}

复用==,<逻辑即可完成对象的所有比较运算符的重载。