STL之序列式容器（Vector/Deque/List）

序列式容器

序列式容器包括：静态数组 array 、动态数组 vector 、双端队列 deque 、单链表 forward_ list 、双链表 list 。这五个容器中，我们需要讲解三个 vector 、 deque 、 list 的使 用，包括：初始化、遍历、尾部插入与删除、头部插入与删除、任意位置进行插入与 删除、元素的清空、获取元素的个数与容量的大小、元素的交换、获取头部与尾部元素等。

头文件

#include <vector>
template<class T,class Allocator = std::allocator<T>
> class vector;#include <deque>
template<class T,class Allocator = std::allocator<T>
> class deque;#include <list>
template<class T,class Allocator = std::allocator<T>
> class list;

初始化容器对象

对于序列式容器而言，初始化的方式一般会有五种。

初始为空

vector<int> number;
deque<int> number;
list<int> number;

初始为多个相同的值

vector<int> number(10, 1);
deque<int> number(10, 1);
list<int> number(10, 1);

使用迭代器范围

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> number(arr, arr + 10);//左闭右开区间
//vector可以直接替换为deque与list

使用大括号

vector<int> number = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//vector可以直接替换为deque与list

拷贝构造或者移动构造

vector<int> number1 = {1, 2, 4, 6};
vector<int> number2(number1);
vector<int> number3(std::move(number1));
//vector可以直接替换为deque与list

遍历容器中的元素

就是访问容器中的每个元素，一般可以采用下标或者迭代器的方式进行遍历。

//1、使用下标进行遍历(要求容器必须是支持下标访问的，list不支持下标，所以就不适用)
for(size_t idx = 0; idx != number.size(); ++idx)
{cout << number[idx] << " ";
}//2、使用未初始化的迭代器进行遍历
vector<int>::iterator it;
for(it = numbers.begin(); it != numbers.end(); ++it)
{cout << *it << " ";
}//3、使用初始化迭代器进行遍历
vector<int>::iterator it = number.begin();
for(; it != number.end(); ++it)
{cout << *it << " ";
}//4、使用for加上auto进行遍历
for(auto &elem : number)
{cout << elem << " ";
}

在容器的尾部插入与删除

可以向容器的尾部插入一个元素或者将容器的最后一个元素删除。

//尾部插入一个元素（注意：是拷贝一份副本到尾部）
void push_back( const T& value);
void push_back( T&& value);
//尾部删除
void pop_back();

在容器的头部插入与删除

可以向容器的头部插入一个元素或者将容器的第一个元素删除。

//头部插入
void push_front( const T& value);
void push_front( T&& value);
//头部删除
void pop_front();

对于 deque 与 list 而言，是支持这两个操作的， 但是对于vector没有提供这两个操作。 vector 不支持在头部进行插入元素与删除元素。 这是从效率方面进行的考虑。

vector的原理

vector 头部是固定的，不能进行插入与删除，只提供了在尾部进行插入与删除的操作，所以如果真的要在头部插入或者删除，那么其他的元素会发生移动，这样操作就比较复杂。

探讨 vector 的 底层实现 ，三个指针：

_ M _ start ：指向第一个元素的位置；

_ M _ finish ：指向最后一个元素的下一个位置；

_ M _ end _ of _ storage ：指向当前分配空间的最后一个位置的下一个位置；

那么这三个指针是怎么来的呢，我们可以从其源码中获取答案（这里可以阅读 vector的源码）

void test()
{
vector<int> number = {1, 2, 3, 4};
&number;//error,只是获取对象栈上的地址,也就是_M_start的地址
&number[0];//ok
&*number.begin();//ok
int *pdata = number.data();//ok
cout << "pdata = " << pdata << endl;//使用printf，思考一下printf与cout打印地址的区别
}

deque的原理

探索 deque 的 底层实现 ：

deque 是由多个片段组成的，片段内部是连续的，但是片段之间不连续的、分散的，多个片段被一个称为中控器的结构控制，所以说deque 是在物理上是不连续的，但是逻辑上是连续的。

我们依旧可以从其源码中获取答案（这里可以阅读 deque 的源码）

从继承图中可以看到，中控器其实是一个二级指针，由 _M_map 表示，还有一个表示中控器数组大小的 _M_map_size ， deque 的迭代器也不是一个简单类型的指针，其迭代器是一个类类型，deque 有两个迭代器指针，一个指向第一个小片段，一个指向最后一个小片段。其结构图如下：

list的原理

list是双向链表，其实现如下:

在容器的任意位置插入

三种序列式容器在任意位置进行插入的操作是insert函数，函数接口如下

