STL,学名Standard Template Library，一般我们称他为标准模板库，是一系列软件的统称。

从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map一大堆，STL也是算

法和其他一些组件的集合。比如说<algorithm>中sort函数、<string>中string类都

是STL的内容。

STL库还有很多内容，比如：向量（vector）、栈（stack）、队列（queue）、优先队列

（priority_queue）、链表（list）、集合（set）、映射（map）等容器；min、max、swap

、sort、lower_bound、upper_bound 等算法，有的甚至都没人知道。ㄟ( ▔, ▔ )ㄏ

One.快速排序(Sort):

众所周知，c++有各种正常排序和奇葩的排序，比如说冒泡排序，时间复杂度为N(O^2)，就很离谱

是不是，随便排一个100000的元素的数组就超时。

所以，咱们以后不用冒泡，用sort快排（弃暗投明）,时间复杂度为N*LogN，对一百万个数排序也不会超过1秒。

1.Sort的基本用法:

sort是STL自带的系统函数，它的格式是：

void sort(要排序元素的起始地址，要排序元素的结束地址，比较函数)；

这里可以省略比较函数，他是默认从小到大排序的（升序排序）


#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int a[]={3,5,2,6,9,3,5};
	sort(a,a+7);//7是数组的元素个数，这里a为数组的开头，a+7就等于排序到数组的第七个元素
	for(int i=0;i<6;i++)
		cout<<a[i]<<" ";
}

输出:

2 3 3 5 5 6

2.Sort进阶用法（CMP）：

void sort(要排序元素的起始地址，要排序元素的结束地址，比较函数)；,没错又是他，这里我们发

现还有个比较函数没说，这个比较函数的作用就是可以自定义排序方式，比如降序排序。

定义：bool cmp(int x,int y).....，如果返回True那么x就排在y前面。


#include<algorithm>
#include<iostream>
using namespace std;
bool cmp(int x,int y)
{
	if(x>y)return true;//降序
	return false;
}
int main()
{
	int a[]={3,5,2,6,9,3,5};
	sort(a,a+7,cmp);//7是数组的元素个数
	for(int i=0;i<6;i++)
		cout<<a[i]<<" ";
}

输出：

9 6 5 5 3 3

3.Sort对结构体(或者类)的排序：

同学们进行干饭比赛，参赛队员分别为“法外狂徒张三”，“干饭者老八”以及王五同学，谁吃的更多谁就排在更前面，如果吃的一样多那么谁吃的老八汉堡多谁就排在更前面：


#include<algorithm>
#include<iostream>
using namespace std;
struct ganfan
{
	string name;
	int zongshu;
	int hanbao;
};
bool cmp(ganfan x,ganfan y)
{
	if(x.zongshu>y.zongshu)return true;
	else if(x.hanbao>y.hanbao&&x.zongshu==y.zongshu)//如果一样多那么比谁吃的汉堡多
	return false;
}
int main()
{
	ganfan a[3];
	a[0].name="zhangsan";a[0].zongshu=200;a[0].hanbao=6;
	a[1].name="laoba";a[1].zongshu=170;a[1].hanbao=13;
	a[2].name="wangwu";a[2].zongshu=170;a[2].hanbao=10;
	sort(a,a+3,cmp);
	for(int i=0;i<3;i++)
		cout<<a[i].name<<" ";
}

输出：

wangwu laoba zhangsan

我们可以看到，张三的干饭总数是最多的，所以排在最前面，老八和王五的干饭总数一样多，但是老八吃的汉堡更多些，所以老八排在王五前面。

Two.Map

Map简介:

map是STL的一个关联容器，它提供一对一的hash。

第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
第二个可能称为该关键字的值(value)；

定义：

map<类型,类型> m;

举个栗子:

记录每个人的名字的对应的爱好,张三喜欢吃汉堡：


#include<map>
#include<iostream>
using namespace std;
int main()
{
	map<string,string> m;
	m["张三"]="吃汉堡";
	cout<<"张三: "<<m["张三"]; 
}

