【C++】手撕vector类（从会用到理解）

一、标准库中的vector类

1.1 vector类介绍

1.2 vector的常用接口

1.2.1 常用的构造函数

1.2.2 容量操作接口

（1）size

（2）capacity

（3）empty

（4）resize

（5）reserve

1.2.3 访问和遍历

（1）operator[]

（2）迭代器

（3）at

（4）back

（5）front

1.2.4 vector的增删查改

（1）push_back

（2）pop_back

（3）find

（4）insert

（5）erase

（6）swap

（7）assign

（8）clear

1.3 迭代器失效

二、模拟实现vector类

一、标准库中的vector类

1.1 vector类介绍

vector用于表示大小可以变化的数组。 

与数组类似，vector也采用连续的存储空间来存储元素，也就是说我们可以和数组一样使用下标对vector进行随机访问。但是相对于不能改变空间大小的数组而言，vector的优势在于它的大小可以动态改变。

前面我们学习了string类，对于同样使用顺序表结构的vector类而言，二者的很多地方是相通的，例如vector也可以进行尾插和尾删等操作。

vector是一个模板类，在使用时我们需要给出元素的类型。

vector类中通常有三个迭代器类型的成员变量，分别指向vector的开头、最后一个有效元素的后一位和vector的结尾

iterator _start;
iterator _finish;
iterator _end_of_storage;

所以，vector的有效元素个数就等于_finish - _start，容量等于_end_of_storage - _start

我们通过vector类中的接口就能对这三个迭代器进行操作，从而完成增删查改等功能

在使用vector类时，必须包含头文件<vector>和using namespace std;

1.2 vector的常用接口

1.2.1 常用的构造函数

vector();

vector类的默认构造函数，构造一个没有元素的空容器

例如：

vector(size_type n, const value_type& val = value_type());

构造一个vector类对象并用n个val初始化

例如：

vector(const vector& x);

vector类的拷贝构造函数

例如：

Template<class InputIterator>

vector(InputIterator first, InputIterator last);

使用迭代器进行初始化构造

例如：

1.2.2 容量操作接口

（1）size

size_type size() const;

获取有效元素个数

例如：

（2）capacity

size_type capacity() const;

获取容量大小

例如：

（3）empty

bool empty() const;

判断容器是否为空

例如：

（4）resize

void resize(size_type n, value_type val = value_type());

将有效元素的个数修改为n，并且如果n大于原来的size，多出来的地方用val填充

如果没有给出val，就用0填充

例如：

（5）reserve

void reserve(size_type n);

改变容量大小

例如：

1.2.3 访问和遍历

（1）operator[]

reference operator[](size_type n);

const_reference operator[](size_type n) const;

用下标访问vector

例如：

（2）迭代器

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

迭代器，用于获取容器中第一个元素的位置和最后一个元素的下一个位置

例如：

reverse_iterator rbegin();

const_reverse_iterator rbegin() const;

reverse_iterator rend();

const_reverse_iterator rend() const;

反向迭代器，rbegin获取容器中最后一个元素的位置，rend获取容器中的第一个元素的前一个位置

例如：

需要注意，反向迭代器rit也要用++而不是--

（3）at

reference at(size_type n);

const_reference at(size_type n) const;

返回容器中位置n处的元素的引用

例如：

（4）back

reference back();

const_reference back() const;

返回容器中最后一个元素的引用

例如：

（5）front

reference front();

const_reference front() const;

返回容器中第一个元素的引用

例如：

1.2.4 vector的增删查改

（1）push_back

void push_back(const value_type& val);

从容器尾部插入一个元素

例如：

（2）pop_back

void pop_back();

从容器尾部删除一个元素

例如：

（3）find

template <class InputIterator, class T>

InputIterator find(InputIterator first, InputIterator last, const T& val);

在两个迭代器区间寻找val并返回其所在处的迭代器

例如：

需要注意的是，该函数并非vector的成员函数，是标准库中的函数，多个容器共用该find函数

