紫书: STL 代码例子展示

紫书的代码的展示，为了能清晰的进行学习和比对

集合：set

更多请查看：https://www.cnblogs.com/ChinaHook/p/6985444.html和
http://c.biancheng.net/view/545.html（c语言中文网multiset）http://c.biancheng.net/view/535.html（c语言中文网set）

以下为字符函数库中常用的函数：

--------#include <cctype>的函数
c++中应该是#include <cctype>
c中应该是#include <ctype.h>
函数名称返回值
isalnum() 如果参数是字母数字，即字母或数字，该函数返回true
isalpha() 如果参数是字母，该函数返回真
isblank() 如果参数是空格或水平制表符，该函数返回true
iscntrl() 如果参数是控制字符，该函数返回true
isdigit() 如果参数是数字（0～9），该函数返回true
isgraph() 如果参数是除空格之外的打印字符，该函数返回true
islower() 如果参数是小写字母，该函数返回true
isprint() 如果参数是打印字符（包括空格），该函数返回true
ispunct() 如果参数是标点符号，该函数返回true
isspace() 如果参数是标准空白字符，如空格、进纸、换行符、回车
水平制表符或者垂直制表符，该函数返回true
isupper() 如果参数是大写字母，该函数返回true
isxdigit() 如果参数是十六进制的数字，即0～9、a_f、AF，该函数返回true
tolower() 如果参数是大写字符，则返回其小写，否则返回该参数
toupper() 如果参数是小写字母，则返回其大写，否则返回该参数

set和multset的函数

特殊的搜寻函数：
count (elem)
返回元素值为elem的个数
find(elem)
返回元素值为elem的第一个元素，如果没有返回end()
lower _bound(elem)
返回元素值为elem的第一个可安插位置，也就是元素值 >= elem的第一个元素位置
upper _bound (elem)
返回元素值为elem的最后一个可安插位置，也就是元素值 > elem 的第一个元素位置
equal_range (elem)
返回elem可安插的第一个位置和最后一个位置，也就是元素值==elem的区间

迭代器相关函数
c.begin()
返回一个随机存取迭代器，指向第一个元素
c.end()
返回一个随机存取迭代器，指向最后一个元素的下一个位置
c.rbegin()
返回一个逆向迭代器，指向逆向迭代的第一个元素
c.rend()
返回一个逆向迭代器，指向逆向迭代的最后一个元素的下一个位置

安插和删除函数：
c.insert(elem)
插入一个elem副本，返回新元素位置，无论插入成功与否。
c.insert(pos, elem)
安插一个elem元素副本，返回新元素位置，pos为收索起点，提升插入速度。
c.insert(beg,end)
将区间[beg,end)所有的元素安插到c，无返回值。
c.erase(elem)
删除与elem相等的所有元素，返回被移除的元素个数。
c.erase(pos)
移除迭代器pos所指位置元素，无返回值。
c.erase(beg,end)
移除区间[beg,end)所有元素，无返回值。
c.clear()
移除所有元素，将容器清空

例5-3安迪的第一个字典（uva10815）

#include<cstdio>
#include<algorithm>
#include<iostream> 
#include<cstring>
#include<sstream>
#include<set>
using namespace std;
set<string>dict;

int main(){
    string s,buf;
    while(cin>>s){
        for(int i=0;i<s.length();i++)
        if(isalpha(s[i]))
            s[i]=tolower(s[i]);
        else s[i]=' ';
        stringstream ss(s);
        while(ss>>buf) dict.insert(buf);
    }
    for(set<string>::iterator it=dict.begin();it!=dict.end();++it)
        cout<<*it<<"\n";
    return 0;
}

映射：map

例5-4反片语(uva156)

题意：输入一些单词,找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中的大小写，按字典序进行排序。
做题思路：先输入单词，（利用vector），先把单词中的大写全部转化成小写，然后把单词中的每个字母都排序一遍，然后放进<map>里进行统计。如果只出现一次就输出（转自https://blog.csdn.net/hoaresky1998/article/details/51351588）

#include<cstdio>
#include<algorithm>
#include<iostream> 
#include<cstring>
#include<vector>
#include<map>
#include<cctype>
using namespace std;

map<string,int>cnt;
vector<string>words;

//将单词标准化（全部转化成小写并排序）
string repr(const string& s){
    string ans=s;
    for(int i=0;i<ans.length();i++)
        ans[i]=tolower(ans[i]);
    sort(ans.begin(),ans.end()) ;
    return ans;
} 

int main(){
    int n=0;
    string s;
    while(cin>>s){
        if(s[0]=='#')break;
        words.push_back(s);
        string r=repr(s);
        if(!cnt.count(r))cnt[r]=0;
        cnt[r]++;
    } 
    vector<string>ans;
    for(int i=0;i<words.size();i++)
        if(cnt[ repr( words[i] ) ] ==1) 
            ans.push_back(words[i]);
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<"\n";
    return 0;
}

结果：

图片.png

栈

例5-5.集合栈计算机(uva12096)

洛谷地址：
https://www.luogu.org/problemnew/show/UVA12096

