序列式容器

概念

序列容器，就是以线性排列（类似普通数组的存储方式）来存储某一指定类型的数据，并且该类容器并不会自动对存储的元素按照值的大小进行排序。

内容

array（数组容器）	表示可以存储N个T类型的容器，该容器一旦建立那么容量就是固定的，因此不能额外增加或删除元素，只能修改其值
vector（向量容器）	大部分与array类似，但是vector是长度可变的，可以看成是可以动态变化长度的数组，因此在其尾部增加或删除元素效率可以看成是O(1)，对其他位置的操作为O(n)
deque（双端队列容器）	大部分与vector类似，但是deque在头部插入与删除也是O(1)，在其中部插入与删除元素才是O(n)
list（链表容器）	一个长度可变的T类型的序列，内部采用双向链表实现，由于双向链表的特性，对其在任何位置插入与删除都将是O(1)，但是由于list对应的迭代器类型为双向迭代器，决定了list的访问必须逐个访问，因此对list的访问速度要慢于array、vector和deque
forward_list（正向链表容器）	十分接近list，但是内部采用的是单链表实现，因此节省了一定的内存，但是访问也需要逐个访问

序列式容器迭代器的通用函数

由于序列式容器（除了forward_list外）都是支持随机访问迭代器的，所以他们有一些通用的对迭代器的操作方法，这里直接给出：

begin()	返回指向第一个元素的随机访问迭代器
end()	返回指向容器最后一个元素之后一个位置的随机访问迭代器
rbegin()	返回指向最后一个元素的随机访问迭代器
rend()	返回指向第一个元素之前一个位置的随机访问迭代器
cbegin()	和 begin() 功能相同，只不过在其基础上增加了 const 属性，不能用于修改元素
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素

举个栗子：

std:: array<int, 5> v{1,2,3,4,5};
for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {
    std::cout << *it << ' ';
}
std::cout << std::endl;//Output 1 2 3 4 5
for (std::array<int, 5>::reverse_iterator it = v.rbegin(); it != v.rend(); it++) {//注意此处需要使用反向迭代器和++
    std::cout << *it << ' ';
}
std::cout << std::endl;//Output 5 4 3 2 1

关于这几个对迭代器的操作方法，可以见下图：

除此之外对于迭代器的操作，可以使用auto关键字，编译器会自动识别其迭代器的类型。

序列式容器用法

array

array是一种不可以修改其长度，在普通数组的基础上增加了一些全局变量和函数的序列式容器，比起不同数组效率更高更安全。

定义

array的定义:

namespace std{
    template <typename T, size_t N>
    class array;
}

可以看到array被定义在命名空间std中

因此创建array可以有以下两种方式:

#include<array> //使用array必须导入array头文件
std::array<int, 5> v;

或:

#include<array>
using namespace std;
int main() {
	array<int, 5> v;
}

初始化

array的初始化可以采用默认初始化方式：

std:: array<int, 5> v{};//默认初始化
for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {
	std::cout << *it << ' ';
}
//输出5个0

也可以采用类似数组的初始化方式：

std:: array<int, 10> v{1,2,5};
for (std::array<int, 10>::iterator it = v.begin(); it != v.end(); it++) {
    std::cout << *it << ' ';
}
//输出1 2 5 0 0 0 0 0 0 0

成员函数

array因为支持随机访问迭代器，所以上文提到的8个操作array都支持

除此之外，array还支持其他几个操作

size()	返回array中的元素个数，由于array长度是固定的，所以相当于返回构造array的第二个参数N
max_size()	返回可容纳元素的最大数量，由于array长度是固定的，所以相当于返回构造array的第二个参数N
empty()	返回array是否非空
at(i)	返回array第i个位置(从0开始)的元素的引用，这意味着我们可以直接对他进行修改，并且它会自动检查i是否会导致越界，如果越界会抛出std::out_of_range的异常
front()	返回容器中第一个元素的直接引用，该函数不适用于空的array容器
back()	返回容器中最后一个元素的直接应用，该函数同样不适用于空的array容器
data()	返回一个指向容器首个元素的指针
operator[]	类似于数组元素的下标访问方式，返回数组对应下标的引用，可以直接操作(包括修改)
fill(T& val)	将val赋值给array中的每一个元素，相当于批量赋值，可以用于初始化
array1.swap(array2)	在array1和array2的T与N一致的情况下交换两个array中的元素

举个栗子：

std:: array<int, 5> v{1,2,3,4,5};
v[2] = 7;
std::cout << v.at(2) << std::endl;//Output 7
v.at(2) = 5;
std::cout << v.at(2) << std::endl;//Output 5
for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {//Output 1 2 5 4 5
	std::cout << *it << ' ';
}
std::cout << std::endl;
std::cout << v.front() << std::endl;//Output 1
std::cout << v.back() << std::endl;//Output 5
v.fill(10);
for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {//Output 10 10 10 10 10
	std::cout << *it << ' ';
}
std::cout << std::endl;
*(v.data()) = 4;
for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {//Output 4 10 10 10 10
	std::cout << *it << ' ';
}

