【C++】vector模拟实现

个人主页 ： zxctscl如有转载请先通知

1. 前言

在之前已经介绍了vector【C++】vector介绍，这次来看看它的模拟实现。

2. vector源码

来看一下vector源码：这里的成员变量都是iterator，而iterator是value_type*，看源码中value_type*又是T。

再来看一下构造，为了方便知道它最开始的初始化。

来看一下push_back：

3. 构造、赋值和析构

3.1 无参构造

像源码里面的一样，成员变量直接给缺省值，这样在构造的时候就走初始化列表。

namespace
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		vector() 
		{}
	private:
		iterator _start=nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;

	};
}

3.2 拷贝构造

这里是一个深拷贝，先开空间reserve(v.capacity())，再把数据插入进去。

		// v2(v1)
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (auto& e : v)
			{
				push_back(e);
			}
		}

3.3 迭代器区间构造

类模板里面的成员函数可以是函数模板。 可以是其他容器的迭代器也可以用。就是遍历这个迭代区间，然后把数据放进去就行。

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

还可以用string类，支持隐式类型转换，就转换为对应的ASCII码：

	void test_vector4()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(4);
		print_vector(v1);

		vector<int> v2(v1.begin()+1, v1.end()-1);
		print_vector(v2);

		string str("abcd");
		vector<int> v3(str.begin() , str.end() );
		print_vector(v3);
	}

size_type就是size_t:

value_type是T:

这里缺省值不能给0，T类型可能会string，也可能是int,所以这里就用一个T类型的匿名对象。直接开n个空间，然后插入这n个数据push_back(val)。

		vector(size_t n, const T& val = T())
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}

		}

此时在调用的时候出现了非法的间接寻址：

因为这里调用到的是：

发现把这段代码屏蔽调之后就没有问题：

那么为什么会只有一个的时候就没有问题，两个都有就会出现非法的间接寻址这样的问题呢？编译器更喜欢上面的模板函数，就是匹配的问题，用其他的来匹配函数模板的构造是没有问题的：

所以为了避免这个问题，来看看源代码是怎么解决方式：

源代码直接重载，那么我们也写一个就行解决：

		vector(int n, const T& val = T())
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}

		}

在c++11里面支持花括号：

其实就是两个指针：

单参数的构造函数，隐式类型转换：还可以直接push_back一个常量字符串

想要模拟实现支持花括号的构造，就得用到initializer_list

initializer_list里面就包了迭代器：

所以模拟实现出来就是：

		vector(initializer_list<T> il)	
		{
			reserve(il.size());
			for(auto& e:il)
			{
				push_back(e);
			}
		}

结果测试没有问题：

3.4 赋值

如果把v3赋值给v1，传值传参，v就是v3的拷贝，然后和this交换，返回*this.

		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

3.5 析构

      ~vector()
		{
			delete[] _start;
			_start = _finish = _endofstorage=nullptr;
		}

4. Capacity

4.1 size

        size_t size() const
		{
			return _finish - _start;
		}

4.2 capacity

        size_t capacity() const
		{
			return _endofstorage - _start;
		}

4.3 empty

      bool empty()
		{
			return _start == _finish;
		}

4.4 resize

resize这里要给一个缺省值，这个缺省值不能给0。这里可能会是string也可能是vector，所以这里用一个无参匿名对象const T& val = T()。内置类型没有初始化，但是C++出现模板之后，被迫给内置类型也有构造和析构。来看个例子：

如果空间不够就先扩容reserve(n);，然后再插入。删除就只保留n个数据，直接把_finish = _start + n;

      void resize(size_t n, const T& val = T())
		{
			if (n > size())
			{
				reserve(n);
				// 插入
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				// 删除
				_finish = _start + n;
			}
		}

来个代码测试一下：

	void test_vector2()
	{
		

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(4);
		print_vector(v1);

		v1.resize(10);
		print_vector(v1);

		v1.resize(3);
		print_vector(v1);
	}

