C++ STL简述

前言

最近要找工作，免不得要有一番笔试，今年好像突然就都流行在线笔试了，真是搞的我一塌糊涂。有的公司呢，不支持Python，Java我也不会，C有些数据结构又有些复杂，所以是时候把STL再看一遍了…不会告诉你距离上次使用可能已经有半年以上了。

STL是什么

STL为C++的标准模版库，又称为C++泛型库，在std命名空间中定义了常用的数据结构和算法，使用起来十分方便。STL提供三种类型的组件：

容器。主要有两类：顺序容器和关联容器。前者主要包括：vector，list，deque和string等，为一些列元素的有序集合。后者主要有：set，multiset，map和multimap，包含查找元素的键值
迭代器的作用是遍历容器
算法库。主要包括四类算法：排序算法，不可变序算法，变序性算法和数值算法

容器常用操作

这一节主要说一下各种容器的常用操作，直接看代码实例即可。

vector

向量容器可以像数组一样对元素进行随机访问，还可以在尾部插入元素，完全可以替代数组。具有内存自动管理的功能，对元素的插入和删除可以动态调整所占用的内存空间。

#include<vector>#include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{// 初始化有三种方式// 元素下标均从0开始 vector<int> v1;//不指定元素个数 vector<double> v2（10）; // 10个元素，每个初值窦唯0.0 vector<int> v3（10, 1）;// 10个元素，每个值都为1// 尾部追加新元素v1.push_back（1）;// 有2种方式访问元素 // 使用下标方式访问元素cout<<v2[8]<<endl;// 使用迭代器访问 vector<int>::iterator it;for（it=v1.begin（）;it！=v1.end（）;it++）cout<<*it<<" ";// 元素的插入注意：插入的位置为迭代器的位置，不是下标 v3.insert（v3.begin（）+2, 0）;// 元素的删除，删除迭代器所指的一个元素或一段区间的所有元素v3.erase（v3.begin（）+2）; // 删除第3个元素v3.erase（v3.begin（）+1, v3.begin（）+5）; // 第二到第五个，前开后闭// 清空v3.clear（）; // 判断是否为空v1.empty（）;// 为空则返回假，反之为真 // 查看元素个数v2.size（）;// reverse反向排列算法，需#include<algorithm> reverse（v1.begin（）, v1.end（））;// 排序，需#include<algorithm> sort（v1.begin（）, v1.end（））;// 自己指定排序算法sort（v1.begin（）, v1.end（）, Comp）; }

string

可以把string理解为字符串类，提供了添加、删除、替换、查找和比较丰富的方法，当然也可以使用vector来处理字符串，但是不如string功能丰富。同时可以使用vector这样的向量，类似于字符数组。

#include<string>#include<vector>#include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{// 创建string对象string s;// 赋值s = "abc";// or cin>>s;or char ss[5000]; scanf（"%s", &ss）; s=ss;// 尾部添加字符 s = s + "d";// 尾部添加字符串s = s + "hello world"; // append（）方法添加s.append（"123"）;// 插入字符到迭代器的位置之前s.insert（s.begin（）, "p"）; // 访问string对象元素cout<<s[0]<<endl;//删除string对象元素s.erase（s.begin（））;s.erase（s.begin（）, s.begin（）+2）;//长度cout<<s.length（）<<endl; // 判断空cout<<s.empty（）<<endl;// 替换s.replace（3, 3, "good"）; // 从第四个起，连续三个字符替换成good// 搜索cout<<s.find（"c"）<<endl; // 查到返回下标，反之返回4294967295 cout<<s.find（"123"）<<endl;// 比较cout<<s.compare（"cat"）<<endl; // 比对方大返回1，小为-1，相等为0// 反向排列reversereverse（s.begin（）, s.end（））;// string对象做vector元素vector<string> v;}

set