array相比数组的提升

1.array可以实现大小的比较

大小比较的规则与字符串的大小比较规则一致

std::array<char, 20> h{ "helloworld" };
std::array<char, 20> a{ "apple" };	
if (a < h) {//no
    std::cout << "yes\n";
}
else {
    std::cout << "no\n";
}

2.array可以直接赋值

std::array<char, 20> h{ "helloworld" };
std::array<char, 20> a{ "apple" };
a = h;
for (auto e : a) {//helloworld
    std::cout << e;
}

3.at方法可以自动检查边界问题

vector

vector是向量容器，一个向量用于存储同一个类型的一组值

定义

一个向量的定义需要引入如下代码段:

#include <vector>
using namespace std;

或以下列形式创建，(T)是一个类型

#include <vector>
std::vector<T> v;

注意，这样定义的 vector 容器，因为容器中没有元素，所以没有为其分配空间。当添加第一个元素（比如使用 push_back() 函数）时，vector 会自动分配内存。

对于vector，有容量（capacity）和size（大小）的区分。

容量指的是vector能够容纳的最大元素数，这是一个可以拓展的值，通过调用reserve()来拓展容量，如果新的容量小于等于当前容量，那么没有操作，其不会影响原有元素，也不会生成新元素，但是要注意，一旦使用了reserve()那么原油的所有迭代器都将会失效，因为拓展容量时会修改整个vector的地址。

大小指的是vector当前实际容纳的元素数，其也可以修改，通过调用resize()来修改值，如果新的size比容量要大，那么会自动扩容。

初始化

第一种方式，初始化成员列表：
vector<int> v1{1,2,3,4,5};
第二种方式，指定元素个数（默认初始化为0）
vector<int> v2(5);//5个0
第三种方式，指定元素个数并全部初始化为1
vector<int> v3(5,1);//5个1 
第四种方式，存储已经存在的vector容器值或数组
vector<int> a(v3); //5个1
vector<int> b(v1.begin(),v1.begin()+3);//1 2 3
int arr[3] = {4,5,6};
vector<int> c(arr,arr+3);//4 5 6

需要注意的是，由于vector是可以直接创建空的vector的，所以这样的初始化是错误的

vector<int> v;
for (auto it = v.begin();it != v.end();it++){
	*it = 1;
    cout << *it << ' '; 
}
//不会报错，但是不会做到预想的结果，因为空的vector的begin() == end()

成员函数

vector因为支持随机访问迭代器，所以上文提到的8个操作vector都支持

除此之外，vector还支持其他几个操作

size()	返回实际元素个数
max_size()	返回元素个数的最大值。这通常是一个很大的数
resize()	改变实际元素的个数
capacity()	返回当前容量
reserve()	增加容器的容量
empty()	返回vector是否非空
at(i)	返回vector第i个位置(从0开始)的元素的引用，这意味着我们可以直接对他进行修改，并且它会自动检查i是否会导致越界，如果越界会抛出std::out_of_range的异常
front()	返回容器中第一个元素的直接引用，该函数不适用于空的vector容器
back()	返回容器中最后一个元素的直接应用，该函数同样不适用于空的vector容器
data()	返回一个指向容器首个元素的指针
operator[]	类似于数组元素的下标访问方式，返回数组对应下标的引用，可以直接操作(包括修改)
assign(val)	将val赋值给vector中的每一个元素，相当于批量赋值，可以用于初始化
push_back()	在vector的尾部添加一个元素，先创建，然后拷贝移动到vector末尾
pop_back()	移出vector尾部的元素，对于空的vector不适用，移除后size-1，而capacity不变
insert()	在指定的位置插入一个或多个元素，插入后size+1，capacity可能不变
erase()	移出一个元素或一段元素，移除后size减小，capacity不变
clear()	移出所有的元素，容器大小变为 0
swap()	交换两个容器的所有元素/td>
emplace()	在指定的位置直接生成一个元素，大小+1
emplace_back()	在vector尾部生成一个元素，由于其是在尾部直接生成而不是拷贝元素或移动，因此效率比push_back高

一些例子：

vector<int> v;
cout << v.front() << endl;//Error
cout << v.back() << endl;//Error
cout << v.size() << endl;//Output 0
v.pop_back();//Error
for (auto e : v) {//no Output
    cout << e << ' ';
}
cout << v.max_size() << endl;//Output 1073741823
v.resize(10);
cout << v.max_size() << endl;//Output 1073741823
cout << v.size() << endl;//Output 10
for (auto e : v) {//Output 0 0 0 0 0 0 0 0 0 0
    cout << e << ' ';
}

其中某些函数存在多个重载，或其调用有其独特的含义，如对参数由特定要求等，这里单独列出：

1.insert
iterator insert(iterator pos,const T& elem)	在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器。
iterator insert(iterator pos,int n,const T& elem)	在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。
iterator insert(iterator pos,first,last) 	在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。
iterator insert(iterator pos,initializer_list<T> initlist)	在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。
                                                                                    
