Blog

C++ STL容器用法

Posted on Edited on In

顺序容器

vector

类模板声明：

template < class T, class Alloc = allocator<T> > class vector;

vector是一个封装了动态大小数组的顺序容器（sequence container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

容性特性

顺序序列
    顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。   
动态数组    
   支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作。 
能够感知内存分配器的（Allocator-aware） 
   容器使用一个内存分配器对象来动态地处理它的存储需求。

模板参数

T

存储在容器中的元素的数据类型。

必须保证在执行移动操作时不会抛出异常，因为在重分配时，实现者（标准库内部）可以进行优化使仅仅移动元素而不是拷贝所有。

在类模板内部，使用其别名为 value_type 的成员类型。

Alloc

容器内部用来管理内存分配及释放的内存分配器的类型。

这个参数是可选的，它的默认值是 std::allocator<T>，这个是一个最简单的非值依赖的（Value-independent）内存分配器。在类模板内部，使用其别名为 allocator_type 的成员类型。

详细说明

在向量中，所有元素都是连续存储的。也就是说，不仅可以通过迭代器（Iterators）访问各个元素，也可以通过指向元素的指针加上偏移来访问。还意味着，当向任意函数传递向量的一个元素的指针时，这个指针可以直接被认为指向了一个数组中的某个元素。

向量内部的存储调整是自动处理的，按需扩展或压缩。通常，相比静态数组（Static arrays），向量将会占用更多的存储空间，因为额外的内存将被未来增长的部分所使用。就因为这点，当插入元素时，向量不需要太频繁地重分配（Reallocate）内存。当前最大容量可以通过函数 capacity() 查询。额外的内存可以通过调用 shrink_to_fit() 函数返还给操作系统。

当增加向量对象中的序列的长度时，如果超出当前存储容量上限，就会发生内存重分配（Reallocation），即内部将会重新分配一个数组，然后按顺序逐个拷贝元素。其它的插入及删除操作将会修改序列中部分元素的内存地址。在上述所有情况下，指向序列中被修改部分的迭代器或引用将会失效。当未发生内存重分配，仅指向插入或删除点之前元素的迭代器或引用才会保持有效性。

标准库可以执行不同的增长策略来平衡内存的使用量与重分配所耗的性能。但不管哪种情况下，重分配内存的大小必须以指数方式增长，只有这样，才能将在向量末尾逐个插入元素所需的时间复杂度整体分摊（Amortized）为一个恒定值。

内存重分配就性能而言是一个高代价操作。如果在使用向量前知道元素的数量，可以通过 reserve() 消除内存重分配。

向量支持在序列末尾恒定耗时的插入及删除元素。而在向量的中间插入或删除元素则需要线性的时间。在只涉及向序列起始或未尾插入及删除元素操作时，std::deque​ 容器的性能将会高出很多。当涉及向序列中的任意位置进行插入及删除操作时，std::list 容器的性能将会高出很多。

常用操作的算法复杂度（性能相关）如下：

  • 随机访问，时间复杂度为 O(1)
  • 在未尾插入或删除元素，整体分摊的时间复杂度为 O(1)
  • 其它位置插入或删除元素，与当前位置至向量末尾的距离有关，时间复杂度 O(n)​​

成员类型

成员类型 定义
value_type 第一个模板参数 T
allocator_type 第二个模板参数 Alloc
size_type 无符号整数类型（通常为 size_t）
difference_type 有符号整数类型（通常为 ptrdiff_t）
reference Allocator::reference 已弃用
value_type& (C++11)
const_reference Allocator::const_reference 已弃用
const value_type&(C++11)
pointer Allocator::pointer 已弃用
std::allocator_traits<Allocator>::pointer (C++11)
const_pointer Allocator::const_pointer 已弃用
std::allocator_traits<Allocator>::const_pointer(C++11)
iterator 随机访问迭代器
const_iterator 常量随机访问迭代器
reverse_iterator std::reverse_iterator<iterator>
const_reverse_iterator std::reverse_iterator<const_iterator>

成员函数

(constructor) 创建 vector
(destructor) 释放 vector
operator= 值赋操作

Iterators

