【C++】30h速成C++从入门到精通（STL容器listvector）

list

list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。

list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

list的构造

构造函数	接口说明
list()	构造空的list
list(size_type n,const value_type& val=value_type())	构造的list中包含n个值为val的元素
list(const list& x)	拷贝构造函数
list(inputlterator first,inputlierator last)	用{first，last}区间中的元素构造list

// constructing lists
#include <iostream>
#include <list>
int main ()
{std::list<int> l1; // 构造空的l1std::list<int> l2 (4,100); // l2中放4个值为100的元素std::list<int> l3 (l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3std::list<int> l4 (l3); // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = {16,2,77,29};std::list<int> l5 (array, array + sizeof(array) / sizeof(int) );// 用迭代器方式打印l5中的元素for(std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)std::cout << *it << " ";std::cout<<endl;// C++11范围for的方式遍历for(auto& e : l5)std::cout<< e << " ";std::cout<<endl;return 0;
}

list iterator（迭代器）的使用

函数声明	接口说明
begin+end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend	返回第一个元素reverse_iterator，即end位置，返回最后一个元素下一个reverse_iterator，即begin的位置

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

#include <iostream>
using namespace std;
#include <list>
void print_list(const list<int>& l)
{// 注意这里调用的是list的 begin() const，返回list的const_iterator对象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";// *it = 10; 编译不通过}cout << endl;
}
int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素for (list<int>::iterator it = l.begin(); it != l.end(); ++it)cout << *it << " ";cout << endl;// 使用反向迭代器逆向打印list中的元素for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)cout << *it << " ";cout << endl;return 0;
}

list capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回flase
size	返回list中有效节点的个数

list element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为vai的元素
pop_front	删除list中的第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中的最后一个元素
insert	在list position位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的元素

#include <list>
void PrintList(list<int>& l)
{for (auto& e : l)cout << e << " ";cout << endl;
}
//=====================================================================================
====
// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] = { 1, 2, 3 };list<int> L(array, array+sizeof(array)/sizeof(array[0]));// 在list的尾部插入4，头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}
//=====================================================================================
====
// insert /erase 
void TestList3()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1+sizeof(array1)/sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}
// resize/swap/clear
void TestList4()
{// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1+sizeof(array1)/sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout<<l2.size()<<endl;
}

list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值l.erase(it); ++it;}
}
// 改正
void TestListIterator()
{ int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}

list的模拟实现