2.emplace()
该函数与insert很像，都是在某个位置插入元素，但是要注意这个函数一次只能插入一个，同时该函数的效率比insert单次插入要高                                                                               
iterator emplace(iterator pos,const T& elem)                                             
                                                                                    
3.erase()
iterator erase(iterator pos) 删除某个指定位置的元素，返回指向被删除元素下一个位置元素的迭代器       iterator erase(iterator begin,iterator end)删除[begin,end)范围的元素，返回指向被删除元素下一个位置元素的迭代器   
                
void show(vector<int> v) {
	for (auto c : v) {
		cout << c << ' ';
	}
	cout << endl;
}
int main() {
	vector<int> v{ 1,2,4,5 };
	v.insert(v.begin() + 2, 3);
	show(v);//1 2 3 4 5
	v.insert(v.begin(), 3, 0);
	show(v);//0 0 0 1 2 3 4 5
	array<int, 2> arr{ 6,7 };
	v.insert(v.end(), arr.begin(), arr.end());
	show(v);//0 0 0 1 2 3 4 5 6 7
	v.insert(v.end(), { 8,9 });
	show(v);//0 0 0 1 2 3 4 5 6 7 8 9
	v.emplace(v.end(), 10);
	show(v);//0 0 0 1 2 3 4 5 6 7 8 9 10
	v.erase(v.begin());
	show(v);//0 0 1 2 3 4 5 6 7 8 9 10
}                                                                    

一些小tips

虽然我们创建一个向量vector的时候，理论上这个T可以是任意类型，但是bool类型作为T是会出现问题的因为其牵扯到复杂的历史遗留问题，不做展开。

deque

deque是双端队列容器，其在某些方面与vector高度相似，其对头尾的插入为O（1），对中间位置的插入为O（n），但是其与vector有一个很大的不同在于deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

定义

类似的，deque的创建也有两种方式:

1.
#include<deque>
using namespace std;
deque<int> deq;
2.
#include<deque>
std::deque<int> deq;

注意，这样定义的deque容器，因为容器中没有元素，所以没有为其分配空间。当添加第一个元素（比如使用 push_back() 函数）时，deque 会自动分配内存。

初始化

与vector类似的5种初始化方式

第一种方式，初始化成员列表：
deque<int> v1{1,2,3,4,5};
第二种方式，指定元素个数（默认初始化为0）
deque<int> v2(5);//5个0
第三种方式，指定元素个数并全部初始化为1
deque<int> v3(5,1);//5个1 
第四种方式，存储已经存在的deque容器值或数组
deque<int> a(v3); //5个1
deque<int> b(v1.begin(),v1.begin()+3);//1 2 3
int arr[3] = {4,5,6};
deque<int> c(arr,arr+3);//4 5 6

也跟vector一样在某些方面有限制

deque<int> v;
for (auto it = v.begin();it != v.end();it++){
	*it = 1;
    cout << *it << ' '; 
}
//不会报错，但是不会做到预想的结果，因为空的deque的begin() == end()

成员函数

因为deque支持随机访问迭代器，所以上面对随机访问迭代器的8种操作deque都支持

除此之外，deque还支持其他几个操作

size()	返回实际元素个数
max_size()	返回元素个数的最大值。这通常是一个很大的数
resize()	改变实际元素的个数
empty()	返回deque是否非空
shrink _to_fit()	将内存减少到等于当前元素实际所使用的大小
at(i)	返回deque第i个位置(从0开始)的元素的引用，这意味着我们可以直接对他进行修改，并且它会自动检查i是否会导致越界，如果越界会抛出std::out_of_range的异常
front()	返回容器中第一个元素的直接引用，该函数不适用于空的deque容器
back()	返回容器中最后一个元素的直接应用，该函数同样不适用于空的deque容器
operator[]	类似于数组元素的下标访问方式，返回数组对应下标的引用，可以直接操作(包括修改)
assign(val)	将val赋值给deque中的每一个元素，相当于批量赋值，可以用于初始化
push_back()	在deque的尾部添加一个元素，先创建，然后拷贝移动到deque末尾
pop_back()	移出deque尾部的元素，对于空的deque不适用，移除后size-1，而capacity不变
push_front()	在deque的头部添加一个元素，先创建，然后拷贝移动到deque头部
pop_front()	移出deque头部的元素，对于空的deque不适用，移除后size-1，而capacity不变
insert()	在指定的位置插入一个或多个元素，插入后size+1，capacity可能不变
erase()	移出一个元素或一段元素，移除后size减小，capacity不变
clear()	移出所有的元素，容器大小变为 0
swap()	交换两个容器的所有元素/td>
emplace()	在指定的位置直接生成一个元素，大小+1
emplace_back()	在deque尾部生成一个元素，由于其是在尾部直接生成而不是拷贝元素或移动，因此效率比push_back高
emplace_front()	在deque头部生成一个元素，由于其是在头部直接生成而不是拷贝元素或移动，因此效率比push_front高

