C++ STL汇总

学习《C语言中文网STL教程》笔记

STL由六大组件组成：

1. 容器
2. 算法
3. 迭代器
4. 函数对象
5. 适配器
6. 内存分配器

STL头文件：

序列式容器

array

C++11标准中新增的序列容器，在C++普通数组的基础上，添加了一些成员函数和全局函数。在使用上比普通数组更安全。可以修改array中元素的值，但不能向array中插入和删除元素。

头文件及命名空间

#include<array>

using namespce std;

//array容器类模板定义
namespace std{
    template <typename T, size_t N>
    class array;
}
1
2
3
4
5
6
7
8
9

创建容器

array<double,10> values;

array<double,10> values {};

array<double,10> values {0.1,0.2,0.3};
1
2
3
4
5

增加及修改元素

fill(val)
swap()
1
2

获取元素

begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
at(n)      //返回容器中 n 位置处元素的引用，该函数自动检查 n 是否在有效的范围内，如果不是则抛出 out_of_range 异常。
front()    //返回容器中第一个元素的直接引用，该函数不适用于空的 array 容器。
back()     //返回容器中最后一个元素的直接应用，该函数同样不适用于空的 array 容器。
data()    //返回一个指向容器首个元素的指针。利用该指针，可实现复制容器中所有元素等类似功能。
1
2
3
4
5
6
7
8
9
10
11
12

其它

size()     //返回容器中当前元素的数量，其值始终等于初始化 array 类的第二个模板参数 N。
max_size() //返回容器可容纳元素的最大数量，其值始终等于初始化 array 类的第二个模板参数 N。
empty()    //判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快。
1
2
3

vector

动态数组，即动态调整所占用的空间。

头文件及命名空间

#include<vector>

using namespace std;
1
2
3

创建vector容器

//直接执行类型创建vector，此时是一个空的vector，没有为其分配内存空间，当添加第一个元素时，vector会自动分配内存空间
vector<double> values;

//创建vector时除了指定元素类型外，可以指定初始值以及元素的个数
vector<int> values {2,3,4,5,6,7,8};
vector<double> values(20);
vector<double> values(20,1.0);

//通过类型相同的其他vector来创建vector
vector<double> va(values);
1
2
3
4
5
6
7
8
9
10

增加及修改元素

operator[]      //重载了[]运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改vector容器中的元素
push_back()     //在序列的尾部添加一个元素
insert()        //在指定的位置插入一个或多个元素
emplace()       //在指定的位置直接生成一个元素
emplace_back()  //在序列尾部生成一个元素
assign()        //用新元素替换原有内容
swap()          //交换两个容器的所有元素
1
2
3
4
5
6
7

删除元素

pop_back  //移出序列尾部的元素
erase()   //移出一个或一段元素
clear()   //移出所有的元素，容器大小为0
1
2
3

获取元素

operator[] //重载了[]运算符，可以通过小标访问容器中的元素
at()       //通过索引号访问元素
front()    //返回第一个元素的引用
back()     //返回最后一个元素的引用
data()     //返回指向容器中的第一个元素的指针
begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
1
2
3
4
5
6
7
8
9
10
11
12
13

其它

size()           //返回容器实际元素个数
max_size()       //返回元素个数的最大值
resize()         //改变实际元素的个数
capacity()       //返回当前容量
empty()          //判断容器是否有元素，无元素返回true，有元素，返回false
reserve()        //增加容器的容量
shrink_to_fit()  //将内存减少到等于当前元素实际所使用的大小
1
2
3
4
5
6
7

list

双向链表容器，即底层以双向链表的形式实现的

头文件及命名空间

#include<list>

using namespace std;
1
2
3

创建list容器

list<int> values;        //空的list容器
list<int> values(10);    //包含10个元素的list容器
list<int> values(10,5);  //包含10个元素，每个元素的初始值为5

//通过拷贝已有list容器内容创建新的list容器
list<int> value1(10);
list<int> value2(value1);

//拷贝其它类型的容器中指定区域内的元素，创建新的list容器
int a[]={1,2,3,4};
list<int> values(a,a+5);

array<int,5>a{1,2,3,4};
list<int>values(a.begin()+2,a.end());
1
2
3
4
5
6
7
8
9
10
11
12
13
14

增加及修改元素

assign()         //用新元素替换原有内容
emplace()        //在容器中的指定位置插入元素
emplace_front()  //在容器头部生成一个元素，和push_front()的功能相同，但效率更高
emplace_back()   //在容器尾部生成一个元素，和push_back()的功能相同，但效率更高
push_front()     //在容器头部插入一个元素
push_back()      //在容器尾部插入一个元素
insert()         //在指定的位置插入一个或多个元素
swap()           //交换两个容器的所有元素
splice()         //将一个list容器中的元素插入到另一个容器的指定位置
1
2
3
4
5
6
7
8
9

删除元素

pop_front()    //删除容器头部的一个元素
pop_back()     //删除容器尾部的一个元素
erase()        //删除容器中的一个或某区域内的元素
clear()        //删除容器存储的所以元素
remove(val)    //删除容器中所有等于val的元素
remove_if()    //删除容器中满足条件的元素
unique()       //删除容器中相邻的重复元素，只保留一个
1
2
3
4
5
6
7

获取元素

begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
front()    //返回第一个元素的引用
back()     //返回最后一个元素的引用
1
2
3
4
5
6
7
8
9
10

其它

empty()       //判断容器是否有元素，无元素返回true，有元素，返回false
size()        //返回容器实际元素个数
max_size()    //返回元素个数的最大值
resize()      //调整容器的大小
merge()       //合并两个事先已排好序的list容器，合并之后的list容器依然是有序的
sort()        //通过更改容器中的元素的位置，将它们进行排序
reverse()     //反转容器中元素的顺序
1
2
3
4
5
6
7

forward_list

是 C++ 11 新添加的一类容器，其底层实现和 list 容器一样，采用的也是链表结构，只不过 forward_list 使用的是单链表。forward_list 容器只提供前向迭代器，而不是双向迭代器。

头文件及命名空间

#include<forward_list>

using namespace std;
1
2
3

创建forward_list容器

forward_list<int> values;        //空的forward_list容器
forward_list<int> values(10);    //包含10个元素的forward_list容器
forward_list<int> values(10,5);  //包含10个元素，每个元素的初始值为5

//通过拷贝已有list容器内容创建新的forward_list容器
forward_list<int> value1(10);
forward_list<int> value2(value1);

//拷贝其它类型的容器中指定区域内的元素，创建新的forward_list容器
int a[]={1,2,3,4};
forward_list<int> values(a,a+5);

array<int,5>a{1,2,3,4};
forward_list<int>values(a.begin()+2,a.end());
1
2
3
4
5
6
7
8
9
10
11
12
13
14

增加及修改元素