namespace bite
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};/*List 的迭代器迭代器有两种实现方式，具体应根据容器底层数据结构实现：1. 原生态指针，比如：vector2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下
方法：1. 指针可以解引用，迭代器的类中必须重载operator*()2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可
以向前 移动，所以需要重载，如果是forward_list就不需要重载--4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()*/template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr): _pNode(pNode){}ListIterator(const Self& l): _pNode(l._pNode){}T& operator*(){return _pNode->_val;}T* operator->(){return &(operator*());}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp(*this);_pNode = _pNode->_pNext;return temp;}Self& operator--();Self& operator--(int);bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode != l._pNode;}PNode _pNode;};template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i)push_back(value);}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换list<T> temp(l.cbegin(), l.cend());this->swap(temp);}list<T>& operator=(const list<T> l){this->swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return iterator(_pHead->_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin(){return const_iterator(_pHead->_pNext);}const_iterator end(){return const_iterator(_pHead);}///// List Capacitysize_t size()const;bool empty()const;// List AccessT& front();const T& front()const;T& back();const T& back()const;// List Modifyvoid push_back(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){PNode pNewNode = new Node(val);PNode pCur = pos._pNode;// 先将新节点插入pNewNode->_pPre = pCur->_pPre;pNewNode->_pNext = pCur;pNewNode->_pPre->_pNext = pNewNode;pCur->_pPre = pNewNode;return iterator(pNewNode);}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){// 找到待删除的节点PNode pDel = pos._pNode;PNode pRet = pDel->_pNext;// 将该节点从链表中拆下来并删除pDel->_pPre->_pNext = pDel->_pNext;pDel->_pNext->_pPre = pDel->_pPre;delete pDel;return iterator(pRet);}void clear();void swap(List<T>& l);private:void CreateHead(){_pHead = new Node;_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}private:PNode _pHead;};
}

// 正向打印链表
template<class T>
void PrintList(const bite::list<T>& l)
{auto it = l.cbegin();while (it != l.cend()){cout << *it << " ";++it;}cout << endl;
}
// 测试List的构造
void TestList1()
{bite::list<int> l1;bite::list<int> l2(10, 5);PrintList(l2);int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };bite::list<int> l3(array, array+sizeof(array)/sizeof(array[0]));PrintList(l3);bite::list<int> l4(l3);PrintList(l4);l1 = l4;PrintList(l1);PrintListReverse(l1);
}
// PushBack()/PopBack()/PushFront()/PopFront()
void TestList2()
{// 测试PushBack与PopBackbite::list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);PrintList(l);l.pop_back();l.pop_back();PrintList(l);l.pop_back();cout << l.size() << endl;// 测试PushFront与PopFrontl.push_front(1);l.push_front(2);l.push_front(3);PrintList(l);l.pop_front();l.pop_front();PrintList(l);l.pop_front();cout << l.size() << endl;
}
void TestList3()
{int array[] = { 1, 2, 3, 4, 5 };bite::list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto pos = l.begin();l.insert(l.begin(), 0);PrintList(l);++pos;l.insert(pos, 2);PrintList(l);l.erase(l.begin());l.erase(pos);PrintList(l);// pos指向的节点已经被删除，pos迭代器失效cout << *pos << endl;auto it = l.begin();while (it != l.end()){it = l.erase(it);}cout << l.size() << endl;
}

vector

vector的介绍

1. vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

vector的使用

https://cplusplus.com/reference/vector/vector/

vector的定义

构造函数声明	接口说明
vector()	无参构造
vector(size_type n,const value_type& val=value_type())	构造并初始化n个val
vector(const vector& x);	拷贝构造
vector(inputlterator first,inputlterator last)	使用迭代器进行初始化构造

// constructing vectors
#include <iostream>
#include <vector>
int main ()
{// constructors used in the same order as described above:std::vector<int> first; // empty vector of intsstd::vector<int> second (4,100); // four ints with value 100std::vector<int> third (second.begin(),second.end()); // iterating through secondstd::vector<int> fourth (third); // a copy of third// 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分// the iterator constructor can also be used to construct from arrays:int myints[] = {16,2,77,29};std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );std::cout << "The contents of fifth are:";for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

vector iterator的使用说明

iterator的使用	接口说明
begin+end	获取第一个数据位置的iterator/const_iterator，获取最后一个数据下一个位置的iterator/const_iterator
rbegin+rend	获取最后一个数据位置的iterator/const_iterator，获取第一个数据前一个位置的iterator/const_iterator

#include <iostream>
#include <vector>
using namespace std;
void PrintVector(const vector<int>& v)
{// const对象使用const迭代器进行遍历打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}
int main()
{// 使用push_back插入4个数据vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器进行遍历打印vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;// 使用迭代器进行修改it = v.begin();while (it != v.end()){*it *= 2;++it;}// 使用反向迭代器进行遍历再打印vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;PrintVector(v);return 0;
}

vector的空间增长问题

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变vector的size
reserve	改变vector放入capacity

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

• reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

• resize在开空间的同时还会进行初始化，影响size。

// vector::capacity
#include <iostream>
#include <vector>
int main ()
{ size_t sz;std::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i=0; i<100; ++i) {foo.push_back(i);if (sz!=foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}
}
vs：运行结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
g++运行结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128

// vector::reserve
#include <iostream>
#include <vector>
int main ()
{size_t sz;std::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i=0; i<100; ++i) {foo.push_back(i);if (sz!=foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}std::vector<int> bar;sz = bar.capacity();bar.reserve(100); // this is the only difference with foo abovestd::cout << "making bar grow:\n";for (int i=0; i<100; ++i) {bar.push_back(i);if (sz!=bar.capacity()) {sz = bar.capacity();std::cout << "capacity changed: " << sz << '\n';}}return 0;
}

// vector::resize
#include <iostream>
#include <vector>
int main ()
{std::vector<int> myvector;// set some initial content:for (int i=1;i<10;i++)myvector.push_back(i);myvector.resize(5);myvector.resize(8,100);myvector.resize(12);std::cout << "myvector contains:";for (int i=0;i<myvector.size();i++)std::cout << ' ' << myvector[i];std::cout << '\n';return 0;
}

vector的增删查改

函数声明	接口说明
push_back	尾插
pop_back	头插
find	查找
insert	在position之前插入val
erase	删除position位置前的数据
swap	交换两个vector的数据空间
operator[]	像数组一一昂访问

// push_back/pop_back
#include <iostream>
#include <vector>
using namespace std;
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a+sizeof(a)/sizeof(int));vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;return 0;
}