注意，deque没有data()函数，这是deque的底层实现决定的。

由于函数的定义与重载与vector十分类似，这里不再演示

deque的底层原理

deque的底层原理，是借助这样的一个结构实现的

map是一个地址数组，存储着各个连续空间的首地址，通过这个map数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。

list

双向链表容器，底层是以双向链表的形式实现的。因此，list 容器中的元素可以分散存储在内存空间里。

定义

类似的，list的创建也有两种方式:

1.
#include<list>
using namespace std;
list<int> L;
2.
#include<list>
std::list<int> L;

注意，这样定义的list容器，因为容器中没有元素，所以没有为其分配空间。当添加第一个元素（比如使用 push_back() 函数）时，list 会自动分配内存。

初始化

与vector类似的5种初始化方式

第一种方式，初始化成员列表：
list<int> v1{1,2,3,4,5};
第二种方式，指定元素个数（默认初始化为0）
list<int> v2(5);//5个0
第三种方式，指定元素个数并全部初始化为1
list<int> v3(5,1);//5个1 
第四种方式，存储已经存在的list容器值或数组
list<int> a(v3); //5个1
list<int> b(v1.begin(),v1.begin()+3);//1 2 3
int arr[3] = {4,5,6};
list<int> c(arr,arr+3);//4 5 6

也跟vector一样在某些方面有限制

list<int> v;
for (auto it = v.begin();it != v.end();it++){
	*it = 1;
    cout << *it << ' '; 
}
//不会报错，但是不会做到预想的结果，因为空的list的begin() == end()

成员函数

比起vector，array和deque，list的迭代器类型为双向迭代器，这决定了对于list的迭代器不能使用任何的比较运算符，+=、-=之类的一次跨越多步的运算符以及不能通过下标访问元素。但是其支持使用==和!=运算符

size()	返回实际元素个数
max_size()	返回元素个数的最大值。这通常是一个很大的数
resize()	调整容器的大小
empty()	返回list是否非空
front()	返回容器中第一个元素的直接引用，该函数不适用于空的list容器
back()	返回容器中最后一个元素的直接应用，该函数同样不适用于空的list容器
assign(val)	将val赋值给list中的每一个元素，相当于批量赋值，可以用于初始化
push_back()	在list的尾部添加一个元素，先创建，然后拷贝移动到list末尾
pop_back()	移出list尾部的元素，对于空的list不适用，移除后size-1，而capacity不变
push_front()	在list的头部添加一个元素，先创建，然后拷贝移动到list头部
pop_front()	移出list头部的元素，对于空的list不适用，移除后size-1，而capacity不变
insert()	在指定的位置插入一个或多个元素，插入后size+1，capacity可能不变
erase()	移出一个元素或一段元素，移除后size减小，capacity不变
clear()	移出所有的元素，容器大小变为 0
swap()	交换两个容器的所有元素
emplace()	在指定的位置直接生成一个元素，大小+1
emplace_back()	在list尾部生成一个元素，由于其是在尾部直接生成而不是拷贝元素或移动，因此效率比push_back高
emplace_front()	在list头部生成一个元素，由于其是在头部直接生成而不是拷贝元素或移动，因此效率比push_front高
splice()	将一个 list 容器中的元素插入到另一个容器的指定位置
remove(val)	删除容器中所有等于 val 的元素
remove_if()	删除容器中满足条件的元素
unique()	删除容器中相邻的重复元素，只保留一个
merge()	合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的，如果原本的两个list无序则报错
sort()	通过更改容器中元素的位置，将它们进行排序
reverse()	反转容器中元素的顺序

另外，由于list底层的实现机制的原因，对list容器进行插入、删除、结合等操作的时候不会导致原有的迭代器失效，只有删除会导致当前指向的迭代器失效。

部分list添加的函数举例:

void show(list<int> v) {
	for (auto c : v) {
		cout << c << ' ';
	}
	cout << endl;
}
int main() {
	list<int> L{ 0,0,0,1,4,3 };
	show(L);//0 0 0 1 4 3
	L.remove(0);
	show(L);//1 4 3
	L.sort();
	show(L);//1 3 4 
	list<int> L2{ 4,5,6 };
	L.merge(L2);
	show(L);//1 3 4 4 5 6
	L.unique();
	show(L);//1 3 4 5 6
	L.reverse();
	show(L);//6 5 4 3 1
}

insert、erase等函数的使用方法与上文一致，这里不再重复
但是对于一些新的方法这里给出使用形式

1.splice()
splice() 成员方法的作用对象是其它 list 容器，其功能是将其它 list 容器中的元素添加到当前 list 容器中指定位置处
void splice (iterator pos, list& l);将 l 容器中存储的所有元素全部移动当前 list 容器中 pos 指明的位置处。
void splice (iterator pos, list& l, iterator it);将 l 容器中 it 指向的元素移动到当前容器中 pos 指明的位置处
void splice (iterator pos, list& l, iterator first, iterator last);将 l 容器 [first, last) 范围内所有的元素移动到当前容器 pos 指明的位置处
注意，无论使用哪种形式，添加完成后l都为空
                                                                           
