【STL】 vector的底层实现

1.vector的模拟代码完整实现（后面会拆分开一个一个细讲）

#pragma once
#include<assert.h>// 抓重点namespace bit
{/*template<class T>class vector{public:typedef T* iterator;private:T* _a;size_t _size;size_t _capacity;};*/template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}iterator begin(){return _start;}iterator end(){return _finish;}// 类模板的成员函数// 函数模板 -- 目的支持任意容器的迭代器区间初始化template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()) //创建一个包含 n 个元素的向量，并且每个元素都被初始化为 val 的值。//如果没有提供 val 参数，则默认使用 T() 构造出的默认值。{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(initializer_list<T> il)//vector(initializer_list<T> il)：这是 vector 类的构造函数。它允许使用花括号 {} 括起来的一组元素来初始化 vector 对象。{reserve(il.size());for (auto e : il){push_back(e);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}// 强制编译器生成默认的vector() = default;// v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}// 16:05继续void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}// v1 = v3vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * old_size);for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}}size_t capacity() const{return _end_of_storage - _start;}size_t size()  const{return _finish - _start;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}void push_back(const T& x){/*if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;*/insert(end(), x);}void pop_back(){assert(size() > 0);--_finish;}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}// 迭代器// 勿在浮沙筑高台void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};

2.vector的成员变量

在查看STL库里面vector的实现时，我们发现它是一个类模板并且定义了三个成员变量，分别是iterator start、iterator finish、 iterator end_of_storage用来标记开始，结束，以及总容量，对于vector来说其迭代器iterator就是T*，例如我们之前学习过的顺序表插入的是int类型的数据，所以对存放int类型的vector来说T*就是int*。以此类推，在定义的时候<>里面定义的类型就是容器中所存放的类型  char string list等都可以存放在里面

3.vector中的部分成员变量

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}iterator begin(){return _start;}iterator end(){return _finish;}

4.vector中的构造函数

        1.默认构造

vector():_start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{}
//上下等价
//vector() = default; //强制编译器生成默认的

        2.拷贝构造

// v2 (v1)
vector(const vector<T>& v)
{reserve(v.capacity());for (auto e : v) push_back(e);
}

        3.迭代器区间初始化

//类模板的成员函数,迭代器区间初始化
//函数模板  -- 目的支持任意容器迭代器区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{//reserve(last - first);while (first != last){push_back(*first);++first;}
}

        4.n个val构造

//n个val构造
vector(size_t n, const T& val = T())//缺省值不能给0，因为T可能是string，所以给匿名对象T()
{reserve(n);while(n--){push_back(val);}
}//n个val构造，第一个参数为int类型
vector(int n, const T& val = T())//缺省值不能给0，因为T可能是string，所以给匿名对象
{reserve(n);while(n--){push_back(val);}
}

5.对于构造函数的测试

void test_vector7()
{vector<string> v1(10);vector<string> v2(10, "xxx");for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}cout << endl;vector<int> v3(10,1); //若没有迭代器函数区间匹配，可以将就运行//vector <int> v3(10u, 1); //因为调用的是unsigned那个for (auto e : v3){cout << e << " ";}cout << endl;vector<int> v4(10, 1);for (auto e : v4){cout << e << " ";}cout << endl;
}

6.initializer_list构造

initializer_list是C++新增的一个类型，方便初始化，支持将花括号括起来的值initializer_list，initializer_list对象里面有两个指针，指向花括号里面值开始和结尾的下一个，并支持迭代器，所以可以使用范围for来遍历，当然这个要编译器支持将花括号传给容器

//initializer_list构造
vector(initializer_list<T> il)
{reserve(il.size());//size表示数据个数for (auto i : il){push_back(i);}
}

6.1 initializer_list构造的测试代码

void test_vector8() //initializer_list构造测试
{//隐式类型转换vector<int> v1({ 1,2,3,4,5 });vector<int> v2 = { 6,7,8,9,10 };for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}
}

7.赋值运算符的重载

// v1 = v3
vector<T>& operator = (vector<T> v)
{swap(v);return *this;
}

这里使用传值传参，是实参的拷贝，所以我们将它与被赋值的对象交换后返回即可完成赋值，并且交换后形参生命周期结束就会自动调用析构函数释放原来的空间。

5.vector类中的容量操作

1.size 与 capacity