set实现了红黑树的平衡二叉检索树的数据结构，在插入元素的时候会自动调整二叉树的排列，把元素放到适当的位置，以确保每个子树根节点键值大于左子树所有节点，同时小于右边节点；另外，还要得确保左右子树高度相等。不会插入同样键值的元素。平衡二叉检索树的检索采用中序遍历算法，构造set的目的是为了快速检索。

#include<string>#include<vector>#include<set>#include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{set<int> s;// 插入s.insert（0）;s.insert（2）;s.insert（0）; // 只有一个0// 遍历set<int>::iterator it;for（it=s.begin（）;it！=s.end（）;it++）cout<<*it<<endl;// 反向遍历for（set<int>::reverse_iterator rit=s.rbegin（）;rit！=s.rend（）;rit++）cout<<*rit<<endl;// 删除元素s.erase（0）;// 检索，find（），找到，返回迭代器位置，反之返回最后一个元素的后一个位置，即end（）s.find（20）; }

map

map映照容器的元素数据由key, value组成，也采用红黑树实现，不允许重复键，比较函数只对value值比较，各项数据可以通过key检索。

#include<string>#include<vector>#include<set>#include<map>#include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{// 初始化 map<string, float> m;// 插入元素m["wang"] = 99.9;m["zhao"] = 100.0;// 前向遍历map<string, float>::iterator it;for（it=m.begin（）;it！=m.end（）;it++）cout<<（*it）.first<<":"<<（*it）.second<<endl;// 删除元素m.erase（"wang"）;// 搜索 ，和set一样 it = m.find（"zhao"）;}

deque

双端队列，可以在两侧进行操作。

#include<string>#include<vector>#include<set>#include<map>#include<deque> #include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{// initdeque<int> d;deque<float> dd（10）;deque<int> ddd（10, 1）;// 尾部插入，扩张队列 d.push_back（1）;d.push_back（2）;d.push_back（3）;// 头部插入，会覆盖原有元素d.push_front（10）;d.push_front（20）; // 此时为 20, 10, 1 // 前向遍历for（int i=0;i<d.size（）;i++）cout<<d[i]<<endl;for（deque<int>::iterator it=d.begin（）;it！=d.end（）;it++）cout<<*it<<endl;// 反向遍历， deque<int>::reverse_iterator rit, rbegin, rend// 删除d.pop_front（）;d.pop_back（）;d.erase（d.begin（））;// 清空d.clear（）;return 0;}

list

双向链表，节点保存不在连续内存中，所以迭代器只能通过 ++ 或 -- 操作来移动到前驱或者后继节点，不能使用 +n 或者 -n 来操作。

#include<string>#include<vector>#include<set>#include<map>#include<deque> #include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{// initlist<int> l;list<int> ll（10）;// 插入，3种方法链表都会自动扩张l.push_back（1）;l.push_front（2）;l.push_back（3）;l.push_back（4）;l.insert（l.begin（）, 20）;// 遍历同其他容器// 删除l.remove（1）; // 删除值为 1的所有元素l.pop_front（）;l.pop_back（）;l.erase（l.begin（））;// 清空l.clear（）; // findl.find（l.begin（）, l.end（）, 5）;// sortl.sort（）; // 升序排序// 删除重复元素l.unique（）;return 0; }

stack

#include<stack>#include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{// initstack<int> s;s.push（1）;s.push（3）;s.pop（）;s.top（）;cout<<s.size（）<<endl;cout<<s.empty（）<<endl;return 0;}

queue

#include<queue>#include<iostream>using namespace std;// sort指定的排序算法 bool Comp（const int &a, const int &b）{if（a！=b）return a>b;elsereturn a>b; } int main（void）{queue<int> q;q.push（1）;q.push（1）;q.push（1）;cout<<q.size（）<<endl;cout<<q.front（）<<endl;// 读取队首位置元素cout<<q.back（）<<endl; // 队尾cout<<q.empty（）<<endl; q.pop（）;}

本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-11/136950.htm