C++STL入门笔记

╰半夏微凉° 2022-04-13 03:51 197阅读 0赞

C++ STL中最基本以及最常用的类或容器无非就是以下几个：

*  string
 *  vector
 *  set
 *  list
 *  map

首先看看我们C语言一般怎么使用字符串的

char* s1 = "Hello SYSU!"; //创建指针指向字符串常量，这段字符串我们是不能修改的
    
    //想要创建 可以修改的字符串，我们可以使用数组分配空间
    char s2[20] = "Hello SYSU!";
    //或者这样
    char s3[] = "Hello SYSU!";
    
    //当然我们也可以动态分配内存
    char* s4 = (char*)malloc(20）;
    gets(s4);

C++ 标准库中的string表示可变长的字符串，它在头文件string里面。

#include <string>

用string初始化字符串分两类：用“=”号就是拷贝初始化，否则就是直接初始化。

![170624074561101.png][]

string s1;//初始化字符串，空字符串
    string s2 = s1; //拷贝初始化，深拷贝字符串
    string s3 = "I am Yasuo"; //直接初始化，s3存了字符串
    string s4(10, 'a'); //s4存的字符串是aaaaaaaaaa
    string s5(s4); //拷贝初始化，深拷贝字符串
    string s6("I am Ali"); //直接初始化
    string s7 = string(6, 'c'); //拷贝初始化，cccccc

![170624074561102.png][]

#include <iostream>
 #include <string>
 
 using namespace std;
 
 int main()
 {
 string s1;//初始化字符串，空字符串
 string s2 = s1; //拷贝初始化，深拷贝字符串
 string s3 = "I am Yasuo"; //直接初始化，s3存了字符串
 string s4(10, 'a'); //s4存的字符串是aaaaaaaaaa
 string s5(s4); //拷贝初始化，深拷贝字符串
 string s6("I am Ali"); //直接初始化
 string s7 = string(6, 'c'); //拷贝初始化，cccccc
 
 //string的各种操作
 string s8 = s3 + s6;//将两个字符串合并成一个
 s3 = s6;//用一个字符串来替代另一个字符串的对用元素
 
 cin >> s1;
 
 cout << s1 << endl;
 cout << s2 << endl;
 cout << s3 << endl;
 cout << s4 << endl;
 cout << s5 << endl;
 cout << s6 << endl;
 cout << s7 << endl;
 cout << s8 << endl;
 cout << "s7 size = " << s7.size() << endl; //字符串长度，不包括结束符
 cout << (s2.empty() ? "This string is empty" : "This string is not empty") << endl;;
 
 system("pause");
 return 0;
 }

string的IO操作

使用cin读入字符串时，遇到空白就停止读取。比如程序输入的是

"     Hello   World"

那么我们得到的字符串将是"Hello"，前面的空白没了，后面的world也读不出来。

如果我们想把整个hello world读进来怎么办？那就这样做

cin>>s1>>s2;

hello存在s1里，world存在s2里了。

有时我们想把一个句子存下来，又不想像上面那样创建多个string来存储单词，怎么办？

那就是用getline来获取一整行内容。

string str;
 getline(cin, str);
 cout << str << endl;

当把string对象和字符面值及字符串面值混在一条语句中使用时，必须确保+的两侧的运算对象至少有一个是string

string s1 = s2 + ", "; //正确
    string s3 = "s " + ", "; //错误
    string s4 = "hello" + ", " + s1; //错误
    string s5 = s1 + "hello " + ", "; //改一下顺序，s1放前头，正确了，注意理解=号右边的运算顺序

处理string中的字符

访问字符串的每个字符

for (int i = 0; i < s3.size(); i++)
 {
 cout << s3[i] << endl;
 s3[i] = 's';
 }

在C语言中我都是用下标或者指针来访问数组元素，而在C++里，有个新奇的东西叫做迭代器iterator，我们可以使用它来访问容器元素。

![170624074561104.png][]

string str("hi sysu");
 for (string::iterator it = str.begin(); it != str.end(); it++)
 {
 cout << *it << endl;
 }

我们也可以是使用const\_iterator使得访问元素时是能读不能写，这跟常量指针意思差不多。

string str2("hi sysu");
 for (string::const_iterator it = str2.begin(); it != str2.end(); it++)
 {
 cout << *it << endl;
 *it = 'l'; //这是错误的，不能写
 }

![170624074561105.png][]

string还有一些很好用的函数，比如找子串

string sq("heoolo sdaa ss");
 cout << s.find("aa", 0) << endl; //返回的是子串位置。第二个参数是查找的起始位置，如果找不到，就返回string::npos
 if (s.find("aa1", 0) == string::npos)
 {
 cout << "找不到该子串！" << endl;
 }

## vector ##

C++ STL中的verctor好比是C语言中的数组，但是vector又具有数组没有的一些高级功能。与数组相比，vector就是一个可以不用再初始化就必须制定大小的边长数组，当然了，它还有许多高级功能。

要想用vector首先得包含头文件vector。

#include <vector>

怎么初始化？

![170624074561106.png][]

如果vector的元素类型是int，默认初始化为0；如果vector元素类型为string，则默认初始化为空字符串。

vector<int> v1;
 vector<father> v2;
 vector<string> v3;
 vector<vector<int> >; //注意空格。这里相当于二维数组int a[n][n];
 vector<int> v5 = { 1,2,3,4,5 }; //列表初始化,注意使用的是花括号
 vector<string> v6 = { "hi","my","name","is","lee" };
 vector<int> v7(5, -1); //初始化为-1,-1,-1,-1,-1。第一个参数是数目，第二个参数是要初始化的值
 vector<string> v8(3, "hi");
 vector<int> v9(10); //默认初始化为0
 vector<int> v10(4); //默认初始化为空字符串

如何向vector添加元素？

请使用push\_back加入元素，并且这个元素是被加在数组尾部的。

for (int i = 0; i < 20; i++)
 {
 v1.push_back(i);
 }

vector其他的操作

![170624074561107.png][]

访问和操作vector中的每个元素

for (int i = 0; i < v1.size(); i++)
 {
 cout << v1[i] << endl;
 v1[i] = 100;
 cout << v1[i] << endl;
 }

注意：只能对已存在的元素进行赋值或者修改操作，如果是要加入新元素，务必使用push\_back。push\_back的作用有两个：告诉编译器为新元素开辟空间、将新元素存入新空间里。

比如下面的代码是错误的，但是编译器不会报错，就像是数组越界。

vector<int> vec;
 vec[0] = 1; //错误！

当然我们也可以选择使用迭代器来访问元素

vector<string> v6 = { "hi","my","name","is","lee" };
 for (vector<string>::iterator iter = v6.begin(); iter != v6.end(); iter++)
 {
 cout << *iter << endl;
 //下面两种方法都行
 cout << (*iter).empty() << endl;
 cout << iter->empty() << endl; 
 }

上面是正向迭代，如果我们想从后往前迭代该如何操作？  
使用反向迭代器

for (vector<string>::reverse_iterator iter = v6.rbegin(); iter != v6.rend(); iter++)
 {
 cout << *iter << endl;
 
 }

vector最常用的增删操作

![170624074561108.png][]

#include <iostream>
 #include <vector>
 #include <string>
 
 using namespace std;
 
 template <typename T>
 void showvector(vector<T> v)
 {
 for (vector<T>::iterator it = v.begin(); it != v.end(); it++)
 {
 cout << *it;
 }
 cout << endl;
 }
 
 int main()
 {
 vector<string> v6 = { "hi","my","name","is","lee" };
 v6.resize(3); //重新调整vector容量大小
 showvector(v6);
 
 vector<int> v5 = { 1,2,3,4,5 }; //列表初始化,注意使用的是花括号
 cout << v5.front() << endl; //访问第一个元素
 cout << v5.back() << endl; //访问最后一个元素
 
 showvector(v5);
 v5.pop_back(); //删除最后一个元素
 showvector(v5);
 v5.push_back(6); //加入一个元素并把它放在最后
 showvector(v5);
 v5.insert(v5.begin()+1,9); //在第二个位置插入新元素
 showvector(v5);
 v5.erase(v5.begin() + 3); //删除第四个元素
 showvector(v5);
 v5.insert(v5.begin() + 1, 7,8); //连续插入7个8
 showvector(v5);
 v5.clear(); //清除所有内容
 showvector(v5);
 
 system("pause");
 return 0;
 }

注意：虽然vertor对象可以动态增长，但是也或有一点副作用：已知的一个限制就是不能再范围for循环中向vector对象添加元素。另外一个限制就是任何一种可能改变vector对象容量的操作，不如push\_back，都会使该迭代器失效。

总而言之就是：但凡使用了迭代器的循环体，都不要向迭代器所属的容器添加元素！

C++中push\_back和insert两个有什么区别?

顾名思义push\_back把元素插入容器末尾，insert把元素插入任何你指定的位置。  
不过push\_back速度一般比insert快。如果能用push\_back尽量先用push\_back。

## set ##

set跟vector差不多，它跟vector的唯一区别就是，set里面的元素是有序的且唯一的，只要你往set里添加元素，它就会自动排序，而且，如果你添加的元素set里面本来就存在，那么这次添加操作就不执行。要想用set先加个头文件set。

#include <set>

#include <iostream>
 #include <set>
 #include <string>
 
 using namespace std;
 
 template <typename T>
 void showset(set<T> v)
 {
 for (set<T>::iterator it = v.begin(); it != v.end(); it++)
 {
 cout << *it;
 }
 cout << endl;
 }
 
 int main()
 {
 set<int> s1{9,8,1,2,3,4,5,5,5,6,7,7 }; //自动排序，从小到大,剔除相同项
 showset(s1);
 set<string> s2{ "hello","sysy","school","hello" }; //字典序排序
 showset(s2);
 s1.insert(9); //有这个值了，do nothing
 showset(s1);
 s2.insert("aaa"); //没有这个字符串，添加并且排序
 showset(s2);
 
 system("pause");
 return 0;
 }

## list ##

list就是链表，在C语言中我们想使用链表都是自己去实现的，实现起来倒不难，但是如果有现成的高效的链表可以使用的话，我们就不需要重复造轮子了。STL就提供了list容器给我们。

list是一个双向链表，而单链表对应的容器则是foward\_list。

list即双向链表的优点是插入和删除元素都比较快捷，缺点是不能随机访问元素。

初始化方式就大同小异了，跟vector基本一样。要想用list先加个头文件list。

#include <list>

#include <iostream>
 #include <list>
 #include <string>
 
 using namespace std;
 
 template <typename T>
 void showlist(list<T> v)
 {
 for (list<T>::iterator it = v.begin(); it != v.end(); it++)
 {
 cout << *it;
 }
 cout << endl;
 }
 
 int main()
 {
 list<int> l1{ 1,2,3,4,5,5,6,7,7 };
 showlist(l1);
 list<double> l2;
 list<char> l3(10);
 list<int> l4(5, 10); //将元素都初始化为10
 showlist(l4);
 
 
 system("pause");
 return 0;
 }

值得注意的是，list容器不能调用algorithm下的sort函数进行排序，因为sort函数要求容器必须可以随机存储，而list做不到。所以，list自己做了一个自己用的排序函数，用法如下：

list<int> l1{ 8,5,7,6,1,2,3,4,5,5,6,7,7 };
 l1.sort();

## map ##

map运用了哈希表地址映射的思想，也就是key-value的思想，来实现的。

首先给出map最好用也最最常用的用法例子，就是用字符串作为key去查询操作对应的value。

要使用map得先加个头文件map。

#include <map>

#include <iostream>
 #include <map>
 #include <string>
 
 using namespace std;
 
 void showmap(map<string, int> v)
 {
 for (map<string, int>::iterator it = v.begin(); it != v.end(); it++)
 {
 cout << it->first << " " << it->second << endl; //注意用法，不是用*it来访问了。first表示的是key，second存的是value
 }
 cout << endl;
 }
 
 int main()
 {
 map<string, int> m1; //<>里的第一个参数表示key的类型,第二个参数表示value的类型
 m1["Kobe"] = 100;
 m1["James"] = 99;
 m1["Curry"] = 98;
 
 string s("Jordan");
 m1[s] = 90;
 
 cout << m1["Kobe"] << endl;
 cout << m1["Jordan"] << endl;
 cout << m1["Durant"] << endl; //不存在这个key，就显示0
 
 m1.erase("Curry");//通过关键字来删除
 showmap(m1);
 m1.insert(pair<string, int>("Harris", 89)); //也可以通过insert函数来实现增加元素
 showmap(m1);
 m1.clear(); //清空全部
 
 
 system("pause");
 return 0;
 }

如果想看看某个存不存在某个key，可以用count来判断

if (m1.count("Lee"))
 {
 cout << "Lee is in m1!" << endl;
 }
 else
 {
 cout << "Lee do not exist!" << endl;
 }

用迭代器来访问元素

for (map<string, int>::iterator it = m1.begin(); it != m1.end(); it++)
 {
 cout << it->first<<" "<<it->second << endl; //注意用法，不是用*it来访问了。first表示的是key，second存的是value
 }

**一、一般介绍**

STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming），引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术；

从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。如果查阅任何一个版本的STL源代码，你就会发现，模板作为构成整个STL的基石是一件千真万确的事情。除此之外，还有许多C++的新特性为STL的实现提供了方便；

**二、STL的六大组件**

*  容器（Container），是一种数据结构，如list，vector，和deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器；
 *  迭代器（Iterator），提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator\*()以及其他类似于指针的操作符地方法的类对象；
 *  算法（Algorithm），是用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象，函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；
 *  仿函数（Function object，仿函数(functor)又称之为函数对象（function object），其实就是重载了()操作符的struct，没有什么特别的地方
 *  迭代适配器（Adaptor）
 *  空间配制器（allocator）其中主要工作包括两部分1.对象的创建与销毁    2.内存的获取与释放

以下主要讨论：容器，迭代器，算法，适配器。如欲详加了解 参见C++ Primer

**1.STL容器**

**1）序列式容器（Sequence containers**），每个元素都有固定位置－－取决于插入时机和地点，和元素值无关，vector、deque、list；

**Vectors：**将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时；

**Deques**：是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时；

** Lists：**双向链表，不提供随机存取（按顺序走到需存取的元素，O(n)），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针；

**2）关联式容器（Associated containers**），元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap；

**Sets/Multisets**：内部的元素依据其值自动排序，Set内的相同数值的元素只能出现一次，Multisets内可包含多个数值相同的元素，内部由二叉树实现（实际上基于红黑树(RB-tree）实现），便于查找；

**Maps/Multimaps**：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现（实际上基于红黑树(RB-tree）实现），便于查找；

另外有其他容器hash\_map,hash\_set,hash\_multiset,hash\_multimap。

容器的比较：

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;">&nbsp;</td> 
 <td style="vertical-align:top;">Vector</td> 
 <td style="vertical-align:top;">Deque</td> 
 <td style="vertical-align:top;">List</td> 
 <td style="vertical-align:top;">Set</td> 
 <td style="vertical-align:top;">MultiSet</td> 
 <td style="vertical-align:top;">Map</td> 
 <td style="vertical-align:top;">MultiMap</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;">内部结构</td> 
 <td style="vertical-align:top;">dynamic array</td> 
 <td style="vertical-align:top;">array of arrays</td> 
 <td style="vertical-align:top;">double linked list</td> 
 <td style="vertical-align:top;">binary tree</td> 
 <td style="vertical-align:top;">binary tree</td> 
 <td style="vertical-align:top;">binary tree</td> 
 <td style="vertical-align:top;">binary tree</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;">随机存取</td> 
 <td style="vertical-align:top;">Yes</td> 
 <td style="vertical-align:top;">Yes</td> 
 <td style="vertical-align:top;">No</td> 
 <td style="vertical-align:top;">No</td> 
 <td style="vertical-align:top;">No</td> 
 <td style="vertical-align:top;">Yes(key)</td> 
 <td style="vertical-align:top;">No</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;">搜索速度</td> 
 <td style="vertical-align:top;">慢</td> 
 <td style="vertical-align:top;">慢</td> 
 <td style="vertical-align:top;">很慢</td> 
 <td style="vertical-align:top;">快</td> 
 <td style="vertical-align:top;">快</td> 
 <td style="vertical-align:top;">快</td> 
 <td style="vertical-align:top;">快</td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;">快速插入移除</td> 
 <td style="vertical-align:top;">尾部</td> 
 <td style="vertical-align:top;">首尾</td> 
 <td style="vertical-align:top;">任何位置</td> 
 <td style="vertical-align:top;">--</td> 
 <td style="vertical-align:top;">--</td> 
 <td style="vertical-align:top;">--</td> 
 <td style="vertical-align:top;">--</td> 
 </tr> 
 </tbody> 
</table>

**2.STL迭代器 **

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素,   
而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了\*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；

常见的一些迭代器类型：iterator、const\_iterator、reverse\_iterator和const\_reverse\_iterator

迭代器一般声明使用示例

vector<T>::iterator it;
 list<T>::iterator it;
 deque<T>::iterator it；

![161101112229931.jpg][]

input        output

\\            /

forward

bidirectional

random access

要注意，上面这图表并不是表明它们之间的继承关系：而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如：forward迭代器不但拥有input和output迭代器的所有功能，还拥有更多的功能。

各个迭代器的功能如下：

<table> 
 <tbody> 
 <tr> 
 <td> 迭代器类别 </td> 
 <td> 说明 </td> 
 </tr> 
 <tr> 
 <td> 输入 </td> 
 <td> 从容器中读取元素。输入迭代器只能一次读入一个元素向前移动，输入迭代器只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列 </td> 
 </tr> 
 <tr> 
 <td> 输出 </td> 
 <td> 向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法，统一输出迭代器不能两次遍历一个序列 </td> 
 </tr> 
 <tr> 
 <td> 正向 </td> 
 <td> 组合输入迭代器和输出迭代器的功能，并保留在容器中的位置 </td> 
 </tr> 
 <tr> 
 <td> 双向 </td> 
 <td> 组合正向迭代器和逆向迭代器的功能，支持多遍算法 </td> 
 </tr> 
 <tr> 
 <td> 随机访问 </td> 
 <td> 组合双向迭代器的功能与直接访问容器中任何元素的功能，即可向前向后跳过任意个元素 </td> 
 </tr> 
 </tbody> 
</table>

迭代器的操作：

每种迭代器均可进行包括表中前一种迭代器可进行的操作。

<table> 
 <tbody> 
 <tr> 
 <td> 迭代器操作 </td> 
 <td> 说明 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 所有迭代器 </td> 
 </tr> 
 <tr> 
 <td> p++ </td> 
 <td> 后置自增迭代器 </td> 
 </tr> 
 <tr> 
 <td> ++p </td> 
 <td> 前置自增迭代器 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 输入迭代器 </td> 
 </tr> 
 <tr> 
 <td> *p </td> 
 <td> 复引用迭代器，作为右值 </td> 
 </tr> 
 <tr> 
 <td> p=p1 </td> 
 <td> 将一个迭代器赋给另一个迭代器 </td> 
 </tr> 
 <tr> 
 <td> p==p1 </td> 
 <td> 比较迭代器的相等性 </td> 
 </tr> 
 <tr> 
 <td> p!=p1 </td> 
 <td> 比较迭代器的不等性 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 输出迭代器 </td> 
 </tr> 
 <tr> 
 <td> *p </td> 
 <td> 复引用迭代器，作为左值 </td> 
 </tr> 
 <tr> 
 <td> p=p1 </td> 
 <td> 将一个迭代器赋给另一个迭代器 </td> 
 </tr> 
 <tr> 
 <td> 正向迭代器 </td> 
 <td> 提供输入输出迭代器的所有功能 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 双向迭代器 </td> 
 </tr> 
 <tr> 
 <td> --p </td> 
 <td> 前置自减迭代器 </td> 
 </tr> 
 <tr> 
 <td> p-- </td> 
 <td> 后置自减迭代器 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 随机迭代器 </td> 
 </tr> 
 <tr> 
 <td> p+=i </td> 
 <td> 将迭代器递增i位 </td> 
 </tr> 
 <tr> 
 <td> p-=i </td> 
 <td> 将迭代器递减i位 </td> 
 </tr> 
 <tr> 
 <td> p+i </td> 
 <td> 在p位加i位后的迭代器 </td> 
 </tr> 
 <tr> 
 <td> p-i </td> 
 <td> 在p位减i位后的迭代器 </td> 
 </tr> 
 <tr> 
 <td> p[i] </td> 
 <td> 返回p位元素偏离i位的元素引用 </td> 
 </tr> 
 <tr> 
 <td> p&lt;p1 </td> 
 <td> 如果迭代器p的位置在p1前，返回true，否则返回false </td> 
 </tr> 
 <tr> 
 <td> p&lt;=p1 </td> 
 <td> p的位置在p1的前面或同一位置时返回true，否则返回false </td> 
 </tr> 
 <tr> 
 <td> p&gt;p1 </td> 
 <td> 如果迭代器p的位置在p1后，返回true，否则返回false </td> 
 </tr> 
 <tr> 
 <td> p&gt;=p1 </td> 
 <td> p的位置在p1的后面或同一位置时返回true，否则返回false </td> 
 </tr> 
 </tbody> 
</table>

只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下：

<table> 
 <tbody> 
 <tr> 
 <td> 容器 </td> 
 <td> 支持的迭代器类别 </td> 
 <td style="vertical-align:top;"> 说明 </td> 
 </tr> 
 <tr> 
 <td> vector </td> 
 <td> 随机访问 </td> 
 <td style="vertical-align:top;"> 一种随机访问的数组类型，提供了对数组元素进行快速随机访问以及在序列尾部进行快速的插入和删除操作的功能。可以再需要的时候修改其自身的大小 </td> 
 </tr> 
 <tr> 
 <td> deque </td> 
 <td> 随机访问 </td> 
 <td style="vertical-align:top;"> 一种随机访问的数组类型，提供了序列两端快速进行插入和删除操作的功能。可以再需要的时候修改其自身的大小 </td> 
 </tr> 
 <tr> 
 <td> list </td> 
 <td> 双向 </td> 
 <td style="vertical-align:top;"> 一种不支持随机访问的数组类型，插入和删除所花费的时间是固定的，与位置无关。 </td> 
 </tr> 
 <tr> 
 <td> set </td> 
 <td> 双向 </td> 
 <td style="vertical-align:top;"> 一种随机存取的容器，其关键字和数据元素是同一个值。所有元素都必须具有惟一值。 </td> 
 </tr> 
 <tr> 
 <td> multiset </td> 
 <td> 双向 </td> 
 <td style="vertical-align:top;"> 一种随机存取的容器，其关键字和数据元素是同一个值。可以包含重复的元素。 </td> 
 </tr> 
 <tr> 
 <td> map </td> 
 <td> 双向 </td> 
 <td style="vertical-align:top;"> 一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个特定的关键字只能与一个元素关联。 </td> 
 </tr> 
 <tr> 
 <td> multimap </td> 
 <td> 双向 </td> 
 <td style="vertical-align:top;"> 一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个关键字可以与多个数据元素关联。 </td> 
 </tr> 
 <tr> 
 <td> stack </td> 
 <td> 不支持 </td> 
 <td style="vertical-align:top;"> 适配器容器类型，用vector，deque或list对象创建了一个先进后出容器 </td> 
 </tr> 
 <tr> 
 <td> queue </td> 
 <td> 不支持 </td> 
 <td style="vertical-align:top;"> 适配器容器类型，用deque或list对象创建了一个先进先出容器 </td> 
 </tr> 
 <tr> 
 <td> priority_queue </td> 
 <td> 不支持 </td> 
 <td style="vertical-align:top;"> 适配器容器类型，用vector或deque对象创建了一个排序队列 </td> 
 </tr> 
 </tbody> 
</table>

** 3.STL算法**

STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。要使用 STL中的算法函数必须包含头文件<algorithm>，对于数值算法须包含<numeric>，<functional>中则定义了一些模板类，用来声明函数对象。 
STL中算法大致分为四类： 
1）、非可变序列算法：指不直接修改其所操作的容器内容的算法。 
2）、可变序列算法：指可以修改它们所操作的容器内容的算法。 
3）、排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。 
4）、数值算法：对容器内容进行数值计算。

以下对所有算法进行细致分类并标明功能： 
   ** <一>查找算法(13个)：**判断容器中是否包含某个值 
    adjacent\_find:            在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的ForwardIterator。否则返回last。重载版本使用输入的二元操作符代替相等的判断。 
    binary\_search:            在有序序列中查找value，找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。 
    count:                    利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数。 
    count\_if:                利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数。 
    equal\_range:              功能类似equal，返回一对iterator，第一个表示lower\_bound，第二个表示upper\_bound。 
    find:                    利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的一个InputIterator。 
    find\_end:                在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个ForwardIterator，否则返回输入的"另外一对"的第一个ForwardIterator。重载版本使用用户输入的操作符代替等于操作。 
    find\_first\_of:            在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。 
    find\_if:                  使用输入的函数代替等于操作符执行find。 
    lower\_bound:              返回一个ForwardIterator，指向在有序序列范围内的可以��入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。 
    upper\_bound:              返回一个ForwardIterator，指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值。重载函数使用自定义比较操作。 
    search:                  给出两个范围，返回一个ForwardIterator，查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向last1。重载版本使用自定义的比较操作。 
    search\_n:                在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。 
  
    **<二>排序和通用算法(14个)：**提供元素排序策略 
    inplace\_merge:            合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序。 
    merge:                    合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。 
    nth\_element:              将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作。 
    partial\_sort:            对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作。 
    partial\_sort\_copy:        与partial\_sort类似，不过将经过排序的序列复制到另一个容器。 
    partition:                对指定范围内元素重新排序，使用输入的函数，把结果为true的元素放在结果为false的元素之前。 
    random\_shuffle:          对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。 
    reverse:                  将指定范围内元素重新反序排序。 
    reverse\_copy:            与reverse类似，不过将结果写入另一个容器。 
    rotate:                  将指定范围内元素移到容器末尾，由middle指向的元素成为容器第一个元素。 
    rotate\_copy:              与rotate类似，不过将结果写入另一个容器。 
    sort:                    以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。 
    stable\_sort:              与sort类似，不过保留相等元素之间的顺序关系。 
    stable\_partition:        与partition类似，不过不保证保留容器中的相对顺序。 
  
    **<三>删除和替换算法(15个)** 
    copy:                    复制序列 
    copy\_backward:            与copy相同，不过元素是以相反顺序被拷贝。 
    iter\_swap:                交换两个ForwardIterator的值。 
    remove:                  删除指定范围内所有等于指定元素的元素。注意，该函数不是真正删除函数。内置函数不适合使用remove和remove\_if函数。 
    remove\_copy:              将所有不匹配元素复制到一个制定容器，返回OutputIterator指向被拷贝的末元素的下一个位置。 
    remove\_if:                删除指定范围内输入操作结果为true的所有元素。 
    remove\_copy\_if:          将所有不匹配元素拷贝到一个指定容器。 
    replace:                  将指定范围内所有等于vold的元素都用vnew代替。 
    replace\_copy:            与replace类似，不过将结果写入另一个容器。 
    replace\_if:              将指定范围内所有操作结果为true的元素用新值代替。 
    replace\_copy\_if:          与replace\_if，不过将结果写入另一个容器。 
    swap:                    交换存储在两个对象中的值。 
    swap\_range:              将指定范围内的元素与另一个序列元素值进行交换。 
    unique:                  清除序列中重复元素，和remove类似，它也不能真正删除元素。重载版本使用自定义比较操作。 
    unique\_copy:              与unique类似，不过把结果输出到另一个容器。 
  
    **<四>排列组合算法(2个)：**提供计算给定集合按一定顺序的所有可能排列组合 
    next\_permutation:        取出当前范围内的排列，并重新排序为下一个排列。重载版本使用自定义的比较操作。 
    prev\_permutation:        取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。

** <五>算术算法(4个)** 
    accumulate:              iterator对标识的序列段元素之和，加到一个由val指定的初始值上。重载版本不再做加法，而是传进来的二元操作符被应用到元素上。 
    partial\_sum:              创建一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义操作代替加法。 
    inner\_product:            对两个序列做内积(对应元素相乘，再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的操作。 
    adjacent\_difference:      创建一个新序列，新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差。 
  
    **<六>生成和异变算法(6个)** 
    fill:                    将输入值赋给标志范围内的所有元素。 
    fill\_n:                  将输入值赋给first到first+n范围内的所有元素。 
    for\_each:                用指定函数依次对指定范围内所有元素进行迭代访问，返回所指定的函数类型。该函数不得修改序列中的元素。 
    generate:                连续调用输入的函数来填充指定的范围。 
    generate\_n:              与generate函数类似，填充从指定iterator开始的n个元素。 
    transform:                将输入的操作作用与指定范围内的每个元素，并产生一个新的序列。重载版本将操作作用在一对元素上，另外一个元素来自输入的另外一个序列。结果输出到指定容器。

**<七>关系算法(8个)** 
    equal:                    如果两个序列在标志范围内元素都相等，返回true。重载版本使用输入的操作符代替默认的等于操作符。 
    includes:                判断第一个指定范围内的所有元素是否都被第二个范围包含，使用底层元素的<操作符，成功返回true。重载版本使用用户输入的函数。 
    lexicographical\_compare:  比较两个序列。重载版本使用用户自定义比较操作。 
    max:                      返回两个元素中较大一个。重载版本使用自定义比较操作。 
    max\_element:              返回一个ForwardIterator，指出序列中最大的元素。重载版本使用自定义比较操作。 
    min:                      返回两个元素中较小一个。重载版本使用自定义比较操作。 
    min\_element:              返回一个ForwardIterator，指出序列中最小的元素。重载版本使用自定义比较操作。 
    mismatch:                并行比较两个序列，指出第一个不匹配的位置，返回一对iterator，标志第一个不匹配元素位置。如果都匹配，返回每个容器的last。重载版本使用自定义的比较操作。

**<八>集合算法(4个)** 
    set\_union:                构造一个有序序列，包含两个序列中所有的不重复元素。重载版本使用自定义的比较操作。 
    set\_intersection:        构造一个有序序列，其中元素在两个序列中都存在。重载版本使用自定义的比较操作。 
    set\_difference:          构造一个有序序列，该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作。 
    set\_symmetric\_difference: 构造一个有序序列，该序列取两个序列的对称差集(并集-交集)。

**<九>堆算法(4个)** 
    make\_heap:                把指定范围内的元素生成一个堆。重载版本使用自定义比较操作。 
    pop\_heap:                并不真正把最大元素从堆中弹出，而是重新排序堆。它把first和last-1交换，然后重新生成一个堆。可使用容器的back来访问被"弹出"的元素或者使用pop\_back进行真正的删除。重载版本使用自定义的比较操作。 
    push\_heap:                假设first到last-1是一个有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较操作。 
    sort\_heap:                对指定范围内的序列重新排序，它假设该序列是个有序堆。重载版本使用自定义比较操作。

**4.适配器**

STL提供了三个容器适配器：queue、priority\_queue、stack。这些适配器都是包装了vector、list、deque中某个顺序容器的包装器。注意：适配器没有提供迭代器，也不能同时插入或删除多个元素。下面对各个适配器进行概括总结。

**（1）stack用法**

#include <stack>
 template < typename T, typename Container=deque > class stack;

可以使用三个标准顺序容器vecotr、deque(默认)、list中的任何一个作为stack的底层模型。

bool stack<T>::empty() //判断堆栈是否为空
 void stack<T>::pop() //弹出栈顶数据
 stack<T>::push(T x) //压入一个数据
 stack<T>::size_type stack<T>::size() //返回堆栈长度
 T stack<T>::top() //得到栈顶数据

代码示例：

stack<int> intDequeStack; 
 stack<int,vector<int>> intVectorStack; 
 stack<int,list<int>> intListStack;

**（2）queue用法**

#include <queue>
 template<typename T, typename Container = deque<T> > class queue;

第一个参数指定要在queue中存储的类型，第二个参数规定queue适配的底层容器，可供选择的容器只有dequeue和list。对大多数用途使用默认的dequeue。

queue<T>::push(T x)
 void queue<T>::pop()
 T queue<T>::back()
 T queue<T>::front()
 queue<T>::size_type 
 queue<T>::size()
 bool queue<T>::empty()

代码示例：

queue<int> intDequeQueue; 
 queue<int,list<int>> intListQueue;
 （3）priority_queue用法

#include <queue>
 template <typename T, typename Container = vector<T>, typename Compare = less<T> > class priority_queue;

priority\_queue也是一个队列，其元素按有序顺序排列。其不采用严格的FIFO顺序，给定时刻位于队头的元素正是有最高优先级的元素。如果两个元素有相同的优先级，那么它们在队列中的顺序就遵循FIFO语义。默认适配的底层容器是vector，也可以使用deque，list不能用，因为priority\_queue要求能对元素随机访问以便进行排序。

priority_queue<T>::push(T x)
 void priority_queue<T>::pop()
 T priority_queue<T>::top()
 priority_queue<T>::size_type 
 priority_queue<T>::size()
 bool priority_queue<T>::empty()

代码示例：

priority_queue< int, vector<int>, greater<int> >
 priority_queue< int, list<int>, greater<int> >

标准库默认使用元素类型的<操作符来确定它们之间的优先级关系，用法有三：

优先队列第一种用法，通过默认使用的<操作符可知在整数中元素大的优先级高。

priority_queue<int> qi;

示例中输出结果为：9 6 5 3 2

优先队列第二种用法，建立priority\_queue时传入一个比较函数，使用functional.h函数对象作为比较函数。

priority_queue<int, vector<int>, greater<int> >qi2;

示例2中输出结果为：2 3 5 6 9

优先队列第三种用法，是自定义优先级。

struct node 
 {
 friend bool operator< (node n1, node n2)
 {
 return n1.priority < n2.priority;
 } 
 int priority;
 int value; 
 }; 
 priority_queue<node> qn;

在示例3中输出结果为：

优先级  值

9          5

8          2

6          1

2          3

1          4

在该结构中，value为值，priority为优先级。通过自定义operator<操作符来比较元素中的优先级。注意：必须是自定义<操作符才行，把上述的结构中的<操作符改成>编译不通过。

[170624074561101.png]: /images/20220413/76592b0444004f01be6d609e99a876e0.png
[170624074561102.png]: /images/20220413/c96bbcd586ae4479903f46a83db7bcb1.png
[170624074561104.png]: /images/20220413/d46e802116874868a7c8b3f8b951f9e0.png
[170624074561105.png]: /images/20220413/bc9a1abeb58545ceba52d2a1a81031ee.png
[170624074561106.png]: /images/20220413/b32cfd23b0544ccdb5458c32ca930b0e.png
[170624074561107.png]: /images/20220413/c94dce11de514f26b5bba37056ae7b23.png
[170624074561108.png]: /images/20220413/5dc94ab194b8411d944d156e0115f33a.png
[161101112229931.jpg]: /images/20220413/d9d663c904a44a00b9e9ff8381ab2afd.png