begin 返回指向容器起始位置的迭代器（iterator）
end 返回指向容器末尾位置的迭代器
rbegin 返回指向容器逆序起始位置的逆序迭代器（reverse_iterator）
rend 返回指向容器逆序末尾位置的逆序迭代器
cbegin(C++11) 返回指向容器起始位置的常迭代器（const_iterator）
cend(C++11) 返回指向容器末尾位置的常迭代器
crbegin(C++11) 返回指向容器逆序起始位置的常逆序迭代器（const_reverse_iterator）
crend(C++11) 返回指向容器逆序末尾位置的常逆序迭代器

Capacity

size 返回有效元素个数
max_size 返回 vector 支持的最大元素个数
resize 改变有效元素的个数
capacity 返回当前可使用的最大元素内存块数（即存储容量）
empty 判断是否为空
reserve 请求改变存储容量
shrink_to_fit(C++11) 请求移除未使用的存储空间

Element access

operator[] 访问元素
at 访问元素
front 访问第一个元素
back 访问最后一个元素
data(C++11) 返回当前向量内部数组的指针

Modifiers

assign 将新的内容赋值给容器
push_back 在末尾增加一个元素
pop_back 删除最后一个元素
insert 插入元素
erase 删除元素
swap 交换内容
clear 清空内容
emplace(C++11) 构造及插入一个元素
emplace_back(C++11) 在容器末尾构造及插入一个元素

Allocator

get_allocator 获得内存分配器

非成员函数

operator==、operator!=、operator<、operator<=、operator>、operator>= 

关系操作符
std::swap 交换两个向量的内容

list

类模板声明：

template < class T, class Alloc = allocator<T> > class list;

列表（list）是一个允许在序列中任何一处位置以常量耗时插入或删除元素且可以双向迭代的顺序容器（Sequence container）。

容性特性：

顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

双向链表

容器中的每个元素保存了定位前一个元素及后一个元素的信息，允许在任何一处位置以常量耗时进行插入或删除操作，但不能进行直接随机访问（Direct random access）。

能够感知内存分配器的（Allocator-aware）

容器使用一个内存分配器对象来动态地处理它的存储需求。

模板参数

T

存储在容器中的元素的数据类型。

在类模板内部，使用其别名为 value_type 的成员类型。

Alloc

容器内部用来管理内存分配及释放的内存分配器的类型。

这个参数是可选的，它的默认值是 std::allocator<T>，这个是一个最简单的非值依赖的（Value-independent）内存分配器。 在类模板内部，使用其别名为 allocator_type 的成员类型。

详细说明

标准模板库（Standard Template Library，简称STL）中的列表容器采用的是双向链表（Doubly-linked lists）数据结构。双向链表可以保存以不同且无关的储存位置容纳的元素。元素间的顺序是通过各个元素中指向前一个元素的链接及指向后一个元素的链接等联系维护的。

该特点跟 std:: forward_list 容器的有点相似：主要的区别就是 std:: forward_list 是一个单向链表，因此它只能被正向迭代（ Iterated forward），以换取更小更高效的特点。

增加或移动列表中的元素不会使指向它们的指针、引用、迭代器失效，只有当对应的元素被销毁时才会如此。

你可能会好奇，为什么STL同时提供列表（std::list）跟向量（std::vector）及其它等多种容器，原因是它们的底层实现方式是不一样的，每一种实现方式都有各自的消耗（空间或时间）及优点。

相比较于其它的基本标准顺序容器（数组 std::array、向量 std::vector、双端队列 std::deque 等），列表通常在容器中已获得迭代器的任意位置处插入、获得（Extracting，提取）、移动元素等操作中表现出更出色的性能，对那些密集使用上述操作的算法，使用列表同样能提升性能，比如排序算法。

双向链表（std::list）及正向链表（std:: forward_list(C++11) ）相比于其它顺序容器的主要缺点是它们不能够通过元素在容器中的位置直接访问（Direct access）元素。举个例子：如果想访问一个列表中的第六个元素，那么就必须从一个已知位置（比如开头或末尾）处开始迭代，这会消耗与两个位置之间距间相关的线性时间。而且它们还为保存各个元素间的链接信息消耗更多额外的内存（这点对由小尺寸元素组成的大列表尤为明显）。

成员类型

