一、vector介紹和使用

1.1 vector的介紹

• vector是表示可變大小數組的序列容器。
• 就像數組一樣，vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數組一樣高效。但是又不像數組，它的大小是可以動態改變的，而且它的大小會被容器自動處理。
• 本質講，vector使用動態分配數組來存儲它的元素。當新元素插入時候，這個數組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數組，然后將全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。
• vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
• 因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態增長。
• 與其它動態序列容器相比（deque, list and forward_list）， vector在訪問元素的時候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list
  統一的迭代器和引用更好。

問題：vector<char>和string有什么區別？
vector<char> 是vector以char類型為模板實例化的類模板，她一次只能對單個字符進行操作，所擁有的也是vector這個類的集體屬性，而string類一次可以完成對多個字符的操作（字符串或字符），擁有字符串所具有的特性，例如+=。

1.2vector的使用

1.2.1 vector的構造函數

構造函數聲明	接口說明
vector()(重點)	無參構造
vector（size_type n, const value_type& val = value_type()）	構造并初始化,n個val
vector (const vector& x); (重點)	vector (const vector& x);
vector (InputIterator ?rst, InputIterator last);	使用迭代器進行初始化構造

1.2.2 vector iterator的使用

iterator的說明	接口說明	圖示
begin+end(重點)	獲取第一個數據位置的iterator/const_iterator， 獲取最后一個數據的下一個位置的iterator/const_iterator
rbegin+rend	獲取最后一個數據位置的reverse_iterator，獲取第一個數據前一個位置的reverse_iterator

1.2.3 vector的空間問題

容量空間	接口說明
size	獲取數據個數
capacity	獲取容量大小
empty	判斷是否為空
resize(重點)	改變vector的size
reserve (重點)	改變vector的capacity

1.2.4 vector的增刪查改

操作	接口說明
push_back（重點）	尾插
pop_back （重點）	尾刪
?nd	（注意這個是算法模塊實現，不是vector的成員接口）頭文件<algorithm>
sort	排序
insert	在pos之前插入val
erase	刪除pos位置的數據
swap	交換兩個vector的數據空間
operator[] (重點)	像數組一樣訪問

sort函數的使用：
sort(a.begin(), a.end(),greater<int>()); 降序排序
sort(a.begin(), a.end()); 升序排序

二、vector的深度剖析及實現

2.1 基本框架

template <typename T>
class vector
{
private:public:}

2.2 私有成員

private:T* _start = nullptr;T* _finish = nullptr;T* _end_of_storage = nullptr;

2.3 構造與賦值

	//強制使用默認構造vector() default;	//缺省形參，用n個val構造vector(size_t n, const T& val=T())	{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}//使用[first,last)構造template <class InputIterator>	vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}//拷貝構造vector(const vector<T>& v)		{reserve(v.capacity());for (auto e : v){push_back(e);}}//使用初始化列表初始化vector(initializer_list<T> il)	{reserve(il.size());for (auto e : il){push_back(e);}}

對initializer_list()的解釋:

	//賦值vector<T>& operator=(const vector& v){clear();reserve(v.capacity());for (auto e : v){push_back(e);}return *this;}vector<T>& operator=(const vector v){swap(v);return *this;}

2.4 析構函數

	//析構~vector(){if(_start)//判空{delete[] _start;_start = _finish = _end_of_storage = nullptr;}}

2.5 迭代器

	//迭代器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;}

2.6 對容器大小的操作

	size_t size() const	//元素個數{return _finish - _start;}size_t capacity() const	//容量大小{return _end_of_storage - _start;}void reserve(size_t n)	//擴容操作{if (n > capacity()){size_t oldsize = size();T* temp = new T[n];//if (_start)//{//memcpy(temp, _start, sizeof(T) * n);//對字符串進行淺拷貝，會出錯//delete[] _start;//}if(_start){for (size_t i = 0; i < oldsize; i++){temp[i] = _start[i];//調用賦值}delete[] _start;}_start = temp;_finish = _start + oldsize;_end_of_storage = _start + n;}}bool empty()	//判空{return size() == 0;}void swap(vector<T>& v)	//交換{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}

對reserve()函數的分析:

• memcpy是內存的二進制格式拷貝，將一段內存空間中內容原封不動的拷貝到另外一段內存空間中
• 如果拷貝的是自定義類型的元素，memcpy既高效又不會出錯，但如果拷貝的是自定義類型元素，并且
  自定義類型元素中涉及到資源管理時，就會出錯，因為memcpy的拷貝實際是淺拷貝。
  
  
  如果對象中涉及到資源管理時，千萬不能使用memcpy進行對象之間的拷貝，因為memcpy是
  淺拷貝，否則可能會引起內存泄漏甚至程序崩潰。

2.7 對數據的訪問

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

2.8 對容器的增刪查改

	void push_back(const T& val)		//尾插{if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = val;++_finish;//insert(end() val);       用insert()插入}void pop_back()	//尾刪{assert(size()>0)_finish--;}void clear()	//清空{_finish = _start;}iterator insert(iterator pos, const T& val)	//插入{assert(pos <= _finish);//==finish就可以實現尾插assert(pos >= _start);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;}iterator erase(iterator pos)	//刪除{assert(pos < _finish);assert(pos >= _start);size_t len = pos - _start;iterator cur = pos;while (cur < _finish){*cur = *(cur + 1);cur++;}--_finish;return _start + len;}
};