C++ —— vector 的模拟实现

前言

1. vector深度剖析

2. 基础框架

3. 核心接口

3.1 reserve

3.2 push_back 和 pop_back

3.3 print

3.4 insert

3.5 erase

3.6 resize

4. 拷贝构造

4.1 构造与析构

4.2 拷贝构造

4.3 赋值重载

4.4 迭代器区间

5. 使用memcpy拷贝问题

前言

接:C++ —— 关于vector-CSDN博客https://blog.csdn.net/hedhjd/article/details/142334349?spm=1001.2014.3001.5501

1. vector深度剖析

_start ：相当于begin，指向开始的位置
_finish ：相当于size，指向最后一个数据的位置
_end_of_storage ：相当于_capacity

2. 基础框架

//因为vector是用模板写的，所以不能进行声明和定义分离，否则会出现链接错误
#pragma once
#include<assert.h>

 // _start ：相当于begin，指向开始的位置
//_finish ：相当于size，指向最后一个数据的下一个位置
//_end_of_storage ：相当于_capacity

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迭代器
		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}


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

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


		//可读可写
		T& operator[](size_t i)
		{
			assert(i < size());

			return _start[i];
		}

		//只读
		const T& operator[](size_t i) const
		{
			assert(i < size());

			return _start[i];
		}

		//判断是否为空
		bool empty()
		{
			return _start == _finish;
		}


	private:
		iterator _start = nullptr;//给个缺省值
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};

3. 核心接口

3.1 reserve

//修改之后
//扩容
void reserve(size_t n)
{
	if (n > capacity())
	{
		//提前将旧size赋给新size
		size_t old_size = size();
 
		//开辟新空间，创建临时变量
		//new出来的空间是初始化好的，所以可以直接用
		T* tmp = new T[n];

		//memcpy(tmp, _start, old_size * sizeof(T));
		/*如果T是string或者vector类型，就需要进行深拷贝
		 需要赋值进行拷贝数据，否则使用浅拷贝会导致内存泄漏
		*/
		for (size_t i = 0; i < old_size; i++)
		{
			//赋值就是string/vector的赋值，也就是深拷贝
			tmp[i] = _start[i];
		}
		//释放旧空间
		delete[] _start;
		//再把三个私有变量指向新空间
		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

3.2 push_back 和 pop_back

/*T有可能是一个int,也有可能是一个string，还可能是一个vector，
所以需要传&，传&不改变需要加上一个const*/
//尾插
void push_back(const T& x)
{
	//先判断需不需要扩容
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	//如果不需要就直接插入到_finish的位置
	*_finish = x;
	++_finish;
}

//尾删
void pop_back()
{
	assert(!empty());
	--_finish;
}

3.3 print

如果给出的代码编译器不知道该代码是类型还是变量，所以导致识别不出来，那么可以在前面加上 typename 或者改为 auto 自动推导

//给print_vector套一层模板，让它被谁都可以使用
template<class T>
void print_vector(const vector<T>& v)
{
	//如果typename在没有实例化的类模板里面取东西，
	// 那么编译器不能区分这里const_iterator是类型还是静态成员变量
	//typename vector<T>::const_iterator it = v.begin();

	//那么使用auto可以自动推导，由v.begin()推导
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

将print彻底转换成模板，使所有类型都可以使用，不管是string，vector等等

//将print彻底转换成模板，使所有类型都可以使用，不管是string，vector等等
template<class Container>
void print_container(const Container& v)
{
	/*auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;*/

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

3.4 insert

insert在扩容后原来的pos位置就会失效，也就是迭代器失效，就相当于成为了野指针，解决方法是将扩容之前的位置记录下来在扩容后更新pos的位置

//在指定位置插入数据
void insert(iterator pos, const T& x)
{
    assert(pos >= _start);
	assert(pos <= _finish);

	// 扩容
	if (_finish == _end_of_storage)
	{
		/*为了防止迭代器失效的情况，先创建一个临时变量len
		记录扩容之前pos - _start的位置*/
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		//然后再更新pos的位置
		pos = _start + len;
	}

	//将最后一个数据的位置给临时变量end
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;

	++_finish;

	return pos;
}

3.5 erase

erase之后也会出现迭代器失效，所以需要先记录pos原来的位置然后再更新pos

//删除指定位置的数据
void erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);

	iterator it = pos + 1;
	while (it != end())
	{
		*(it - 1) = *it;
		++it;
	}

	--_finish;
}

3.6 resize

用于改变vector的有效长度，也可以用来初始化指定长度的指定数据

三种情况：

1. 当n < size()时，删除多余的元素，直接缩容

2. 当size() < n < capacity()时，直接插入数据

3. 当capacity() < n时，先扩容再插入数据

//用于改变vector的有效长度
//也可以开辟n个空间，使用val去初始化
void resize(size_t n, T val = T())
{
	//n < size，删除数据
	if (n < size())
	{
		_finish = _start + n;
	}
	else//>=size
	{
		//扩容
		reserve(n);
		while (_finish < _start + n)
		{
			//插入数据val
			*_finish = val;
			++_finish;
		}
	}
}

4. 拷贝构造

4.1 构造与析构


	//默认构造
    vector()
	{}

    // C++11 强制生成默认构造
	//vector() = default;



    
	//析构
	~vector()
	{
		if (_start)
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}
	}

4.2 拷贝构造


		//拷贝构造
		vector(const vector<T>& v)
		{
			reserve(v.size());
			for (auto& e : v)
			{
				push_back(e);
			}
		}

4.3 赋值重载

//赋值重载的传统写法
//clear清除数据但是不释放空间
void clear()
{
	_finish = _start;
}

// v1 = v3
vector<T>& operator=(const vector<T>& v)
{
	if (this != &v)
	{
		clear();

		reserve(v.size());
		for (auto& e : v)
		{
			push_back(e);
		}
	}

	return *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);
}

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

	return *this;
}