思路：对于集合的集合，我们很难直接表示，因此，我们可以换一种想法，既然集合的集合难以表示，我们就只需要给每种集合一个唯一的ID就可以了，这样，集合中的元素就可以通过ID来表示。一个集合就可以表示为一个set<int>
在这里，我们使用STL中的set进行表示，就会容易很多，加入栈中的元素也就可以是int类型了。
在进行操作时，我们可以用map将每种集合与对应的ID关联起来，这样做既可以完成查找ID的任务，还可以同时判定是否出现了新的集合。
我们可以用vector作为存储每种集合的cache，这样，每当map中没有相应的ID时，我们就向vector中加入一个set<int>元素，并将下标作为ID进行唯一的标识。
使用vector将set存储起来的好处是，反过来我们也可以用ID查询到对应的set，这样，通过map和vector，我们实现了set 到ID 的双射。
最后，输出栈顶集合的size属性，即可。（来自https://www.cnblogs.com/luruiyuan/p/5782852.html）

typedef set<int>Set;
    map<Set,int> IDcache;//把集合映射成id
    vector<Set> Setcache;//根据id取集合

//查找给定集合x的id，如果找不到，分配一个新的id
int ID(Set x)
{
    if(IDcache.count(x))return IDcache[x];
    Setcache.push_back(x);//添加新集合
    return IDcache[x]=Setcache.size()-1;
}

对任意集合S，IDcache[s]就是它的ID，而Setcache[IDcache[s]]就是s本身。
下面是ALL,INS两个宏

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

分别表示“所有的内容”，和“插入迭代器”，以下是主程序

    int n;
    stack<int>s;
    cin>>n;
    for(int i=0;i<n;i++){
        string op;
        cin>>op;
        if(op[0]=='P')s.push(ID(Set()));
        else if(op[0]=='D')s.push(s.top());
        else {
            Set x1=Setcache[s.top()];s.pop();
            Set x2=Setcache[s.top()];s.pop();
            Set x;
            if(op[0]=='U')set_union(ALL(x1),ALL(x2),INS(x));
            if(op[0]=='I')set_intersection(ALL(x1),ALL(x2),INS(x));
            if(op[0]=='A'){x=x2;x.insert(ID(x1));}
            s.push(ID(x));
        }
        cout<<Setcache[s.top()].size()<<endl;
    }

以下是整个程序：

#include<cstdio>
#include<algorithm>
#include<iostream> 
#include<map>
#include<vector>
#include<set>
#include<stack> 
using namespace std;
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
typedef set<int>Set;
    map<Set,int> IDcache;//把集合映射成id
    vector<Set> Setcache;//根据id取集合

//查找给定集合x的id，如果找不到，分配一个新的id
int ID(Set x)
{
    if(IDcache.count(x))return IDcache[x];
    Setcache.push_back(x);//添加新集合
    return IDcache[x]=Setcache.size()-1;
}
     
int main(){
    int n,t;
    cin>>t;
    while(t--){
    stack<int>s;
    cin>>n;
    for(int i=0;i<n;i++){
        string op;
        cin>>op;
        if(op[0]=='P')s.push(ID(Set()));
        else if(op[0]=='D')s.push(s.top());
        else {
            Set x1=Setcache[s.top()];s.pop();
            Set x2=Setcache[s.top()];s.pop();
            Set x;
            if(op[0]=='U')set_union(ALL(x1),ALL(x2),INS(x));
            if(op[0]=='I')set_intersection(ALL(x1),ALL(x2),INS(x));
            if(op[0]=='A'){x=x2;x.insert(ID(x1));}
            s.push(ID(x));
        }
        cout<<Setcache[s.top()].size()<<endl;
    }
    cout<<"***"<<endl;
}
    return 0;
}

结果
预期结果：

来自洛谷https://www.luogu.org/problemnew/show/UVA12096

样例1：

图片.png

样例2：

图片.png

队列

例5-6.团体队列（uva540）

#include<cstdio>
#include<algorithm>
#include<iostream> 
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxt=1000+10;

int main(){

    int t,kase=0;
    while(scanf("%d",&t)==1&&t){
        printf("Scenario #%d\n",++kase);
        
        //记录所有人的团队编号
        map<int ,int>team;
        for(int i=0;i<t;i++){
            int n,x;
            scanf("%d",&n);
            while(n--){
                scanf("%d",&x);
                team[x]=i;
            }
        }
        
        //模拟
        queue<int>q,q2[maxt];//分别是团队序列和团队成员的序列
        for(;;){
            int x;
            char cmd[10];
            scanf("%s",cmd);
            if(cmd[0]=='S')break;
            else if(cmd[0]=='D'){
                int t=q.front();
                printf("%d\n",q2[t].front());
                q2[t].pop();
                if(q2[t].empty())q.pop();//团体t全体出队列 
            }
            else if(cmd[0]=='E'){
                scanf("%d",&x);
                int t=team[x];
                if(q2[t].empty())q.push(t);//团队t进入队列
                q2[t].push(x); 
            }
        } 
        printf("\n");
        } 
    return 0;
}

样例1：

图片.png

样例2：

图片.png

优先队列

例5-7.丑数

丑数：不能被除2,3,5之外的其他素数整除的数
生成第1500个丑数

#include<cstdio>
#include<algorithm>
#include<iostream> 
#include<set>
#include<queue>
using namespace std;

typedef long long ll;
const int coeff[3]={2,3,5};

int main(){
    priority_queue<ll,vector<ll>,greater<ll> >pq;
    set<ll>s;
    pq.push(1);
    s.insert(1);
    for(int i=1;;i++){
        ll x=pq.top();
        pq.pop();
        if(i==1500){
            cout<<"The 1500'th ugly number is "<<x<<".\n";
            break;
        }
        for(int j=0;j<3;j++){
            ll x2=x*coeff[j];
            if(!s.count(x2)){
                s.insert(x2);
                pq.push(x2);
            }
        }
    }
    return 0;
}

结果：