2.remove_if()
remove_if(lambda)该函数接受一个lambda表达式（实际上是一个函数），满足条件的都将被删除。                        
void show(list<int> v) {
	for (auto c : v) {
		cout << c << ' ';
	}
	cout << endl;
}
int main() {
	list<int> L{ 0,0,0,1,4,3 };
	list<int> L2{ 4,5,6 };
	L.splice(L.begin(), L2);//4 5 6 0 0 0 1 4 3
	show(L);
	L.splice(L.end(), L2, L2.begin());//0 0 0 1 4 3 4
	show(L);
	L.splice(L.end(), L2, L2.begin(), L2.end());//0 0 0 1 4 3 4 5 6
	show(L);
    L.remove_if([&](int data) {return data <= 0; });//1 4 3
	show(L);
}                                                                     

list的底层原理

list的底层即双向链表

forward_list

forward_list，采用单链表构建的一种stl数据结构

定义

类似的，forward_list的创建也有两种方式:

1.
#include<forward_list>
using namespace std;
forward_list<int> L;
2.
#include<forward_list>
std::forward_list<int> L;

注意，这样定义的forward_list容器，因为容器中没有元素，所以没有为其分配空间。当添加第一个元素（比如使用 push_back() 函数）时，forward_list 会自动分配内存。

初始化

与vector类似的5种初始化方式

第一种方式，初始化成员列表：
forward_list<int> v1{1,2,3,4,5};
第二种方式，指定元素个数（默认初始化为0）
forward_list<int> v2(5);//5个0
第三种方式，指定元素个数并全部初始化为1
forward_list<int> v3(5,1);//5个1 
第四种方式，存储已经存在的forward_list容器值或数组
forward_list<int> a(v3); //5个1
forward_list<int> b(v1.begin(),v1.begin()+3);//1 2 3
int arr[3] = {4,5,6};
forward_list<int> c(arr,arr+3);//4 5 6

也跟vector一样在某些方面有限制

forward_list<int> v;
for (auto it = v.begin();it != v.end();it++){
	*it = 1;
    cout << *it << ' '; 
}
//不会报错，但是不会做到预想的结果，因为空的forward_list的begin() == end()

成员函数

因为forward_list底层采用了单链表的形式，因此forward_list的迭代器为正向迭代器，因此其对应的前面八个迭代器函数中带r的都不存在

before_begin()	返回指向容器中第一个元素之前的位置的迭代器
cbefore_begin()	返回指向容器中第一个元素之前的位置的迭代器，不能用于修改元素
max_size()	返回元素个数的最大值。这通常是一个很大的数
resize()	调整容器的大小
empty()	返回list是否非空
front()	返回容器中第一个元素的直接引用，该函数不适用于空的list容器
assign(val)	将val赋值给list中的每一个元素，相当于批量赋值，可以用于初始化
push_front()	在list的头部添加一个元素，先创建，然后拷贝移动到list头部
emplace_front()	在list头部生成一个元素，由于其是在头部直接生成而不是拷贝元素或移动，因此效率比push_front高
pop_front()	移出list头部的元素，对于空的list不适用
insert_after()	在指定的位置插入一个元素,返回一个指向新元素的迭代器
emplace_after()/td>	在指定的位置插入一个元素,效率高于insert_after()
erase_after()	删除容器中某个指定位置或区域内的所有元素
clear()	移出所有的元素，容器大小变为 0
swap()	交换两个容器的所有元素/td>
splice_after()	将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后
remove(val)	删除容器中所有等于 val 的元素
remove_if()	删除容器中满足条件的元素
unique()	删除容器中相邻的重复元素，只保留一个
merge()	合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的，如果原本的两个list无序则报错
sort()	通过更改容器中元素的位置，将它们进行排序
reverse()	反转容器中元素的顺序

注意没有size()函数

forward_list的底层原理

forward_list 使用的是单链表

0、序列式容器

vector

一、vector6种初始化

1、vector<int> vec1;// 默认初始化，vector为空，size为0，需要动态添加
2、vector<int> vec1(7);//包含7个缺省的值初始化，即7个0.
3、vector<int> vec1(7,3);// 包含7个值为3的int
4、vector<int> vec2(vec1);
   vector<int> vec2=vec1;// 两种方式等价，vec2初始化为vec1的拷贝
5、vector<int> vec1={1,2,3,5,6};// 列表初始化
6、vector<int> vec2(vec1.begin()+2,vec1.end());// 两个迭代器范围

list

deque

头尾两端分别做元素插入与删除。处理数据库事务或模拟一家超市的结账队列，像这两种应用都可以充分利用 deque 容器。

与vector区别：

1：deque可以在容器的头部和尾部高效地添加或删除对象，这是它相对于 vector 容器的优势。

2：没有容量观念，动态分段连续空间组合，没必要vector的空间保留。

基本操作：

增删：

push_back在尾部添加一个元素  push_front在首部添加一个元素