int main(){cout << "指定⼤⼩为10时：\n";vector<int> v(10, 1);cout << v.size() << endl;cout << v.capacity() << endl;vector<int> v1;v1.push_back(1);v1.push_back(1);v1.push_back(1);v1.push_back(1);cout << "插⼊四个数据时：\n";cout << v1.size() << endl;cout << v1.capacity() << endl;cout << "插⼊五个数据时：\n";v1.push_back(1);cout << v1.size() << endl;cout << v1.capacity() << endl;return 0;}
输出结果：
指定⼤⼩为10时：
1010
插⼊四个数据时：
44
插⼊五个数据时：
58

capacity的代码在g++ vs 和 clang下分别允许会发现，vs下capacity是按1.5倍增⻓，clang和g++是按2倍增⻓。这个 问题经常会考察，不要固化的认为，vector增容都是2倍，具体增⻓多少是根据具体的需求定义的。vs是PJ版本 STL，g++是SGI版本STL

2.resize

resize在开空间的同时还会进⾏初始化，影响size 使⽤resize()函数可以改变调⽤对象的size和capacity⼤⼩，如果指定的⼤⼩⼩于size时相当于删除数据，当指定⼤⼩ ⼤于size时则作⽤为扩容＋初始化（对于int默认初始化为0）

int main(){vector<int> v(10, 1);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//1 1 1 1 1 1 1 1 1 1 
v.resize(20);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
v.resize(5);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//1 1 1 1 1 
//指定⼤⼩⼩于当前的size时，再指定初始化内容时不会修改原始内容
v.resize(3, 3);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}//1 1 1return 0;}

3.reserve

reserve只负责开辟空间，如果确定知道需要⽤多少空间，reserve可以缓解vector增容的代价缺陷问题。 使⽤reserve()函数可以更改调⽤对象的capacity的⼤⼩，注意，如果指定⼤⼩⼩于当前的capacity时，则不会做任何 处理

int main(){vector<int> v(10, 1);cout << "原始⼤⼩：\n";cout << v.capacity() << endl;cout << v.size() << endl;cout << "扩容到20：\n";v.reserve(20);cout << v.capacity() << endl;cout << v.size() << endl;cout << "扩容到5：\n";v.reserve(5);cout << v.capacity() << endl;cout << v.size() << endl;return 0;}
输出结果：
原始⼤⼩：
1010
扩容到20：
2010
扩容到5：
2010

6.vector类中的数据遍历操作

void test2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);
//迭代器遍历
//指明迭代器类型
vector<int>::iterator it1 = v.begin();while (it1 != v.end()) {cout << *it1 <<" ";it1++;}cout << endl;//1 2 3 4//下标遍历
for (size_t i = 0; i < v.size(); i++) {cout << v[i] << " ";}cout << endl;//1 2 3 4//范围forfor(auto &e : v){cout << e <<" ";}cout << endl;//1 2 3 4}int main(){test2();}

6.2 operator 与at()函数

6.3 正向遍历begin()和end()迭代器——⾮const

#include <iostream>#include <vector>using namespace std;int main(){vector<int> v(10, 1);//正向迭代器——⾮constvector<int>::iterator it = v.begin();while (it != v.end()){*it = 2;//可修改
cout << *it << " ";it++;}return 0;}
输出结果：
2 2 2 2 2 2 2 2 2 2

6.4逆向遍历rbegin()和rend()迭代器——⾮const

#include <iostream>#include <vector>using namespace std;int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//逆向迭代器——⾮constvector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){(*rit)++;//可修改
cout << *rit << " ";
rit++;}return 0;}
输出结果：
5 4 3 2

6.5 assign()函数

//使⽤⼀个对象的迭代器区间为调⽤对象分配内容
#include <iostream>#include <vector>using namespace std;int main(){//vector<int> v(5, 1);vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto num : v){cout << num << " ";}
cout << endl;vector<int> v1(10, 2);//v.assign(v1.begin(), v1.end());v.assign(v1.begin(), v1.end());for (auto num : v){cout << num << " ";}return 0;}
输出结果：
1 2 3 42 2 2 2 2 2 2 2 2 2//指定n个内容为调⽤对象分配
#include <iostream>#include <vector>using namespace std;int main(){//vector<int> v(5, 1);vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto num : v){cout << num << " ";}cout << endl;//vector<int> v1;//v1.push_back(5);//v1.push_back(6);//v1.push_back(7);//v1.push_back(8);//v.assign(v1.begin(), v1.end());v.assign(10, 5);for (auto num : v){cout << num << " ";}return 0;}
输出结果：
1 2 3 45 5 5 5 5 5 5 5 5 5

