3.4STL

3.4STL

目录
  • 3.4STL
    • 1. STL：stack\queue\set\map\algorithm
    • P1449 后缀表达式
    • P1981 [NOIP2013 普及组] 表达式求值
    • P1996 约瑟夫问题
    • P4715 【深基16.例1】淘汰赛
    • P3378 【模板】堆

1. STL：stack\queue\set\map\algorithm

C++参考手册：https://zh.cppreference.com/

（概念了解即可）STL是Standard Template Library的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。
从根本上说，STL是一些"容器"的集合，这些"容器"有list,vector,set,map等，STL也是算法和其他一些组件的集合。
这里的"容器"和算法的集合指的是世界上很多聪明人很多年的杰作。

STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。
STL是C++的一部分，因此不用安装额外的库文件。
STL是一种泛型编程。面向对象编程关注的是编程的数据方面，而泛型编程关注的是算法。

它们之间的共同点是抽象和创建可重用代码，但它们的理念截然不同。
STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

迭代器部分主要由头文件,和组成。
是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明；
中提供了迭代器使用的许多方法；
以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。

算法部分主要由头文件，和组成。是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，
其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。
体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
中则定义了一些模板类，用以声明函数对象。

C++标准模板库的核心包括以下三个组件：
容器（Containers）：容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 deque、list、vector、map 等。
算法（Algorithms）：算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。
迭代器（iterators）：迭代器用于遍历对象集合的元素。
这些集合可能是容器，也可能是容器的子集。

在C++标准中，STL被组织为下面的13个头文件:

、、、、
、、、、、
、、、。

容器（Containers）:stack/queue/deque/priority_queue/vector/map/set

deque

