C++ : STL容器之vector剖析

发布于：2024-10-13 ⋅ 阅读:(14) ⋅ 点赞:(0)

在这里插入图片描述

STL容器之vector剖析

一、构造函数与赋值

（一）默认构造

采用初始化列表初始化，将三个迭代器都初始化为 nullptr，用三个指针的关系间接地控制size,capacity以及``data`.

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

（二）拷贝构造

拷贝构造可以用两种方式来实现，下面第一种是直接深拷贝的思路，另外还可以采用复用的方式。

这种方式可以使得拷贝后，size(), capacity()和拷贝的值相等

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

这种方式采用复用，简洁了代码,可以多采用这种方式书写代码。

vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (auto& e : v)
			{
				push_back(e);
			}
		}

（三）几个相同值构造

拷贝几个相同的值进入一个新的 vector，我们用了两个方式来实现，用 size_t来做参数，扩大n的取值范围，这样的化还需要重载一个函数 int,这是因为下面还有一个迭代器构造函数用函数模板实现，如果不这样的化，我们如果需要3个5的vector，就会自动调用函数模板，达不到预期，还会报错。

vector(size_t n, const T& value = T())
{
	_start = new T[n];
	for (int i = 0; i < n; i++) {
		_start[i] = value;
	}
	_finish = _start + n;
	_endofstorage = _start + n;
}

vector(int n, const T& value = T())
{
	_start = new T[n];
	for (int i = 0; i < n; i++) {
		_start[i] = value;
	}
	_finish = _start + n;
	_endofstorage = _start + n;
}

（四）迭代器构造

成员函数也可以用函数模板来实现，可以用其它容器的迭代器来构造 vector，只要能够进行自动类型转换即可。

		template<class InputIterator>
		vector(InputIterator first, InputIterator second)
		{
			size_t n = second - first;
			_start = new T[n];
			for (int i = 0; i < n; i++) {
				_start[i] = *(first + i);
			}
			_finish = _start + n;
			_endofstorage = _start + n;
		}

void test09()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		vector<int> v2(v1.begin(), v1.end());
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

		string s1("hello");
		vector<int> v3(s1.begin(), s1.end());
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v4(10, 1);
		vector<double> v5(10, 1.1);
		for (auto e : v4)
		{
			cout << e << " ";
		}
		cout << endl;
	}

在这里插入图片描述

（五）initializer_list 构造

initailzer_list是一个 std 库里面的一个对象,原理大概就是开一个数组用两个首尾指针来维护它

		vector(initializer_list<T> il)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			int n = il.size();
			_start = new T[n];
			auto x = il.begin();
			for (int i = 0; i < n; i++) {
				_start[i] = *(x + i);
			}
			_finish = _start + n;
			_endofstorage = _finish;
		}

下面的实例中，v1先构造了一个initializer_list 对象，接着隐式类型转换，但是编译器优化为直接构造。而v2就是直接构造，接着下面演示了如何初始化这种对象。

void test11()
{
	vector<int> v1 = { 1,2,3,4,5,6 };
	vector<int> v2({ 1,2,3,4,5,6 });

	auto il1 = { 1, 2, 3, 4, 5, 6 };
	initializer_list<int> il2 = { 1, 2, 3, 4, 5, 6 };
	for (auto x : il2) {
		cout << x  << " ";
	}
}

（六）赋值重载

现代写法，这种写法简直拉满了，妙哉。
我们知道函数值传参会调用拷贝构造，我们只需要将需要赋值的对象和形参交换，就能达到赋值的效果，而函数结束后会调用析构函数自动释放形参的空间，妙不可言。

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

		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

二、几个重要接口

（一）reserve

在完成这个函数时，一定要采取for循环来依次赋值，如果使用 memcpy ,会发生一个深层次深浅拷贝的问题,如果_start指向的这片空间设计到动态内存开辟，那么会造成析构时释放两次的现象。

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

（二）resize

设置有效元素个数，分情况讨论即可，如果 reserve 里面采用了memcpy 涉及到复用，这里也可能会报错。

void resize(size_t n, T value = T())
{
	if (n <= size()) {
		int num = size() - n;
		_finish -= num;
	}
	else {
		reserve(n);
	    while (size() < capacity()) {
			push_back(value);
		}
	}
}

（三）erase

删除指定元素，并且返回当前删除元素的下一个元素的迭代器，返回值需要注意，否则可能发生迭代器失效的问题。

		iterator erase(iterator pos)
		{
			assert(pos < _finish);
			assert(pos >= _start);
			for (auto x = pos + 1; x != _finish; x++) {
				*(x - 1) = *(x);
			}
			_finish--;
			return pos;
		}

（四）insert

插入一个元素，这里用到了 reserve，因此pos指向的元素可能已经是另外开辟的空间，造成迭代器失效，这种情况我们要记住pos和_start的相对位置，这样我们才能在新的数组空间还原pos的位置。`

		iterator insert(iterator pos, const T& value)
		{
			assert(pos <= _finish);
			assert(pos >= _start);
			if (_finish == _endofstorage) {
				int n = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + n;
			}
			for (auto x = _finish; x > pos; x--) {
				*(x) = *(x - 1);
			}
			*(pos) = value;
			_finish++;
			return pos;
		}

