【STL】vector的底层原理及其实现

vector的介绍

vector是一个可变的数组序列容器。
在这里插入图片描述
1.vector的底层实际上就是一个数组。因此vector也可以采用连续存储空间来存储元素。也可以直接用下标访问vector的元素。我们完全可以把它就当成一个自定义类型的数组使用。
2.除了可以直接用下标访问元素，vector还支持动态开辟空间以提高其灵活度。这也是vector与数组最大的区别之一。
3.为了减少不断插入元素带来的扩容消耗问题，vector会分配一些额外的空间以适应可能的增长，因此实际开辟的空间需要比已存在元素占有空间要大。vector的底层采用每次扩容原来空间的1.5或者2倍（不同编译器的扩容策略可能不同）。
4.由于底层是用数组实现的，不可避免地也具有数组的缺点，即除了尾插的插入、删除的效率低下。

vector的使用

关于vector的使用在cplusplus上一览无余。我接下来介绍常用的一些接口。

vector的定义

在这里插入图片描述
vector一共有4个构造函数，分别对应不同的构造场景。

1.vector().无参构造
2.vector(size_type n,const value_type& val=value_type()).构造并且初始化n个元素的值为value.
3.vector(const vector& x).拷贝构造
4.vector(InputIterator first,InputIterator last).迭代器初始化构造