//1、在容器的某个位置前面插入一个元素
iterator insert( iterator pos, const T& value );
iterator insert( const_iterator pos, const T& value );
number.insert(it, 22);//2、在容器的某个位置前面插入count个相同元素
void insert(iterator pos, size_type count, const T& value)；
iterator insert(const_iterator pos, size_type count, const T& value)；
number.insert(it1, 4, 44);//3、在容器的某个位置前面插入迭代器范围的元素
template<class InputIt>
void insert(iterator pos, InputIt first, InputIt last);
template<class InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last)；
vector<int> vec{51, 52, 53, 54, 55, 56, 57, 58, 59};
number.insert(it, vec.begin(), vec.end());//4、在容器的某个位置前面插入大括号范围的元素
iterator insert(const_iterator pos, std::initializer_list<T> ilist)；
number.insert(it, std::initialiser_list<int>{1, 2, 3});

三种序列式容器的插入示例如下：

//此处list可以换成vector或者deque
list<int> number = {1, 4, 6, 8, 9};
++it;
auto it = number.begin();//1、在容器的某个位置前面插入一个元素
number.insert(it, 22);//2、在容器的某个位置前面插入count个相同元素
number.insert(it, 3, 100);//3、在容器的某个位置前面插入迭代器范围的元素
vector<int> vec{51, 52, 53, 54, 55, 56, 57, 58, 59};
number.insert(it, vec.begin(), vec.end());//4、在容器的某个位置前面插入大括号范围的元素
number.insert(it, {1, 2, 3});

insert 在任意位置进行插入， list 使用起来很好，没有任何问题，但是 deque 与 vector 使用起来可能会出现问题，因为 vector 是物理上连续的 ，所以在中间插入元素会导致插入元素后面的所有元素向后移动，deque 也有类似情况， 可能因为插入而引起底层容量 不够而扩容，从而使得迭代器失效 ( 申请了新的空间，但是迭代器还指向老的空间 ) ，即使没有扩容，插入之后的迭代器也失效了( 不再指向之前的元素了 ) 。

vector的迭代器失效

以 vector 为例，如果使用 insert 插入元素，而每次插入元素的个数不确定，可能剩余空间不足以存放插入元素的个数，那么insert 在插入的时候 底层就可能导致扩容，从而导 致迭代器还指向老的空间，继续使用该迭代器会出现迭代器失效的问题 。

void test()
{
vector<int> number = {1, 2, 3, 4, 5, 6, 7, 8, 9};
display(number);
cout << "number.size() = " << numbers.size() << endl;//9
cout << "number.capacity() = " << numbers.capacity() << endl;//9cout << endl << "在容器尾部进行插入: " << endl;
number.push_back(10);
number.push_back(11);
display(number);
cout << "number.size() = " << number.size() << endl;//11
cout << "number.capacity() = " << number.capacity() << endl;//18cout << endl << "在容器vector中间进行插入: " << endl;
auto it = number.begin();
++it;
++it;
number.insert(it, 22);
display(number);
cout << "*it = " << *it << endl;
cout << "number.size() = " << number.size() << endl;//12
cout << "number.capacity() = " << number.capacity() << endl;//18numbers.insert(it, 7, 100);//因为插入个数不确定，有可能底层已经发生了扩容
display(numbers);
cout << "*it = " << *it << endl;
cout << "numbers.size() = " << numbers.size() << endl;//19
cout << "numbers.capacity() = " << numbers.capacity() <<endl;//24//正确办法是重置迭代器的位置
vector<int> vec{51, 52, 53, 56, 57, 59};
numbers.insert(it, vec.begin(), vec.end());//继续使用该迭代器就会出现问题（内存错误）
display(numbers);
cout << "*it = " << *it << endl;
cout << "numbers.size() = " << numbers.size() << endl;
cout << "numbers.capacity() = " << numbers.capacity() << endl;//解决方案：每次在插入元素的时候，可以将迭代器的位置进行重置更新，避免因为底层扩容，迭代器还指向老
//的空间而出现问题
vector<int> vec{51, 52, 53, 56, 57, 59};
it = number.begin();//重新置位
++it;
++it;
numbers.insert(it, vec.begin(), vec.end());//继续使用该迭代器就会出现问题（内存错误）
display(numbers);
cout << "*it = " << *it << endl;
cout << "numbers.size() = " << numbers.size() << endl;
cout << "numbers.capacity() = " << numbers.capacity() << endl;
}

因为 vector 的 push _ back 操作每次只会插入一个元素，所以可以按照统一的形式 2 * capacity() ，但是 insert 的时候，插入的元素个数是不定的，所以就不能一概而论。这里可以分别讨论一下，我们设置capacity () = n , size () = m , insert 插入的元素个数为 t个：

如果 t < n - m ，新插入元素的个数比剩余空间小，这个时候就无需扩容，所以直接插入;

如果 n - m < t < m ，就按照 m 的 2 倍去进行扩容，新的空间就是 2 * m ；如果n - m < t < n 且 t > m , 就按照 t + m 去进行扩容；