// find / insert / erase
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 在pos位置之前插入30v.insert(pos, 30);vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据v.erase(pos);it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;return 0;
}

// operator[]+index 和 C++11中vector的新式for+auto的遍历
// vector使用这两种遍历方式是比较便捷的。
#include <iostream>
#include <vector>
using namespace std;
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 通过[]读写第0个位置。v[0] = 10;cout << v[0] << endl;// 通过[i]的方式遍历vectorfor (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;vector<int> swapv;swapv.swap(v);cout << "v data:";for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;cout << "swapv data:";for (size_t i = 0; i < swapv.size(); ++i)cout << swapv[i] << " ";cout << endl;// C++11支持的新式范围for遍历for(auto x : v)cout<< x << " ";cout<<endl;return 0;
}

vector迭代器失效的问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间，可能会引起扩容，而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值，可能会引起底层容量改变v.assign(100, 8);/*出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
空间，而引起代码运行时崩溃。解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
赋值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
}

2. 指定位置元素的删除操作--erase

#include <iostream>
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据，导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效 了。

vector的模拟实现

#include <iostream>
using namespace std;
#include <assert.h>
// 注意这里namespace大家下去就不要取名为bit了，否则出去容易翻车。^^
namespace bit
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator cbegin() const { return _start; }
const_iterator cend() const { return _finish; }// construct and destroy
vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{}
vector(int n, const T& value = T()): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{reserve(n);while (n--){push_back(value);}
}
// 如果使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器
// 重新声明迭代器，迭代器区间[first,last]可以是任意容器的迭代器
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{reserve(last - first);while (first != last){push_back(*first);++first;}
}
vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{reserve(v.capacity());iterator it = begin();const_iterator vit = v.cbegin();while (vit != v.cend()){*it++ = *vit++;}
}
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}
~vector()
{delete[] _start;_start = _finish = _endOfStorage = nullptr;
}// capacitysize_t size() const { return _finish - _start; }size_t capacity() const { return _endOfStorage - _start; }bool empty() const {return _first == _finish; }
void reserve(size_t n)
{if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];// 这里直接使用memcpy?//if (_start)// memcpy(tmp, _start, sizeof(T)*size);if (_start){for (size_t i = 0; i < oldSize; ++i)tmp[i] = _start[i];}_start = tmp;_finish = _start + size;_endOfStorage = _start + n;}
}
void resize(size_t n, const T& value = T())
{// 1.如果n小于当前的size，则数据个数缩小到nif (n <= size()){_finish = _start + n;return;}// 2.空间不够则增容if (n > capacity())reserve(n);// 3.将size扩大到niterator it = _finish;iterator _finish = _start + n;while (it != _finish){*it = value;++it;}
}///access///T& operator[](size_t pos){return _start[pos];}const T& operator[](size_t pos)const {return _start[pos];}///modify/
void push_back(const T& x){insert(end(), x);}
void pop_back(){erase(--end());}void swap(vector<T>& v)
{swap(_start, v._start);swap(_finish, v._finish);swap(_endOfStorage, v._endOfStorage);
}iterator insert(iterator pos, const T& x)
{assert(pos <= _finish);// 空间不够先进行增容if (_finish == _endOfStorage){size_t size = size();size_t newCapacity = (0 == capacity())? 1 : capacity() * 2;reserve(newCapacity);// 如果发生了增容，需要重置pospos = _start + size;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}
// 返回删除数据的下一个数据
// 方便解决:一边遍历一边删除的迭代器失效问题
iterator erase(Iterator pos)
{// 挪动数据进行删除iterator begin = pos + 1;while (begin != _finish) {*(begin - 1) = *begin;++begin;}--_finish;return pos;
}
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
}

// constructing vectors
void TestVector1()
{// constructors used in the same order as described above:bite::vector<int> first; // empty vector of ints
bite::vector<int> second(4, 100); // four ints with value 
100bite::vector<int> third(second.Begin(), second.End()); // iterating through 
secondbite::vector<int> fourth(third); // a copy of third// the iterator constructor can also be used to construct from arrays:int myints[] = { 16, 2, 77, 29 };bit::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));std::cout << "The contents of fifth are:";for (bit::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)std::cout <<*it<< " ";std::cout << endl;// 测试T是string时，拷贝问题bit::vector<string> strV;strV.PushBack("1111");strV.PushBack("2222");strV.PushBack("3333");strV.PushBack("4444");for (size_t i = 0; i < strV.size(); ++i){cout << strV[i] << " ";}cout << endl;
}
//vector iterator的使用
void PrintVector(const bite::vector<int>& v)
{// 使用const迭代器进行遍历打印bit::vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}
void TestVector2()
{// 使用push_back插入4个数据bite::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);PrintVector(v);// 使用迭代器进行修改
auto it = v.begin();while (it != v.end()){*it *= 2;++it;}PrintVector(v);// 这里可以看出C++11支持iterator及接口，就支持范围forfor(auto e : v)cout<<e<<" ";
}
// find / insert / erase
void TestVector3()
{int a[] = { 1, 2, 3, 4 };bite::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));// 使用find查找3所在位置的iteratorauto pos = find(v.begin(), v.end(), 3);// 在pos位置之前插入30v.insert(pos, 30);PrintVector(v);// 删除pos位置的数据pos = find(v.begin(), v.end(), 3);v.Erase(pos);PrintVector(v); 
}
// iterator失效问题
void TestVector4()
{int a[] = { 1, 2, 3, 4 };bite::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));// 删除pos位置的数据，导致pos迭代器失效auto pos = find(v.begin(), v.end(), 3);v.erase(pos);cout << *pos << endl; // 此处会导致非法访问// 在pos位置插入数据，导致pos迭代器失效。// insert会导致迭代器失效，是因为insert可// 能会导致增容，增容后pos还指向原来的空间，而原来的空间已经释放了。pos = find(v.begin(), v.end(), 3);v.insert(pos, 30);cout << *pos << endl; // 此处会导致非法访问// 实现删除v中的所有偶数// 下面的程序会崩溃掉，如果是偶数，erase导致it失效// 对失效的迭代器进行++it，会导致程序崩溃auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}// 以上程序要改成下面这样，erase会返回删除位置的下一个位置it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}
}

list与vector对比

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率o（1）	不支持随机访问，效率o（n）
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为o（n），擦汗如是可能需要增容：开辟新的空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率不高，不需要搬移元素，时间复杂度为0（1）
空间利用率	底层连续空间不易形成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针（结点指针）进行封装
迭代器失效	再插入元素时，要给所有迭代器重新赋值，因为插入元素可能会导致重新扩容，导致迭代器失效，删除时当前迭代器需要重新赋值	插入元素不会导致迭代器失效，删除会导致失效，其他不受影响
使用场景	需要高效率存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问