成员类型 定义
value_type 第一个模板参数 T
allocator_type 第二个模板参数 Alloc
size_type 无符号整数类型（通常为 size_t）
difference_type 有符号整数类型（通常为 ptrdiff_t）
reference Allocator::reference(已弃用) 
value_type&amp(C++11);
const_reference Allocator::const_reference(已弃用) 
const value_type&amp(C++11); 
pointer Allocator::pointer(已弃用) 
std::allocator_traits(C++11)<Allocator>::pointer 
const_pointer Allocator::const_pointer(已弃用) 
std::allocator_traits(C++11)<Allocator>::const_pointer 
iterator 双向迭代器
const_iterator 常双向迭代器
reverse_iterator std::reverse_iterator<iterator>
const_reverse_iterator std::reverse_iterator<const_iterator>

成员函数

(constructor) 创建 list
(destructor) 释放 list
operator= 值赋操作

Iterators:

begin 返回指向容器起始位置的迭代器（iterator）
end 返回指向容器末尾位置的迭代器
rbegin 返回指向容器逆序起始位置的逆序迭代器（reverse_iterator）
rend 返回指向容器逆序末尾位置的逆序迭代器
cbegin(C++11) 返回指向容器起始位置的常迭代器（const_iterator）
cend(C++11) 返回指向容器末尾位置的常迭代器
crbegin(C++11) 返回指向容器逆序起始位置的常逆序迭代器（const_reverse_iterator）
crend(C++11) 返回指向容器逆序末尾位置的常逆序迭代器

Capacity:

empty 判断是否为空
size 返回有效元素个数
max_size 返回 list 支持的最大元素个数

Element access:

front 访问第一个元素
back 访问最后一个元素

Modifiers：

assign 将新的内容赋值给容器
emplace_front(C++11)  在容器开头构造及插入一个元素
push_front 在容器开头插入一个元素
pop_front 删除第一个元素
emplace_back(C++11) 在容器末尾构造及插入一个元素
push_back 在末尾增加一个元素
pop_back 删除最后一个元素
emplace(C++11)  构造及插入一个元素
insert 插入元素
erase 删除元素
swap 交换内容
resize 改变有效元素的个数
clear 清空内容

Operations:

splice 使元素从一个列表移动到另一个列表
remove 删除值为指定值的元素
remove_if 删除满足指定条件的元素
unique 删除重复值
merge 合并已排序的列表
sort 为容器中的所有元素排序
reverse 反转元素的顺序

Observers：

get_allocator 获得内存分配器

非成员函数

operator==、operator!=、operator<、operator<=、operator>、operator>= 关系操作符
std::swap 交换两个列表的内容

deque

类模板声明：

template < class T, class Alloc = allocator<T> > class deque;

双端队列（Double-ended queue，缩写为deque）是一个大小可以动态变化（Dynamic size）且可以在两端扩展或收缩的顺序容器。

容性特性：

顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

动态数组

通常采用动态数组这一数据结构。支持对序列中的任意元素进行快速直接访问。操供了在序列末尾相对快速地添加/删除元素的操作。

能够感知内存分配器的（Allocator-aware）

容器使用一个内存分配器对象来动态地处理它的存储需求。

模板参数

T

存储在容器中的元素的数据类型。

在类模板内部，使用其别名为 value_type 的成员类型。

Alloc

容器内部用来管理内存分配及释放的内存分配器的类型。

这个参数是可选的，它的默认值是 std::allocator<T>，这个是一个最简单的非值依赖的（Value-independent）内存分配器。在类模板内部，使用其别名为 allocator_type 的成员类型。

详细说明

不同的库可能会按不同的方式来实现双端队列，通常实现为某种形式的动态数组。但不管通过哪种方式，双端队列都允许通过随机迭代器直接访问各个元素，且内部的存储空间会按需求自动地扩展或收缩。

容器实际分配的内存数超过容纳当前所有有效元素所需的，因为额外的内存将被未来增长的部分所使用。就因为这点，当插入元素时，容器不需要太频繁地分配内存。

因此，双端队列提供了类似向量（std::vector）的功能，且不仅可以在容器末尾，还可以在容器开头高效地插入或删除元素。

但是，相比向量，双端队列不保证内部的元素是按连续的存储空间存储的，因此，不允许对指针直接做偏移操作来直接访问元素。