#include
#include
#include
using namespace std;
int n=10;  deque dque;
int main(){
    for(int i=0; i>x; dque.push_front(x); }//队首添加
    dque.push_back(10); //队尾添加
    dque.pop_back();    //队尾出队
    cout<<"dque.front()="<

priority_queue

#include
#include
#include
#include
using namespace std;
int n=10,a[10]={1,2,3,4,5,6,7,8,9,0};
priority_queue q1;  //默认大顶堆
priority_queue, greater > q2;//小顶堆
priority_queue, less > q3;   //大顶堆
int main() {
    for(int i=0; i

vector & 迭代器（iterators）

#include
#include
#include
using namespace std;
int n=10;   vector v;
int main(){
    cout<<"size="<>x; v.push_back(x); }
    cout<<"size="<::iterator it=v.begin(); it!=v.end(); it++) cout<<*it<<" "; cout<

map:键值对的集合，按照键排序，键是唯一的，即key-value,按key排序

#include
#include
#include
#include
using namespace std;
int n=10,x=2;  map t;
int main(){
    for(int i=0; i>x; t.insert(make_pair(x,i));
    //t.insert(pair(x,i));}
    for(map::iterator it=t.begin(); it!=t.end(); it++){
        cout<first<<":"<second<#include
#include
#include
#include
using namespace std;
int n=10,x=2;  set s;
int main(){
    for(int i=0; i>x; s.insert(x); }
    for(set::iterator it=s.begin(); it!=s.end(); it++) cout<<*it<<" "; cout<#include
#include
using namespace std;
const int N=1e4;
int a[N], n=10, x=2; 
int main(){
    for(int i=0; i>a[i];
    sort(a, a+n); //升序排序
    for(int i=0; iP1449 后缀表达式

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，

所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：3*(5–2)+7 对应的后缀表达式为：3．5．2．-*7．+@。

'@'为表达式的结束符号，'.'为操作数的结束符号。字符串长度在1000内。


输入格式：后缀表达式

输出格式：表达式的值

输入样例：3.5.2.-*7.+@

输出样例：16


#include
using namespace std;
stack sta;  int a,b,c;	char ch;
int main(){
    while((ch=getchar())!='@'){
        if(ch<='9' && ch>='0'){
            a=a*10+ch-'0';
        }else if(ch=='.'){
            sta.push(a);  a=0;
        }else {
            a=sta.top();  sta.pop();  b=sta.top();  sta.pop();
            if(ch=='+'){ c = b+a; }
            else if(ch=='-'){ c = b-a; }
            else if(ch=='*'){ c = b*a; }
            else if(ch=='/'){ c = b/a; }
            sta.push(c);  a=b=0;
        }
    }
    cout<


P1981 [NOIP2013 普及组] 表达式求值


给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。


输入一行需要计算的表达式，表达式中只包含数字、加法运算符‘+’和乘法运算符‘×’，且没有括号，

所有参与运算的数字均为 0 到 pow(2,31)-1之间的整数。输入数据保证这一行只有 0-9、+、× 这12种字符。

输出一个整数，表示这个表达式的值，当答案长度多于4位时，请只输出最后4位，前导0不输出。


输入样例：1+1*3+4

输出样例：8


#include
using namespace std;
stack sta;
int a,b,ans=0, mod=10000;  char ch;
int main() {
    cin>>a;  a %= mod;  sta.push(a);
    while(cin>>ch>>b) {
        b %= mod;
        if(ch=='*') {
            a = sta.top();  sta.pop();
            sta.push(a*b%mod);
        } else if(ch=='+') { sta.push(b); }
    }
    while(!sta.empty()) {
        ans += sta.top();
        ans %= mod;  sta.pop();
    }
    cout<


P1996 约瑟夫问题


n 个人围成一圈，从第一个人开始报数，数到 m 的人出列，

再由下一个人重新从 1 开始报数，数到 m 的人再出圈，

依次类推，直到所有的人都出圈，请输出依次出圈人的编号。


输入格式：输入两个整数 n,m（1≤m,n≤100）。

输出格式：输出一行 n 个整数，按顺序输出每个出圈人的编号。


输入样例：10 3
输出样例：3 6 9 2 7 1 8 5 10 4



#include
using namespace std;
queue que;
int main(){
    int n,m,cnt=1; cin>>n>>m;
    for(int i=1; i<=n; i++) que.push(i);
    while(!que.empty()){
        if(cnt


P4715 【深基16.例1】淘汰赛


有 2^n(n≤7) 个国家参加世界杯决赛圈且进入淘汰赛环节。

我经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。

1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……

晋级后的国家用相同的方法继续完成赛程，直到决出冠军。

给出各个国家的能力值，请问亚军是哪个国家？


输入样例
3
4 2 3 1 10 5 9 7
输出样例
1



#include
#include
#include
#include
using namespace std;
int main() {
    int n; cin>>n; n = pow(2, n); // n=1< > que;
    for(int i=1; i<=n; i++) {
        int a; cin>>a; que.push(make_pair(i, a));
    }
    while( que.size() > 2 ){
        pair x,y;
        x = que.front(); que.pop();
        y = que.front(); que.pop();
        if(x.second > y.second) que.push(x);
        else que.push(y);
    }
    pair x,y;
    x = que.front(); que.pop();
    y = que.front(); que.pop();
    if(x.second > y.second) cout<


P3378 【模板】堆


给定一个数列，初始为空，请支持下面三种操作：


    

  1. 给定一个整数 x，请将 x 加入到数列中。
    2. 

  2. 输出数列中最小的数。
    3. 

  3. 删除数列中最小的数（如果有多个数最小，只删除 1 个）。
    4. 



输入格式：第一行是一个整数，表示操作的次数 n。

接下来 n 行，每行表示一次操作。每行首先有一个整数 op 表示操作类型。

若 op=1，则后面有一个整数 x，表示要将 x 加入数列。

若 op=2，则表示要求输出数列中的最小数。

若 op=3，则表示删除数列中的最小数。如果有多个数最小，只删除 1 个。


输出格式：对于每个操作 2，输出一行一个整数表示答案。


输出样例：
5
1 2
1 5
2
3
2
输出样例：
2
5



#include
#include
using namespace std;
priority_queue, greater > pq;
//priority_queue, less > pq;
int main(){
    int n;  cin>>n;
    for(int i=1; i<=n; i++){
        int f; cin>>f;
        if(f==1){
            int x;  cin>>x;  pq.push(x);
        }else if(f==2){
            cout<
信息学普及组3

相关

标签

一品网 冀ICP备14022925号-6