初级STL-关联式容器

废话

想了一下还是在这里写了，博客园没设置好真的就是一股十年前的味道，虽然说我理智上很欣赏这样的商业味道不浓的网站，但是它的UI设计我生理上还是抵触的。可能等我学了JS以后会自己去倒腾一下吧。
另外反正大家都用的是markdown，就算复制粘贴一下也不费事，另外牛客网成功地建立了一个社交关系所以在这里发一发博客还能交流一下。

首先这篇笔记要感谢ZT大佬的帮助，如果不是ZT大佬本菜鸡连课都听不了嘤嘤嘤……
本文基本上来自于https://www.icourse163.org/learn/PKU-1001553023
PKU郭炜老师的《程序设计与算法（一）C语言程序设计》课程，内容实在是良心。

sort

以前都没人告诉过本菜鸡从大到小居然有标准模板可以直接套，本菜鸡以前一直是自己写一个cmp依据函数……

int a[]= {8,5,4,6,7};
sort(a,a+5,greater<int>());//直接用模板

二分查找

前提是数据有序

int a[]= {8,6,5,3,1};
int flag=binary_search(a,a+5,6);//有就返回1 没有就返回0
int flag1=binary_search(a,a+5,6,greater<int>()); //必须和排序依据相吻合

int b[5]= {1,3,5,8,9};    
int *p1=lower_bound(b,b+5,3);
//返回的是一个指针：下标最小的 大于等于[值]的元素地址 下界 
//如果找不到 指向b+5 即范围的右边界 右边界不在查找范围内
int *p2=upper_bound(b,b+5,3);//返回下标最小的 大于[值]的元素地址 上界 
sort(b,b+5,greater<int>());
int *p3=lower_bound(b,b+5,3,greater<int>());
//返回的是按照排序依据，在值后面的，也就是说，这种情况下，返回的是 下标最小的 大于等于[值]的元素地址
cout<<p1-b<<endl;//输出该元素下标

multiset

可以使用multiset set multimap map这样的“排序容器”，它们自带平衡二叉树，在插入的时候就可以排序。
要指向容器里的元素，必须使用【迭代器】，迭代器和指针一样，可以++ -- != ==，但是不能比较大小，不能加减整数，不能相减。这是multiset迭代器的特性，并非所有迭代器都是这样。
声明一个迭代器和别的容器是一样的：

定义

multiset<int>a;
multiset<int>iterator it;
for(it=a.begin();it!=a.end();it++) cout<<*it<<" ";

a.begin()等返回值也是迭代器，另外，multiset不允许像数组那样访问，我猜测这是它的迭代器和别的容器的迭代器不同的原因。

插入

a.insert(x);//插入

寻找

multiset<int>::iterator pi;
pi=a.find(5);//查找有没有5 有就返回迭代器
if(pi==a.end()) cout<<"not found"<<endl;//没有找到就返回a.end的迭代器

二分查找上下界

    multiset<int>::iterator p1,p2;

    p1=a.lower_bound(12);cout<<*p1<<endl;
    //返回>='值'的元素的迭代器 
    p2=a.upper_bound(6);cout<<*p2<<endl;
    //返回>'值'的元素的迭代器 

删除某个元素

a.erase(p1);//删除p1指向的元素 

自定义规则排序的multiset

#include <iostream>
#include <cstring>
#include <set> //使用multiset和set需要此头文件
using namespace std;
struct Rule1 {//这个似乎只能写成这样的结构体 结构体里面居然可以有函数
bool operator()( const int & a,const int & b) const {
return (a%10) < (b%10);
}//返回值为true则说明a必须排在b前面
};
int main() {
    multiset<int, greater<int> > st; //排序规则为从大到小
    int a[10] = {1, 22, 12, 13, 7, 13, 21, 19, 32, 81 };
    for(int i = 0; i < 10; ++i)
        st.insert(a[i]);
    multiset<int, greater<int> >::iterator i;
    for(i = st.begin(); i != st.end(); ++i)
        cout << * i << ",";
    cout << endl;
    multiset<int, Rule1 > st2;//st2的元素排序规则为：个位数小的排前面
    for(int i = 0; i < 10; ++i)
        st2.insert(a[i]);
    multiset<int, Rule1>::iterator p;
    for(p = st2.begin(); p != st2.end(); ++p)
        cout << * p << ",";
    cout << endl;
    p = st2.find(133);//可以找到 13 find的原理在于找不到的值不比它大也不比它小
    cout << * p << endl;
    return 0;
}
//find(x): 在排序容器中找一个元素y，使得“x必须排在y前面”和 “y必须排在x前面”都不成立