如果 t > n 时，依旧按照 t + m 去进行扩容 ；

这就是vector 进行 insert 扩容的原理（这个原理可以了解一下，主要是为了告诉大家不

是两倍扩容）。

在容器的任意位置删除元素

三种序列式容器的删除操作是erase函数，函数接口如下

//删除指定迭代器位置的元素
iterator erase(iterator position);
//删除一个迭代器范围的元素
iterator erase(iterator first, iterator last);

对于 vector 而言，会导致删除迭代器之后的所有元素前移，从而导致删除元素之后的所有迭代器失效（迭代器的位置没有改变，但是因为元素的移动，导致迭代器指向的不是删除之前的元素，所以失效）；deque 比 vector 复杂，要看 pos 前后的元素个数来决定，deque 的 erase 函数可以看 STL 源码，需要看删除位置与 size () 的一半的大小，然后看是挪动前一半还是后一半，尽量减少挪动的次数；list 会删除指向的元素，从而导致指向删除元素的迭代器失效。

这里以 vector 的 erase 为例，看看其删除元素的操作与删除后的效果。

//题意：删除vector中所有值为4的元素。
vector<int> vec = {1, 3, 5, 4, 4, 4, 4, 7, 8，4, 9};
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
{if(4 == *it){vec.erase(it);}
}//发现删除后有些4没有删除掉，可以推测出是什么原因吗？是那些4没有删除呢？
//正确解法：
for (auto it = vec.begin(); it != vec.end();)
{ if (4 == *it){vec.erase(it);//此处可以使用it接收erase的结果，更通用一些，即：it = vec.erase(it);}else{++it;}
}

其他操作

//1、清除容器中的所有元素(三个序列式容器都有)
void clear();//2、获取元素个数(三个序列式容器都有)
size_type size() const;//3、获取容量大小（只有vector有）
size_type capacity() const;//4、回收多余的空间，使得元素的个数与容量大小对应，不存在没有使用的空间（vector与deque有这个函数）
void shrink_to_fit();//5、交换两个相同容器中的元素(三个序列式容器都有)
void swap( vector& other);
vector<int> number1 = {1, 2, 3};
vector<int> number2 = {10, 20, 30};
number1.swap(number2);//之后number1中的内容与number2中的内容做了交换//6、更改容器中元素个数(三个序列式容器都有)
//以vector为例，执行resize时候，如果count < size(),就将多余的元素删除；如果count > size(),就在//之前的元素后面执行insert添加元素（没有指定就添加默认值）,元素的个数在改变的同时，容量也在发生改变 //（上一次的两倍或者本次元素个数）
void resize( size_type count, T value = T() );
void resize( size_type count);
void resize( size_type count, const value_type& value);//7、获取第一个元素(三个序列式容器都有)
reference front();
const_reference front() const;//8、获取最后一个元素(三个序列式容器都有)
reference back();
const_reference back() const;//9、C++11增加的可变参数模板的几个函数
//在容器的尾部就地构造一个元素
template< class... Args >
void emplace_back( Args&&... args);
vector<Point> vec;
vec.emplace_back(1, 2);//就地将(1, 2)构建为一个对象存放在vector的尾部，减少拷贝或者移动

list的特殊操作

排序函数sort

void sort();//默认以升序进行排序，其实也就是，使用operator<进行排序
template< class Compare >
void sort(Compare comp);//其实也就是传入一个具有比较的类型，即函数对象
template <typename T1, typename T2>
struct Compare
{bool operator()(const T1 &a, const T2 &b) const{return a < b;}
};

移除重复元素u n i q u e

void unique();
size_type unique();

注意使用 unique 的时候，要保证元素 list 是已经排好顺序的，否则使用 unique 是没有用的。

逆置链表中的元素r e v e r s e

void reverse();
void reverse() noexcept;

将链表中的元素逆置。

合并链表的函数m e r g e

//合并两个链表（other既可以是左值也可以是右值）
void merge( list& other );
void merge( list&& other );
template <class Compare>
void merge( list& other, Compare comp );
template <class Compare>
void merge( list&& other, Compare comp );

合并的链表必须是有序的，如果没有顺序，合并没有效果。两个链表合并之后，并且另一个链表就为空了。

从一个链表转移元素到另一个链表s p l i c e

//移动other链表到另一个链表的某个指定位置前面
void splice(const_iterator pos, list& other);
void splice(const_iterator pos, list&& other);//移动other链表中的某个元素到另一个链表的某个指定位置前面
void splice(const_iterator pos, list& other, const_iterator it);
void splice(const_iterator pos, list&& other, const_iterator it);//移动other链表的一对迭代器范围元素到另一个链表的某个指定位置前面
void splice(const_iterator pos,list& other, const_iterator first, const_iterator last);
void splice(const_iterator pos,list&& other,const_iterator first, const_iterator last);