assign()         //用新元素替换原有内容
emplace_front()  //在容器头部生成一个元素，和push_front()的功能相同，但效率更高
emplace_after()  //在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。和 insert_after() 的功能相同，但效率更高。
push_front()     //在容器头部插入一个元素
insert_after() 	 //在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。
swap()           //交换两个容器的所有元素
splice_after() 	 //将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后。
1
2
3
4
5
6
7

删除元素

pop_front()    //删除容器头部的一个元素
erase_after() //删除容器中某个指定位置或区域内的所有元素。
clear()        //删除容器存储的所以元素
remove(val)    //删除容器中所有等于val的元素
remove_if()    //删除容器中满足条件的元素
unique()       //删除容器中相邻的重复元素，只保留一个
1
2
3
4
5
6

获取元素

before_begin() 	 //返回一个前向迭代器，其指向容器中第一个元素之前的位置。
begin()          //返回指向容器中的第一个元素的迭代器
end()            //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
cbegin()         //在begin()的基础上增加了const属性，无法修改元素
cend()           //在end()的基础上增加了const属性，无法修改元素
front()          //返回第一个元素的引用
1
2
3
4
5
6

其它

empty()       //判断容器是否有元素，无元素返回true，有元素，返回false
max_size()    //返回元素个数的最大值
resize()      //调整容器的大小
merge()       //合并两个事先已排好序的forward_list容器，合并之后的forward_list容器依然是有序的
sort()        //通过更改容器中的元素的位置，将它们进行排序
reverse()     //反转容器中元素的顺序
1
2
3
4
5
6

deque

双端队列容器，deque容器中存储的元素并不能保证所有的元素否存储到连续的内存空间中

头文件及命名空间

#include<deque>

using namespace std;
1
2
3

创建deque容器

deque<int> values;        //空的deque容器
deque<int> values(10);    //包含10个元素的deque的容器
deque<int> values(10,5);  //包含10个元素的，每个元素初始值为5的deque容器

//拷贝一个已有的deque容器来创建一个新的deque容器
deque<int> d1(10);
deque<int> d2(d1);

//通过拷贝其它类型容器中指定区域的元素，来创建一个新的deque容器
int a[]={1,2,3,4,5};
deque<int> d(a,a+5);

array<int,5>a{1,2,3,4,5,6};
deque<int>d(a.begin()+2,a.end());
1
2
3
4
5
6
7
8
9
10
11
12
13
14

增加及修改元素

assign()         //用新元素替换原有内容
push_back()      //在序列的尾部添加一个元素
push_front()     //在序列的头部添加一个元素
insert()         //在指定的位置插入一个或多个元素
swap()           //交换两个容器的所有元素
emplace()        //在容器中的指定位置插入元素
emplace_front()  //在容器头部生成一个元素，和push_front()的功能相同，但效率更高
emplace_back()   //在容器尾部生成一个元素，和push_back()的功能相同，但效率更高
1
2
3
4
5
6
7
8

删除元素

pop_back()    //移除容器的尾部的元素
pop_front()   //移除容器的头部的元素
erase()       //移除一个或一段元素
clear()       //移除所有的元素，容器大小为0
1
2
3
4

获取元素

begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
at()       //使用索引访问元素
front()    //返回第一个元素的引用
back()     //返回最后一个元素的引用
1
2
3
4
5
6
7
8
9
10
11

其它

size()           //返回容器实际元素个数
max_size()       //返回元素个数的最大值
resize()         //改变实际元素的个数
empty()          //判断容器是否有元素，无元素返回true，有元素，返回false
shrink_to_fit()  //将内存减少到等于当前元素实际所使用的大小
1
2
3
4
5

关联式容器

set

set容器存储的各个键值对，要求键key和值value必须相等

头文件及命名空间

 #include <set>

using namespace std;

//set容器模板类定义
templat<class T,class Compare=less<T>,class Alloc=allocator<T>> class set;
//class T:键key和值value的类型
//class Compare=less<T>: 指定set容器内部的排序规则
//class Alloc=allocator<T>: 指定分配器对象的类型
1
2
3
4
5
6
7
8
9

创建容器

set<string> values; //创建空的set容器

set<string> values{"123","234","345"}; //创建set容器时对其进行初始化

set<string> value1;
set<string> value2(value1);  //利用已有的set容器创建一个新的set容器
1
2
3
4
5
6

增加及修改元素

insert()  //向 set 容器中插入元素。
swap()    //交换 2 个 set 容器中存储的所有元素。这意味着，操作的 2 个 set 容器的类型必须相同。
emplace() //在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
emplace_hint()  //在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
1
2
3
4

删除元素

erase()  //删除 set 容器中存储的元素。
clear()  //清空 set 容器中所有的元素，即令 set 容器的 size() 为 0。
1
2

获取元素

begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
find(val)  //在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val)  //返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)  //返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val)  //该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。
count(val)      //在当前 set 容器中，查找值为 val 的元素的个数，并返回。注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13

其它

empty()       //若容器为空，则返回 true；否则 false。
size()        //返回当前 set 容器中存有键值对的个数。
max_size()    //返回 set 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
1
2
3

map

map容器存储的各个键值对，键的值既不能重复也不能被修改。

头文件及命名空间

#include <map>

using namespace std;

//map容器模板定义如下：
template<class Key, class T, class Compare=less<Key>, class Alloc=allocator<pair<const Key,T>>> class map;
//class Key: 指定键的类
//class T:   指定值的类型
//class Compare=less<Key>: 指定排序规则
//class Alloc=allocator<pair<const Key,T>>: 指定分配器对象的类型
1
2
3
4
5
6
7
8
9
10

创建容器

map<string,int> values; //创建一个空的map容器

map<string,int> values {{"aaa",1},{"bbb",2}}; //创建map容器时进行初始化
map<string,int> values {make_pair("aaa",1),make_pair("bbb",2)}; 

map<string,int> map1(map2);//使用一个已创建好的map容器创建一个新的map容器。
map<string,int> map1(++map2.begin(),map2.end());
1
2
3
4
5
6
7

增加及修改元素

insert()         //向map中插入键值对
swap()           //交换两个map容器中存储的键值对
emplace()        //在当前map容器中指定位置处构造新的键值对
emplace_hint()   //在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
operator[]       //map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。
1
2
3
4
5

删除元素

erase()  //删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。
clear()  //清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
1
2

获取元素

begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
find(key)  //在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key)   //返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key)   //返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key)   //该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。
operator[]        //map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。
at(key)          //找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
count(key)       //在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其它

empty()       //若容器为空，则返回 true；否则 false。
size()        //返回当前 map 容器中存有键值对的个数。
max_size()    //返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
1
2
3

multiset

可以存储多个值相同的元素

头文件及命名空间

#include <set>

using namespace std;

//multiset 容器类模板的定义
template <class T,class Compare=less<T>, class Alloc=allocator<T>>> class multiset;
//class T: 存储元素的类型
//class Compare=less<T>: 指定容器内部的排序规则
//class Alloc=allocator<T>> 指定分配器对象的类型
1
2
3
4
5
6
7
8
9