4.5 reserve

先判断给的空间是不是大于n，如果大于就开新空间，再把原来的数据拷贝到新开的空间，然后删除就空间，更新_start、_finish和_endofstorage。空间够了，就插入数据，最后++_finish。

      void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t old_size = size();
				memcpy(tmp, _start, size() * sizeof(T));
				delete[] _start;

				_start = tmp;
				_finish = tmp + old_size;
				_endofstorage = tmp + n;
			}
		}

但是用string类型插入，就挂了:

调试发现这里发生权限：

问题就在reserve里面的memcpy,vector深拷贝了，但是这里的string是浅拷贝，就是说memcpy导致string是浅拷贝：

要解决这里问题就需要string深拷贝，释放上面的空间，对下面的没有影响。解决方式就是：直接赋值

       void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t old_size = size();
				//memcpy(tmp, _start, size() * sizeof(T));
				for (size_t i = 0; i < old_size; i++)
				{
					tmp[i] = _start[i];
				}
				delete[] _start;

				_start = tmp;
				_finish = tmp + old_size;
				_endofstorage = tmp + n;
			}
		}

这样就没有问题了：

5. 下标访问和迭代器

下标访问，const对象和非const对象都写：

       T& operator[](size_t pos)
		{
			assert(pos < size());
            return _start[pos];
		}
		
		const T& operator[](size_t pos)const
		{
			assert(pos < size());
			return _start[pos];
		}

都和之前的string的底层相同。迭代器先得有开始和结尾,就先记录一下，const对象和非const对象都写：

        typedef T* iterator;
		typedef const T* const_iterator;
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}

		const_iterator begin()const
		{
			return _start;
		}
	    const_iterator end()const
		{
			return _finish;
		}

来个例子测试一下：

void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

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

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

	}

6. 输出

想要实现不同类型的vector打印输出，就直接定义一个类模板template<class T>然后再写打印函数输出的时候把T代入：

void print_vector(const vector<T>& v)
	{
		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;
	}

来个代码测试一下：

        vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(4);
		print_vector(v1);

		vector<double> v2;
		v2.push_back(1.1);
		v2.push_back(2.2);
		v2.push_back(3.1);
		print_vector(v2);

这样不同类型的vector就都可以实现输出：

7. Modifiers

7.1 push_back

先检查是否想要扩容，如果没有开空间，就先给4，不然就扩容2倍：size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;，再把原来的数据拷贝到新开的空间，然后删除就空间，更新_start、_finish和_endofstorage。空间够了，就插入数据，最后++_finish。

void push_back(const T& val)
		{
			if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				T* tmp = new T[newcapacity];
				memcpy(tmp, _start, size() * sizeof(T));
				delete[] _start;

				_start = tmp;
				_finish = tmp + size();
				_endofstorage = tmp + newcapacity;

			}
			*_finish = val;
			++_finish;
		}

用代码测试的时候发现出错：

这个是因为在计算新开辟空间的_finish时候用的size是新空间的，而原来空间的已经丢失了。

为了避免这样，先记录一下原来的size大小size_t old_size = size();,再将原来的代码修改为：

void push_back(const T& val)
		{
			if (_finish == _endofstorage)
			{
				size_t old_size = size();
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				T* tmp = new T[newcapacity];
				memcpy(tmp, _start, size() * sizeof(T));
				delete[] _start;

				_start = tmp;
				_finish = tmp + old_size;
				_endofstorage = tmp + newcapacity;

			}
			*_finish = val;
			++_finish;
		}

加上测试代码看看结果：

void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

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

	}

发现可以了：

7.2 pop_back

先判断一下里面是不是有数据，就先判断一下，在执行尾删。尾删就直接--_finish;

        void pop_back()
		{
			assert(!empty());

			--_finish;			
		}

来看看测试：