输出：

张三: 吃汉堡

刷题时间!

题目：离散化基础

在使用离散化方法编程时，通常要知道每个数排序后的编号(rank值)，相同的数对应同一个编号。

输入格式

第1行：一个整数N。 1<=N<=100000。
第2行：有N个整数，每个数都是int范围的。注意：可能有相同整数。

输出格式

依次输出每个数的排名。

输入/输出例子1

输入：

5
8 2 6 9 2

输出：

3 1 2 4 1

题解:

这题用Sort和Map就可以很容易解决:


#include<bits/stdc++.h>
using namespace std;
int N,a[100001],b[100001];
map<int,int> m;
int main(){
    
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b,b+N);//将数组排序
    int c=1;//排名
    m[b[0]]=1;//因为数组经过排序，所以第1个元素肯定是第一
    for(int i=1;i<N;i++)
    {
        if(b[i]!=b[i-1])//判断是否不与前一个数相等
        {
            c++;
            m[b[i]]=c;
        }
    }
    for(int i=0;i<N;i++)
        if(m[a[i]]!=0)
            cout<<m[a[i]]<<" ";//按照原来的下标输出
    
    return 0;
}

Three.stack(栈)

头文件:

#include<stack>

stack好像还有个翻译叫“咸鱼”...嘿嘿。

栈的介绍：

栈就像一个盒子，可以放入或去除元素，但是个人类都知道，要把盒子底下的东西取出来，就必须先取出他上面的东西。

假如我们把1、2、3、4、5按顺序分别入栈：

——博主美丽的手绘

栈的定义：


stack<类型(可以不写)> st;
或者stack st;

很easy是不？

栈的成员函数：

.empty()	判断栈是否为空，空则返回true
.pop()	移除栈顶元素
.push(啥啥啥)	在栈顶增加元素
.size()	返回栈中元素数目
.top()	返回栈顶元素

.empty() 判断栈是否为空。


stack st;
if(st.empty())//如果是空那么执行下面代码
    ......

.push(啥啥啥),在栈顶增加元素。

.top()，返回栈顶元素，记住是返回，要单独输出。


#include<stack>
#include<iostream>
using namespace std;
stack<int> st;
int main(){
    
    st.push(5418);
    cout<<st.top();//输出栈顶元素
    return 0;
}

输出5418。

.size(), 返回栈中元素数目。


#include<stack>
#include<iostream>
using namespace std;
stack<int> st;
int main(){
    
    st.push(5418);
    cout<<st.size();
    
    return 0;
}

输出1

.pop()，移除栈顶元素：


#include<stack>
#include<iostream>
using namespace std;
stack<int> st;
int main(){
    
    st.push(1452);
    st.push(5418);
    st.pop();
    cout<<st.top();
    
    return 0;
}

输出1452。

简单不？

Four.二分查找

头文件：

#include <algorithm>

美妙的函数：

1.lower_bound函数

对于有序容器，有序容器，有序容器（重要的事情说三遍）快速二分查找出第一个大于等于

指定数的位置（下标），如果没有找到，返回最后一个数据后面的位置。

对于数组，通常的格式为：

查找的数组下标 = lower_bound(数组要查找的开始位置，数组要查找的结束位置后面，要找的数) – 数组开始位置(一般写数组名);

比如：


#include<algorithm>
#include<iostream>
 
using namespace std;
 
int main() {
 
    int a[5] = { 1,2,3,3,8 };
 
    //从 a 数组中找到第一个不小于   3 的元素
 
    int   index = lower_bound(a, a + 5, 3)-a;//查找的数组下标 = lower_bound(数组要查找的开始位置，数组要查找的结束位置后面，要找的数) – 数组开始位置;
 
    if   (index==5 ) cout << " not found! ";//index=5，也就是数组末尾的位置。
    else  cout << index;
 
    return   0;
 
}