#include <iostream>
#include <cstring>
#include <set> //使用multiset和set需要此头文件
using namespace std;
struct Student {
    char name[20];
    int id;
    int score;
};
Student students [] = { {"Jack", 112, 78}, {"Mary", 102, 85},
    {"Ala", 333, 92}, {"Zero", 101, 70}, {"Cindy", 102, 78}
};
struct Rule {
    bool operator() (const Student & s1, const Student & s2) const {
        if( s1.score != s2.score)
            return s1.score > s2.score;
        else
            return (strcmp(s1.name, s2.name) < 0);
    }
};
int main() {
    multiset<Student, Rule> st;
    for(int i = 0; i < 5; ++i)
        st.insert(students[i]); //插入的是students[i]的复制品
    multiset<Student, Rule>::iterator p;
    for(p = st.begin(); p != st.end(); ++p)
        cout << p->score << " " << p->name << " "
             << p->id << endl;
    Student s = { "Mary", 1000, 85};
    p = st.find(s);
    if( p != st.end())
        cout << p->score << " " << p->name << " "
             << p->id << endl;
    return 0;
}

pair 模板

pair<T1,T2>类型等价于：
struct {
T1 first;
T2 second;
};
例如：pair<int, double> a;
等价于：
struct {
int first;
double second;
} a;
a.first = 1;
a.second = 93.93; 

其实pair就是一个对象。而make_pair则可以快速生成一个pair对象

make_pair(5,'d');//无需指出变量类型
make_pair(a.f,b.g);//也可以从结构体里抽调，用途比较广泛

set

set和multiset的区别在于容器里不能有重复元素
a和b重复 等价于 “a必须排在b前面” 和“b必须排在a前面”都不成立

set插入元素可能不成功

#include <iostream>
#include <cstring>
#include <set> //使用multiset和set需要此头文件
using namespace std;
using namespace std;
int main() {
    set<int> st;
    int a[10] = { 1, 2, 3, 8, 7, 7, 5, 6, 8, 12 };
    for(int i = 0; i < 10; ++i)
        st.insert(a[i]);
    cout << st.size() << endl; //输出：8
    set<int>::iterator i;
    for(i = st.begin(); i != st.end(); ++i)
        cout << * i << ","; //输出：1,2,3,5,6,7,8,12,
    cout << endl;
    pair<set<int>::iterator, bool> result = st.insert(2);//一个是迭代器 一个是bool
    if( ! result.second ) //条件成立说明插入不成功
        cout << * result.first << " already exists."<< endl;
    else
        cout << * result.first << " inserted." << endl;
    return 0;
}

multimap

multimap容器里的元素，都是pair形式的

multimap<T1,T2> mp;

则mp里的元素都是如下类型：

struct {
T1 first;  //关键字
T2 second; //值
};

multimap中的元素按照first排序，并可以按first进行查找
缺省的排序规则是 "a.first < b.first" 为true,则a排在b前面

multimap的应用

一个学生成绩录入和查询系统，接受以下两种输入:
Add name id score
Query score
name是个不超过16字符的字符串，中间没有空格，代表学生姓名。id
是个整数，代表学号。score是个整数，表示分数。学号不会重复，分数
和姓名都可能重复。
两种输入交替出现。第一种输入表示要添加一个学生的信息，碰到这
种输入，就记下学生的姓名、id和分数。第二种输入表示要查询，碰到这
种输入，就输出已有记录中分数比score低的最高分获得者的姓名、学号
和分数。如果有多个学生都满足条件，就输出学号最大的那个学生的信
息。如果找不到满足条件的学生，则输出“Nobody”
multimap的应用
输入样例：
Add Jack 12 78
Query 78
Query 81
Add Percy 9 81
Add Marry 8 81
Query 82
Add Tom 11 79
Query 80
Query 81
输出样例：
Nobody
Jack 12 78
Percy 9 81
Tom 11 79
Tom 11 79

