【C++初阶】vector的模拟实现

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

大家好我是沐曦希💕

文章目录

一、前言
二、无参构造&析构
三、基础接口
四、reserve和resize
五、尾插尾删
六、其他构造
- 1.迭代器区间构造
- 2.拷贝构造
七、memcpy问题
八、完整代码

一、前言

在模拟实现容器时候我们需要的不是造一个更好的轮子而是在了解原理更好理解和运用容器。

那么通过查看源码抽出vector容器主题框架:

template <class T, class Alloc = alloc>
class vector {
     typedef T value_type;
     typedef value_type* iterator;
     typedef const value_type* const_iterator;
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
}

本质上与T*a,size_t size,size_t capacity是类似的
在这里插入图片描述
对于size = _finish - _start

在这里插入图片描述

对于capacity = _endofstorage-_start

二、无参构造&析构

无参构造

初始化值为空。

vector()
  :_start(nullptr)
  ,_finish(nullptr)
  ,_endofstarge(nullptr)
{}

析构

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

三、基础接口

1.empty和clear

empty

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

clear

void clear()
{
	_finish = _start; //这里可不能置为nullptr
}

2.size和capacity

size

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

-capacity

int capacity() const
{
	return _endofstarge - _start;
}

加const是让const类对象和非const类对象都能调用

3.[]和iterator

这里提供const和非const两个版本加const是只可读不能更改不加const是可读可写。

[]

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

iterator
同理普通迭代器和const迭代器版本,同理范围for循环此时也是可以实现的

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

四、reserve和resize

reserve

reserve最大问题是深拷贝开辟新空间进行赋值的时候如果直接使用memcpy是浅拷贝。

void reserve(size_t n)
{
	if (n > capacity())
	{
		int Oldsize = size();//size需要保存方便更改_finsih
		T* tmp = new T[n];
		//为空不需要拷贝
		if (_start)
		{
			for (size_t i = 0; i < Oldsize; ++i)
			{
				tmp[i] = _start[i];
			}
		}
		_start = tmp;
		_finish = _start + Oldsize;
		_endofstarge = _start + n;
		tmp = nullptr;
	}
}

size()要保存

因为size = _finish - _start_start已经改变了。而_finish没有改变那么size就是一个任意数了不再是原来的size了就需要在开始时候用Oldsize进行存储size

使用memcpy问题

memcpy拷贝数据是按字节来拷贝的属于浅拷贝对于需要在堆开辟空间的自定义类型存在问题多次释放同一块空间将导致程序崩溃

vector<vector<int>> vv;
vector<int> v(4, 1);
//复用push_back尾插
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
//需要扩容成2倍
vv.push_back(v);
for (size_t i = 0; i < vv.size(); i++)
{
	for (size_t j = 0; j < vv[i].size(); j++)
	{
	  cout << vv[i][j] << " ";
	}
	cout << endl;
}

resize

用n个数据初始化vector那么就要用n和size进行比对分情况讨论:
1、当n大于当前的size时将size扩大到n扩大的数据为val若val未给出则默认为容器所存储类型的默认构造函数所构造出来的值。
2、当n小于当前的size时将size缩小到n。

根据resize函数的规则进入函数我们可以先判断所给n是否小于容器当前的size若小于则通过改变_finish的指向直接将容器的size缩小到n即可否则先判断该容器是否需要增容然后再将扩大的数据赋值为val即可。

void resize(size_t n, const T& value = T())
{
	if (n < size())
	{
		_finish = _start + n;
	}
	reserve(n); // reserve对于n<capacity是不会做任何事情的
	for (size_t i = 0; i < n - size(); ++i)
	{
		_finish[i] = value;
	}
	_finish = _start + n;
}

resize的参数初始化值为T类型的构造这里可不能直接初始化为0要是T是自定义类型呢是vector呢所以这里如果T是vector的化调用的就是vector的构造函数。另外这里还需要注意的一点是构造vector的时候是匿名对象匿名对象具有常性不可修改所以要加上const修饰。对于内置类型比如int都是有构造函数的

五、尾插尾删

void push_back(const T& value)
{
	if (_finish == _endofstarge)
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*_finish = value;
	++_finish;
}
void pop_back()
{
	assert(_start < _finish);
	if (_finish > _start)
	{
		--_finish;
	}
}

六、其他构造

1.迭代器区间构造

vector(InputIterator first, InputIterator last)
    :_start(nullptr)
	,_finish(nullptr)
	,_endofstarge(nullptr)
{
	while (first != last)
	{
		push_back(*first);//int不能解引用
		++first;
	}
}

类模板的成员函数可以是函数模板使之可以是任意类型的迭代器区间包括了自身的迭代器区间构造
另外初始化列表全部初始化为nullptr没有初始化就是随机值出现野指针

2.拷贝构造

初始化列表全都要初始化为nullptr否则就是随机值

//写法一
vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstarge(nullptr)
{
	reserve(v.capacity());
	for (const auto& e : v)
	{
		push_back(e);
	}
}
//写法二
void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstarge, v._endofstarge);
}
vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstarge(nullptr)
{
	vector<T> tmp(v.begin(), v._end());
	swap(tmp);
}

赋值重载

可以复用拷贝构造

//缺陷是不能自己拷贝自己
vector& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

这种写法就是有一个小问题如果是自己拷贝自己呢加个判断没用因为此时已经传值传参过来了加个判断没啥意义了。但是这个问题不大我们允许存在平时自己也很少自己赋值自己。

另外这里是传值调用有人会说了传引用也可以啊此时如果是引用的话v2赋值给v1,v1不是v2的拷贝直接把v2换成了v1,v1换给了v2,v2本身已经发生变化了这不是赋值了。

