Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法…感兴趣就关注我bua！
Vector
0.Vector简介
Vector是一个动态数组的容器，可以容纳各种类型的序列容器。称其为数组，意味着：**其也可以用下标去访问，类似与之前的顺序表。**所以，Vector分配空间的时候也不是说用多少就分配多少，会多分配一些，因为向系统申请空间这个成本是相对较大的。
1.Vector常用接口
因为String之前已经详细解读了各个接口，在标准STL中，各个接口的传入参数，返回值都大多相同。所以在这一篇章不重点讲解接口。遗忘的uu们可以去看看这篇文章 [String解析]((45条消息) 【C++技能树】String类解析与模拟实现_ppeua的博客-CSDN博客)
vector的声明方式,其中T为模板
vector<T>v;
1.1constructor构造函数
| (constructor)构造函数声明 | 接口说明 |
| vector() | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个va |
| vector (const vector& x); | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
直接上代码来看看Vector构造函数的使用
1.默认构造函数:
vector (const allocator_type& alloc = allocator_type());
其中 const allocator_type& alloc = allocator_type()是指用来创建一个自定义的分配器来实现特殊的内存管理行为，如对齐、缓存池等.在初学C++的阶段我们只需要使用默认内存分配策略即可.
所以其默认构造函数使用为
vector<T>v; vector<int>v;
2.填充构造函数:
vector (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());
往容器中填充n个val
vector<int>v(5,1);
3.使用迭代器构造函数:
template <class InputIterator> vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
vector<int>v(5,3); vector<int>v1(v.begin(),v.end());
首先,先使用填充构造,往v里填充5个3.之后使用迭代器构造函数,begin()–end()这个范围里的内容都放到v1中.
4.拷贝构造函数:
vector (const vector& x);
1.2 iterator
| iterator的使用 | 接口说明 |
| begin()+end() | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator |
| rbegin()+rend() | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator |
**这是[begin(),end()]与[rbegin(),rend()]的结构图:**任何使用迭代器的场景中,其都是[begin(),end())左闭右开的模式(也就是可以取到左边,但取不到右边)
sort与find
这两个函数是 algorithm中给出的函数.
find
InputIterator find (InputIterator first, InputIterator last, const T& val);
在指定区间中寻找val,找到之后返回其iterator,其实现如下,通过遍历区间去寻找val
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; }
vector<int>v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout<<*find(v.begin(),v.end(),3);
输出结果为:3
sort
void sort (RandomAccessIterator first, RandomAccessIterator last);
将指定区间中的数据进行排序.默认使用 < 进行排序 (相同元素不保证是稳定排序.也就是会改变原始数据的位置)
vector<int>v; v.push_back(4); v.push_back(1); v.push_back(3); v.push_back(2); sort(v.rbegin(),v.rend()); for(auto s:v) cout<<s;
使用逆向迭代器,进行从大到小的排序.
输出结果为:4321
1.3 Capacity相关接口
| 容量空间 | 接口说明 |
| size | 返回数据个数 |
| capacity | 返回当前占用空间大小 |
| empty | 返回是否为空 |
| resize | 改变size |
| reserve | 改变capacity |
和string都相同,这里 就不过多赘述
1.4 Modify相关接口
| Modify | 接口说明 |
| push_back | 尾插 |
| pop_back | 尾删 |
| insert | 插入 |
| erase | 删除 |
| swap | 交换两个vector空间 |
| operator[] | 像数组一样访问 |
这里需要重点讲解下erase与insert,他们的作用其是通过当前迭代器的位置插入或删除一个元素.
但是如果直接使用之前的迭代器,可能会出现迭代器失效的问题:本质原因就是访问了已经不属于自己的迭代器
vector底层原理旧空间被释放掉， 而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的 空间，而引起代码运行时崩溃。 解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新 赋值即可。
2. Vector模拟实现
Vector和String类似,也有三个私有属性,用来表示存储空间的范围(STL源码可能实现不一样 但思想是这样).
并先声明迭代器(可以简单的看为类型指针)
typedef T* iterator; typedef const T* const_iterator; private: _start; _finish; _endofstorage;
2.1 构造函数
2.1.1无默认参数构造函数
vector(): _start(nullptr), _finish(nullptr), _endofstorage(nullptr) { }
这是最初版的构造函数,需要用到初始化列表对其进行构造.但是在C++11后打了补丁后,可以在私有属性的时候就给其默认参数.
private: _start=nullptr; _finish=nullptr; _endofstorage=nullptr;
此时的默认构造函数就可以什么都不需要写了.
vector(): { }
2.1.2 带参数默认构造函数
1.填充形构造函数：
vector(size_t n, const T& val = T()) { resize(n, val); } vector(int n, const T& val = T()) { resize(n, val); } template<class InputIterator> vector(InputIterator begin, InputIterator end) { while (begin != end) { push_back(*begin); begin++; } }
第二个形式参数给了一个默认参数，在C++中每一个类型都可以看成一个类，此时其默认构造函数就是类名（），例如
int(),double(),string()…
第一种和第二种本质是在完成同一个事情，但是由于有了迭代器的加入。当你使用如下构造方案时
vector<int>v(1,5);
我们给的构造参数是两个相同的类型,我们本意是想让他走第一种进行初始化构造,但因为类型相同,往往会被识别成第三种,使用迭代器进行初始化.
所以我们需要对int进行单独处理,所以有了第二种.
2.使用vector类型进行构造:
vector(const vector<T>& v) { _start = new T[v.capacity()]; for (size_t i = 0; i < v.size(); i++) { _start[i] = v._start[i]; } //_finish = v._finish; 只是令地址相等 _finish = _start + v.size(); _endofstorage = _start + v.capacity(); }
在类的成员函数中可以直接访问类的私有成员变量,
这里不能使用memcpy:因为memcpy是对内存进行拷贝,若是内置类型则可以完成任务.但为自定义类型,则会变成浅拷贝,所以需要调用=进行重载完成拷贝
整体思路为:先给start分配一段新的空间,然后依次将形参中的东西拷贝过来,最后计算长度与空间大小.(注意这里finish是地址不能直接赋值)
2.2析构函数
要把申请的空间全部还给系统.
~vector() { if (_start) { delete[]_start; _start = _finish = _endofstorage = nullptr; } }
2.3 迭代器
iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; }
2.4 Capacity相关接口
size_t capacity()const { return _endofstorage - _start; } size_t size()const { return _finish - _start; }
resize():
void resize(size_t n, const T& val) { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish != _start + n) { *_finish = val; _finish++; } } }
void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n; } }
这里与string类差不多就不过多解释了.
2.5 swap()
void swap(vector<T>v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }
2.6operator =
vector<T>& operator= (const vector<T>& v) { swap(v); return *this; }
2.7 push_back()
void push_back(const T& x) { if (_finish == _endofstorage) { reserve(capacity() == 0 ? 1 : capacity() * 2); } *_finish = x; _finish++; }
2.8 insert()
iterator insert(iterator pos, const T& val) { assert(pos < _finish&& pos >= _start); if (_finish == _endofstorage) { size_t newpos = pos - _start; reserve(capacity() == 0 ? 1 : capacity() * 2); pos = _start + newpos; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = end; end--; } *pos = val; ++_finish; return pos; }
2.9 erase()
iterator erase(iterator pos) { assert(pos < _finish&& pos >= _start); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; it++; } _finish; return pos; }
2.10 pop_back()
void pop_back() { erase(--end()); }
2.11 opeartor []
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; }
pos < _finish&& pos >= _start); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; it++; } _finish; return pos; }
## 2.10 pop_back() ~~~cpp void pop_back() { erase(--end()); }
2.11 opeartor []
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; }
