【C++】vector模拟实现

04-08 1974阅读

个人主页： zxctscl

如有转载请先通知

文章目录

1. 前言
2. vector源码
3. 构造、赋值和析构

3.1 无参构造
3.2 拷贝构造
3.3 迭代器区间构造
3.4 赋值
3.5 析构
4. Capacity

4.1 size
4.2 capacity
4.3 empty
4.4 resize
4.5 reserve
5. 下标访问和迭代器
6. 输出
7. Modifiers

7.1 push_back
7.2 pop_back
7.3 insert
7.4 erase
7.5 swap
8. 迭代器失效

8.1 insert导致迭代器失效
8.2 erase导致迭代器失效

9. 附代码

1. 前言

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

2. vector源码

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

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

来看一下push_back：

3. 构造、赋值和析构

3.1 无参构造

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

namespace
{
	template
	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& v)
		{
			reserve(v.capacity());
			for (auto& e : v)
			{
				push_back(e);
			}
		}

3.3 迭代器区间构造

类模板里面的成员函数可以是函数模板。

可以是其他容器的迭代器也可以用。

就是遍历这个迭代区间，然后把数据放进去就行。

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

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

	void test_vector4()
	{
		vector 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 v2(v1.begin()+1, v1.end()-1);
		print_vector(v2);
		string str("abcd");
		vector 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  
此时在调用的时候出现了非法的间接寻址：
因为这里调用到的是：
发现把这段代码屏蔽调之后就没有问题： 
那么为什么会只有一个的时候就没有问题，两个都有就会出现非法的间接寻址这样的问题呢？
编译器更喜欢上面的模板函数，就是匹配的问题，用其他的来匹配函数模板的构造是没有问题的：
所以为了避免这个问题，来看看源代码是怎么解决方式：
源代码直接重载，那么我们也写一个就行解决： 
		vector(int n, const T& val = T())
		{
			reserve(n);
			for (int i = 0; i  
在c++11里面支持花括号：
 
其实就是两个指针：
单参数的构造函数，隐式类型转换：
还可以直接push_back一个常量字符串 
想要模拟实现支持花括号的构造，就得用到initializer_list
initializer_list里面就包了迭代器：
所以模拟实现出来就是： 
		vector(initializer_list il)	
		{
			reserve(il.size());
			for(auto& e:il)
			{
				push_back(e);
			}
		}
 
结果测试没有问题：
 
3.4 赋值 
如果把v3赋值给v1，传值传参，v就是v3的拷贝，然后和this交换，返回*this. 
		vector& operator=(vector 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  
来个代码测试一下： 
	void test_vector2()
	{
		
		vector 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  
这样就没有问题了：
 
5. 下标访问和迭代器 
下标访问，const对象和非const对象都写： 
       T& operator[](size_t pos)
		{
			assert(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 v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		for (size_t i = 0; i