在内部，双端队列与向量的工作方式完全不同：向量使用单数组数据结构，在元素增加的过程中，需要偶尔的内存重分配，而双端队列中的元素被零散地保存在不同的存储块中，容器内部会保存一些必要的数据使得可以以恒定时间及一个统一的顺序接口直接访问任意元素。因此，双端队列的内部实现比向量的稍稍复杂一点，但这也使得它在一些特定环境下可以更高效地增长，特别是对于非常长的序列，内存重分配的代价是及其高昂的。

对于大量涉及在除了起始或末尾以外的其它任意位置插入或删除元素的操作，相比列表（std::list）及正向列表（std::forward_list），deque 所表现出的性能是极差的，且操作前后的迭代器、引用的一致性较低。

成员类型

成员类型 定义
value_type 第一个模板参数 T
allocator_type 第二个模板参数 Alloc
size_type 无符号整数类型（通常为 <a">size_t）
difference_type 有符号整数类型（通常为 ptrdiff_t）
reference Allocator::reference(已弃用) 
value_type&amp(C++11);
const_reference Allocator::const_reference(已弃用) 
const value_type(C++11)& 
pointer Allocator::pointer(已弃用)
std::allocator_traits(C++11)<Allocator>::pointer 
const_pointer Allocator::const_pointer(已弃用)
std::allocator_traits(C++11)<Allocator>::const_pointer 
iterator 随机访问迭代器
const_iterator 常量随机访问迭代器
reverse_iterator std::reverse_iterator<iterator>
const_reverse_iterator std::reverse_iterator<const_iterator>

成员函数

(constructor) 创建 deque
(destructor) 释放 deque
operator= 值赋操作

​Iterators:

begin 返回指向容器起始位置的迭代器（iterator）
end 返回指向容器末尾位置的迭代器
rbegin 返回指向容器逆序起始位置的逆序迭代器（reverse_iterator）
rend 返回指向容器逆序末尾位置的逆序迭代器
cbegin(C++11) 返回指向容器起始位置的常迭代器（const_iterator）
cend(C++11) 返回指向容器末尾位置的常迭代器
crbegin(C++11) 返回指向容器逆序起始位置的常逆序迭代器（const_reverse_iterator）
crend(C++11) 返回指向容器逆序末尾位置的常逆序迭代器

Capacity:

size 返回有效元素个数
max_size 返回 deque 支持的最大元素个数
resize 改变有效元素的个数
empty 判断是否为空
shrink_to_fit(C++11) 请求移除未使用的存储空间

Element access:

operator[] 访问元素
at 访问元素
front 访问第一个元素
back 访问最后一个元素

Modifiers:

assign 将新的内容赋值给容器
push_back 在末尾增加一个元素
push_front 在开头增加一个元素
pop_back 删除最后一个元素
pop_front 删除第一个元素
insert 插入元素
erase 删除元素
swap 交换内容
clear 清空内容
emplace(C++11) 构造及插入一个元素
emplace_front(C++11) 在容器开头构造及插入一个元素
emplace_back(C++11) 在容器末尾构造及插入一个元素

Allocator:

get_allocator 获得内存分配器

非成员函数

operator==、operator!=、operator<、operator<=、operator>、operator>= 

关系操作符
std::swap 交换两个双端队列的内容

算法相关

<algorithm&gt头文件中包含大量与 deque 相关的算法，常使用的有：

搜索算法 std::adjacent_find、std::count、
std::count_if、std::find、
std::find_if、std::find_end、
std::find_first_of、std::search、
std::search_n、std::equal、
std::mismatch
分类排序 std::sort、std::partial_sort、
std::stable_sort、
二分查找（Binary search） std::lower_bound、std::upper_bound、
std::equal_range、std::binary_search
集合（Set）操作 std::includes、std::set_difference、
std::set_intersection、std::set_union、
std::set_symmetric_difference
堆（Heap）操作 std::make_heap、std::push_heap、
std::pop_heap、std::sort_heap
最大与最小 std::min_element、std::max_element
字典序比较 std::lexicographical_compare
排列生成器 std::next_permutation、
std::prev_permutation
第n个元素 std::nth_element
其它操作 std::all_of、std::any_of、std::none_of、
std::for_each、std::copy、std::copy_if、
std::copy_n、std::copy_backward、
​std::move、std::move_backward、
std::swap_ranges、std::iter_swap、
std::transform、std::replace、
​std::replace_if、std::replace_copy、
std::replace_copy_if、std::fill、
std::fill_n、std::generate、
std::generate_n、std::remove、
std::remove_if、std::unique、
std::unique_copy、std::reverse、
​std::reverse_copy、std::rotate、
std::rotate_copy、std::random_shuffle、
std::shuffle、std::partition、
std::is_partitioned、std::stable_partition、
​std::partition_copy、std::merge

