前言

vector是STL中的顺序容器，支持随机访问，其底层数据结构就是动态开辟的数组，发生扩容时gcc两倍扩容，msvc是1.5倍扩容。容器本质就是一个存储数据的地方，以便于我们进行增删改查的算法操作，来支持业务的进行。STL的出现极大的提高了编程的效率，完全的贯彻了RAII的思想，资源获取即初始化，资源释放则销毁，尽可能减少程序员手动操作出现的错误。回想使用C语言创建数组并遍历的过程，我们得malloc申请内存获取返回的指针强转，然后操控指针遍历赋值，而vector直接使用列表初始化一行即可完成C语言十几行的操作，并且还无需手动释放堆区内存。

实现vector

原理

vector的内部就是三个指针维持着操作，first指向堆区起始地址，last指向了当前已分配还未使用的堆区首地址，endd已分配地址的后续地址，视为无效地址。利用空间分配器将堆区资源的申请和对象的构造解耦开，将对象的析构和堆区资源的释放解耦开，最大程度提升资源的利用率。使用模板技术来支持泛型编程，将元素的类型参数化。结合迭代器，将容器和算法连接起来，实现容器遍历的统一性。

空间配置器

template<typename T>
class Allocator
{
public:
	T* allocate(size_t size)//负责开辟空间 
	{
		return (T*)malloc(sizeof(T) * size);
	}
	void deallocate(void* p)//负责释放空间 
	{
		free(p);
	}
	template<typename ...type>
	void construct(T* p, type&& ...arg)//负责对象的构造 
	{
		new (p)T(forward<type>(arg)...);//使用定位new 在指定的内存上构造对象
	}
	void destrory(T* p)//负责对象析构
	{
		p->~T();//~T()代表了T类型的析构函数
	}
};

allocate就是负责调用malloc开辟堆区的内存空间，deallocate用来释放堆区空间，destrory对传入的对象调用析构函数。
construct使用到了可变参，万能引用和完美转发技术。在模板中的type&& 叫做万能引用，会根据传入的实参类型自动推导为左值或者右值引用，如果传递为左值那么type会被推导为左值引用type&，整体表现为type& &&进行引用折叠显示为type&,如果传递为右值T会被推导为非引用类型，整体表现为T&&保持为右值引用。
typename …types是可变参数模板，…types表示可以接收任意数量、任意类型的参数。
forward<type>(arg)是完美转发技术，会将参数arg的值的类别(左值/右值)通过type来识别，因为无论是type&还是type&&它们都是左值，为了还原原始参数的类别而使用type来识别。
placement new是一种定位构造对象的new，new(ptr) T(…)表示在ptr指向的预分配内存上构造T类型对象。它直接调用T的构造函数，不涉及内存的分配。（new是一个运算符，其有三种类型plain new，nothrow new，placement new可以自行了解，这里不展开讨论）。
vector中涉及堆区分配的内容全都交由空间分配器来进行，这样就完全达到了内存和对象构建解耦的目的。而且可以根据用户传入指定空间分配器。

迭代器

迭代器存在的意义是为了实现容器的统一操作，将不同容器通过一种手段适配到算法模板上去。迭代器的本质也是一个类嵌套在容器之中，底层是通过指针实现的，用法和指针相同，因为它重载了*,++,->运算符。使用迭代器要注意迭代器失效问题，当进行erase或者insert操作时，当前迭代器之后的所有迭代器都会失效。

迭代器类型

按照定义方式分

• 正向迭代器:容器类目:iterator 迭代器
• 常量正向迭代器:容器类名::const_iterator 迭代器名
• 反向迭代器:reverse_iterator 迭代器名
• 常量反向迭代器:reverse_iterator 迭代器名
• 正向迭代器进行++操作迭代器会指向容器中的后一个元素，反向迭代器的++操作，迭代器指向容器的前一个元素。
  
  

按功能分类

不同容器的迭代器功能强弱不同，有输入、输出、正向、双向、随机访问这5类迭代器，这里介绍最常使用的三类迭代器。

• 正向迭代器：支持++和*操作，可以进行==和!=比较
• 双向迭代器，支持正向迭代器的所有操作，还支持–操作。
• 随机访问迭代器：支持双向迭代器的所有功能，并且还支持随机访问p[i]
  
  

