STL向量容器vector简单实现

什么是容器

就是保存其他对象的对象。而且，这种“对象”还有处理“其他对象”的方法

C++采用基于模版的方式处理容器，STL中的容器提供了多种数据结构。

它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作动态数组。

特点

1. 随机访问
2. 线性顺序结构。可以指定一块连续的空间，也可以不预先指定大小，空间可自动扩展，也可以像数组一样被操作，即支持[ ]操作符和vector.at()，因此可看做动态数组，通常体现在追加数据push_back()和删除末尾数据pop_back()。
3. 当分配空间不够时，vector会申请一块更大的内存块（以2的倍数增长），然后将原来的数据拷贝到新内存块中并将原内存块中的对象销毁，最后释放原来的内存空间。因此如果vector保存的数据量很大时会很消耗性能，因此在预先知道它大小时性能最优。
4. 节省空间。因为它是连续存储，在存储数据的区域是没有浪费的，但实际上大多数时候是存不满的，因此实际上未存储的区域是浪费的。
5. 在内部进行插入和删除的操作效率低。由于vector内部按顺序表结构设计，因此这样的操作基本上是**，它被设计成**。

简单版

template <typename T>
class vector//向量容器
{
public:
	vector(int size = 10)//构造
	{
		_first = new T[size];
		_last = _first;
		_end = _first + size;
	}
	~vector()//析构
	{
		delete[]_first;
		_first = _last = _end = nullptr;
	}
	vector(const vector<T> &rhs)//拷贝构造
	{
		int size = rhs._end - rhs._first;//空间大小
		_first = new T[size];
		int len = rhs._last - rhs._first;//有效元素
		for (int i=0; i<len; ++i)
		{
			_first[i] = rhs._first[i];
		}
		_last = _first + len;
		_end = _first + size;
	}
	vector<T>& operator=(const vector<T> &rhs)//赋值运算符重载
	{
		if (this == &rhs)
		{
			return *this;
		}

		delete[]_first;

		int size = rhs._end - rhs._first;
		_first = new T[size];
		int len = rhs._last - rhs._first;
		for (int i=0; i<len; i++)
		{
			_first[i] = rhs._fisrt[i];
		}
		_last = _first + len;
		_end = _fitst = size;
		return *this;
	}
	void push_back(const T &val)//尾插
	{
		if (full())
		{
			expand();
		}
		*_last++ = val;
	}
	void pop_back()//尾删
	{
		if (empty()) return;
		--_last;
	}
	T back()const//返回容器末尾元素值
	{
		return *(_last - 1);
	}
	bool full()const
	{
		return _last == _end;
	}
	bool empty()const
	{
		return _first == _last;
	}
	int size()const//返回容器中元素个数
	{
		return _last - _first;
	}
private:
	T *_first;//起始数组位置
	T *_last;//指向最后一个有效元素后继位置
	T *_end;//指向数组空间的后继位置

	void expand()//扩容
	{
		int size = _end - _first;
		T *ptmp = new T[2*size];
		for (int i=0; i<size; ++i)
		{
			ptmp[i] = _first[i];
		}
		delete[]_first;
		_first = ptmp;
		_last = _first + size;
		_end = _first + 2*size;
	}
};

int main()
{
	vector<int> vec;
	for (int i=0; i<20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	while (!vec.empty())
	{
		cout << vec.back() << " ";
		vec.pop_back();
	}
	cout << endl;
	
	return 0;
}

这里只是简单实现以下vector容器，但是还少了空间配置器allocator。 库中定义的vector：

template<class _Ty,
	class _Alloc = allocator<_Ty> >
	class vector
		: public _Vector_alloc<!is_empty<_Alloc>::value,
			_Vec_base_types<_Ty, _Alloc> >