【C++】STL---vector

一、vector 的介绍

1. vector 是表示可变大小数组的序列容器。
2. 就像数组一样，vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自
   动处理。
3. 本质讲，vector 使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小。为了增加存储空间，其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
4. vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。
5. 因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

二、vector 的模拟实现

vector 学习时一定要学会查看文档：vector文档介绍，vector 在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面我们直接开始模拟实现，在模拟实现中我们实现的是常见的接口，并且会在实现中讲解它们的使用以及注意事项。

首先我们将 vector 放到我们自己的命名空间 namespace Young 中；其次我们需要知道，在 vs2019 中，vector 的实现是用三个迭代器实现的，这三个迭代器分别指向的是：数据块的开始、有效数据的尾、存储容量的尾，它跟 string 的实现方式差不多，就是换了一种表达形式，本质上还是一样的，声明如下：

		namespace Young{// 使用模板，泛型编程template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:// 给缺省值iterator _start = nullptr;  // 指向数据块的开始iterator _finish = nullptr;  // 指向有效数据的尾iterator _endofstorage = nullptr; // 指向存储容量的尾};}

1. 容量相关的接口

（1）size

我们要获取到有效数据的长度，只需要用两个迭代器相减，用指向有效数据尾部的减去指向数据块开头的即可，实现如下：

			// 获取有效数据长度size_t size() const{return _finish - _start;}

（2）capacity

获取容量的接口与上面的相似，如下：

			// 获取容量size_t capacity() const{return _endofstorage - _start;}

（3）reserve

reserve 我们在 string 中也实现过，vector 的 reserve 与 string 的相似，当 n（需要调整的空间大小） 大于 capacity() 才进行扩容，否则不会缩容；并且它只改变 capacity 不改变 size；其实现如下：

			// 申请空间void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){// 不能使用 memcpy 拷贝数据 --- 浅拷贝问题// memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;	}}

注意，我们在进行拷贝数据的时候，不能使用 memcpy 进行拷贝，因为这会导致深层度的浅拷贝问题，例如实例化以下的对象：

我们在进行尾插的时候，由于 v 对象没有空间，所以需要开空间，我们默认是开4个空间，当我们需要插入第5个数据的时候，需要再次扩容，此时问题就体现出来了，如下图：

因为 _start 维护的数据块中，里面是 string 自定义类型，所以它里面的 _str 指针应该指向一段字符串，在我们需要扩容的时候，memcpy 会按照逐字节的方式进行拷贝，拷贝到 _tmp 中，其中 _tmp 中的 string 的 _str 也是指向原来的空间中，当我们 delete[] _start; 的时候，_start 的空间被释放掉了，而 _tmp 中还有指针指向那段被释放的空间，所以这是造成了野指针问题，所以不能用 memcpy 进行拷贝数据。

所以我们应该采用赋值的方式进行拷贝，如下，如果是像上面的自定义类型 string，它会调用它自己的赋值重载，是深拷贝，所以不会造成上面的问题；

				for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}

还需要注意的是，我们在拷贝数据前，需要记录原来的长度，在拷贝完数据后，将 _tmp 重新赋给 _start 后，需要更新 _finish 和 _endofstorage，就需要用到原来的长度和容量相加了。

（4）resize

			// 调整空间为 n，并初始化空间void resize(size_t n,const T& value = T()){// 如果 n 小于原来的长度，调整 _finish 的位置if (n <= size()){_finish = _start + n;}// 否则，重新开空间，并在数据的尾部插入需要初始化的值else{reserve(n);while (_finish < _start + n){*_finish = value;_finish++;}}}

（5）empty

			// 判断是否空bool empty(){return _start == _finish;}

2. [] 重载

在 vector 中我们也可以实现下标的随机访问，所以我们可以重载 [] ，支持随机访问，实现如下：

非 const 对象：

			// [] 重载T& operator[](size_t pos){assert(pos < size());return _start[pos];}

const 对象：

			const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}

3. 迭代器

非 const 对象：

			// 迭代器iterator begin(){return _start;}iterator end(){return _finish;}

const 对象：

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

4. 修改数据相关的接口

（1）push_back

尾插需要注意先要判断空间是否满了，满了就要扩容，如果一开始为空，我们默认开 4 个空间，实现如下：

			// 尾插void push_back(const T& x){if (size() == capacity())//if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}

（2）pop_back

尾删只需要将 _finish 减减即可；实现如下：

			// 尾删void pop_back(){assert(size() > 0);_finish--;}

（3）insert

