vector的模拟实现

用户11628325

发布于 2025-12-30 11:29:13

360

文章被收录于专栏：用户11628325的专栏用户11628325的专栏

一、前言

“知所从来，方知其往”。知道一个结构的根本构造才能更好的运用结构。正所谓知己知彼百战不殆。我们了解vector顺序表的大致构造才能更好的运用vector。

二、vector的实现

2.1 vector中的私有变量

前面我们提到过，将类中的的变量私有防止被访问修改。那我们为什么不使用我们模拟string类中的类似数组的结构，增加一个_size和_capacity来判断是否需要扩容？硬是要用_start与_finish相减得出size()和capacity()。主要原因是指针的灵活性与便利性，C语言中最出名的也是最难的就是C语言的指针。并且为了和其他STL容器形成“掎角之势”，vector肯定也要参考其他STL容器的结构，而很多STL容器的基本结构非常复杂，基本上都是通过指针来对元素进行增删查改的。所以这就是为什么vector是用指针实现对数组增删查改的的原因。

//定义一个类模版参数来接收插入vector元素的类型
template<class T>
vector<T>
{
private:
    // 最开始因为没有存储数据就将他们赋值为nullptr，等插入数据后再做调整。
    //起始位置
    T* _start = nullptr;
    //插入的有效元素的末尾位置的下一个位置
    T* _finish = nullptr;
    //有效空间末尾位置的下一个位置
    T* _End_Of_Storahe = nullptr;
}

2.2 vector中的size()和capacity()函数

通过有效元素的末尾位置的下一个位置(_finish)与起始位置(_start)相减得到插入vector元素个数。同理通过new出来的的空间的末尾位置的下一个位置与起始位置的我们可以得到new出来的空间大小。至于为什么都是末尾位置的下一个位置与起始位置相减？其实_finish也可以理解为尾插位置(在元素末尾插入的位置)，如果是末尾位置与起始位置相减则忽略了起始位置元素，如果是尾插位置与起始位置不仅正好将起始位置元素给补上，还使尾插元素更加方便了，可谓是一举两得。

size_t size()
{
    return _finish - _start;
}

size_t capacity()
{
    return _End_Of_Storage - _start;
}

2.3 vector的reserve()和resize()函数

reserve()函数只有一个参数，reserve()会根据接收到的形参开出空间，并将之前vector所保存的值拷贝进来，根据编程环境的不同，对reserve()函数的功能有不同的实现方式，这也就导致了在有些编程环境下可以缩容，有些编程环境只能用来扩容。resize()函数则用来重新调整vector的size大小。关于resize()有两个参数，第一个参数是新的size的值。当要调整到的size超出capacity时自动扩容，开空间肯定需要初始化值的，所以resize()第二个参数用于初始化（在开好空间的时候将值放入新开的空间中）。

我们来根据reserve()函数和resize()函数特性来模拟。由于缩容不太方便管理，所以我们采用reserve()接收到的参数大于capacity()时选择扩容，小于capacity()时则不做处理。resize()扩容时可以借用一下reserve()函数，毕竟有个现成的扩容函数，缩小size时只需要调整尾部的指针与初始位置指针的距离为新的size就行了。

 void reserve(size_t n)
 {
     if (n > capacity())
     {
         //this指针，每个类函数再调用时都会有一个隐藏this指针，通过this指针调用类中的函数和使用类中的变量。
         //进行调佣函数和变量，一般this指针可省略
         size_t size = this->size();
         T* tmp = new T[ n ];
         T* start = _start;

         //理论上可以用memcpy()函数，但是vector可能会存放一些STL的容器
         //或者一些类，这些类仅仅拷贝地址是不行的，需要operator = 
         //等号运算符重载
         for (int i = 0; i < size; ++i)
         {
             *(tmp + i) = *(_start + i);
         }

         delete[] _start;
         _start = tmp;
         _finish = _start + size;
         _End_Of_Storage = _start + n;
     }
 }

//当没有传回value时用缺省值，由于类型不确定
//所以用T()模板的匿名对象专门来给不确定类型的变量初始化
//对于内置类型T()一般都是初始化为零。
 void resize(size_t n, const T& value = T())
 {
     //扩容
     if (n > capacity())
     {
         reserve(n > 2 * capacity() ? n : 2 * capacity());
     }
        
     int size = this->size();
        
     //对新开的空间初始化
     for (int i = size; i < n; ++i)
         _start[i] = value;

     _finish = _start + n;
 }

2.4 构造函数 and 析构函数

构造函数和析构函数。关于构造函数我们可以先不去管他，等插入数据时在申请内存，因为你拿了内存可能并不会立刻就用，你电脑上的其他程序也肯定需要内存，所以我们这里偷个懒，默认构造函数写个空壳，或是直接将指针置为nullptr。