array

类模板声明：

template < class T, size_t N > class array;

数组（array）是一个固定大小（Fixed-size）的顺序容器（Sequence container）。容器容纳了具体（Specific）数目的元素，这些元素逐个排列在一个严格的线性序列中。

容性特性：

顺序序列（Sequence）

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

连续存储空间（Contiguous storage）

所有元素存储在一个连续的内存位置处，使得可以以常量时间随机访问元素。指向元素的指针可以通过偏移访问其它元素。

固定大小的聚集体（Fixed-size aggregate）

容器使用隐式（Implicit）构造函数（Constructor）及析构函数（Destructor）来静态地分配所需的存储空间。它的大小是一个编译时（Compile-time）确定的常量。除了自身所需外，不会消耗额外的内存或时间。

模板参数

T

容器所包含的元素的类型。

在类模板内部，使用其别名为 value_type 的成员类型。

N

数组的大小，以元素的个数为单位。

详细说明

在 array 容器内部，不会保存除了元素的任意其它数据（甚至没保存容器的大小，这个是一个模板参数，在编译时就已固定）。该容器同由言语中的括号语义（[]）定义的普通数组一样高效。array 仅仅是为普通数组添加了一些成员或全局函数，这使得数组能够被当成标准容器来使用。

区别于其它标准容器，array 拥有一个固定的大小，且不需要通过内存分配器（Allocator）管理元素的储存空间。它是一个封装了固定数量元素的数组的聚合类型（Aggregate）。因此，array 不能被动态地扩展或压缩。

大小为 0 的 array 容器是允许的，但是这样的数组里的元素是不能被解引用的（Dereferenced）（因为没有元素可以被解引用，相关成员函数有 front、back、及 data）。

区别于其它标准容器，交换（Swap）两个 array 容器是一个线性操作（即时间复杂度为 O(n)），涉及分别交换范围内的所有元素，这通常被认为是一个低效的操作。

array 容器唯一具有的另一个特征是：可以把 array 容器当成一个多元组（Tuple）对象。在头文件 <array> 中，通过重载全局函数 get 使得通过 get 访问 array 中的元素时，array 容器就像一个多元组。

成员类型

成员类型 定义
value_type 第一个模板参数 T
size_type 第二个模板参数 N，无符号整数类型（通常为 size_t）
difference_type 有符号整数类型（通常为 ptrdiff_t）
reference value_type&
const_reference const value_type&
pointer T*
const_pointer const T*
iterator 随机访问迭代器
const_iterator 常量随机访问迭代器
reverse_iterator std::reverse_iterator<iterator>
const_reverse_iterator std::reverse_iterator<const_iterator>

成员函数

迭代器（​Iterators）

begin 返回指向容器起始位置的迭代器（iterator）
end 返回指向容器末尾位置的迭代器
rbegin 返回指向容器逆序起始位置的逆序迭代器（reverse_iterator）
rend 返回指向容器逆序末尾位置的逆序迭代器
cbegin 返回指向容器起始位置的常迭代器（const_iterator）
cend 返回指向容器末尾位置的常迭代器
crbegin 返回指向容器逆序起始位置的常逆序迭代器（const_reverse_iterator）
crend 返回指向容器逆序末尾位置的常逆序迭代器

容量（Capacity）

size 返回有效元素个数
max_size 返回 array 支持的最大元素个数
empty 检测 array 是否为空

元素访问（Element access）

operator[] 访问元素
at 访问元素
front 访问第一个元素
back 访问最后一个元素
data 返回 array 内部数组的指针

修改器（Modifiers）

fill 用新的值填充容器
swap 交换内容

非成员函数

operator==、operator!=、operator<、operator<=、operator>、operator>= 

关系操作符
std::swap 交换两个数组的内容

特例化

