STL (Standard Template Library) 标准模版库

一、sort 二、二分查找

三、排序容器

1. multiset

• 要 #include;

• 用法1: multiset st;

  • 定义了一个multiset变量st，st里面可以存放T类型的数据，并且能自动排序

  • 排序的规则： 表达式 a<b 为true，则a排在b前面，否则b排a前面 (从小到大)
  • st.insert(i) 添加元素 st.find(i) 查找和i相等的元素，返回值是迭代器 st.erase(i) 删除元素
  • st.begin()返回指向第一个元素的迭代器 st.end()返回指向最后一个元素后面的迭代器

  • st.lower_bound(i)返回指向下界的迭代器 st.upper_bound(i) 返回指向上界的迭代器

• 迭代器（类似指针）

  • 要访问multiset得通过迭代器

  • 定义迭代器 multiset::iterator p;

  • p是迭代器，用于指向multiset中的元素。

  • 迭代器可++，--，！=，==。 但是不可以加减一个整数，也不可以相减、比大小。

#include<iostream>
#include<set>
using namespace std;
int main()
{
    int a[10] = {1,14,13,23,18,42,8,7,8,6},i;
    multiset<int> st;
    for(i = 0;i < 10;i++)
        st.insert(a[i]); //插入的只是复制品
    multiset<int>::iterator p; //p是迭代器
    for(p = st.begin();p != st.end();p++)
    {
        cout << *p << ","; //输出 1,6,7,8,8,13,14,18,23,42,
    }
    p = st.find(12); // 找不到，返回st.end() //如果找到则返回指向该元素的迭代器
    if(p == st.end())
    {
        cout<<"not found"<<endl;
    }

    p = st.lower_bound(12);
    cout<< *p << endl; //输出13
    cout<< *st.upper_bound(8) <<endl; //输出13
    st.erase(13);
    cout << *st.upper_bound(8) << endl; //输出14
    return 0;
}

• 用法2: multiset<T,greater>

  • 与用法一相反，从大到小排
  • greater后不加括号

• 用法3: multiset<T,Rule>

  • Rule是自定义排序规则的结构名

  • 与sort以及二分查找部分的区别是：Rule后不加括号

#include<iostream>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;

struct Student
{
    char name[20];
    int score;
};
struct Rule //先按分数从高到底，分数相同则名字按字典序排
{
    bool operator()(const Student &a1,const Student &a2)
    {
        if(a1.score != a2.score)
            return a1.score > a2.score;
        else
            return (strcmp(a1.name,a2.name) < 0);
    }
};

int main()
{
    int i ;
    multiset<Student,Rule> st;
    Student a[5] ={ {"Alier",78},{"Mestry",66},{"Jane",87},
                    {"Hebe",93},{"Arre",87}};
    for(i = 0;i < 5;i++)
    {
        st.insert(a[i]);
    }
    multiset<Student,Rule>::iterator p;
    for(p = st.begin();p != st.end();p++)
    {
        cout << p->score << " "<< p->name << endl;
    }
    return 0;
}
/*输出
93 Hebe
87 Arre
87 Jane
78 Alier
66 Mestry */

2. set

• 与multiset的区别

  • set不能有重复元素（重复的意思是按照排序规则是相等的）

  • insert插入可能失败（因为可能插入的元素已经存在）

  • insert返回值是 pair< set::iterator , bool > ,如果插入成功则返回指向插入的元素的迭代器，bool为true；插入失败返回的迭代器指向的是与插入元素相同的元素的位置，bool为false

struct Student
{
    char name[20];
    int score;
};
struct Rule //先按分数从高到底，分数相同则名字按字典序排
{
    bool operator()(const Student &a1,const Student &a2)
    {
        if(a1.score != a2.score)
            return a1.score > a2.score;
        else
            return (strcmp(a1.name,a2.name) < 0);

    }
};
int main()
{
    set<int> st;
    int a[10] = {1,14,13,23,18,42,8,7,8,7},i;
    for(i = 0;i < 10;i++)
        st.insert(a[i]);
    cout << st.size() << endl; // 输出8 因为数组里有两个7两个8
  
    set<Student,Rule> t;
    Student s[6] ={ {"Alier",78},{"Mestry",66},{"Jane",87},
                    {"Hebe",93},{"Arre",87},{"Arre",87} };
    pair<set<Student,Rule>::iterator,bool> result;
  /*相当于 sturct { 
                    set<Student,Rule>::iterator first
                    bool second
}*/
    for(i = 0;i < 6;i++)
    {
        result = t.insert(s[i]);
        if(!result.second)
        {
            cout << result.first->score << " " << result.first->name << " has existed"<< endl;
        }
        else
        {
            cout << result.first->score << " " << result.first->name << " inserted" << endl;
        }
    }
    return 0;
}
/* 输出
8
78 Alier inserted
66 Mestry inserted
87 Jane inserted
93 Hebe inserted
87 Arre inserted
87 Arre has existed */

• pair

pair<T1,T2> a;      //T1 T2指的是类型
等价于
  struct 
  {
    T1 first;
    T2 second;
  }