创建容器

multiset<string> values;  //创建空的multiset容器

multiset<string> values{"123","123","123"};  //创建multiset容器时对其进行初始化

multiset<string> values1;
multiset<string> values2(values1);  //利用已有的multiset容器创建一个新的multiset容器
1
2
3
4
5
6

增加及修改元素

insert()  //向 multiset 容器中插入元素。
swap()    //交换 2 个 multiset 容器中存储的所有元素。这意味着，操作的 2 个 multiset 容器的类型必须相同。
emplace() //在当前 multiset 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
emplace_hint()  //在本质上和 emplace() 在 multiset 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
1
2
3
4

删除元素

erase()  //删除 multiset 容器中存储的元素。
clear()  //清空 multiset 容器中所有的元素，即令 multiset 容器的 size() 为 0。
1
2

获取元素

begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
find(val)  //在 multiset 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val)  //返回一个指向当前 multiset 容器中第一个大于或等于 val 的元素的双向迭代器。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)  //返回一个指向当前 multiset 容器中第一个大于 val 的元素的迭代器。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val)  //该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素.
count(val)      //在当前 multiset 容器中，查找值为 val 的元素的个数，并返回。
1
2
3
4
5
6
7
8
9
10
11
12
13

其它

empty()       //若容器为空，则返回 true；否则 false。
size()        //返回当前 multiset 容器中存有键值对的个数。
max_size()    //返回 multiset 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
1
2
3

multimap

可以存储多个键相同的键值对

头文件及命名空间

#include <map>

using namespace std;

//multimap容器类模板定义
template<class Key,class T,class Compare=less<Key>,class Alloc=allocator<pair<const Key,T>>> class multimap;
//class Key: 键的类型
//class T:   值的类型
//class Compare=less<Key>:  排序规则
//class Alloc=allocator<pair<const Key,T>>: 指定分配器对象的类型
1
2
3
4
5
6
7
8
9
10

创建容器

multimap<string,string> values;

multimap<string,string>values{{"123","111"},{"123","222"},{"123","333"}};
multimap<string,string>values{pair<string,string>{"123","111"},pair<string,string>{"123","222"},pair<string,string>{"123","333"}};
multimap<string,string>values{make_pair<string,string>{"123","111"},make_pair<string,string>{"123","222"},make_pair<string,string>{"123","333"}};

multimap<string,string> values1{{"123","111"},{"123","222"},{"123","333"}};
multimap<string,string> values2(values1);
1
2
3
4
5
6
7
8

增加及修改元素

insert()       //向 multimap 容器中插入键值对。
swap()         //交换 2 个 multimap 容器中存储的键值对
emplace()      //在当前 multimap 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
emplace_hint() //在本质上和 emplace() 在 multimap 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
1
2
3
4

删除元素

erase()   //删除 multimap 容器指定位置、指定键（key）值或者指定区域内的键值对。
clear()   //清空 multimap 容器中所有的键值对，使 multimap 容器的 size() 为 0。
1
2

获取元素

begin()    //返回指向容器中的第一个元素的迭代器
end()      //返回指向容器中的最后一个元素所在位置的后一个位置的迭代器
rbegin()   //返回指向容器中的最后一个元素的迭代器
rend()     //返回指向容器中的第一个元素所在位置前一个位置的迭代器
cbegin()   //在begin()的基础上增加了const属性，无法修改元素
cend()     //在end()的基础上增加了const属性，无法修改元素
crbegin()  //在rbegin()的基础上增加了const属性，无法修改元素
crend()    //在rend()的基础上增加了const属性，无法修改元素 
find(key)  //在 multimap 容器中查找首个键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key)  //返回一个指向当前 multimap 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key) 	//返回一个指向当前 multimap 容器中第一个大于 key 的键值对的迭代器。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key)  //该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对。
count(key) //在当前 multimap 容器中，查找键为 key 的键值对的个数并返回。
1
2
3
4
5
6
7
8
9
10
11
12
13

其它

empty()     //若容器为空，则返回 true；否则 false。
size()      //返回当前 multimap 容器中存有键值对的个数。
max_size()  //返回 multimap 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
1
2
3

unordered_map

无序map容器，底层采用的是哈希表存储结构。

头文件及命名空间

#include <unordered_map>

using namespace std;

//unordered_map容器模板定义
template < class Key,class T,class Hash = hash<Key>,class Pred = equal_to<Key>,class Alloc = allocator< pair<const Key,T>>> class unordered_map;

//class T：键值对中键的类型
//class Hash = hash<Key>：键值对中值的类型
//class Pred = equal_to<Key>： 判断各个键值对键相同的规则
//class Alloc = allocator< pair<const Key,T>> 指定分配器对象的类型

//总的来说，当无序容器中存储键值对的键为自定义类型时，默认的哈希函数 hash 以及比较函数 equal_to 将不再适用，只能自己设计适用该类型的哈希函数和比较函数，并显式传递给 Hash 参数和 Pred 参数。至于如何实现自定义，后续章节会做详细讲解
1
2
3
4
5
6
7
8
9
10
11
12
13

创建容器

unordered_map<string,string> values;

unordered_map<string,string> values {{"123","111"},{"234","222"}};

unordered_map<string,string> values1;
unordered_map<string,string> values2(values1);
unordered_map<string,string> values2(++values1.begin(),values1.end());

1
2
3
4
5
6
7
8

增加及修改元素

operator[key]    //该模板类中重载了[]运算符，其功能是可以向访问数组中元素那样，只要给定某个键值对的键 key，就可以获取该键对应的值。注意，如果当前容器中没有以 key 为键的键值对，则其会使用该键向当前容器中插入一个新键值对。
emplace()         //向容器中添加新键值对，效率比 insert() 方法高。
emplace_hint()    //向容器中添加新键值对，效率比 insert() 方法高。
insert()          //向容器中添加新键值对。
1
2
3
4

删除元素

erase()    //删除指定键值对。
clear()    //清空容器，即删除容器中存储的所有键值对。
swap()     //交换 2 个 unordered_map 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。
1
2
3

获取元素

begin()    //返回指向容器中第一个键值对的正向迭代器。
end()      //返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin()   //和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend()     //和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
at(key)    //返回容器中存储的键 key 对应的值，如果 key 不存在，则会抛出 out_of_range 异常
find(key)  //查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
operator[key]      //该模板类中重载了[]运算符，其功能是可以向访问数组中元素那样，只要给定某个键值对的键 key，就可以获取该键对应的值。注意，如果当前容器中没有以 key 为键的键值对，则其会使用该键向当前容器中插入一个新键值对。
equal_range(key)   //返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。
1
2
3
4
5
6
7
8

其它