（4）insert

iterator insert(iterator position, const value_type& val);

void insert(iterator position, size_type n, const value_type& val);

在position位置插入元素

例如：

对于这类可能会修改容量的函数，容易导致迭代器失效的问题，后面我们会详细讲

所以insert函数不仅需要完成插入元素的工作，有时还需要返回新的迭代器

（5）erase

iterator erase(iterator position);

iterator erase(iterator first, iterator last);

删除position位置的元素或者 [first，last) 区间的所有元素

例如：

（6）swap

void swap(vector& x);

交换两个vector的数据空间

例如：

（7）assign

template <class InputIterator>

void assign(InputIterator first, InputIterator last);

void assign(size_type n, const value_type& val);

为vector指定新内容，替换其当前内容并修改size

例如：

（8）clear

void clear();

从vector中删除所有元素，不改变容量大小

例如：

1.3 迭代器失效

迭代器的底层实际上就是一个指针或指针的封装，例如vector的迭代器就是一个原生态指针

当迭代器底层的指针指向的空间被销毁时，如果继续在程序中使用该迭代器，就会造成程序崩溃，这就是迭代器失效

对于vector，会导致迭代器失效的操作有：

• 可能造成空间改变的操作，如resize、reserve、insert、assign、push_back等

以上函数在使用时都可能会导致vector扩容，在扩容时原空间会被释放，迭代器就会指向一块被释放的空间

• 删除操作

假设有迭代器pos，使用pos删除pos对应位置的元素后，该迭代器对应的元素发生改变，属于迭代器失效

如果pos刚好对应最后一个元素，删除后迭代器pos就超出了有效元素范围，可能导致非法访问，属于迭代器失效

迭代器失效后，如果我们需要继续使用迭代器，给迭代器重新赋值即可

二、模拟实现vector类

知道了vector类中各种常用接口的用法后，我们就可以开始自己手撕一个自己的vector类了

为了不和标准库中的vector类冲突，我们可以开一个自己的命名空间

#include <iostream>
#include <assert.h>
#include <string>
using namespace std;

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

		vector()
			//此处包括下面的初始化列表都可以换用缺省值
			:_start(nullptr)
			,_finish(nullptr)
			,_end_of_storage(nullptr)
		{}

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

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

		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(v.capacity());
			for (size_t i = 0; i < v.size(); ++i)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
		}

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

		vector<T>& operator=(vector<T>& v)
		{
			if (this != &v)
			{
				reserve(v.capacity());
				for (size_t i = 0; i < v.size(); ++i)
				{
					_start[i] = v._start[i];
				}
				_finish = _start + v.size();
				return *this;
			}
		}

		iterator begin()
		{
			return _start;
		}

		const_iterator cbegin() const
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator cend() const
		{
			return _finish;
		}

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

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

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t sz = size();
				if (_start)
				{
					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

		void resize(size_t n, T val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			if (n > size())
			{
				if (n > capacity())
					reserve(n);
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

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

		void push_back(const T& x)
		{
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			*_finish = x;
			++_finish;
		}

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

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

		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _end_of_storage)
			{
				size_t range = pos - _start; //在扩容前需要记录相对位置
				//在插入数据时发生了扩容，迭代器的位置会发生改变,叫做迭代器失效
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + range; //将pos也更新到新的位置
			}
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = val;
			++_finish;
			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			iterator start = pos + 1;
			while (start < _finish)
			{
				*(start - 1) = *start;
				++start;
			}
			--_finish;
			return pos;
		}

		T& front()
		{
			return *_start;
		}

		const T& front() const
		{
			return *_start;
		}

		T& back()
		{
			return *(_finish - 1);
		}

		const T& back() const
		{
			return *(_finish - 1);
		}

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

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

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

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

如有错误，欢迎在评论区指出

完.文章来源地址https://www.toymoban.com/news/detail-843398.html

到了这里，关于【C++】手撕vector类（从会用到理解）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！