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

2023-02-27 20:41 429人阅读评论(0)

大家好我是沐曦希💕

文章目录

一、前言
二、无参构造&析构
三、基础接口
四、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;
	}
}

转载：https://blog.csdn.net/m0_68931081/article/details/128211297

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章