empty()              //若容器为空，则返回 true；否则 false。
size()               //返回当前容器中存有键值对的个数。
max_size()           //返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
count(key)           //在容器中查找值为 key 的元素的个数。
bucket_count()       //返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count()   //返回当前系统中，unordered_map 容器底层最多可以使用多少桶。
bucket_size(n)       //返回第 n 个桶中存储键值对的数量。
bucket(key)          //返回以 key 为键的键值对所在桶的编号。
load_factor()        //返回 unordered_map 容器中当前的负载因子。负载因子，指的是的当前容器中存储键值对的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()    //返回或者设置当前 unordered_map 容器的负载因子。
rehash(n)            //将当前容器底层使用桶的数量设置为 n。
reserve()            //将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function()      //返回当前容器使用的哈希函数对象。
1
2
3
4
5
6
7
8
9
10
11
12
13

unordered_set

无序set容器，不再以键值对的形式存储数据，而是直接存储数据的值，底层采用哈希表结构存储数据有关。

头文件及命名空间

#include <unordered_set>

using namespace std;

template < class Key,class Hash = hash<Key>,class Pred = equal_to<Key>,class Alloc = allocator<Key>> class unordered_set;

//class Key:容器中存储元素的类型
//class Hash = hash<Key>:确定元素存储位置所用的哈希函数
//class Pred = equal_to<Key>:判断各个元素是否相等所用的函数
//class Alloc = allocator<Key>:指定分配器对象的类型

//如果 unordered_set 容器中存储的元素为自定义的数据类型，则默认的哈希函数 hash<key> 以及比较函数 equal_to<key> 将不再适用，只能自己设计适用该类型的哈希函数和比较函数，并显式传递给 Hash 参数和 Pred 参数。
1
2
3
4
5
6
7
8
9
10
11
12

创建容器

unordered_set<string> values;

unordered_set<string> values {"111",'222'};

unordered_set<string> values1
unordered_set<string> values2(values1);
unordered_set<string> values2(++values1.begin(),values1.end());
1
2
3
4
5
6
7

增加及修改元素

emplace()         //向容器中添加新键值对，效率比 insert() 方法高。
emplace_hint()    //向容器中添加新键值对，效率比 insert() 方法高。
insert()          //向容器中添加新键值对。
1
2
3

删除元素

erase()    //删除指定键值对。
clear()    //清空容器，即删除容器中存储的所有键值对。
swap()     //交换 2 个 unordered_sety 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。
1
2
3

获取元素

begin()    //返回指向容器中第一个键值对的正向迭代器。
end()      //返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin()   //和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend()     //和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
at(key)    //返回容器中存储的键 key 对应的值，如果 key 不存在，则会抛出 out_of_range 异常
find(key)  //查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
equal_range(key)   //返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。
1
2
3
4
5
6
7

其它

empty()              //若容器为空，则返回 true；否则 false。
size()               //返回当前容器中存有键值对的个数。
max_size()           //返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
count(key)           //在容器中查找值为 key 的元素的个数。
bucket_count()       //返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count()   //返回当前系统中，unordered_set 容器底层最多可以使用多少桶。
bucket_size(n)       //返回第 n 个桶中存储键值对的数量。
bucket(key)          //返回以 key 为键的键值对所在桶的编号。
load_factor()        //返回 unordered_set 容器中当前的负载因子。负载因子，指的是的当前容器中存储键值对的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()    //返回或者设置当前 unordered_set 容器的负载因子。
rehash(n)            //将当前容器底层使用桶的数量设置为 n。
reserve()            //将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function()      //返回当前容器使用的哈希函数对象。
1
2
3
4
5
6
7
8
9
10
11
12
13

unordered_multimap

头文件及命名空间

#include <unordered_map>

using namespace std;

template < class Key,      
           class T,       
           class Hash = hash<Key>,    
           class Pred = equal_to<Key>,     
           class Alloc = allocator< pair<const Key,T> > 
         > class unordered_multimap;

//无序容器中存储的各个键值对，都会哈希存到各个桶中，而对于unordered_multimap容器来说，其存储的所有键值对中，键相等的键值对会被哈希到同一个桶中存储。
    
Hash = hash<Key>    //用于指明容器在存储各个键值对时要使用的哈希函数，默认使用 STL 标准库提供的 hash<key> 哈希函数。注意，默认哈希函数只适用于基本数据类型（包括 string 类型），而不适用于自定义的结构体或者类。
    
Pred = equal_to<Key>   //unordered_multimap 容器可以存储多个键相等的键值对，而判断是否相等的规则，由此参数指定。默认情况下，使用 STL 标准库中提供的 equal_to<key> 规则，该规则仅支持可直接用 == 运算符做比较的数据类型。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

创建容器

std::unordered_multimap<std::string, std::string>mymap{
    {1,"234"},
    {2,"456"},
    {1,"121"} 
};

unordered_multimap<string, string>mymap2(mymap);

//返回临时 unordered_multimap 容器的函数
td::unordered_multimap <std::string, std::string > retmap() {
	std::unordered_multimap<std::string, std::string>tempmap{
        {1,"234"},
    	{2,"456"},
    	{1,"121"} 
    };
    return tempmap;
}

//创建并初始化 myummap 容器
std::unordered_multimap<std::string, std::string> mymap(retmap());

//传入 2 个迭代器，
std::unordered_multimap<std::string, std::string> mymap2(++mymap.begin(), mymap.end());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

增加及修改元素

emplace() 	      //向容器中添加新键值对，效率比 insert() 方法高。
emplace_hint() 	  //向容器中添加新键值对，效率比 insert() 方法高。
insert()  	      //向容器中添加新键值对。
swap() 	          //交换 2 个 unordered_multimap 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。

1
2
3
4
5

删除元素

erase() 	   //删除指定键值对。
clear()  	   //清空容器，即删除容器中存储的所有键值对。

1
2
3

获取元素

begin() 	//返回指向容器中第一个键值对的正向迭代器。
end()  	    //返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin() 	//和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend() 	    //和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
find(key) 	//查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。

1
2
3
4
5
6

其它

empty() 	        //若容器为空，则返回 true；否则 false。
size() 	            //返回当前容器中存有键值对的个数。
max_size() 	        //返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
count(key) 	        //在容器中查找以 key 键的键值对的个数。
equal_range(key) 	//返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。
bucket_count() 	    //返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count() 	//返回当前系统中，unordered_multimap 容器底层最多可以使用多少桶。
bucket_size(n) 	    //返回第 n 个桶中存储键值对的数量。
bucket(key) 	    //返回以 key 为键的键值对所在桶的编号。
load_factor() 	    //返回 unordered_multimap 容器中当前的负载因子。负载因子，指的是的当前容器中存储键值对的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()   //返回或者设置当前 unordered_multimap 容器的负载因子。
rehash(n) 	        //将当前容器底层使用桶的数量设置为 n。
reserve() 	        //将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function() 	//返回当前容器使用的哈希函数对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

unordered_multiset

头文件及命名空间

#include <unordered_set>

using namespace std;