7.插入insert

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){//防止迭代器因为后面的扩容失效，所以要提前记录pos位置size_t len = pos - _start;//size_t len = size();size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len; //判断扩容之后os位置，防止野指针出现使迭代器失效}iterator end = _finish - 1; //后移while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

这里要注意迭代器因为扩容导致pos失效的问题(野指针)，所以要提前规避，记录好pos相对位置，然后再即时更新pos迭代器，否则就会出现随机值;

此外，insert的参数pos是对实参的拷贝，形参的改变不会影响实参，所以外部的实参也会失效，但是我们也不能通过引用传参，因为其迭代器返回的是临时拷贝具有常性不能通过引用传参，所以这里我们就可以通过控制insert函数的返回值来解决，我们会返回更新后的迭代器，这样就可以访问该位置了。

7.2push_back可以直接复用insert进行实现

//尾插
void push_back(const T& x)
{insert(end(), x);
}

7.3push_back与pop_back函数的测试

//在指定的的迭代器位置后插⼊内容val#include <iostream>#include <vector>using namespace std;
int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;v.insert(v.begin() + 3, 5);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}return 0;}
输出结果：
1 2 3 41 2 3 5 4

7.4在指定的迭代器位置后开始插⼊n个val

//在指定的迭代器位置后开始插⼊n个val#include <iostream>#include <vector>using namespace std;int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;v.insert(v.begin() + 3, 5, 10);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}return 0;}
输出结果：
1 2 3 41 2 3 10 10 10 10 10 4

7.5在指定的迭代器位置后开始插⼊⼀个其他对象对应的迭代器区间中的内容

#include <iostream>#include <vector>using namespace std;int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;vector<double> v1;v1.push_back(5.2);v1.push_back(6.3);v1.push_back(7.4);v1.push_back(8.5);//根据调⽤对象的类型决定强制转换的类型
v.insert(v.begin() + 3, v1.begin(), v1.end());//将double强制转换成int类型存⼊int类型的vector对象
for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;v1.insert(v1.begin() + 3, v.begin(), v.end());//将int强制转换成double类型存⼊double类型的vector
对象
}for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}return 0;
输出结果：
1 2 3 41 2 3 5 6 7 8 45.2 6.3 7.4 1 2 3 5 6 7 8 4 8.5

8.删除erase

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != _finish) //从pos + 1开始往前移动{*(it - 1) = *it;++it;}--_finish;return pos;
}

erase()之后迭代器失效问题

• 有可能删除之后缩容
• 删除最后一个位置会导致越界访问

所以我们认为删除操作之后迭代器也会失效，和插入函数一样通过返回迭代器来更新迭代器使用才行

8.2 删除指定位置的⼀个数据

//删除指定位置的⼀个数据
#include <iostream>#include <vector>using namespace std;int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//1 2 3 4vector<int>::iterator it = v.begin() + 1;v.erase(it);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//1 3 4//不可以再删除迭代器⼀开始指向的位置，存在迭代器失效问题
//v.erase(it);//如果还需要删除下标为1的位置需要再将迭代器更新
it = v.begin() + 1;v.erase(it);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";//1 4}return 0;}

8.3 删除迭代器区间中的内容

 //删除迭代器区间中的内容
#include <iostream>#include <vector>
using namespace std;int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//1 2 3 4v.erase(v.begin() + 2, v.end());for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//1 2return 0;}

9.swap函数

使⽤swap()函数可以交换调⽤对象和指定对象中的数据

#include <iostream>#include <vector>using namespace std;int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>    
v1(5, 1);cout << "交换前：\n";cout << "v的size：" << v.size() << endl;//4cout << "v的capacity：" << v.capacity() << endl;//4for (auto num : v){cout << num << " ";}cout << endl;//1 2 3 4cout << "v1的size：" << v1.size() << endl;//5cout << "v1的capacity：" << v1.capacity() << endl;//5
for (auto num : v1){cout << num << " ";}//1 1 1 1 1v.swap(v1);cout << "\n交换后：\n";cout << "v的size：" << v.size() << endl;//5cout << "v的capacity：" << v.capacity() << endl;for (auto num : v){cout << num << " ";}//11111cout << endl;cout << "v1的size：" << v1.size() << endl;//4cout << "v1的capacity：" << v1.capacity() << endl;//4for (auto num : v1){cout << num << " ";}//1234return 0;}

10.find函数

#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator it = find(v.begin(), v.end(), 3);
cout << *it << endl;//3return 0;}

11.某帅哥做的笔记——pdf

vector