tuple_element<array> 基于 array 的多元组（Tuple）中的元素类型
tuple_size<array> 基于 array 的多元组的大小

算法相关

<algorithm>头文件中包含大量与 array 相关的算法，常使用的有

搜索算法 std::adjacent_find、std::count、
std::count_if、std::find、
std::find_if、std::find_end、
std::find_first_of、std::search、
std::search_n、std::equal、
std::mismatch
分类排序 std::sort、std::partial_sort、
std::stable_sort、
二分查找（Binary search） std::lower_bound、std::upper_bound、
std::equal_range、std::binary_search
集合（Set）操作 std::includes、std::set_difference、
std::set_intersection、std::set_union、
std::set_symmetric_difference
堆（Heap）操作 std::make_heap、std::push_heap、
std::pop_heap、std::sort_heap
最大与最小 std::min_element、std::max_element
字典序比较 std::lexicographical_compare
排列生成器 std::next_permutation、
std::prev_permutation
第 n 个元素 std::nth_element
其它操作 std::all_of、std::any_of、std::none_of、
std::for_each、std::copy、std::copy_if、
std::copy_n、std::copy_backward、
​std::move、std::move_backward、
std::swap_ranges、std::iter_swap、
std::transform、std::replace、
​std::replace_if、std::replace_copy、
std::replace_copy_if、std::fill、
std::fill_n、std::generate、
std::generate_n、std::remove、
std::remove_if、std::unique、
std::unique_copy、std::reverse、
​std::reverse_copy、std::rotate、
std::rotate_copy、std::random_shuffle、
std::shuffle、std::partition、
std::is_partitioned、std::stable_partition、
​std::partition_copy、std::merge

forward_list

类模板声明：

template < class T, class Container = deque<T> > class queue;

正向列表（Forward list）是一个允许在序列中任何一处位置以常量耗时插入或删除元素的顺序容器（Sequence container）。

容性特性：

顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

单链表

容器中的每个元素保存了定位前一个元素及后一个元素的信息，允许在任何一处位置以常量耗时进行插入或删除操作，但不能进行直接随机访问（Direct random access）。

能够感知内存分配器的（Allocator-aware）

容器使用一个内存分配器对象来动态地处理它的存储需求。

模板参数

T

存储在容器中的元素的数据类型。

在类模板内部，使用其别名为 value_type 的成员类型。

Alloc

容器内部用来管理内存分配及释放的内存分配器的类型。

这个参数是可选的，它的默认值是 std::allocator<T>，这个是一个最简单的非值依赖的（Value-independent）内存分配器。 在类模板内部，使用其别名为 allocator_type 的成员类型。

详细说明

标准模板库（Standard Template Library，简称STL）中的正向列表容器采用的是单链表（Singly-linked lists）数据库构。单链表可以保存以不同且无关的储存位置容纳的元素。元素间的顺序是通过各个元素中指向下一个元素的链接这一联系维护的。

该特点跟 std:: list 容器的有点相似：主要的区别就是 std:: list 的元素中不仅保存了指向下一个元素的链接，还保存了指向上一个元素的链接，这使得 std::list 允许双向迭代，但消耗更多的存储空间且在插入删除元素时会有稍高（Slight higher）的耗时。因此 std::forward_list 对象比 std::list 对象更高效，尽管它们只能正向迭代。

增加或移动正向列表中的元素不会使指向它们的指针、引用、迭代器失效，只有当对应的元素被销毁时才会如此。

相比较于其它的基本标准顺序容器（数组 std::array、向量 std::vector、双端队列 std::deque 等），正向列表通常在容器中已获得迭代器的任意位置处插入、获得（Extracting，提取）、移动元素等操作中表现出更出色的性能，对那些密集使用上述操作的算法，使用正向列表同样能提升性能，比如排序算法。

双向链表（std::list）及正向链表（std:: forward_list）相比于其它顺序容器的主要缺点是它们不能够通过元素在容器中的位置直接访问（Direct access）元素。举个例子：如果想访问一个正向列表中的第六个元素，那么就必须从一个已知位置（比如开头或末尾）处开始迭代，这会消耗与两个位置之间距间相关的线性时间。而且它们还为保存各个元素间的链接信息消耗更多额外的内存（这点对由小尺寸元素组成而元素数较大的正向列表尤为明显）。

