推荐|C++入门小馆: 探寻vector类

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集数据结构漫游记闲言碎语小记坊题山采玉领略算法真谛

vector的使用:

模拟实现vector:

先来了解一下vector的使用

vector的使用:

初始化方式:

这一坨实现的是内存池，如果你对STL里面的内存池不满意可以自己传入内存池，自己写一个。

第一个是无参构造

第二个是构造n个一样的类型一样的值

第三个是利用迭代器区间构造。

第四个是拷贝构造。

也可以使用initializer_list类型来构造。

由于vector没有重载>>和<<运算符，但也没有必要重载,我们打印也可以用范围for来遍历。


for(auto& x : v1)
	{
		cout << x << " ";
	}

结果:

这些迭代器也很眼熟了，没有什么好讲的，用法也差不多。

shrink_to_fit是用来缩容的，一般不咋用。

front和back是返回第一个和最后一个元素，可以使用下标加方括号就可以访问到所有元素了。这两个也不咋常用。

这些也是看的很眼熟了，这里在C++11有一个emplace这个和插入的功能所实现的效果是一样的，但这个使用起来更高效。

外部有一个swap和内部也有一个swap，还是类似于string类，外部的swap实现起来，造成了很多浪费。

注意这里的insert和erase要传入迭代器了，不像string能传入位置，要传入迭代器。

模拟实现vector:

我们先来看看STL源码里面的vector怎么实现的

vector要使用模版，另一个是内存池。

这是成员变量：

从下面可以看到vector的迭代器在这个版本的STL中是用原生指针来实现的，但不能说只能用原生指针来实现，其他版本可能使用其他方式实现。

_start 来指向第一个元素，_finish指向的是最后一个元素后面一个位置，_end_of_storage指向内存最大值的下一个位置。

从这些就可以看出来。

好了看了基本的内容，我们就来自己实现一下吧！因为内存池这里，我还没有学习过，就先不实现了。

写个成员变量：


namespace refrain
{
	template <class T>
	class vector
	{
	public:
		typedef T* iterator;
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

默认构造

无参构造


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

容量，数量:


size_t capacity()
{
	return _end_of_storage - _start;
}
size_t size(size_t i)
{
	return _end_of_storage - _start;
}

我们先来实现插入，方便我们好检查我们是否写错了

但我们实现push_back()之前要先实现一下扩容逻辑，因为push_back可以复用reserve函数。

reserve:


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

注意这里这里要先用oldsize存一下原来的size不然，后面_start+size()会调用size函数

这个时候_start已经改变了，得到的finish就不是我们期望的值。

然后push_back的逻辑就简单了：


	void push_back(const T& x)
	{
		//检查是否需要扩容
		if (_finish == _end_of_storage)
		{
			size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
			reserve(newcapacity);
		}
		*(_finish) = x;
		_finish++;
	}

pop_back就更简单了：


void pop_back()
{
	assert(_finish > _start);
 
	_finish--;
}

我们再重载一下方括号和迭代器相关的接口，来实现打印一下。


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


T& operator[](size_t i)
{
	return *(_start + i);
}

接下来的实现insert和erase操作的逻辑就和string差不多了


void insert(iterator pos, T x)
{
	assert(pos >= _start);
	assert(pos < _finish);
 
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
		reserve(newcapacity);
		pos = _start + len;
	}
	iterator it = _finish - 1;
	while (it >= pos)
	{
		*(it + 1) = *it;
		it--;
	}
	*(pos) = x;
	_finish++;
 
}
void erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);
 
	iterator it = pos;
	while (it < _finish)
	{
		*(it) = *(it + 1);
		it++;
	}
	_finish--;
 
}

写下面这个方便打印


void print(const vector<int>& v)
{
	for (auto& k : v)
	{
		cout << k << " ";
	}
	cout << endl;
}

我们看看下面这个程序：

我们再来写一个程序，用来删去v里面的偶数。

我们不能使用已经失效的迭代器，我们咋解决这个问题呢我们看看库里面的insert和erase

它们都是有返回值的，返回指向下一个位置的迭代器。

所以我们的insert和erase就成了:


iterator insert(iterator pos, T x)
{
	assert(pos >= _start);
	assert(pos < _finish);
 
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
		reserve(newcapacity);
		pos = _start + len;
	}
	iterator it = _finish - 1;
	while (it >= pos)
	{
		*(it + 1) = *it;
		it--;
	}
	*(pos) = x;
	_finish++;
	return pos;
 
}
iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);
 
	iterator it = pos;
	while (it < _finish)
	{
		*(it) = *(it + 1);
		it++;
	}
	_finish--;
	return pos;
}

就欧克了。这里就出现了迭代器失效的问题。

最后来实现一下赋值运算符和拷贝构造吧！


vector(const vector& v)
{
	reserve(v.capacity());
	for (auto& x : v)
	{
		push_back(x);
	}
}
void swap(const vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}
vector& operator=(vector v)
{
	swap(v);
	return *this;
}

不多说了和string差不多。

vector的使用:

模拟实现vector:

评论记录：