pop_back在尾部删除一个元素    pop_front在首部删除一个元素

emplace (C++11)在迭代器位置插入元素（emplace使用直接构造函数，insert使用复制构造函数）

emplace_front (C++11)在首部添加一个元素

emplace_back (C++11)在尾部添加一个元素

insert迭代器位置插入元素，或者插入连续的序列

erase擦除迭代器位置的元素，或者擦除连续的序列

访问元素：

operator[]直接访问指定位置的元素

at直接访问指定位置的元素，指定位置超出有效范围会报出异常

front访问首元素

back访问尾元素

判断：

size返回目前元素的数量

max_size返回可以拓展的最大容量

resize改变目前容器的大小

empty判断容器是否为空

迭代器

begin 将迭代器返回到开头（增长方向：begin -> end）

end将迭代器返回到结尾

rbegin返回反向迭代器以反向开始（增长方向：rbegin -> rend）

rend将反向迭代器返回到反向结束

 

stack

先进后出，

基本操作：

增删：s.push(int x)将x 接到队列的末端    s.pop()  弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问元素：q.top() 获取栈顶元素

判断：q.empty() 当队列空时，返回true       q.size()访问队列中的元素个数

queue

先进先出，queue不提供遍历功能，也没有迭代器。

基本操作：

增删：q.push(int x)将x 接到队列的末端    q.pop()  弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问元素：q.front() 访问队首元素，即最早被压入队列的元素    q.back()访问最后被压入队列的元素

判断：q.empty() 当队列空时，返回true       q.size()访问队列中的元素个数

heap

heap是priority_queue的幕后英雄

操作：make_heap  ,  push_heap,   pop_heap , sort_heap

参数都是：sort_heap  (Iterator first,Iterator second)迭代器

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int a[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
	vector<int> vec(a, a + 9);

	make_heap(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++)
		cout << vec[i] << " ";  // 958340231

	vec.push_back(7);
	push_heap(vec.begin(), vec.end());// 前面已经make_heap过，后面新增用push_heap
	for (int i = 0; i < vec.size(); i++)
		cout << vec[i] << " ";  // 9783502314

	pop_heap(vec.begin(), vec.end());
	cout << vec.back() << endl;// 9 有返回但是没有删除
	vec.pop_back();//删除

	sort_heap(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++)
		cout << vec[i] << " ";  // 012345678
}

priority_queue

底层：最大堆，但是依权值高低自动递减排序。

声明用法：（默认降序）

    //下面两种优先队列的定义是等价的，默认降序
    priority_queue<int> q;
    priority_queue<int,vector<int>,less<int> >;//后面有一个空格
    // 升序
    priority_queue<int,vector<int>,greater<int> >;

基本操作：

增删元素：push(int x),  pop() 

访问元素：top() , 

判断：empty()   size()  

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int a[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
	priority_queue<int> q(a, a + 9);

	while (!q.empty()){
		cout << q.top();// 985433210
		q.pop();
	}
	return 0;
}

 

1、关联式容器

set

在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变*iter=9错误。

声明用法：（默认升序）

    //下面两种优先队列的定义是等价的，默认升序
    set<int> q;
    set<int,vector<int>,less<int> >;//后面有一个空格
    // 降序
    set<int,vector<int>,greater<int> >;

基本操作：

insert()   

pair<iterator,bool> insert(int x);// 返回一个键值对<新插元素迭代器，成功与否>
iterator insert(iteration position, int x);// 返回指向插入元素的迭代器
void insert (Iterator first,Iterator second);// 范围

erase()

void erase(Iteration position);// 删除该迭代器指向位置元素
void erase(Iteration first,Iteration second)// 区间上元素

find(Iterator first,Iterator second, int x), count(int x), lower_bound(int x),upper_bound(int x),

#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int a[5] = { 0,1,2,3,4 };
	set<int> s(a,a+5);

	s.insert(5);// 012345
	s.erase(1);// 02345

	// find函数返回迭代器
	set<int>::iterator cc = s.begin();// 初始化迭代器
	cc=s.find(3);
	if (cc != s.end())
		cout << "2 found" << endl;

	// 企图通过迭代器修改set，不允许
	*cc = 9;//错误

	return 0;
}

map

map和set一样是关联式容器，它们的底层容器都是红黑树，区别就在于map的值不作为键，键和值是分开的。它的特性如下：

map以RBTree作为底层容器
所有元素都是键+值存在
不允许键重复
所有元素是通过键进行自动排序的
map的键是不能修改的，但是其键对应的值是可以修改的
在map中，一个键对应一个值，其中键不允许重复，不允许修改，但是键对应的值是可以修改的，原因可以看上面set中的解释。

#include <map>    
#include <string>   
#include <iostream>   
using namespace std;  
  
