【C++】vector介绍以及模拟实现（超级详细＜=＞源码并存）

欢迎来到我的Blog，点击关注哦💕

前言

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中不采用mencpy
  1. mencpy拷贝只能进行内置类型的浅拷贝，不能进行自定义类型的深拷贝
  2. 在这里面进行依次赋值，或者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，以避免重复扩容效率低下
• 在开始时候记录原始空间的大小，是为了避免迭代器失效
  1. 进行空间的扩容，会将原来的空间析构，原始的计算空间大小已经已释放，指向的_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

• 两种情况

  1. N<capacity

     直接进行移动_finish

  2. N>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

• 首先进行容量的检查

• 直接将_finsih位置解引用赋值，++_finsih

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://iteratorconst_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;}//capacityvoid 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;}//modifyvoid 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;};}