template <  class Key,      
			class Hash = hash<Key>,  
			class Pred = equal_to<Key>,  
			class Alloc = allocator<Key> 
   		> class unordered_multiset;


//unordered_multiset 不以键值对的形式存储数据，而是直接存储数据的值；
//该类型容器底层采用的也是哈希表存储结构,它不会对内部存储的数据进行排序；
//unordered_multiset 容器内部存储的元素，其值不能被修改。
//unordered_multiset 容器可以同时存储多个值相同的元素，且这些元素会存储到哈希表中同一个桶（本质就是链表）上。

Hash = hash<Key>		 //指定 unordered_multiset 容器底层存储各个元素时所使用的哈希函数。需要注意的是，默认哈希函数 hash<Key> 只适用于基本数据类型（包括 string 类型），而不适用于自定义的结构体或者类。

Pred = equal_to<Key>   //用于指定 unordered_multiset 容器判断元素值相等的规则。默认情况下，使用 STL 标准库中提供的 equal_to<key> 规则，该规则仅支持可直接用 == 运算符做比较的数据类型。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

创建容器

std::unordered_multiset<std::string> myset{ "123","234","123" };

std::unordered_multiset<std::string> myset2(myset);

//返回临时 unordered_multiset 容器的函数
std::unordered_multiset <std::string> retset() {
	std::unordered_multiset<std::string> tempumset{ "123","234","123" };
        return tempumset;
}
//调用移动构造函数，创建 umset 容器
std::unordered_multiset<std::string> myset(retset());


//传入 2 个迭代器，
std::unordered_multiset<std::string> myset2(++myset.begin(), myset.end());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

增加及修改元素

emplace() 	     //向容器中添加新元素，效率比 insert() 方法高。
emplace_hint() 	 //向容器中添加新元素，效率比 insert() 方法高。
insert() 	     //向容器中添加新元素。
swap() 	         //交换 2 个 unordered_multimap 容器存储的元素，前提是必须保证这 2 个容器的类型完全相等。

1
2
3
4
5

删除元素

erase() 	//删除指定元素。
clear() 	//清空容器，即删除容器中存储的所有元素。

1
2
3

获取元素

begin() 	        //返回指向容器中第一个元素的正向迭代器。
end() 	            //返回指向容器中最后一个元素之后位置的正向迭代器。
cbegin() 	        //和 begin() 功能相同，只不过其返回的是 const 类型的正向迭代器。
cend() 	            //和 end() 功能相同，只不过其返回的是 const 类型的正向迭代器。
find(key) 	        //查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如果 end() 方法返回的迭代器）。
equal_range(key) 	//返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中值为 key 的元素所在的范围。

1
2
3
4
5
6
7

其它

empty() 	          //若容器为空，则返回 true；否则 false。
size() 	              //返回当前容器中存有元素的个数。
max_size() 	          //返回容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
count(key) 	          //在容器中查找值为 key 的元素的个数。
bucket_count() 	      //返回当前容器底层存储元素时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count() 	  //返回当前系统中，容器底层最多可以使用多少桶。
bucket_size(n) 	      //返回第 n 个桶中存储元素的数量。
bucket(key) 	      //返回值为 key 的元素所在桶的编号。
load_factor() 	      //返回容器当前的负载因子。所谓负载因子，指的是的当前容器中存储元素的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor() 	  //返回或者设置当前 unordered_map 容器的负载因子。
rehash(n) 	          //将当前容器底层使用桶的数量设置为 n。
reserve() 	          //将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function() 	  //返回当前容器使用的哈希函数对象。
1
2
3
4
5
6
7
8
9
10
11
12
13

容器适配器

stack

stack适配器是一种单端开口容器，模拟栈存储结构

头文件及命名空间

#include <stack>

using namespace std;

stack适配器的模板类 stack<T,Container=deque<T>>(T为存储元素的类型，Container表示底层容器的类型，底层容器类型必须支持empty(),size(),back(),push_back(),pop_back())
1
2
3
4
5

创建容器

stack<int> values;   //不包含任何元素的stack适配器，并采用默认的deque基础容器

stack<int,list<int>> values; //使用list基础容器的stack适配器

list<int> values {1,2,3};
stack<int,list<int>> va(values);  //使用一个list基础容器来初始化stack适配器，只要该容器的类型和stack底层使用的基础容器类型相同即可

//用一个stack适配器来初始化另一个stack适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可。
stack<int,list<int>> value1;
stack<int,list<int>> value2(value1);
1
2
3
4
5
6
7
8
9
10

增加及修改元素

push(const T& val)  //先复制val，再将val副本压入栈顶
push(T&& obj)       //以移动元素的方式将其压入栈顶
emplace(arg...)     //arg... 可以是一个参数，也可以是多个参数，用于构造一个对象，并在栈顶直接生成该对象，作为新的栈顶元素
swap(stack<T> & other_stack)   //将两个stack适配器中的元素进行互换。
1
2
3
4

删除元素

pop()  //弹出栈顶元素
1

获取元素

top()  //返回一个栈顶元素的引用，类型为T&，如果栈为空，程序会报错
1

其它

empty()  //判断栈stack是否为空 
size()   //返回stack栈中存储元素的个数
1
2

queue

队列容器，一端输入数据，一端输出数据

头文件及命名空间

#include <queue>

using namespace std;

以模板类queue<T,Container=deque<T>>(其中T为存储元素的类型，Container表示底层容器的类型，必须提供front(),back(),push_back(),pop_front(),empty(),size())
1
2
3
4
5

创建容器

queue<int> values; //空的queue容器是配置，底层使用的基础容器选择默认的deque容器

queue<int,list<int>> values; //创建一个使用list容器作为基础容器的queue容器适配器

list<int> values{1,2,3};
queue<int,list<int>> va(values); //使用基础容器来初始化queue容器适配器，只要该容器类型和queue底层使用的基础容器类型相同即可


queue<int,list<int>> value1;
queue<int,list<int>> value2(value1); //通过queue容器适配器来初始化另一个queue容器适配器
1
2
3
4
5
6
7
8
9
10

增加及修改元素

push(const T& obj)  //在queue的尾部添加一个元素的副本
push(T&& obj)       //以移动元素的方式在queue的尾部添加元素
emplace()           //在queue的尾部直接添加一个元素
swap(stack<T> & other_queue)   //将两个queue适配器中的元素进行互换。
1
2
3
4

删除元素

pop()  //删除queue中的第一个元素
1

获取元素

front()   //返回queue中第一个元素的引用
back()   //返回queue中最后一个元素的引用
1
2

其它

empty()  //判断queue是否为空 
size()   //返回queue中存储元素的个数
1
2

priority_queue

优先级队列容器适配器，保证每次从队头移除的都是当前优先级最高的元素。

头文件及命名空间

#include <queue>

using namespace std;