void test_vector1()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		print_vector(v1);

		v1.pop_back();
		v1.pop_back();
		print_vector(v1);
    }

7.3 insert

在pos位置插入一个数据，这个pos位置得先判断一下，必须在_start和_finish之间。

再判断一下是不是想要扩容，如果扩容了要更新pos。为什么要更新pos？开了新的空间pos位置已经释放了，已经成了野指针。所以得计算相对位置size_t len = pos - _start;，更新到新的空间里面才好找到pos：pos = _start + len;。

然后挪动数据到pos位置，再把val插入pos位置，再更新一下_finish。

void insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);

				// 如果扩容了要更新pos
				pos = _start + len;
			}

			iterator it = _finish - 1;
			while (it >= pos)
			{
				*(it + 1) = *it;
				--it;
			}
			*pos = val;
			++_finish;
		}

7.4 erase

删除每个位置的数据，同样得先判断一下pos的位置在_start和_finish之间，然后挪动数据覆盖，再--_finish。

      void erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;
		}

来测试一下：

		vector<double> v2;
		v2.push_back(1.1);
		v2.push_back(2.2);
		v2.push_back(3.3);
		v2.push_back(4.4);
		print_vector(v2);

		v2.insert(v2.begin(), 11.11);
		print_vector(v2);

		
		v2.erase(v2.begin());
		print_vector(v2);

		v2.erase(v2.begin() + 2);
		print_vector(v2);

7.5 swap

这里直接调用库里面的swap：

		void swap(vector<T> v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);

		}

8. 迭代器失效

8.1 insert导致迭代器失效

这里插入数据之后，发现对应出来了随机值

这里是因为it指向旧空间扩容了，被释放了：

怎么解决，如果加引用的话，那么就不能像下面图中这样传了：

而库里面是怎么解决的呢？库里面就直接不使用这个失效的迭代器，所以这里也是，如果要找的话，就重新更新一下

8.2 erase导致迭代器失效

先来看一个代码：删除所有偶数，有三种情况第一种：这个是成功的：

第二种：有连续两个4时候，有个4没有删除：

第三种：最后一个是4，,这样就挂了：

第一种：删除4之后，5就覆盖了4的位置，然后再加加。

第二种：删除4之后，后面一个4就覆盖了4的位置，然后再加加，这里就跳过了后面这个4。

第三种：删除4之后，后面一个5就覆盖了4的位置，然后再加加，这里会出现删除最后这个4之后，it往后再加加，就会和end错开，循环判断条件成立，还好继续，就会越界

那么怎么解决这些问题呢？

迭代器失效后，不要直接使用，如果要使用就按规则重新更新后使用。然后把erase实现里面把返回的位置更新一下就行：

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;

			return pos;
		}

这样就可以使用了：

9. 附代码

#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;

