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

【C++】vector介绍以及模拟实现

• 前言
• • vector介绍
• vector常见操作
• • 构造函数
  • iterator
  • capacity
  • modify
• `vector`模拟实现
• • 存储结构
  • 默认构造函数
  • 构造函数
  • • 拷贝构造函数
    • 赋值运算符重载
    • 析构函数
  • 容量（capacity）
  • • `size`和`capzcity`
    • reserve
    • resize
  • 修改（modify）
  • • push_back
    • • • • 直接将`_finsih`位置解引用赋值，`++_finsih`
    • pop_back
    • insert
    • erase
  • 元素访问（Element access）
  • • operator [ ]
  • 迭代器（iterator）
• 源码

前言

string的特性和用法以及底层的探索已经，虽然string不算container的成员之一，但是也见到了其的影子，接下来让我们看看vector

vector介绍

vector 是 C++ 标准模板库（STL）中的一个动态数组容器，它提供了动态大小调整和高效的随机访问功能。vector 的元素在内存中是连续存储的，这意味着可以通过指针或索引高效地访问元素。vector 自动管理其内部使用的内存，不需要手动分配和释放，支持常见容器操作，如插入、删除、遍历等.

vector常见操作

构造函数

iterator

capacity

modify

vector模拟实现

存储结构

结构上使用命名空间myvector进行封装，防止与库冲突，使用class封装成为对象vector

这样typedef的一点是和STL保持一致

• 写vector写成类模板，可以支持存贮多种类型数据
• _start表示数据存储的开始地址
• _finish表示数据存贮的的下一个地址
• _end_of_storage表示数据当前开辟的最大空间的地址

namespace myvector {     template     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  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& 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 v) {     std::swap(_start, v._start);     std::swap(_finish, v._finish);     std::swap(_end_of_storage, v._end_of_storage); }  vector operator=(vector 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  #include  #include   namespace MyVector { 	template  	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& 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 v) 		{ 			std::swap(_start, v._start); 			std::swap(_finish, v._finish); 			std::swap(_end_of_storage, v._end_of_storage); 		}  		template  		vector(InputIterator first, InputIterator last) 		{ 			while (first != last) 			{ 				push_back(*first); 				++first; 			} 		} 		vector operator=(vector 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; 	};  }