// 构造函数，我们偷个懒。
Vector()
	:_Start(nullptr)
	, _finish(nullptr)
	, _End_Of_Storage(nullptr)
{
	;
}

// 构造函数:根据n个val来初始化Vector。
Vector(size_t n, T val)
{
	reserve(n);
	for (int i = 0; i < n; ++i)
	{
		_Start[i] = val;
	}
	_finish = _Start + n;
}

// initializer_list
// 这里用到C++11的容器initializer_list初始化列表。
// 它可以像我们C语言初始化数组是那样。例如:
// int a[] = { 0 , 21 ,32,132,11,321,152 };
Vector(initializer_list<T> list)
{
    // 再根据这个初始化列表的长度扩容，存放数据。
	reserve(list.size());
	for (auto& e : list)
	{
        // 这个Emplace_back大家最好还是学习C++11在来了解比较好。
        // 总之，只需要知道Emplace比Insert要高效就行了。
		Emplace_back(e);
	}
}

2.5 Insert 函数 and Erase 函数

Insert是插入的意思，顾名思义，它是一种可以根据指定位置插入值。既然将他们放在一块讲解实现，那肯定是他们有互补之处。Erase函数肯定也是可以根据位置做出改变的值。Erase本来就是删除的意思，顾名思义，Insert和Erase都是可以根据参数指向的位置对vector（线性表）做出插入和删除的函数，值的提醒的是指向位置的是迭代器(也就是Iterator，前面说过可以将他理解为一种封装了地址的类)。

Iterator Insert(Iterator pos,const T& val)
{
	// 可用的空间满了。
    // 二倍扩容可以减少向系统申请内存的次数
    // 从而很好地提升效率。
	if (size() == capacity())
	{
		size_t len = pos - _Start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());
        // 特别提醒:扩容后地址会发生变化，所以我们要根据之前pos到_start的距离更新pos。
		pos = _Start + len;
	}

	Iterator end = _finish;

	// 将pos位置上的和pos后位置上的元素往后移动一格。
    // 为新插入的值腾出一个位置出来。
	while (end > pos)
	{
		*(end) = *(end - 1);
		--end;
	}
    // 将腾出来的pos位置赋值为val。
	(*pos) = val;
    // 在加加_finish,更新好Vector的末尾位置。
	++_finish ;

	return pos;
}

// 删除pos位置上的元素。
// 从后往前以一格为单位进行覆盖。
void Erase(Iterator pos)
{
	assert(pos < _finish );
	Iterator tmp = pos;
	while (tmp < _finish )
	{
		*(tmp) = *(tmp + 1);
		++tmp;
	}
	--_finish ;
}

因为小编认为将注意事项写在代码的注释上更好理解，所以这里不做过多解释。

2.6 push_back函数 and pop_back函数

这个非常简单。C++代码讲究能复用就复用，这个可不是偷懒，如果以后你还要修改代码，那你只用修改被复用的代码就行了。所以我们直接用上面的代码，将位置定义为迭代器end或者直接用_End位置。

// 定义begin和end迭代器。
// 这个函数名是系统定好的，不用改。
// 定义好起始位置迭代器和末尾位置的下一个位置(可以理解为有效位置的新插入位置，毕竟一般要插入都是从有效位置的最后一个位置的下一个位置。)的迭代器就好了。
Iterator begin()
{
return _Start;
}

Iterator end()
{
    return _finish;
}

// const迭代器可以理解为int const *(也就是指向位置不变的迭代器。)
// const在*前修饰的是指针指向的位置的数据不发生改变，const在*后修饰的是指针变量的指向不变。
Const_Iterator begin() const
{
    return Const_Iterator(_Start);
}

Const_Iterator end() const
{
    return Const_Iterator(_End);
}

void push_back(T& val)
{
	Insert(end(), val);
}

void pop_back()
{
	Erase(end());
}

2.7 operator 运算符重载函数

这里根据一般的计算机规则明白敲代码就行了，因为数组没必要比较大小，只需要比较是否是同一个数组，改动情况。所以关于判断只写上两个关于operator的函数。

bool operator != (const Self& v)
{
	return !((*this) == v);
}

bool operator == (const Self& v)
{
	if (size() != v.size())
	{
		return false;
	}

	if (_Start != v._Start)
	{
		return false;
	}

	return true;
}

operator = ()拷贝赋值也是一个很重要的代码。赋值时，我们一般只需要令左边的等于右边的就行了，前提要将左边的值清零在进行插入。