#include <iostream>
#include <vector>
int main()
{// constructors used in the same order as described above:std::vector<int> first;                                // 无参构造std::vector<int> second(4, 100);                       // 构造的同时初始化4个元素都为100std::vector<int> third(second.begin(), second.end());  // 迭代器初始化构造std::vector<int> fourth(third);                       // 拷贝构造//迭代器初始化构造示例int myints[] = { 16,2,77,29 };std::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));std::cout << "The contents of fifth are:";for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

vector迭代器的使用

在这里插入图片描述
其中rbegin和rend是反向迭代器reverse_iterator类型，rbegin指向的是vecotr对象的最后一个元素，遍历方式和begin一样，只不过反向迭代器++的时候是往前移动。rend则指向vector第一个元素。

带c表示用const修饰了thsi指针。比如cbegin和cend都用const修饰迭代器指向的内容，即不可以修改迭代器指向元素的值。

const_iterator cbegin() const noexcept;

vector空间增长问题

跟vector空间有关的成员函数有
在这里插入图片描述

1.size（）返回当前元素个数
2.max_size（）返回vector最多能容纳元素的个数

3.关于resize

void resize (size_type n, value_type val = value_type());

resize可以调整vector的元素个数为n。
如果n<size(),删除后面的元素.
如果n>size(),增加元素个数到n,新增元素的值为val。
值得注意的是，如果n>size()并且大于capacity(),则会先扩容到n。

4.capacity()返回当前容量大小。vs下capacity是按1.5倍增长的，g++是按2倍增长的。

5.reserve()

void reserve (size_type n);

reserve(n)要求扩容到至少可以容纳n个元素。

6.shrink_to_fit()要求缩容到合适的容量。这个函数一般不常用。

vector扩容机制

用以下代码观察vs下的vector的扩容机制

int main() {vector<int>A;int t = A.capacity();for (int i = 0; i < 20; i++) {A.push_back(i);if (A.capacity() != t) {//每次容量发生改变就打印并输出cout << A.capacity() << endl;t = A.capacity();}}
}

在这里插入图片描述
每次扩容都是1.5倍，向下取整。

同样的代码，来看g++环境下的扩容机制：
在这里插入图片描述
每次扩容都是原来的2倍！

vector的增删查改

在这里插入图片描述
assign：

range(1)版本的assign函数可以用迭代器给vector对象重新赋值。会覆盖原来的内容，相当于赋值操作。

fill(2)版本的assign函数可以赋值给调用对象n个value的值。
在这里插入图片描述
push_back：尾插一个元素
pop_back:弹出最后一个元素

insert:
在这里插入图片描述
single element（1）版本，在迭代器position指向的位置处插入一个val.

fill（2）版本，可以在迭代器position指向的位置处插入n个值为val的元素。

range（3）版本，在position指向的位置处，插入一段首尾迭代器指向的所有元素。
在这里插入图片描述
erase:

可以删除position指向位置的元素，或者删除first-last所有指向元素。

swap：交换两个vector对象。
clear:清空vector对象的所有元素，并不会清空容量。
emplace:

可以在position指向位置处插入一个以args为参数构造出来的新元素，并返回插入成功后指向该位置的迭代器。
在这里插入图片描述
emplace_back:作用跟empace函数类似，只不过是尾插。

迭代器失效问题

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

简单来说就是我们在扩容的时候会开辟新空间，如果原来的迭代器没有被更新，还是指向原来的地址，那么就会造成程序崩溃。也有可能是在

具体有以下几种情况造成迭代器失效：

会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。
指定位置元素的删除操作–erase

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代
器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是
没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效
了。

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

迭代器失效解决办法：使用之前更新迭代器。

vector的模拟实现

vector.h包含了类的声明与定义。我这里没有分离。

#define _CRT_SECURE_NO_WARNINGS 1
#include<assert.h>
#include<string>
#include<algorithm>
#include<iostream>
namespace bit
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;template<class T> friend void Swap(vector<T>& A, vector<T>& B);iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin() const{return _start;}const_iterator end() const {return _finish;}// construct and destroyvector() {_start = _finish = _endOfStorage = nullptr;}vector(int n, const T& value = T()) {reserve(n);for (size_t i = 0; i < n; i++)push_back(value);}template<class inputiterator>vector(inputiterator first, inputiterator last) {size_t n = last - first;reserve(n);memcpy(_start, first, n * sizeof(T));_finish = _start + n;_endOfStorage = _start + n;}vector(const vector<T>& v) {reserve(v.capacity());for (auto& it : v) {push_back(it);}}vector<T>& operator= (vector<T> v) {reserve(v.capacity());memcpy(_start, v._start, v.size() * sizeof(T));_finish = _start + v.size();return *(this);}~vector() {delete[] _start;_start = _finish = _endOfStorage = nullptr;}// capacitysize_t size() const {return _finish - _start;}size_t capacity() const {return _endOfStorage - _start;}void reserve(size_t n) {if (n>capacity()) {T* temp = new T[n];size_t sz = size();//  memcpy(temp, _start, sz * sizeof(T));for (size_t i = 0; i < sz; i++) {temp[i] = _start[i];}delete[] _start;_start = temp;_finish = _start + sz;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()) {if (n > size()) {reserve(n);T* begin = _start + size();while (begin < _start + n) {*begin = value;begin++;}}else {_finish = _start + n;}}///access///T& operator[](size_t pos) {assert(pos < size()); return _start[pos];}const T& operator[](size_t pos)const {assert(pos < size());return _start[pos];}///modify/void push_back(const T& x) {if (size() == capacity()) {reserve(capacity()==0?4:capacity()*2);}*_finish = x;_finish++;}void pop_back() {assert(size() > 0);_finish--;}void Swap(vector<T>& v) {std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._endOfStorage, _endOfStorage);}bool empty() {return size() == 0;}iterator insert(iterator pos, const T& x) {assert(pos <= _finish&&pos>=_start);size_t len = pos - _start;reserve(size() + 1);pos = _start + len;iterator end = _finish-1;while (end >= pos) {*(end+1) = *end;end--;}*pos = x;_finish++;return _start;}iterator erase(iterator pos) {assert(pos < _finish && pos >= _start);iterator begin = pos+1;while (begin <_finish) {*(begin - 1) = *(begin);begin++;}_finish--;return _start;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};template<class T>void  Swap(vector<T>& A, vector<T>& B) {std::swap(A._start, B._start);std::swap(A._finish, B._finish);std::swap(A._endOfStorage, B._endOfStorage);}}