在 pos 位置插入数据，实现如下：

			// 在 pos 位置插入数据void insert(iterator pos, const T& value){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){// 记录 pos 的长度，防止开空间后迭代器失效size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 开好空间后 _start 重新加上 len ，使 pos 回到原来相对 _start 的位置pos = _start + len;}// 挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}// 插入数据*pos = value;_finish++;}

在实现 insert 的时候需要注意迭代器失效的问题，在上面实现的代码中，如果不记录 pos 的长度，然后空间不够需要扩容的时候， pos 还留在原来的空间中，而原来的空间已经被释放了，所以会导致野指针问题；所以我们为了避免这种问题，在扩容之前需要记录 pos 的长度，开好空间后更新 pos 的位置，让它回到新的空间相对原来空间的位置中。这是第一种迭代器失效的问题。

insert 的使用如下图：

（4）erase

删除在 pos 位置的数据，实现如下：

			// 删除 pos 位置的数据iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);// 挪动数据iterator end = pos + 1;while (end < _finish){*(end - 1) = *end;end++;}// 有效数据减一_finish--;return pos;}

erase 的使用和实现会面临迭代器失效的第二种情况，例如我们就以以上的数据为例，假设我们需要删除数据中的偶数，例如下图：

结果没有把偶数完全删除，这是为什么呢？这是因为删除了第一个 2 后，it 指向原来的第二个 2，再 ++ 后，就错过了第二个 2；后面的 6 也同理，例如下图：

找到偶数：

删除第一个 2 后：

it ++ 后：

这种迭代器失效的情况还可能面临程序崩溃的问题，如果上面的数据中最后只有一个 6 ，it 就会因为与 v1.end() 错过一个位置导致程序崩溃，例如下图：

找到 6 后：

删除后：

it ++ 后：

如上图，这种情况 it 永远都不会等于 v1.end() 所以程序会死循环。

解决方案是什么呢？解决方案就是我们在实现 erase 的时候，需要返回被删除后当前 pos 的位置，例如上面的实现中；而在使用的时候，我们在 erase 之后用 it 接收这个位置，并且不再访问这个位置，例如下图：

这段代码中，我们 erase 后，没有访问当前位置，而是在没有 erase 的时候去访问 it；

			if (*it % 2 == 0){it = v1.erase(it);}else{it++;}

结论： insert 和 erase 以后迭代器都失效了，不能再访问。

（5）swap

我们利用标准库的 swap 函数实现我们 vector 中的 swap 函数，实现如下：

			// 交换void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}

（6）clear

清空数据，只需要将 _finish 变成 _start 即可，实现如下：

			// 清空数据void clear(){_finish = _start;}

5. 构造函数

因为我们在声明处给了缺省值，所以无参的构造函数写成以下形式即可，因为缺省值最终也会走初始化列表：

			// 构造函数vector(){}

我们再重载其它形式的构造函数，例如 vector<int> v(10,0) ，开 10 个空间并将它们初始化为 0，实现如下：

			// vector<int> v(10,0);vector(int n, const T& value = T()){reserve(n);for (int i = 0; i < n; i++){push_back(value);}}

我们在缺省值中给了一个匿名对象，因为我们不知道 T 的类型是什么，所以我们在缺省值中需要给一个匿名对象；如果是内置类型，它会初始化为 nullptr 或 0，我们以前了解到的是编译器不会对内置类型进行处理，但是匿名对象会对它进行处理；注意在类型前要加 const 因为匿名对象具有常性。如果是自定义类型，它会去调自己的构造函数给缺省值。

使用如下图：

我们还需要重载一个构造的形式，用迭代器区间进行构造，实现如下：

			// vector<string> v(str.begin(),str.end());template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

我们在类模板内再使用了函数模板，这个函数模板的生命周期只在这个构造函数内；使用如下：

6. 拷贝构造函数

拷贝构造函数只需要申请和形参对象一样大的空间，然后插入数据即可，实现如下：

			// 拷贝构造函数 -- v2(v1);vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

7. 赋值运算符重载

赋值运算符重载我们利用传参拷贝 tmp，然后将 *this 的数据和 tmp 进行交换即可，最后返回 *this，tmp 出了作用域会自动调用析构函数；实现如下：

			// 赋值运算符重载 -- v2 = v1;vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}

8. 析构函数

析构函数只需要释放 _start 的空间即可，因为 _start, _finish, _endofstorage 实际上都是同一块空间，只是它们所在的位置不一样，实现如下：

			// 析构函数~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}