forward_list 类模板是专为极度考虑性能的程序而设计的，它就跟自实现的C型单链表（C-style singly-linked list）一样高效。甚至为了性能，它是唯一一个缺少 size 成员函数的标准容器：这是出于其单链表的性质，如果拥有 size 成员函数，就必须消耗常量时间来维护一个用于保存当前容器大小的内部计数器，这会消耗更多的存储空间，且使得插入及删除操作略微降低性能。如果想获得 forward_list 的大小，可以使用 std::distance 算法且传递 forward_list::begin 及 forward_list::end 参数，该操作的时间复杂度为 O(n)。

对任意列表（std::list）进行插入或删除元素操作需要访问插入位置前的元素，但对 forward_list 来说访问该元素没有常数时间（Constant-time）的方法。因为这个原因，对传递给清除（Erase）、拼接（Splice）等成员函数的范围参数作了修改，这些范围必须为开区间（即不包括末尾元素的同时也不包括起始元素）。

成员类型

成员类型 定义
value_type 第一个模板参数 T
allocator_type 第二个模板参数 Alloc
size_type 无符号整数类型（通常为 size_t）
difference_type 有符号整数类型（通常为 ptrdiff_t）
reference value_type&
const_reference const value_type&
pointer std::allocator_traits<Allocator>::pointer
const_pointer std::allocator_traits<Allocator>::const_pointer
iterator 正向迭代器
const_iterator 常正向迭代器

成员函数

(constructor) 创建 forward_list
(destructor) 释放 forward_list​
operator= 值赋操作

Iterators:

before_begin 返回指向容器起始位置前的迭代器（iterator）
begin 返回指向容器起始位置的迭代器
end 返回指向容器末尾位置的迭代器
cbefore_begin 返回指向容器起始位置前的常迭代器（const_iterator）
cbegin 返回指向容器起始位置的常迭代器
cend 返回指向容器末尾位置的常迭代器

Capacity:

empty 判断是否为空
max_size 返回 forward_list 支持的最大元素个数

Element access:

front 访问第一个元素

Modifiers：

assign 将新的内容赋值给容器
emplace_front  在容器开头构造及插入一个元素
<apush_front 在容器开头插入一个元素
pop_front 删除第一个元素
emplace_after 构造及插入一个元素
insert_after 插入元素
erase_after 删除元素
swap 交换内容
resize 改变有效元素的个数
clear 清空内容

Operations:

splice_after 使元素从一个正向列表移动到另一个正向列表
remove 删除值为指定值的元素
remove_if 删除满足指定条件的元素
unique 删除重复值
merge 合并已排序的正向列表
sort 为容器中的所有元素排序
reverse 反转元素的顺序

Observers：

get_allocator 获得内存分配器

非成员函数

operator==、operator!=、operator<、operator<=、operator>、operator>= 关系操作符
std::swap 交换两个正向列表的内容

容器适配器

stack

类模板声明：

template < class T, class Container = deque<T> > class stack;

栈（stack）是一个容器适配器（Container adaptor）类型，被特别设计用来运行于LIFO（Last-in first-out）场景，在该场景中，只能从容器末尾添加（Insert）或提取（Extract）元素。

模板参数

T

容器所包含的元素的类型。

在类模板内部，使用其别名为 value_type 的成员类型。

Container

底层的用于存储元素的容器的类型。

详细说明

stack 通常被实现为容器适配器，即使用一个特定容器类的封装对象作为它的底层容器。stack 提供了一系列成员函数用于操作它的元素，只能从容器“后面”压进（Push）元素或从容器“后面”提取（Pop）元素。容器中的“后面”位置也被称为“栈顶”。

用来实现栈的底层容器必须满足顺序容器的所有必要条件。同时，它还必须提供以下语义的成员函数：

  • back()
  • push_back()​
  • pop_back()

满足上述条件的标准容器有 std::vector、std::deque 及 std::list，如果未特别指定 stack 的底层容器，标准容器 std::deque 将被使用。

成员类型

成员类型 定义
value_type 第一个模板参数 T
container_type 第二个模板参数 Container
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference

成员函数

(constructor) 创建 stack
(destructor) 释放 stack
operator= 赋值操作

Element access:

top 访问顶部元素

Capacity:

empty 判断是否为空
size 返回有效元素个数

Modifiers:

push 在容器顶部插入元素
pop 移除容器顶部的元素
emplace(C++11) 在容器顶部放置插入元素
swap 交换容器的内容

非成员函数

operator==、operator!=、operator<、operator<=、operator>、operator>= 

关系操作符
std::swap 交换两个栈的内容

queue

类模板声明：

template < class T, class Container = deque<T> > class queue;

队列（queue）是一个容器适配器（Container adaptor）类型，被特别设计用来运行于FIFO（First-in first-out）场景，在该场景中，只能从容器一端添加（Insert）元素，而在另一端提取（Extract）元素。

模板参数

T

容器所包含的元素的类型。

在类模板内部，使用其别名为 value_type 的成员类型。

Container

底层的用于存储元素的容器的类型。

详细说明

queue 通常被实现为容器适配器，即使用一个特定容器类的封装对象作为它的底层容器。queue 提供了一系列成员函数用于操作它的元素，只能从容器“后面”压进（Push）元素,从容器“前面”提取（Pop）元素。

用来实现队列的底层容器必须满足顺序容器的所有必要条件。同时，它还必须提供以下语义的成员函数：

  • front()
  • back()
  • push_back()​
  • pop_front()

满足上述条件的标准容器有 std::deque 及 std::list，如果未特别指定 queue 的底层容器，标准容器 std::deque 将被使用。

成员类型

成员类型 定义
value_type 第一个模板参数 T
container_type 第二个模板参数 Container
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference

成员函数

(constructor) 创建 queue
(destructor) 释放 queue
operator= 赋值操作

Element access:

front 访问第一个元素
back 访问最后一个元素

Capacity:

empty 判断是否为空
size 返回有效元素个数

Modifiers:

push 在容器顶部插入元素
pop 移除容器顶部的元素
emplace(C++11) 在容器顶部放置插入元素
swap 交换容器的内容

非成员函数

operator==、operator!=、operator<、operator<=、operator>、operator>= 

关系操作符
std::swap 交换两个队列的内容

priority_queue

类模板声明：

template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;

优先级队列（priority queue）是一个容器适配器（Container adaptor）类型，被特别设计使其第一个元素总是容器所包含的元素中按特定的严格弱序排序规则排序后最大的一个。

模板参数

T

容器所包含的元素的类型。

在类模板内部，使用其别名为 value_type 的成员类型。

Container

底层的用于存储元素的容器的类型。

Compare

一个二元谓词，以两个元素为参数返回一个 bool 值。

可以是函数指针（Function pointer）类型或函数对象（Function object）类型。

详细说明

priority_queue的定义使得它类似一个堆（Heap），该堆只能获得它的最大堆元素（在 priority_queue 中即为队列头）。

priority_queue 通常被实现为容器适配器，即使用一个特定容器类的封装对象作为它的底层容器。priority_queue 提供了一系列成员函数用于操作它的元素，只能从容器“后面”提取（Pop）元素，该元素也可认为是 priority_queue 的“顶部（Top）”。

用来实现优先级队列的底层容器必须满足顺序容器的所有必要条件。同时，它还必须提供以下语义的成员函数：

  • front()
  • push_back()​
  • pop_back()

为了使内部始终保持堆结构，底层容器必须支持随机访问迭代器。这样，容器适配器内部就可以在适当的时候自动调用算法函数 std::make_heap、std::push_heap、std::pop_heap。

满足上述条件的标准容器有 std::vector 及 std::deque，如果未特别指定 priority_queue 的底层容器，标准容器 std::vector 将被使用。

成员类型

成员类型 定义
value_type 第一个模板参数 T
container_type 第二个模板参数 Container
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference

成员函数

(constructor) 创建 priority_queue
(destructor) 释放 priority_queue
operator= 赋值操作

Element access:

top 访问顶部元素

Capacity:

empty 判断是否为空
size 返回有效元素个数

Modifiers:

push 在容器顶部插入元素
pop 移除容器顶部的元素
emplace(C++11) 在容器顶部放置插入元素
swap 交换容器的内容

非成员函数

std::swap 交换两个优先级队列的内容

关联容器

set

multiset

map

multimap

无序关联容器

unordered_set

unordered_multiset

unordered_map

unordered_multimap