int main()    
{   
    map<int, string> mapStudent;   // 构造map 

    mapStudent.insert(pair<int, string>(1, "student_one"));// map的insert，用pair  
    mapStudent.insert(pair<int, string>(2, "student_two"));  
    mapStudent.insert(pair<int, string>(3, "student_three"));  
 
    map<int, string>::iterator iter; // 迭代器 
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
       cout<<iter->first<<' '<<iter->second<<endl;  

    // find函数(关键值key)，返回迭代器。
    iter=mapStudent.find(2)

    // 修改value
    iter->second=9;// 正确，关键值不可以修改。
}  

multiset

multimap

hashtable

STL 容器种类和功能

1. 序列容器
   主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置，元素就会位于什么位置。
2. 排序容器
   包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的，即便是插入元素，元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。
3. 哈希容器
   C++ 11 新加入 4 种关联式容器，分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同，哈希容器中的元素是未排序的，元素的位置由哈希函数确定。

迭代器

迭代器的分类

1. 前向迭代器
   假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。
2. 双向迭代器
   双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）。
3. 随机访问迭代器
   随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
   p+=i：使得 p 往后移动 i 个元素。
   p-=i：使得 p 往前移动 i 个元素。
   p+i：返回 p 后面第 i 个元素的迭代器。
   p-i：返回 p 前面第 i 个元素的迭代器。
   p[i]：返回 p 后面第 i 个元素的引用。
   此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。
   

迭代器的定义

1. 正向迭代器

   容器类名::iterator 迭代器名;

2. 常量正向迭代器

   容器类名::const_iterator 迭代器名;

3. 反向迭代器

   容器类名::reverse_iterator 迭代器名;

4. 常量反向迭代器

   容器类名::const_reverse_iterator 迭代器名;
   示例：

#include<bits/stdc++.h> 
using namespace std;
int main()
{
	//v被初始化成有10个元素
    vector<int> v{1,2,3,4,5,6,7,8,9,10}; 
    cout << "第一种遍历方法：随机访问迭代器支持" << endl;
    //像普通数组一样使用vector容器
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] <<" "; 
    
    cout << endl << "第二种遍历方法：三种迭代器均支持" << endl;
    vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
    
    cout << endl << "第三种遍历方法：随机访问迭代器支持" << endl;
    //用 < 比较两个迭代器
    for (i = v.begin(); i < v.end(); ++i) 
        cout << *i << " ";
   
    cout << endl << "第四种遍历方法：随机访问迭代器支持" << endl;
    i = v.begin();
    //间隔一个输出   // 随机访问迭代器支持 "+= 整数"  的操作
    while (i < v.end()) { 
        cout << *i << " ";
        i += 2; 
    }
}

输出：

序列式容器

• array<T,N>（数组容器）：n个固定元素，随机访问
  表示可以存储 N 个 T 类型的元素，是 C++
  本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
• vector（向量容器）：尾部删除插入，随机访问
  用来存放 T类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
• deque（双端队列容器）：头部尾部删除插入，随机访问
  和 vector非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1)常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
• list（链表容器）：任意位置删除插入，两个方向顺序访问
  是一个长度可变的、由 T类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。
• forward_list（正向链表容器）：任何位置删除插入，正向顺序访问
  和 list容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

vector容器包含的成员函数

• begin() 返回指向容器中第一个元素的迭代器。
• end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
• rbegin() 返回指向最后一个元素的迭代器。
• rend() 返回指向第一个元素所在位置前一个位置的迭代器。
• cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
• size() 返回实际元素个数。
• max_size() 返回元素个数的最大值。这通 常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
• resize() 改变实际元素的个数。
• capacity() 返回当前容量。
• empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
• reserve() 增加容器的容量。
• shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
• operator[ ] 重载了 [ ] 运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改 vector 容器中的元素。
• at() 使用经过边界检查的索引访问元素。
• front() 返回第一个元素的引用。
• back() 返回最后一个元素的引用。
• data() 返回指向容器中第一个元素的指针。
• assign() 用新元素替换原有内容。
• push_back() 在序列的尾部添加一个元素。
• pop_back() 移出序列尾部的元素。
• insert() 在指定的位置插入一个或多个元素。
  insert示例代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    std::vector<int> demo{1,2};
    //第一种格式用法
    demo.insert(demo.begin() + 1, 3);//{1,3,2}

    //第二种格式用法
    demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}

    //第三种格式用法
    std::array<int,3>test{ 7,8,9 };
    demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}

    //第四种格式用法
    demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}

    return 0;
}

• erase() 移出一个元素或一段元素。
• remove() 删除容器中所有和指定元素值相等的元素，并返回指向最后一个元素下一个位置的迭代器。值得一提的是，调用该函数不会改变容器的大小和容量。
• clear() 移出所有的元素，容器大小变为 0。
• swap() 交换两个容器的所有元素。
• emplace() 在指定的位置直接生成一个元素。
• emplace_back() 在序列尾部生成一个元素。

示例：