//priority_queue容器适配器的定义如下：
template<typename T,typename Container=vector<T>,typename Compare=less<T>>
class priority_queue{
    //......
}
//typename T：存储元素的具体类型
//typename Container=vector<T>：存储元素的底层基础容器，默认使用vector容器
//typename Compare=less<T>：指定容器中评定元素的优先级所遵循的排序规则，默认使用less<T>按照元素值从大到小进行排序，还可以使用greater<T>按照元素值从小到大排序。也可以使用自定义排序规则
1
2
3
4
5
6
7
8
9
10
11
12

创建容器

priority_queue<int> values; //创建一个空的priority_queue容器适配器，底层采用默认的vector容器

//使用其他容器中指定范围内的数据，对priority_queue容器适配器进行初始化
int values[] {1，2，3，4}；
priority_queue<int> va(values,values+4);
array<int,4>values {1,2,3,4};
priority_queue<int> va(values.begin(),values.end());

//指定priority_queue使用的底层基础容器和排序规则
int values[] {1,2,3,4};
priority_queue<int,deque<int>,greater<int>> va(values,values+4);
1
2
3
4
5
6
7
8
9
10
11

增加及修改元素

push(const T& obj)                 //根据既定的排序规则，将元素 obj 的副本存储到 priority_queue 中适当的位置。
push(T&& obj)                      //根据既定的排序规则，将元素 obj 移动存储到 priority_queue 中适当的位置。
emplace(Args&&... args)            //Args&&... args 表示构造一个存储类型的元素所需要的数据（对于类对象来说，可能需要多个数据构造出一个对象）。此函数的功能是根据既定的排序规则，在容器适配器适当的位置直接生成该新元素。
swap(priority_queue<T>& other)    //将两个 priority_queue 容器适配器中的元素进行互换。
1
2
3
4

删除元素

pop()   //移除priority_queue容器适配器中第一个元素
1

获取元素

top()   //返回priority_queue中第一个元素的引用形式。
1

其它

empty()  //判断priority_queue是否为空 
size()   //返回priority_queue中存储元素的个数
1
2

算法

sort() 排序函数

对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

受到底层实现方式的限制，使用sort() 函数的容器需要具备以下条件：

1. 容器支持的迭代器类型必须为随机访问迭代器。这意味着，sort() 只对 array、vector、deque 这 3 个容器提供支持。
2. 如果对容器中指定区域的元素做默认升序排序，则元素类型必须支持<小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
3. sort() 函数在实现排序时，需要交换容器中元素的存储位置。这种情况下，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

stable_sort()排序函数

和 sort() 函数功能相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置。

#include <algorithm>

//默认的升序排序
void stable_sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

partial_sort ()排序函数

partial_sort (first, middle, last)，部分排序，从 [first,last) 范围内，筛选出 muddle-first 个最小的元素并排序存放在 [first，middle) 区间中。

#include <algorithm>

//按照默认的升序排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
                   RandomAccessIterator middle,
                   RandomAccessIterator last);
//按照 comp 排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
                   RandomAccessIterator middle,
                   RandomAccessIterator last,
                   Compare comp);
1
2
3
4
5
6
7
8
9
10
11

partial_sort_copy ()排序函数

partial_sort_copy (first, last, result_first, result_last)，从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中。

#include <algorithm>

//默认以升序规则进行部分排序
RandomAccessIterator partial_sort_copy (
                       InputIterator first,
                       InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
//以 comp 规则进行部分排序
RandomAccessIterator partial_sort_copy (
                       InputIterator first,
                       InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

is_sorted ()函数

is_sorted (first, last)，检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

is_sorted_until ()函数

is_sorted_until (first, last)，和 is_sorted() 函数功能类似，唯一的区别在于，如果 [first, last) 范围的元素没有排好序，则该函数会返回一个指向首个不遵循排序规则的元素的迭代器。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

nth_element ()排序函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

merge ()函数

将 2 个有序序列合并为 1 个有序序列，前提是这 2 个有序序列的排序规则相同，并且最终借助该函数获得的新有序序列，其排序规则也和这 2 个有序序列相同。

#include <algorithm>

//以默认的升序排序作为排序规则
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result);
//以自定义的 comp 规则作为排序规则
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);
1
2
3
4
5
6
7
8
9
10

inplace_merge ()函数

当 2 个有序序列存储在同一个数组或容器中时，如果想将它们合并为 1 个有序序列，除了使用 merge() 函数，更推荐使用 inplace_merge() 函数。

inplace_merge() 函数也要求 [first, middle) 和 [middle, last) 指定的这 2 个序列必须遵循相同的排序规则，且当采用第一种语法格式时，这 2 个序列中的元素必须支持 < 小于运算符；同样，当采用第二种语法格式时，这 2 个序列中的元素必须支持 comp 排序规则内部的比较运算符。不同之处在于，merge() 函数会将最终合并的有序序列存储在其它数组或容器中，而 inplace_merge() 函数则将最终合并的有序序列存储在 [first, last) 区域中。

#include <algorithm>

//默认采用升序的排序规则
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                    BidirectionalIterator last);
//采用自定义的 comp 排序规则
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                    BidirectionalIterator last, Compare comp);
1
2
3
4
5
6
7
8

find ()函数

本质上是一个模板函数，用于在指定范围内查找和目标元素值相等的第一个元素。

#include <algorithm>

InputIterator find (InputIterator first, InputIterator last, const T& val);
//first 和 last 为输入迭代器，[first, last) 用于指定该函数的查找范围；val 为要查找的目标元素。
1
2
3
4

find_if ()函数

find_if() 函数也用于在指定区域内执行查找操作。不同的是，前者需要明确指定要查找的元素的值，而后者则允许自定义查找规则。确切地说，find_if() 函数会根据指定的查找规则，在指定区域内查找第一个符合该函数要求（使函数返回 true）的元素。

#include <algorithm>

InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
//first 和 last 都为输入迭代器，其组合 [first, last) 用于指定要查找的区域；pred 用于自定义查找规则。

//find_if() 函数底层实现的参考代码
template<class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
    while (first!=last) {
        if (pred(*first)) return first;
        ++first;
    }
    return last;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

find_if_not ()函数

find_if_not() 函数和 find_if() 函数的功能恰好相反，find_if_not() 函数则用于查找第一个不符合谓词函数规则的元素。

#include <algorithm>

InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred);
//first 和 last 都为输入迭代器，[first, last) 用于指定查找范围；pred 用于自定义查找规则。