// 拷贝（旧式写法）
Vector<T>& operator = (const Vector<T>& v)
{
    // 旧式写法
    if((*this) == v)
	{
	    return (*this);
    }
	clear();
	reserve(v.size());
	for (size_t i = 0; i < v.size(); ++i)
	{
		Emplace_back(v[i]);
	}

	return (*this);
	// 旧式写法如果碰到赋值对象是自己的情况，一上来就将自己的内容清空，太不保险了。
}

void Swap(Vector<T>& s)
{
    // 使用C++内部的swap交换变量。
	std::swap(_Start, s._Start);
	std::swap(_End, s._finish);
	std::swap(_End_Of_Storage, s._End_Of_Storage);
}

// 拷贝（新式写法）
// 直接拷贝构造了一个新的对象再完成交换。
Self& operator = (Vector<T> s)
{
	Swap(s);

	return (*this);
}

2.8 clear 函数

直接清零，但是如果回收内存的话，以后要用又要重新申请，所以我们直接将_finish = _Start，这样即清了零，又完成了任务。

void Empty()
{
    _finish = _Start;
}

2.9 empty函数

这个就更简单了，直接判断是否为空就是判断有没有插入数据，判断_Start和_finish是否指向同一位置就行了。

bool Empty()
{
    return _Start == _finish; 
}

2.10 emplace函数 and emplace_back函数

等小编将C++11写好会放个链接在这里的，读者有兴趣可以了解一下。

C++11语法(2)-CSDN博客

下面vector完整版的模拟代码。其中的emplace和emplace_back和Add函数都是用于实现emplace和emplace_back函数的。其实大家实现的时候不用搞这个Add，小编当时只是想分析分析，多搞了个Add函数。

三、全部代码实例

#include <iostream>
#include <cassert>
// <initializer_list>
#include <initializer_list>
#include <utility>
using namespace std;

#include "Iterator.h"

namespace Squence_List
{
	// C++代码坚持能复用就复用。
	template < class T >
	class Vector
	{
	public:
		typedef T* Iterator;
		typedef const T* Const_Iterator;

		typename typedef ReverseIterator < Iterator , T* , T& > Reverser_Iterator;

		typedef Vector< T > Self;

		Vector()
			:_Start(nullptr)
			, _End(nullptr)
			, _End_Of_Storage(nullptr)
		{
			;
		}