七、memcpy问题

如果拷贝的是内置类型的元素memcpy即高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝指向同一块空间假设我们仍然在reserve接口中使用memcpy进行拷贝

int main()
{
	bite::vector<bite::string> v;
	v.push_back("1111");
	v.push_back("2222");
	v.push_back("3333");
	return 0;
}

问题分析

memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
如果拷贝的是内置类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。

结论如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃。

八、完整代码

vector.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace lj
{
	template<class T>
	class vector
	{
	public:
		// Vector的迭代器是一个原生指针
		typedef T* iterator;
		typedef const T* const_iterator;
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const_iterator cbegin() const
		{
			return _start;
		}
		const_iterator cend() const
		{
			return _finish;
		}
		iterator rbegin()
		{
			return _finish;
		}
		iterator rend()
		{
			return _start;
		}
		const_iterator rbegin() const
		{
			return _finish;
		}
		const_iterator rend() const
		{
			return _start;
		}
		// construct and destroy
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{}
		vector(int n, const T& value = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(value);
			}
		}
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		vector(const vector<T>& v)
		{
			int* tmp = new T[v.capacity()];
			for (size_t i = 0; i < v.size(); ++i)
			{
				tmp[i] = v[i];
			}
			_start = tmp;
			_finish = _start + v.size();
			_endofstorage = _start + v.capacity;
		}
		vector<T>& operator=(vector<T> v)
		{
			vector tmp(v);
			_start = _finish = _endofstorage = nullptr;
			swap(_start, tmp._start);
			swap(_finish, tmp._finish);
			swap(_endofstorage, tmp._endofstorage);
		}
		~vector()
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
		// capacity
		size_t capacity() const
		{
			return _endofstorage - _start;
		}
		size_t size() const
		{
			return _finish - _start;
		}
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				int Oldsize = size();
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < size(); ++i)
					{
						tmp[i] = _start[i];
					}
				}
				_start = tmp;
				_finish = _start + Oldsize;
				_endofstorage = _start + n;
				tmp = nullptr;
			}
		}
		void resize(size_t n, const T& value = T())
		{
			if (n <= size())
			{
				_finish = _start + n;
			}
			reserve(n);
			for (size_t i = 0; i < n - size(); ++i)
			{
				_finish[i] = value;
			}
			_finish = _start + n;
		}

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

		///modify/
		void push_back(const T& x)
		{
			if (_finish == _endofstorage)
			{
				int newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}
			*_finish = x;
			++_finish;
		}
		void pop_back()
		{
			assert(_start < _finish);
			if (_finish > _start)
			{
				--_finish;
			}
		}
		void swap(vector<T>& v)
		{
			vector tmp;
			tmp._start = _start;
			_start = v._start;
			v._start = tmp._start;

			tmp._finish = _finish;
			_finish = v._finish;
			v._finish = tmp._finish;

			tmp._endofstorage = _endofstorage;
			_endofstorage = v._endofstorage;
			v._endofstorage = tmp._endofstorage;
			
			tmp._start = tmp._finish = tmp._endofstorage = nullptr;
		}
		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			size_t Olddel = pos - _start;
			if (_finish == _endofstorage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}
			pos = _start + Olddel;
			auto it = _finish;
			while (it > pos)
			{
				*it = *(it - 1);
				it--;
			}
			*pos = x;
			++_finish;
			return pos;
		}
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			auto it = pos;
			while (it < _finish)
			{
				(*it) = *(it + 1);
				it++;
			}
			--_finish;
			return pos;
		}
	private:
		iterator _start; // 指向数据块的开始
		iterator _finish; // 指向有效数据的尾
		iterator _endofstorage; // 指向存储容量的尾
	};
	void test_vector1()
	{
		vector<int> v1(10, 2);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		v1.reserve(20);
		cout << v1.size() << endl;
		cout << v1.capacity() << endl;
		vector<int> v2;
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v2.size() << endl;
		cout << v2.capacity() << 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(5);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		vector<int> v2(v1.rend(), v1.rbegin());
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v2.size() << endl;
		cout << v2.capacity() << endl;
		v2.resize(10, 1);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v2.size() << endl;
		cout << v2.capacity() << endl;
		v2.resize(5);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v2.size() << endl;
		cout << v2.capacity() << endl;
		v2.resize(15, 2);
		vector<int>::iterator it = v2.begin();
		while (it < v2.end())
		{
			cout << (*it) << " ";
			++it;
		}
		cout << endl;
		for (size_t i = 0; i < v2.size(); ++i)
		{
			cout << v2[i] << " ";
		}
		cout << endl;
		v2.pop_back();
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v2.size() << endl;
		cout << v2.capacity() << endl;
		v2.pop_back();
		v2.pop_back();
		v2.pop_back();
		v2.pop_back();
		v2.pop_back();
		v2.pop_back();
		v2.pop_back();
		v2.pop_back();
		v2.pop_back();
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v2.size() << endl;
		cout << v2.capacity() << endl;
		v2.swap(v1);
		cout << "------------------ v1 --------------------" << endl;
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v1.size() << endl;
		cout << v1.capacity() << endl;
		cout << "------------------ v2 --------------------" << endl;
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v2.size() << endl;
		cout << v2.capacity() << endl;
		v1.resize(15);
		cout << v1.size() << endl;
		cout << v1.capacity() << endl;
		v1.insert(v1.begin(), 1);
		v1.insert(v1.end(), 1);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << v1.size() << endl;
		cout << v1.capacity() << endl;
	}
}