//函数底层实现的参考代码
template<class InputIterator, class UnaryPredicate>
InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred)
{
    while (first!=last) {
        if (!pred(*first)) return first;
        ++first;
    }
    return last;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

find_end ()函数

常用于在序列 A 中查找序列 B 最后一次出现的位置。

#include <algorithm>

//查找序列 [first1, last1) 中最后一个子序列 [first2, last2)
ForwardIterator find_end (ForwardIterator first1, ForwardIterator last1,
                          ForwardIterator first2, ForwardIterator last2);
//查找序列 [first2, last2) 中，和 [first2, last2) 序列满足 pred 规则的最后一个子序列
ForwardIterator find_end (ForwardIterator first1, ForwardIterator last1,
                          ForwardIterator first2, ForwardIterator last2,
                          BinaryPredicate pred);

//first1、last1：都为正向迭代器，其组合 [first1, last1) 用于指定查找范围（也就是上面例子中的序列 A）；
//first2、last2：都为正向迭代器，其组合 [first2, last2) 用于指定要查找的序列（也就是上面例子中的序列 B）；
//pred：用于自定义查找规则。该规则实际上是一个包含 2 个参数且返回值类型为 bool 的函数（第一个参数接收 [first1, last1) 范围内的元素，第二个参数接收 [first2, last2) 范围内的元素）。函数定义的形式可以是普通函数，也可以是函数对象。

//函数底层实现参考代码
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2)
{
    if (first2 == last2) return last1;  // specified in C++11
    ForwardIterator1 ret = last1;
    while (first1 != last1)
    {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1 == *it2) {    // or: while (pred(*it1,*it2)) for version (2)
            ++it1; ++it2;
            if (it2 == last2) { ret = first1; break; }
            if (it1 == last1) return ret;
        }
        ++first1;
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

find_first_of ()函数

在 A 序列中查找和 B 序列中任意元素相匹配的第一个元素。

#include <algorithm>

//以判断两者相等作为匹配规则
InputIterator find_first_of (InputIterator first1, InputIterator last1,
                             ForwardIterator first2, ForwardIterator last2);
//以 pred 作为匹配规则
InputIterator find_first_of (InputIterator first1, InputIterator last1,
                             ForwardIterator first2, ForwardIterator last2,
                             BinaryPredicate pred);
//first1、last1：都为输入迭代器，它们的组合 [first1, last1) 用于指定该函数要查找的范围；
//first2、last2：都为正向迭代器，它们的组合 [first2, last2) 用于指定要进行匹配的元素所在的范围；
//pred：可接收一个包含 2 个形参且返回值类型为 bool 的函数，该函数可以是普通函数（又称为二元谓词函数），也可以是函数对象。

//函数底层实现的参考代码
template<class InputIt, class ForwardIt, class BinaryPredicate>
InputIt find_first_of(InputIt first, InputIt last,ForwardIt s_first, ForwardIt s_last,
BinaryPredicate p)
{
    for (; first != last; ++first) {
        for (ForwardIt it = s_first; it != s_last; ++it) {
            //第二种语法格式换成 if (p(*first, *it))
            if (p(*first, *it)) {
                return first;
            }
        }
    }
    return last;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

adjacent_find ()函数

在指定范围内查找 2 个连续相等的元素。

#include <algorithm>

//查找 2 个连续相等的元素
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);
//查找 2 个连续满足 pred 规则的元素
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
//first 和 last 都为正向迭代器，其组合 [first, last) 用于指定该函数的查找范围；pred 用于接收一个包含 2 个参数且返回值类型为 bool 的函数，以实现自定义查找规则。


//函数底层实现的参考代码
template <class ForwardIterator>
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)
{
    if (first != last)
    {
        ForwardIterator next=first; ++next;
        while (next != last) {
            if (*first == *next)     // 或者 if (pred(*first,*next)), 对应第二种语法格式
                return first;
            ++first; ++next;
        }
    }
    return last;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

search ()函数

在序列 A 中查找序列 B 第一次出现的位置.。

#include <algorithm>

//查找 [first1, last1) 范围内第一个 [first2, last2) 子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
                        ForwardIterator first2, ForwardIterator last2);
//查找 [first1, last1) 范围内，和 [first2, last2) 序列满足 pred 规则的第一个子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
                        ForwardIterator first2, ForwardIterator last2,
                        BinaryPredicate pred);
//first1、last1：都为正向迭代器，其组合 [first1, last1) 用于指定查找范围（也就是上面例子中的序列 A）；
//first2、last2：都为正向迭代器，其组合 [first2, last2) 用于指定要查找的序列（也就是上面例子中的序列 B）；
//pred：用于自定义查找规则。该规则实际上是一个包含 2 个参数且返回值类型为 bool 的函数（第一个参数接收 [first1, last1) 范围内的元素，第二个参数接收 [first2, last2) 范围内的元素）。函数定义的形式可以是普通函数，也可以是函数对象。

//函数底层实现的参考代码
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2)
{
    if (first2 == last2) return first1;
    while (first1 != last1)
    {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1 == *it2) {    // 或者 while (pred(*it1,*it2)) 对应第二种语法格式
            if (it2 == last2) return first1;
            if (it1 == last1) return last1;
            ++it1; ++it2;
        }
        ++first1;
    }
    return last1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

search_n ()函数

和 search() 一样，search_n() 函数也定义在<algorithm>头文件中，用于在指定区域内查找第一个符合要求的子序列。不同之处在于，前者查找的子序列中可包含多个不同的元素，而后者查找的只能是包含多个相同元素的子序列。

#include <algorithm>

//在 [first, last] 中查找 count 个 val 第一次连续出现的位置
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                          Size count, const T& val);
//在 [first, last] 中查找第一个序列，该序列和 count 个 val 满足 pred 匹配规则
ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                           Size count, const T& val, BinaryPredicate pred );


//first、last：都为正向迭代器，其组合 [first, last) 用于指定查找范围（也就是上面例子中的序列 A）；
//count、val：指定要查找的元素个数和元素值，以上面的序列 B 为例，该序列实际上就是 3 个元素 4，其中 count 为 3，val 为 4；
//pred：用于自定义查找规则。该规则实际上是一个包含 2 个参数且返回值类型为 bool 的函数（第一个参数接收[first, last) 范围内的元素，第二个参数接收 val）。函数定义的形式可以是普通函数，也可以是函数对象。

//search_n() 函数会返回一个正向迭代器，当函数查找成功时，该迭代器指向查找到的子序列中的第一个元素；反之，如果查找失败，则该迭代器的指向和 last 迭代器相同。