输出2。

2.upper_bound函数

有一个类似lower_bound的函数upper_bound, 快速二分查找出第一个大于指定数的位置（下

标），如果没有找到，返回最后一个数据后面的位置。

举个栗子，啊......快没栗子了。(っ °Д °;)っ


#include<algorithm>
#include<iostream>
 
using namespace std;
 
int main() {
 
    int a[5] = { 1,2,3,3,8 };
    //从 a 数组中找到第一个大于 3 的元素
 
    int   index = upper_bound(a, a + 5, 3)-a;
 
    if   (index==5 ) cout << " not found! ";
    else cout << index;
 
    return   0;
 
}

输出4.

3.binary_search：查找数组内某个元素是否出现。

void binary_search(数组首地址，结束地址，要查找的数)

返回值为bool类型，找到了返回true。

再来一题！

题目：数组线段和M

输入格式

第一行2个正整数N和M，N范围[1，1000000],M范围[1，10^9]。

第二行是N个正整数，每个数范围[1，1000]。

输出格式

一个整数。

输入/输出例子1

输入：

10 20

1 7 10 10 7 10 6 4 6 6

输出：

题解：

这题我是用前缀和的方法解的，因为数据较多，这样快一点,还能变成有序数列。

代码稍稍有点难，大家看着办吧：


#include<bits/stdc++.h>
using namespace std;
int N,M;
int a[1000001];
int main(){
    
    cin>>N>>M;
    cin>>a[0];
    for(int i=1;i<N;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];//求前缀和数组
    }
    int ans=0;
    int mubiao=M;//目标
    for(;int index = lower_bound(a, a + N, mubiao)-a;)
    {
        if(index==N)//找不到了说明没有了
        {
            break;
        }
        if(a[index]==M)
        {
            mubiao=a[index]+1;
        }
        else{
            int fl=a[index]-M;
            int ind=lower_bound(a, a + N, fl)-a;
            if(a[ind]==fl)
                ans++;
            mubiao=a[index]+1;//目标加一，防止重复查找
        }
    }
    cout<<ans;
    
    return 0;
}

思路是找一个比M大的数，如果能找到，那么求出这个数和M的差，再找这个差，如果能找到，那根据前缀和的定义这一串的和就等于M，然后把目标+1，防止重复查找。

Six.list(链表)

常用操作函数：

List.assign() 给list赋值

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

List.begin() 返回指向第一个元素的迭代器

List.clear() 删除所有元素

List.empty() 如果list是空的则返回true

List.end() 返回末尾的迭代器

List.erase() 删除一个元素

List.front() 返回第一个元素

List.get_allocator() 返回list的配置器

List.insert() 插入一个元素到list中

List.max_size() 返回list能容纳的最大元素数量

List.merge() 合并两个list

List.pop_back() 删除最后一个元素

List.pop_front() 删除第一个元素

List.push_back() 在list的末尾添加一个元素

List.push_front() 在list的头部添加一个元素

List.rbegin() 返回指向第一个元素的逆向迭代器

List.remove() 从list删除元素

List.remove_if() 按指定条件删除元素

List.rend() 指向list末尾的逆向迭代器

List.resize() 改变list的大小

List.reverse() 把list的元素倒转

List.size() 返回list中的元素个数

List.sort() 给list排序

List.splice() 合并两个list

List.swap() 交换两个list的内容

List.unique() 删除list中相邻重复的元素

list的定义


list<int> lst1;          //创建一个空list
 
list<int> lst2(10);       //创建一个含有10个元素的list
 
list<int> lst3(3,2);  //创建含有3个元素2的list
 
list<int> lst4(lst2);    //使用lst2初始化lst4
 
list<int> lst5(lst2.begin(),lst2.end());  //同lst4

部分内容与栈那篇差不多，我们不讲。

ヽ(￣ω￣(￣ω￣〃)ゝ今天就到这，大家再见！。

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】