STL常见用法总结

本篇旨在记载STL一些常见函数及用法以备记忆

栈容器 stack

用法：

头文件：#include<stack>

• empty() 堆栈为空则返回真
• pop() 移除栈顶元素
• push() 在栈顶增加元素
• size() 返回栈中元素数目
• top() 返回栈顶元素

初始化： stack<int> s

示例：简单计算器

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
stack<char> op; //符号栈
stack<float> num; //数字栈

float cal(float num1, float num2, char op)
{
    if (op == '+')
        return num1 + num2;
    else if (op == '-')
        return num2 - num1;
    else if (op == '*')
        return num2 * num1;
    else if (op == '/')
        return num2 / num1;
}
int main()
{
    string s;
    while (cin >> s && s != "0") //读入一行表达式
    {
        //cout<<"开始处理"<<endl;
        for (float i = 0; i < s.length(); i++)
        {
            if (s[i] == '+' || s[i] == '-')
            {
                // cout<<s[i]<<endl;
                while (!op.empty())
                {
                    char tmpop = op.top();
                    op.pop();
                    float num1 = num.top();
                    num.pop();
                    float num2 = num.top();
                    num.pop();
                    float calnum = cal(num1, num2, tmpop);
                    num.push(calnum);
                }

                op.push(s[i]);
            }
            else if (s[i] == '*' || s[i] == '/')
            {
                if (!op.empty())
                {
                    while (op.top() != '+' && op.top() != '-')
                    {
                        char tmpop = op.top();
                        op.pop();
                        float num1 = num.top();
                        num.pop();
                        float num2 = num.top();
                        num.pop();
                        float calnum = cal(num1, num2, tmpop);
                        num.push(calnum);
                    }
                }

                op.push(s[i]);
            }
            else
            {
                // cout<<"处理数字"<<s[i]<<endl;
                //输入字符  转数字

                float sum = 0;
                while (s[i] != '+' && s[i] != '-' && s[i] != '*' && s[i] != '/' && i < s.length())
                {
                    sum = sum * 10 + (s[i] - '0');
                    //  cout<<sum<<endl;
                    i++;
                }
                i--;
                //cout << "sum=" << sum << " "<<endl;
                num.push(sum); //存数字
            }
        }
        // cout<<"op栈大小"<<op.size()<<endl;
        //根据op栈处理num栈
        while (!op.empty())
        {
            char tmpop = op.top();
            op.pop();
            float num1 = num.top(); cout<<"num1="<<num1<<endl;
            num.pop();
            float num2 = num.top(); cout<<"num2="<<num2<<endl;
            num.pop();
            float calnum = cal(num1, num2, tmpop);
            num.push(calnum);
        }
        printf("%.2f\n",num.top());
    }
}

优先队列-实现堆 （应用：哈夫曼树）

使用之前的预处理：
include<queue>

利用语句：priority_queue<int> Q; 建立一个保存元素为int的堆Q，默认为大根堆

利用语句：priority_queue<int,vector<int>,greater<int> > Q; 定义小根堆

关于堆的操作如下：

Q.push(x); 将元素x放入堆Q中

Q.top(); 取出堆顶元素

Q.pop(); 弹出堆顶元素，取出后堆会自动调整为一个新的小顶堆

例：

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    priority_queue<int, vector<int>, greater<int> > Q;
    int n;
    while (cin >> n)
    {
        while (!Q.empty())
            Q.pop();
        int a;
        for (int i = 0; i < n; i++)
        {
            cin >> a;
            Q.push(a);
        }
        int ans=0;
        while(Q.size() >1)  //不算入根节点，最后一个节点为根节点
        {
            int a1=Q.top();
            Q.pop();
            int a2=Q.top();
            Q.pop();
            ans+=a1+a2;
            Q.push(a1+a2);
        }
        cout<<ans<<endl;
    }
    return 0;
}

map

map<string,int> M;//定义一个完成从string到int映射的map
M.clear();//清空一个map
M.find(b);//确定map中是否保存string对象b的映射，若没有函数返回M.end()
M[b]=idx;//若map中不存在string对象b的映射，则定义其映射为b映射为idx
idxb=M[b];//若map中存在string对象b的映射，则读出该映射

样例输入

3
Alice Bob Smith John Alice Smith
5
a c c d d e b e a d 
0

样例输出

Yes 
No

代码

#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string, int> arr;
int in[2002];
int main()
{
    int n;
    while (cin >> n && n)
    {
        for (int i = 0; i < 2 * n; i++) //n组胜负关系，至多存在n个队伍
            in[i] = 0;
        string a, b;
        arr.clear();//对map中的映射关系清空
        int idx=0;//下一个被映射的数字
        while (n--)
        {
            cin >> a >> b;
            int idxa,idxb;
            if (arr.find(a) == arr.end())//若尚无对a的映射
            {
               idxa=idx;
               arr[a]=idx++;//设定其映射为idx，并递增idx
            }
            else idxa=arr[a];//否则直接读出该映射
            if(arr.find(b)==arr.end())
            {
                idxb=idx;
                arr[b]=idx++;
            }
            else idxb=arr[b];
            in[idxb]++;//b的入度递增
        }
        int cnt=0;
        for(int i=0;i<idx;i++)
        {
            //确定所有映射数字的入度，统计入度为0的个数
            if(in[i]==0)
              cnt++;
        }
        if(cnt==1) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}