//函数底层实现的参考代码
template<class ForwardIterator, class Size, class T>
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                              Size count, const T& val)
{
    ForwardIterator it, limit;
    Size i;
    limit=first; std::advance(limit,std::distance(first,last)-count);
    while (first!=limit)
    {
        it = first; i=0;
        while (*it==val)       // 或者 while (pred(*it,val))，对应第二种格式
        { ++it; if (++i==count) return first; }
        ++first;
    }
    return last;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

partition ()函数

分组，partition() 函数可根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据。

#include <algorithm>

ForwardIterator partition (ForwardIterator first,ForwardIterator last,
                           UnaryPredicate pred);
//first 和 last 都为正向迭代器，其组合 [first, last) 用于指定该函数的作用范围；pred 用于指定筛选规则。
1
2
3
4
5

stable_partition ()函数

stable_partition() 函数可以保证对指定区域内数据完成分组的同时，不改变各组内元素的相对位置。

#include <algorithm>

BidirectionalIterator stable_partition (BidirectionalIterator first,BidirectionalIterator last, UnaryPredicate pred);
//first 和 last 都为双向迭代器，其组合 [first, last) 用于指定该函数的作用范围；pred 用于指定筛选规则。


1
2
3
4
5
6

partition_copy ()函数

partition_copy() 函数也能按照某个筛选规则对指定区域内的数据进行“分组”，并且分组后不会改变各个元素的相对位置。更重要的是，partition_copy() 函数不会对原序列做修改，而是以复制的方式将序列中各个元组“分组”到其它的指定位置存储。

#include <algorithm>

pair<OutputIterator1,OutputIterator2> partition_copy (
                    InputIterator first, InputIterator last,
                    OutputIterator1 result_true, OutputIterator2 result_false,
                    UnaryPredicate pred);


//first、last：都为输入迭代器，其组合 [first, last) 用于指定该函数处理的数据区域；
//result_true：为输出迭代器，其用于指定某个存储区域，以存储满足筛选条件的数据；
//result_false：为输出迭代器，其用于指定某个存储区域，以存储满足筛选条件的数据；
//pred：用于指定筛选规则，其本质就是接收一个具有 1 个参数且返回值类型为 bool 的函数。注意，该函数既可以是普通函数，还可以是一个函数对象。

//函数底层实现的参考代码
template <class InputIterator, class OutputIterator1,
          class OutputIterator2, class UnaryPredicate pred>
          pair<OutputIterator1,OutputIterator2>
partition_copy (InputIterator first, InputIterator last,
                    OutputIterator1 result_true, OutputIterator2 result_false,
                    UnaryPredicate pred)
{
    while (first!=last) {
        if (pred(*first)) {
            *result_true = *first;
            ++result_true;
        }
        else {
            *result_false = *first;
            ++result_false;
        }
        ++first;
    }
    return std::make_pair (result_true,result_false);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

partition_point ()函数

如何在已分好组的数据中找到分界位置。

#include <algorithm>

ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
                                 UnaryPredicate pred);
//first 和 last 为正向迭代器，[first, last) 用于指定该函数的作用范围；pred 用于指定数据的筛选规则。该函数会返回一个正向迭代器，该迭代器指向的是 [first, last] 范围内第一个不符合 pred 筛选规则的元素。

//函数底层实现的参考代码
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
                                 UnaryPredicate pred)
{
    auto n = distance(first,last);
    while (n>0)
    {
        ForwardIterator it = first;
        auto step = n/2;
        std::advance (it,step);
        if (pred(*it)) { first=++it; n-=step+1; }
        else n=step;
    }
    return first;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

lower_bound ()函数

用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。

#include <algorithm>

//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);
//first 和 last 都为正向迭代器，[first, last) 用于指定函数的作用范围；val 用于指定目标元素；comp 用于自定义比较规则，此参数可以接收一个包含 2 个形参（第二个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。 该函数还会返回一个正向迭代器，当查找成功时，迭代器指向找到的元素；反之，如果查找失败，迭代器的指向和 last 迭代器相同。

//函数底层实现的参考代码
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;
    count = distance(first,last);
    while (count>0)
    {
        it = first; step=count/2; advance (it,step);
        if (*it<val) {  //或者 if (comp(*it,val))，对应第 2 种语法格式
            first=++it;
            count-=step+1;
        }
        else count=step;
    }
    return first;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

upper_bound ()函数

在指定范围内查找大于目标值的第一个元素。

#include <algorithm>

//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);
//first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于执行目标值；comp 作用自定义查找规则。该函数会返回一个正向迭代器，当查找成功时，迭代器指向找到的元素；反之，如果查找失败，迭代器的指向和 last 迭代器相同。

//函数底层实现的参考代码
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;
    count = std::distance(first,last);
    while (count>0)
    {
        it = first; step=count/2; std::advance (it,step);
        if (!(val<*it))  // 或者 if (!comp(val,*it)), 对应第二种语法格式
        { first=++it; count-=step+1;  }
        else count=step;
    }
    return first;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

equel_range ()函数

在指定范围内查找等于目标值的所有元素。

#include <algorithm>

//找到 [first, last) 范围中所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);
//实现方式
template <class ForwardIterator, class T>
std::pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator it = std::lower_bound (first,last,val);
    return std::make_pair ( it, std::upper_bound(it,last,val) );
}
    

//找到 [first, last) 范围内所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
//实现方式
template<class ForwardIterator, class T, class Compare>
std::pair<ForwardIt,ForwardIt> equal_range(ForwardIterator first, ForwardIterator last, const T& val, Compare comp)
{
    ForwardIterator it = std::lower_bound (first,last,val,comp);
    return std::make_pair ( it, std::upper_bound(it,last,val,comp) );
}

//first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于指定目标值；comp 用于指定比较规则

//该函数会返回一个 pair 类型值，其包含 2 个正向迭代器。当查找成功时：
//    第 1 个迭代器指向的是 [first, last) 区域中第一个等于 val 的元素；
//    第 2 个迭代器指向的是 [first, last) 区域中第一个大于 val 的元素。
//反之如果查找失败，则这 2 个迭代器要么都指向大于 val 的第一个元素（如果有），要么都和 last 迭代器指向相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

binary_search ()函数

查找指定区域内是否包含某个目标元素。

#include <algorithm>

//查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T& val);
//实现方式
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
    first = std::lower_bound(first,last,val);
    return (first!=last && !(val<*first));
}

//根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
//实现方式
template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& val, Compare comp)
{
    first = std::lower_bound(first, last, val, comp);
    return (!(first == last) && !(comp(val, *first)));
}

//first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于指定要查找的目标值；comp 用于自定义查找规则
//该函数会返回一个 bool 类型值，如果 binary_search() 函数在 [first, last) 区域内成功找到和 val 相等的元素，则返回 true；反之则返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

all_of、any_of及none_of ()函数

用来检查在算法应用到序列中的元素上时，什么时候使谓词返回 true。这些算法的前两个参数是定义谓词应用范围的输入迭代器；第三个参数指定了谓词。

#include <algorithm>

//all_of() 算法会返回 true，前提是序列中的所有元素都可以使谓词返回 true。
//any_of() 算法会返回 true，前提是序列中的任意一个元素都可以使谓词返回 true。
//none_of() 算法会返回 true，前提是序列中没有元素可以使谓词返回 true。
1
2
3
4
5

equal ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

mismatch ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

lexicographical_compare ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

next_permutation ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

prev_permutation ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

is_permutation ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

copy_n ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

copy_if ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

copy_backward ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

reverse_copy ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

unique ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

rotate ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

rotate_copy ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

move ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

swap_ranges ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

remove ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

fill ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

fill_n ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

generate ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

generate_n ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

transform ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6

replace ()函数

nth_element (first, nth, last)，找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

#include <algorithm>

//默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5
6