template<typename T>
class Iterator 
{
public:
	Iterator() {}
	Iterator(T* ptr) { this->ptr = ptr; }
	T& operator*() const { return *ptr; }
	bool operator== (const Iterator& o) { return o.ptr == this->ptr; }
	bool operator!= (const Iterator& o) { return o.ptr != this->ptr; }
private:
	T* ptr;
};

整体代码

#include<iostream>
//#include<vector>
#include<map>
using namespace std;
template<typename T>
class Iterator 
{
public:
	Iterator() {}
	Iterator(T* ptr) { this->ptr = ptr; }
	T& operator*() const { return *ptr; }
	bool operator== (const Iterator& o) { return o.ptr == this->ptr; }
	bool operator!= (const Iterator& o) { return o.ptr != this->ptr; }
private:
	T* ptr;
};
template<typename T>
class Allocator
{
public:
	T* allocate(size_t size)//负责开辟空间 
	{
		return (T*)malloc(sizeof(T) * size);
	}
	void deallocate(void* p)//负责释放空间 
	{
		free(p);
	}
	template<typename ...type>
	void construct(T* p, type&& ...arg)//负责对象的构造 
	{
		new (p)T(forward<type>(arg)...);//使用定位new 在指定的内存上构造对象
	}
	void destrory(T* p)//负责对象析构
	{
		p->~T();//~T()代表了T类型的析构函数
	}
};
template<typename T, typename Alloc = Allocator<T>>
class vector {
public:
	using iterator = Iterator<T>;
	vector(int size = 10):first(_allocator.allocate(size)),last(first),endd(first + size){}
	~vector()
	{
		for (T* p = first;p != last;p++)
		{
			_allocator.destrory(p);
		}
		_allocator.deallocate(first);
		first = last = endd = nullptr;
	}
	vector(const vector<T>& other)
	{
		int len = other.endd - other.first;
		last = first = _allocator.allocate(len);
		endd  = first + len;
		for (T* i = other.first;i != other.last;i++)
		{
			_allocator.construct(last++, *i);
		}
	}
	//支持列表初始化
	vector(std::initializer_list<T>list):first(_allocator.allocate(list.size())),last(first + list.size()), endd(last)
	{
		memcpy(first,list.begin(),sizeof(T)*list.size());
	}
	vector<T>& operator=(const vector<T>& other)
	{
		if (this == &other)
		{
			return *this;
		}
		for (T* p = first;p != last;p++)
		{
			_allocator.destrory(p);
		}
		_allocator.deallocate(first);
		int len = other.endd - other.first;
		first = _allocator.allocate(len);
		for (T* i = other.first;i != other.last;i++)
		{
			_allocator.allocate(last++, *i);
		}
		endd = first + len;
	}
	T& operator[](int index) 
	{
		return *(first + index);
	}
	template<typename type>
	void push_back(type&&arg) 
	{
		if (full())
		{
			resize();
		}
		_allocator.construct(last++, forward<type>(arg));
	}
	template<typename ...type>
	void emplace_back(type&& ...arg)
	{
		if (full())
		{
			resize();
		}
		_allocator.construct(last++, forward<type>(arg)...);
	}
	bool full() const
	{
		return last == endd;
	}
	bool empty()const
	{
		return last == first;
	}
	void pop_back()
	{
		last--;
		_allocator.destrory(last);
	}
	T back()const
	{
		return *(last - 1);
	}
	int size()
	{
		return last - first;
	}
	void resize()
	{
		int len = endd - first;
		T* temp = _allocator.allocate(2 * len);
		for (int i = 0;i < len;i++)
		{
			_allocator.construct(temp + i, first[i]);
		}
		for (T* p = first;p != last;p++)
		{
			_allocator.destrory(p);
		}
		_allocator.deallocate(first);
		first = temp;
		last = first + len;
		endd = first + 2 * len;
	}
	iterator begin() const { return first; }
	iterator end() const { return end; }
private:
	T* first;//指向数组的起始位置
	T* last;//指向数组的有效元素的后继位置
	T* endd;//指向数组空间的后继位置
	Alloc _allocator;//空间配置器对象
};
class Test {
public:
	Test() { cout << "Test()" << endl; }
	Test(int a) { cout << "Test(int a)" << endl; }
	Test(int a,int b) { cout << "Test(int a,int b)" << endl; }

	Test(const Test& o) { cout << "Test(const Test& o)" << endl; }


	
	~Test() { cout << "析构函数" << endl; }
};
int main()
{
	
	vector<Test>a;
	a.push_back(1);
	a.emplace_back(1,2);
	return 0;
}