4.4 迭代器区间

1. 类模版里的成员函数还能继续是函数模版

2. 在迭代器区间构造的函数时可以使用函数模版，这样可以使用任意容器的迭代器初始化，例如链表

//迭代器区间
// 类模板的成员函数，还可以继续是函数模版
//加上一个模板那么迭代器就可以是任意类型的迭代器
//需要推导
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

//可以直接使用size_t类型  使用n个val初始化
vector(size_t n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

//可以直接使用int类型  使用n个val初始化
vector(int n, const T& val = T())
{
	reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

5. 使用memcpy拷贝问题

memcpy拷贝问题的问题其实就是浅拷贝的原因

浅拷贝就是两个指针指向同一块空间，如果一个指针对该空间进行释放或者其他操作就会影响另一个指针导致内存泄漏等问题

所以最好使用深拷贝让两指针指向不同的空间然后使其数据保持一致

错误代码


		//扩容
		//错误代码
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				//提前将旧size赋给新size
				size_t old_size = size();

				//开辟新空间，创建临时变量
				//new出来的空间是初始化好的，所以可以直接用
				T* tmp = new T[n];

				//将旧空间里的数据拷贝给新空间
				//将 _start指向的size() * sizeof(T)空间里的数据拷贝到临时变量tmp里去
				memcpy(tmp, _start, size() * sizeof(T));

				//释放旧空间
				delete[] _start;
				//再把三个私有变量指向新空间
				_start = tmp;
				_finish = tmp + old_size;
				_end_of_storage = tmp + n;
			}
		}

修改之后

//修改之后
//扩容
void reserve(size_t n)
{
	if (n > capacity())
	{
		//提前将旧size赋给新size
		size_t old_size = size();

		//开辟新空间，创建临时变量
		//new出来的空间是初始化好的，所以可以直接用
		T* tmp = new T[n];

		//memcpy(tmp, _start, old_size * sizeof(T));
		/*如果T是string或者vector类型，就需要进行深拷贝
		 否则使用浅拷贝会导致内存泄漏
		*/
		for (size_t i = 0; i < old_size; i++)
		{
			//赋值就是string/vector的赋值，也就是深拷贝
			tmp[i] = _start[i];
		}
		//释放旧空间
		delete[] _start;
		//再把三个私有变量指向新空间
		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

感谢观看~