#include <iostream>
#include <map> //使用multimap和map需要包含此头文件
#include <cstring>
using namespace std;
struct StudentInfo {
    int id;
    char name[20];
};
struct Student {
    int score;
    StudentInfo info;
};
typedef multimap<int, StudentInfo> MAP_STD;
// 此后 MAP_STD 等价于 multimap<int,StudentInfo>
// typedef int * PINT;
// 则此后 PINT 等价于 int *。 即 PINT p; 等价于 int * p;
int main() {
    MAP_STD mp;
    Student st;
    char cmd[20];
    while( cin >> cmd ) {
        if( cmd[0] == 'A') {
            cin >> st.info.name >> st.info.id >> st.score ;
            mp.insert(make_pair(st.score, st.info ));
        } //make_pair生成一个 pair<int,StudentInfo>变量
//其first 等于 st.score, second 等于 st.info
        else if( cmd[0] == 'Q' ) {
            int score;
            cin >> score;
            MAP_STD::iterator p = mp.lower_bound (score);
            if( p != mp.begin()) {
                --p;
                score = p->first; //比要查询分数低的最高分
                MAP_STD::iterator maxp = p;
                int maxId = p->second.id;
                for(; p != mp.begin() &&
                        p->first == score; --p) {
//遍历所有成绩和score相等的学生
                    if( p->second.id > maxId ) {
                        maxp = p;
                        maxId = p->second.id ;
                    }
                }
                if( p->first == score) {
//如果上面循环是因为 p == mp.begin() 而终止，则p指向的元素还要处理
                    if( p->second.id > maxId ) {
                        maxp = p;
                        maxId = p->second.id ;
                    }
                }
                cout << maxp->second.name << " "
                     << maxp->second.id << " "
                     << maxp->first << endl;
            }
//lower_bound的结果就是 begin，说明没人分数比查询分数低
            else
                cout << "Nobody" << endl;
        }
    }
    return 0;
}

map

不能有关键字重复的元素

可以使用 [ ] ，下标为关键字，返回值为first和关键字相同的元素的second

插入元素可能失败

#include <iostream>
#include <map>
#include <string>
using namespace std;
struct Student {
    string name;
    int score;
};
Student students[5] = {
    {"Jack", 89}, {"Tom", 74}, {"Cindy", 87}, {"Alysa", 87}, {"Micheal", 98}
};
typedef map<string, int> MP;
int main() {
    MP mp;
    for(int i = 0; i < 5; ++i)
        mp.insert(make_pair(students[i].name, students[i].score));
    cout << mp["Jack"] << endl; // 输出 89
    mp["Jack"] = 60; //修改名为"Jack"的元素的second
    for(MP::iterator i = mp.begin(); i != mp.end(); ++i)
        cout << "(" << i->first << "," << i->second << ") ";
//输出：(Alysa,87) (Cindy,87) (Jack,60) (Micheal,98) (Tom,74)
    cout << endl;
    Student st;
    st.name = "Jack";
    st.score = 99;
    pair<MP::iterator, bool> p = mp.insert(make_pair(st.name, st.score));
    if( p.second )
        cout << "(" << p.first->first << ","<< p.first->second << ") inserted" << endl;
    else
        cout << "insertion failed" << endl; //输出此信息
    mp["Harry"] = 78; //插入一元素，其first为"Harry",然后将其second改为78
    MP::iterator q = mp.find("Harry");
    cout << "(" << q->first << "," << q->second << ")" << endl;
//输出 (Harry,78)
    return 0;
}

map例题：单词词频统计程序

输入大量单词，每个单词，一行，不超过20字符，没有空格。按出现次数从多到少输出这些单词及其出现次数。出现次数相同的，字典序靠前的在前面。
输入样例：
this
is
ok
this
plus
that
is
plus
plus
输出样例：
plus 3
is 2
this 2
ok 1
that 1

#include <iostream>
#include <set>
#include <map>
#include <string>
using namespace std;
struct Word {
    int times;
    string wd;
};
struct Rule {
    bool operator () ( const Word & w1, const Word & w2) const {
        if( w1.times != w2.times)
            return w1.times > w2.times;
        else
            return w1.wd < w2.wd;
    }
};
int main() {
    string s;
    set<Word, Rule> st;
    map<string, int> mp;
    while( cin >> s )  mp[s]++ ;
    for( map<string, int>::iterator i = mp.begin();i != mp.end(); i++) {
        Word tmp;
        tmp.wd = i->first;
        tmp.times = i->second;
        st.insert(tmp);
    }
    for(set<Word, Rule>::iterator i = st.begin();i != st.end(); i++)
        cout << i -&g***t;< " " << i -> times << endl;//显示错误 但是编辑界面是正常的
}

成绩排名模板

#include <iostream>
#include <map>
#include <set>
using namespace std;
struct student {
    string name;
    int score;
};
struct Rule {
    bool operator()(const student &s1,const student &s2) {
        if(s1.score==s2.score) return s1.name<s2.name;
        else return s1.score>s2.score;
    }
};
int main() {
    map<string,int>mp;
    set<student,Rule>st;
    string str;
    int num;
    int n;
    cin>>n;
    while(n--) {
        cin>>str>>num;
        mp[str]=num;
    }
    for(map<string,int>::iterator it=mp.begin(); it!=mp.end(); it++) {
        student tmp;
        tmp.name=it->first;
        tmp.score=it->second;
        st.insert(tmp);
    }
    for(set<student,Rule>::iterator it=st.begin(); it!=st.end(); it++) {
        cout<<it->name<<" "<<it->score<<endl;
    }
    st.clear();
    mp.clear();
    return 0;
}