三、vector 的实现（完整源码）

实现vector的时候，我们没有用 capacity size data 来定义，而是用了三个指针来间接地维护这几个值。

#define _CRT_SECURE_NO_WARNINGS 1

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

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

		vector()
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			cout << "vector() 调用" << endl;
		}

		vector(initializer_list<T> il)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			cout << "vector(initializer_list<T> il)调用" << endl;
			int n = il.size();
			_start = new T[n];
			auto x = il.begin();
			for (int i = 0; i < n; i++) {
				_start[i] = *(x + i);
			}
			_finish = _start + n;
			_endofstorage = _finish;
		}

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

		template<class InputIterator>
		vector(InputIterator first, InputIterator second)
		{
			size_t n = second - first;
			_start = new T[n];
			for (int i = 0; i < n; i++) {
				_start[i] = *(first + i);
			}
			_finish = _start + n;
			_endofstorage = _start + n;
		}

		vector(size_t n, const T& value = T())
		{
			_start = new T[n];
			for (int i = 0; i < n; i++) {
				_start[i] = value;
			}
			_finish = _start + n;
			_endofstorage = _start + n;
		}

		vector(int n, const T& value = T())
		{
			_start = new T[n];
			for (int i = 0; i < n; i++) {
				_start[i] = value;
			}
			_finish = _start + n;
			_endofstorage = _start + n;
		}

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

		T& operator[](size_t n) 
		{
			assert(n < size());
			assert(n >= 0);
			return _start[n];
		}

		const T& operator[](size_t n) const
		{
			assert(n < size());
			assert(n >= 0);
			return _start[n];
		}

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

		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

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

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

		void resize(size_t n, T value = T())
		{
			if (n <= size()) {
				int num = size() - n;
				_finish -= num;
			}
			else {
				reserve(n);
			    while (size() < capacity()) {
					push_back(value);
				}
			}
		}

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

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

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

		iterator insert(iterator pos, const T& value)
		{
			assert(pos <= _finish);
			assert(pos >= _start);
			if (_finish == _endofstorage) {
				int n = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + n;
			}
			for (auto x = _finish; x > pos; x--) {
				*(x) = *(x - 1);
			}
			*(pos) = value;
			_finish++;
			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos < _finish);
			assert(pos >= _start);
			for (auto x = pos + 1; x != _finish; x++) {
				*(x - 1) = *(x);
			}
			_finish--;
			return pos;
		}
		

	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};
}

四、结束语

相比于string，vector新加入的一些新的元素，但是大同小异，后面的学习中研究不同点即可，vector中的迭代器失效，以及深浅拷贝的问题在学习时需要注意。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布