		Vector(size_t n, T val)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				_Start[i] = val;
			}
			_End = _Start + n;
		}

		// initializer_list
		Vector(initializer_list<T> list)
		{
			reserve(list.size());
			for (auto& e : list)
			{
				Emplace_back(e);
			}
		}

		// 拷贝构造
		Vector(const Self& v)
		{
			for (int i = 0;i < v.size();++i)
			{
				Emplace_back(v[i]);
			}
		}

		~Vector()
		{
			delete[] _Start;
			_Start = _End = _End_Of_Storage = nullptr;
		}

		size_t size() const
		{
			return _End - _Start;
		}

		size_t capacity() const
		{
			return _End_Of_Storage - _Start;
		}

		Iterator Begin()
		{
			return _Start;
		}

		Iterator End()
		{
			return _End;
		}

		Const_Iterator Begin() const
		{
			return Const_Iterator(_Start);
		}

		Const_Iterator End() const
		{
			return Const_Iterator(_End);
		}

		Reverser_Iterator Rbegin()
		{
			return Reverser_Iterator(End() - 1);
		}

		Reverser_Iterator Rend()
		{
			return Reverser_Iterator(Begin() - 1);
		}

		Reverser_Iterator Rbegin()const
		{
			return Reverser_Iterator(End() - 1);
		}

		Reverser_Iterator Rend()const
		{
			return Reverser_Iterator(Begin() - 1);
		}

		bool operator != (const Self& v)
		{
			return !((*this) == v);
		}

		bool operator == (const Self& v)
		{
			if (size() != v.size())
			{
				return false;
			}

			if (_Start != v._Start)
			{
				return false;
			}

			return true;
		}

		// 拷贝（旧式写法）
		Self& operator = (const Self& v)
		{
			// 旧式写法
			 if((*this) == v)
			 {
				 return (*this);
			 }
			clear();
			reserve(v.size());
			for (size_t i = 0; i < v.size(); ++i)
			{
				Emplace_back(v[i]);
			}

			return (*this);
			// 旧式写法如果碰到赋值对象是自己的情况，一上来就将自己的内容清空，太不保险了。
		}

		//void Swap(Self& s)
		//{
		//	std::swap(_Start, s._Start);
		//	std::swap(_End, s._End);
		//	std::swap(_End_Of_Storage, s._End_Of_Storage);
		//}

		//// 拷贝（新式写法）
		//// 直接拷贝一个新的对象再完成交换。
		//Self& operator = (Vector<T> s)
		//{
		//	Swap(s);

		//	return (*this);
		//}

		const T& operator [] (size_t i) const
		{
			// 满足则不报错，不满足则报错。
			assert(i < size());

			return *(_Start + i);
		}

		T& operator [] (size_t i)
		{
			// 满足则不报错，不满足则报错。
			assert(i < size());

			return *(_Start + i);
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				// 记录一下之前的数组长度，方便更新。
				size_t len = size();
				// memcpy用于浅拷贝。
				// memcpy(tmp ,_Start ,sizeof(T) * len);
				// 循环赋值，可以用于特殊类对象的深拷贝。
				for (size_t i = 0; i < size(); ++i)
				{
					tmp[i] = _Start[i];
				}
				delete[] _Start;
				_Start = tmp;
				_End = _Start + len;
				_End_Of_Storage = _Start + n;
			}
		}

		void resize(size_t n, T val)
		{
			reserve(n > 2 * capacity() ? n : 2 * capacity());
			T* tmp = _Start + n;
			while (_End < tmp)
			{
				(*_End) = val;
				++_End;
			}
		}

		// 将pos位置上的和pos后位置上的元素往后移动一格，插入在pos位置。
		Iterator Insert(Iterator pos,const T& val)
		{
			// 可用的空间满了。
			if (size() == capacity())
			{
				size_t len = pos - _Start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _Start + len;
			}

			Iterator end = _End;

			// 将pos位置上的和pos后位置上的元素往后移动一格。
			while (end > pos)
			{
				*(end) = *(end - 1);
				--end;
			}
			(*pos) = val;
			++_End;

			return pos;
		}

		// 删除pos位置上的元素。
		// 从后往前以一格为单位进行覆盖。
		void Erase(Iterator pos)
		{
			assert(pos < _End);
			Iterator tmp = pos;
			while (tmp < _End)
			{
				*(tmp) = *(tmp + 1);
				++tmp;
			}
			--_End;
		}

		void push_back(T& val)
		{
			Insert(End(), val);
		}

		void pop_back()
		{
			Erase(End());
		}

		// 利用参数包，能够包含多种参数类型的参数。
		// 同时，万能引用还可以减少拷贝构造。
		// 新的模板参数，是为了接受这个参数包。
		// 里面的东西不一定是纯粹的某种类型。但是一定可以解析出类型出来。
		template < class X, class... Args >
		Iterator Add(Const_Iterator position, X&& val, Args&&...args)
		{
			size_t len = position - _Start;

			// 保存这个插入位置。
			// 以后其他元素还要插入到这个插入位置中。
			Iterator it = Insert(_Start + len, val);
			Add(it, args...);

			return it;
		}

		// 重载一个类似于参数包解析完成了，接收参数包的参数为空函数。
		template < class... Args >
		Iterator Add(Iterator it)
		{
			return it;
		}

		template<class... Args>
		Iterator Emplace(Iterator it , Args&&... args)
		{
			return Add(it,args...);
		}

		template < class... Args >
		void Emplace_back(Args&&... args)
		{
			Emplace(End(), args...);
		}

		void clear()
		{
			_End = _Start;
		}

	private:
		T* _Start;
		T* _End;
		T* _End_Of_Storage;
	};

	void test_Vector()
	{
		Vector<int> v;

		/*for (int i = 0; i < 10; ++i)
		{
		}*/
		v.Emplace_back(0, 1, 2, 3, 4, 5, 6);

		//v.Erase(v.End() - 1);

		for (int i = 0; i < 7; ++i)
		{
			cout << v[i] << endl;
		}
	}

	void test02()
	{
		Vector<int> v;

		for (int i = 0; i < 13; ++i)
		{
			v.Emplace_back(i);
		}

		Vector<int>::Reverser_Iterator it = v.Rbegin();

		while (it != v.Rend())
		{
			cout << *(it) << ' ';
			++it;
		}
	}

	void test03()
	{
		Vector<int> v = { 1 , 2 , 3 , 4 , 5 , 6 };

		for (int i = 0;i < v.size();++i)
		{
			cout << v[i] << ' ';
		}
		cout << endl;
	}

	void test04()
	{
		Vector<int> v = { 1 , 2 , 3 , 4 , 5 , 6 };

		v = v;

		for (int i = 0; i < v.size(); ++i)
		{
			cout << v[i] << ' ';
		}
		cout << endl;
	}

	void test05()
	{
		Vector<int> v;

		v.Emplace(v.Begin(), 1, 2, 3, 4, 6, 6, 2);

		Vector<int> v1;

		
		for(int i = 0;i < v.size();++i)
		{
			cout << v[i] << ' ';
		}
		cout << endl;
	}
}
int main()
{
	Squence_List::test04();

	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-12，如有侵权请联系 cloudcommunity@tencent.com 删除

变量