namespace bit
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		vector()
		{}

		// v2(v1)
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (auto& e : v)
			{
				push_back(e);
			}
		}

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		vector(size_t n, const T& val = T())
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}

		}
		vector(int n, const T& val = T())
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}

		}

		vector(initializer_list<T> il)	
		{
			reserve(il.size());
			for(auto& e:il)
			{
				push_back(e);
			}
		}

		void swap(vector<T> v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);

		}

		//v3=v1
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		~vector()
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}

		size_t size() const
		{
			return _finish - _start;
		}

		T& operator[](size_t pos)
		{
			assert(pos < size());

			return _start[pos];
		}


		const T& operator[](size_t pos) const
		{
			assert(pos < size());

			return _start[pos];
		}

		size_t capacity() const
		{
			return _endofstorage - _start;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t old_size = size();
				//memcpy(tmp, _start, size() * sizeof(T));
				for (size_t i = 0; i < old_size; i++)
				{
					tmp[i] = _start[i];
				}
				delete[] _start;

				_start = tmp;
				_finish = tmp + old_size;
				_endofstorage = tmp + n;
			}
		}

		void resize(size_t n, const T& val = T())
		{
			if (n > size())
			{
				reserve(n);
				// 插入
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				// 删除
				_finish = _start + n;
			}
		}

		void push_back(const T& val)
		{
			/*if (_finish == _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			*_finish = val;
			++_finish;*/

			insert(end(), val);
		}

		void pop_back()
		{
			assert(!empty());

			--_finish;

			/*erase(--end());*/
		}

		bool empty()
		{
			return _start == _finish;
		}

		void insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);

				// 如果扩容了要更新pos
				pos = _start + len;
			}

			iterator it = _finish - 1;
			while (it >= pos)
			{
				*(it + 1) = *it;
				--it;
			}
			*pos = val;
			++_finish;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;

			return pos;
		}

	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;
	};

	
	template<class T>
	void print_vector(const vector<T>& v)
	{
		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;

	
	}

	void test_vector1()
	{
		/*vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		print_vector(v1);

		v1.insert(v1.begin()+2, 30);
		print_vector(v1);*/


		vector<double> v2;
		v2.push_back(1.1);
		v2.push_back(2.2);
		v2.push_back(3.3);
		v2.push_back(4.4);
		print_vector(v2);

		v2.insert(v2.begin(), 11.11);
		print_vector(v2);

		
		v2.erase(v2.begin());
		print_vector(v2);

		v2.erase(v2.begin() + 2);
		print_vector(v2);





		/*for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;*/
	}

	void test_vector2()
	{
		

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(4);
		print_vector(v1);

		v1.resize(10);
		print_vector(v1);

		v1.resize(3);
		print_vector(v1);
	}

	void test_vector3()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(4);
		print_vector(v1);

		vector<int> v2=v1;
		print_vector(v2);


	}

	void test_vector4()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(4);
		print_vector(v1);

		/*vector<int> v2(v1.begin()+1, v1.end()-1);
		print_vector(v2);

		string str("abcd");
		vector<int> v3(str.begin() , str.end() );*/
		/*print_vector(v3);*/
	}

	void test_vector5()
	{
		vector<int> v1(10,1);
		print_vector(v1);

		

		/*vector<char> v3(10, 'a');
		print_vector(v3);*/

	}

	void test_vector6()
	{
		//auto x= { 1,2,3,4,5,6,7,8,9,10};
		//cout << typeid(x).name()<< endl;


		//vector<int> v1 = { 1,2,3,4,5,6,7,8 };

		 单参数的构造函数，隐式类型转换
		//string str = "11111"; // 构造 + 拷贝构造 -> 优化 直接构造
		//const string& str1 = "11111"; // 构造临时对象，引用的是临时对象
		//vector<string> v;
		//v.push_back(str);
		//v.push_back(string("22222"));
		//v.push_back("33333");

		
		vector<int> v1 = { 1,2,3,4,5,6,7,8 };
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

	}
	void test_vector7()
	{
		vector<string> v;
		v.push_back("11111");
		v.push_back("22222");
		v.push_back("33333");
		v.push_back("44444");
		v.push_back("55555");

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void test_vector8()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		v1.push_back(6);
		v1.push_back(7);
		v1.push_back(8);
		print_vector(v1);

		vector<int>::iterator it = v1.begin() + 3;
		v1.insert(it, 40);

		print_vector(v1);
		it= v1.begin() + 3;
		cout << *it << endl;
	}
	void test_vector9()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(5);
		v1.push_back(4);
		
		print_vector(v1);

		// 删除偶数 -- 迭代器失效以后，不要直接使用，如果要使用按规则重新更新后使用
		
		vector<int>::iterator it = v1.begin();

		
		while (it != v1.end())
		{
			if (*it % 2 == 0)
			{
				it = v1.erase(it);
			}
			else
			{
				++it;
			}
		}

		//print_vector(v1);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

有问题请指出，大家一起进步！！！