阅读量:0
【C++】vector介绍以及模拟实现
前言
string的特性和用法以及底层的探索已经，虽然string不算container的成员之一，但是也见到了其的影子，接下来让我们看看vector
vector介绍
vector 是 C++ 标准模板库（STL）中的一个动态数组容器，它提供了动态大小调整和高效的随机访问功能。vector 的元素在内存中是连续存储的，这意味着可以通过指针或索引高效地访问元素。vector 自动管理其内部使用的内存，不需要手动分配和释放，支持常见容器操作，如插入、删除、遍历等.
vector常见操作
构造函数
| (constructor)构造函数声明 | 接口说明 |
|---|---|
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); （重点） | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
iterator
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
capacity
| 函数声明 | 接口说明 |
|---|---|
| capacity | 获取容量大小 |
| size | size 获取数据个数 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
modify
| vector增删查改 | 接口说明 |
|---|---|
| push_back（重点） | 尾插 |
| pop_back （重点） | 尾删 |
| find | 查找。（注意这个是算法模块实现，不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] | 像数组一样访问 |
vector模拟实现
存储结构
结构上使用命名空间myvector进行封装，防止与库冲突，使用class封装成为对象vector
这样typedef的一点是和STL保持一致
- 写
vector写成类模板，可以支持存贮多种类型数据 _start表示数据存储的开始地址_finish表示数据存贮的的下一个地址_end_of_storage表示数据当前开辟的最大空间的地址
namespace myvector { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; iterator _finish; iterator _end_of_storage; }; } 默认构造函数
构造函数
- 初始化是使用的都是空指针
vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} - 使用
n个val初始化对象
vector(size_t n, const T& val = T()) { resize(n, val); } - 根据可以模板的嵌套的性质，再次进行模板的定义
- 这是使用两个迭代器的进行初始化
template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } } 拷贝构造函数
- 利用一个对象初始化另外一个对象传引用
new出和传递的对象一样大小的空间，在string类中我们利用了mencpy进行拷贝，在vector中不采用mencpymencpy拷贝只能进行内置类型的浅拷贝，不能进行自定义类型的深拷贝- 在这里面进行依次赋值，或者
push_back
- 最后进行
_finish和_end_of_storage的初始化
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 = _start + v.size(); _end_of_storage = _start + v.capacity(); } 赋值运算符重载
- 在
operator=的参数中是值传递，是实参的拷贝，这里面利用这个特性进数据的交换 - 返回
this指针就是赋值的内容了
void swap(vector<T> v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } vector<T> operator=(vector<T> v) { swap(v); return *this; } 析构函数
- 判断
_start是否为空为空，避免再次析构
~vector() { if (_start) { delete[] _start; _start = _finish = _end_of_storage = nullptr; } } 容量（capacity）
size和capzcity
vector的size和capacity不同于string类中的不一样，vector定义的是指针- 充分利用只针的特性，（指针—指针）是数值，可以计算出
capacity和size
size_t size()const { return _finish - _start; } size_t capacity()const { return _end_of_storage - _start; } reserve
- 开始判断需要扩容的大小是否大于
capacity，以避免重复扩容效率低下 - 在开始时候记录原始空间的大小，是为了避免迭代器失效
- 进行空间的扩容，会将原来的空间析构，原始的计算空间大小已经已释放，指向的
_start_finish_end_of_storage已经失效
- 进行空间的扩容，会将原来的空间析构，原始的计算空间大小已经已释放，指向的
- 这里还是采用在这里面进行依次赋值，或者
push_back - 更新
_start_finish_end_of_storage
void reserve(size_t n) { if (n > capacity()) { T* tmp = new T[n]; size_t sz = size(); if (_start) { //memcpy(tmp, _start, sizeof(T)*capacity()); //string 类深拷贝 for (int i = 0; i < sz; i++) { tmp [i] = _start[i]; } delete[] _start; } _start = tmp; _finish = sz + _start; _end_of_storage = _start + n; } } resize
两种情况
N<
capacity直接进行移动
_finishN>
capacity进行容量的检查和扩容，依次赋值
val
const T& val = T()这句话是针对内置类型和自定义类型，C++这里将内置类型进行了升级int = 1; <=> int(1);//这里int有点像构造函数
void resize(size_t n, const T& val = T()) { if (n < capacity()) { _finish = n + _start; } else { reserve(n); while (_finish != _start + n) { *_finish = val; ++_finish; } } } 修改（modify）
push_back
void push_back(const T& x) { if (_finish == _end_of_storage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; ++_finish; } pop_back
- 复用
erase
void pop_back() { erase(end()-1); } insert
- 进行断言，防止
pos越界访问 - 判断空间的大小
_finish == _end_of_storage size_t step = pos - _start用step记录，距离_start距离，扩容的时候将原空间释放，pos将无法访问,扩容完成后进行pos的恢复- 将
pos位置的数据依次进行移动、 - 插入
pos位置的值，修改_finish - 为了避免迭代器失效，返回现在的位置
pos
iterator insert(iterator pos, const T& x) { assert(pos <= _finish && pos >= _start); if (_finish == _end_of_storage) { //防止迭代器失效 size_t step = pos - _start; size_t newcapacity = capacity() == 0 ? 0 : capacity() * 2; reserve(newcapacity); //防止迭代器失效 pos = _start + step; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; ++end; } *pos = x; ++_finish; return pos } erase
- 进行断言，防止
pos越界访问 - 将
pos后面的元素向前面移动，进行覆盖 - 为了避免迭代器失效，返回现在的位置
pos
iterator erase(iterator pos) { assert(pos <= _finish && pos >= _start); while (pos != _finish) { *pos = *(pos + 1); pos++; } --_finish; return pos } 元素访问（Element access）
operator [ ]
- 实现
const和非const两种，只读和可读可改 - 充分利用字符串特性可以进行下标的访问
T& operator[](size_t pos) { assert(pos >= 0 && pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos >= 0 && pos < size()); return _start[pos]; } 迭代器（iterator）
- 本质还是指针，直接进行指针的返回就好
//iterator const_iterator cbegin() { return _finish; } const_iterator cend() const { return _start; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; 源码
#include <string.h> #include <assert.h> #include <iostream> namespace MyVector { template <class T> class vector { public: //iterator const_iterator cbegin() { return _finish; } const_iterator cend() const { return _start; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; } //默认构造 vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} vector(size_t n, const T& val = T()) { resize(n, val); } ~vector() { if (_start) { delete[] _start; _start = _finish = _end_of_storage = nullptr; } } 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 = _start + v.size(); _end_of_storage = _start + v.capacity(); } void swap(vector<T> v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } } vector<T> operator=(vector<T> v) { swap(v); return *this; } //capacity void reserve(size_t n) { if (n > capacity()) { std::cout << "reserve(size_t n)" << std::endl; T* tmp = new T[n]; size_t sz = size(); if (_start) { //memcpy(tmp, _start, sizeof(T)*capacity()); //string 类深拷贝 for (int i = 0; i < sz; i++) { tmp [i] = _start[i]; } delete[] _start; } _start = tmp; _finish = sz + _start; _end_of_storage = _start + n; } } size_t size() { return _finish - _start; } size_t capacity() { return _end_of_storage - _start; } size_t size()const { return _finish - _start; } size_t capacity()const { return _end_of_storage - _start; } //modify void push_back(const T& x) { if (_finish == _end_of_storage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; ++_finish; } void pop_back() { erase(end()-1); } void insert(iterator pos, const T& x) { assert(pos <= _finish && pos >= _start); if (_finish == _end_of_storage) { //防止迭代器失效 size_t step = pos - _start; size_t newcapacity = capacity() == 0 ? 0 : capacity() * 2; reserve(newcapacity); //防止迭代器失效 pos = _start + step; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; ++end; } *pos = x; ++_finish; return pos; } void erase(iterator pos) { assert(pos <= _finish && pos >= _start); while (pos != _finish) { *pos = *(pos + 1); pos++; } --_finish; return pos; } void resize(size_t n, const T& val = T()) { if (n < capacity()) { _finish = n + _start; } else { reserve(n); while (_finish != _start + n) { *_finish = val; ++_finish; } } } T& operator[](size_t pos) { assert(pos >= 0 && pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos >= 0 && pos < size()); return _start[pos]; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; } 