#include<bits/stdc++.h>
using namespace std;
int main(){
	//	创建int类型vector容器 
	vector<int>v;
	//	获得vector容器容量 
	cout<<v.size()<<endl;
	//	向vector容器尾部插入元素 
	v.push_back(1); 
	v.push_back(2); 
	cout<<v.size()<<endl;
	//增加容器的容量,如果 vector 的容量在执行此语句之前，已经大于或等于 1 个元素
	v.reserve(1);
	cout<<v.size()<<endl;
	v.reserve(10);
	cout<<v.size()<<endl;
	//创建指定容量和元素的vector
	vector<int>va(10,-1);//第一个容量，第二个为值，默认为0 
	//返回元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
	cout<<va.max_size()<<endl; 
	//改变实际元素的个数。
	v.resize(0);
	cout<<v.size()<<endl;
	//返回当前容量。
	cout<<va.capacity()<<endl;
	//判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
	cout<<va.empty()<<endl;
	//将内存减少到等于当前元素实际所使用的大小。
	va.shrink_to_fit();
	cout<<va.size()<<endl;
	//返回第一个元素的引用。
	cout<<va.front()<<endl;
	//返回最后一个元素的引用。
	cout<<va.back()<<endl;
	//返回指向容器中第一个元素的指针。
	cout<<va.data()<<endl;
	//移出序列尾部的元素。
	va.pop_back();
	//在指定的位置插入一个或多个元素。
	va.insert(va.begin()+5,1);
	cout<<va[5]<<endl;
	//用新元素替换原有内容。
	va.assign({1,1,1,1,1,1});
	cout<<va[1]<<endl;
	//移出一个元素或一段元素。
	va.erase(va.begin()+1,va.begin()+3);
	cout<<va.size()<<endl;
	//va.clear()   移出所有的元素，容器大小变为 0。
	//交换两个容器的所有元素。
	swap(v,va);
	cout<<va.size()<<endl;
	return 0;
} 

deque包含的成员函数
deque包含的成员函数和vector基本一致，常用的增加了：

• push_front() 在序列的头部添加一个元素。
• pop_front() 移除容器头部的元素。

list容器可用的成员函数

• empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
• size() 返回当前容器实际包含的元素个数。
• max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
• front() 返回第一个元素的引用。
• back() 返回最后一个元素的引用。
• assign() 用新元素替换容器中原有内容。
• emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。
• push_front() 在容器头部插入一个元素。
• pop_front() 删除容器头部的一个元素。
• emplace_back() 在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同，但效率更高。
• push_back() 在容器尾部插入一个元素。
• pop_back() 删除容器尾部的一个元素。
• emplace() 在容器中的指定位置插入元素。该函数和 insert() 功能相同，但效率更高。
• insert() 在容器中的指定位置插入元素。
• erase() 删除容器中一个或某区域内的元素。
• swap() 交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。
• resize() 调整容器的大小。
• clear() 删除容器存储的所有元素。
• splice() 将一个 list 容器中的元素插入到另一个容器的指定位置。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<double>li1{3.1,2.2,2.9},li2{9.9,10.9};
	//排序 
	li1.sort();
	for (auto it:li1) {
        std::cout << it << " ";
    }
    cout<<endl;
    //指向 li1 容器中的元素 2
    list<double>::iterator it = ++li1.begin();
    //调用第一种语法格式
    li1.splice(it, li2); // li1: 3.1,9.9,10.9,2.2,2.9
                    
    for (auto it:li1) {
        std::cout << it << " ";
    }
    cout<<endl;
    //调用第二种语法格式，将 [li1.begin(),li1.end())范围内的元素移动到 li1.begin() 位置处  
	li2.splice(li2.begin(), li1, li1.begin(), li1.end());
	for (auto it:li2) {
        std::cout << it << " ";
    }
	return 0;
} 

• remove(val) 删除容器中所有等于 val 的元素。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<int>li{1,3,5,2,4,3,5,3,3};
	li.remove(3);
	for (auto it:li) {
        std::cout << it << " ";
    }
	return 0;
} 

• remove_if() 删除容器中满足条件的元素。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<int>li{1,3,5,2,4,3,5,3,3};
	li.remove_if([](int value) {return (value <= 3); }); 
	for (auto it:li) {
        std::cout << it << " ";
    }
	return 0;
} 

• unique() 删除容器中相邻的重复元素，只保留一个。

#include <iostream>
#include <list>
using namespace std;
//二元谓词函数
bool demo(double first, double second)
{
    return (int(first) == int(second));
}

int main()
{
    list<double> mylist{ 1,1.2,1.2,3,4,4.5,4.6 };
    //删除相邻重复的元素，仅保留一份
    mylist.unique();//{1, 1.2, 3, 4, 4.5, 4.6}

    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        cout << *it << ' ';
    cout << endl;
    //demo 为二元谓词函数，是我们自定义的去重规则
    mylist.unique(demo);

    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}

• merge() 合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。

#include<bits/stdc++.h>
using namespace std;
int main(){
	list<int>li{1,3,5,2,4,3,5,3,3},l2{9,8,1,5};
	li.merge(l2); 
	for (auto it:li) {
        std::cout << it << " ";
    }
	return 0;
} 

• sort() 通过更改容器中元素的位置，将它们进行排序。
• reverse() 反转容器中元素的顺序。