C++的STL

众所周知C++是一款编程语言,有些天朝OIers把c++称为c+STL,足以看出STL的重要性.

那什么是STL,又有哪些STL是我们需要熟练掌握的?

1. 什么是STL
2. 常用的STL
   1. queue
   2. stack
   3. vector
   4. algorithm
   5. pair( utility )
3. 练习题

Part 1 什么是STL

STL是Standard Template Library的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL是C++的一部分，因此不用安装额外的库文件。 -----百度百科

简单的说,STL就是c++对于用户的一种外挂,其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。,用户可以使用STL来完成一些简单的操作,如插入,删除,查找,排序....利用STL会使你的程序变得"短小精悍",没有必要再像之前一样写很多很多的函数来表示不同的操作.STL，

Part 2 常用的STL

STL下含6个部分(容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分)。,13个头文件,(algorithm、deque、functional、iterator、vector、list、map、<memory.h>、numeric、queue、set、stack和utility。)这一次我们谈一谈我认为(不要杠)比较重要的几个STL函数

第一个 queue

这是线性表中的一种东西--队列,满足FIFO,先进先出的数据结构,(单行线)

#include<queue>//打STL必须要加上必要的头文件

queue<int> q;//这样就定义了一个存储类型为int的STL队列.

而<queue>这个头文件下还包含了另一个队列(priority queue),优先队列,而这个队列满足的要求是FILO(first in,largest out)优先队列满足了一种叫大根堆的东西,其最大的排在前面的特性使其充分适用于大根堆(题外话,重载运算符后,可以用优先队列写小根堆)奇技淫巧 by 扶苏

这里我们主要谈一谈queue 单调队列

q.empty();//一个bool函数,若队列为空则返回1,不为空,返回0;

int x;//按照定义时的来,不一定是int 
q.push(x); //把x这个变量加入队列中.

q.pop();//弹出队首数据

q.size();//返回的值是队列中非零数据的个数. 

q.front();// 队首值 

q.back();// 队尾值 

queue在运用中大部分的问题都可以运用这些方式解决.

队列在广搜与图论最短路中也有重要应用

第二个 stack 栈

和队列类似,栈也是一种线性表,也满足 FILO(是不是有点眼熟,这个是先进后出 first in last out)

#include<stack>

stack <int> s;

栈的常用操作有五个

分别是(top push pop size empty)

s.top();//栈顶 

int x;
s.push(x);//入栈 

s.pop();//弹出栈顶元素 

s.size();//栈中数据个数 

s.empty(); //判断栈是否为空; 

第三个 vector

很简单来说，vector容器就是一个可以任意更改长短的向量，我们可以存下不超过它的长度的数据，当然也可以随时给他增加长度或者减少长度。

#include<vector>

vector<int> v;

既然是STL模板库里的东西，必定有一些配套的函数，

v.size();v.empty();//好像每一个STL容器都支持这个,含义也相同

v.clear();//把整个vector全部清空

v.front() //返回第一个元素

v.back() //返回最后一个元素

vector<int>::iterator it=v.front();//指向第一个元素 
//迭代器,相当于STL 容器中的指针;
//加减整数--左移右移
//指针相减--下标差

v.pop_back()//弹出最后的元素;
v.push_back(x)//在队尾插入一个元素;  

第四个 algorithm;

algorithm并不是一个函数,而是包含在这个头文件下的函数.

主要的包括(sort,unique,next_permutation(),reverse,upper_bound()以及lower_bound())

一个一个来:

sort 快速排序

​ 把某一段区间中的数按照从小到大的顺序排布(在没写另外的函数的条件下)

sort(begin,end(,cmp));//把数组从begin->end的这一部分按要求排序

unique 去重

把某一段区间中的有序数列做一下去重操作

unique(begin,end)//把begin->end的这一段区间去重

reverse 翻转

把整个数组做翻转操作

reverse(begin,end);//反向存储

next_permutation 下一个排列

例子 从1--n的n!种全排列

for(int i=1;i<=n;i++) a[i]=i;
do{
    for(int i=1;i<n;i++) cout<<a[i]<<" ";
    cout<<a[n]<<endl;
}while(next_permutation(a+1,a+n+1));

lower_/upper_bound

lower_ 在有序的序列中,返回第一个大于等于x的元素的位置的迭代器;

upper_ 在有序的序列中,返回第一个大于x的元素位置的迭代器

upper_bound(begin,end,x);
lower_bound(begin,end,x);//便于二分查找

最后的一个 pair

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量,换句话说,其实pair可以单纯的理解为二元组

pair<string, string> anon;        // 创建一个空对象anon，两个元素类型都是string
pair<string, int> word_count;     // 创建一个空对象 word_count, 两个元素类型分别是string和int类型
pair<string, vector<int> > line;  // 创建一个空对象line，两个元素类型分别是string和vector类型

队成员初始化

pair<string, string> author("James","Joy");    // 创建一个author对象，两个元素类型分别为string类型，并默认初始值为James和Joy。
pair<string, int> name_age("Tom", 18);
pair<string, int> name_age2(name_age);    // 拷贝构造初始化

对于两个元素的访问

pair<int ,double> p1;

p1.first = 1;

p1.second = 2.5;

cout<<p1.first<<' '<<p1.second<<endl;

//输出结果：1 2.5


string firstBook;
if(author.first=="James" && author.second=="Joy")
    firstBook="Stephen Hero";

练习题

既然讲都讲了这么多了,那就拿几道来看看

队列的练习 1 2

栈的练习 1 2

sort的练习 //排序的题单(洛谷)

其实STL并没有太多的专题,大多还是应用于实践的.

那就说这么多吧!

看了这么多,难道不点个赞吗???