01. set/multiset容器

1.1set/multiset简介

• set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
• set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
• set不可以直接存取元素。（不可以使用at.(pos)与[]操作符）。
• multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
• 不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。
• #include <set>

1.2set/multiset构造器

• set<int> setInt; //一个存放int的set容器。
• set<float> setFloat; //一个存放float的set容器。
• set<string> setString; //一个存放string的set容器。
• multiset<int> mulsetInt; //一个存放int的multi set容器。
• multiset<float> multisetFloat; //一个存放float的multi set容器。
• multiset<string> multisetString; //一个存放string的multi set容器。

#include <iostream>
#include <set>
#include <functional>

using namespace std;

int main()
{
        set<int> seta; //默认是小于比较强less<int>的set
        set<int, greater<int>> setb; //创建一个带大于比较器的set，需要包含头文件functional

        int a[5] = { 1,2,3,4,5 };
        set<int> setc(a, a + 5); //数组初始化一个set
        set<int> setd(setc.begin(), setc.end()); //setc初始化一个set
        set<int> sete(setd); //拷贝构造创建set
        return 0;
}

1.3set/multiset容器常用操作

• s.begin() //返回set容器的第一个元素
• s.end() 　　　　 //返回set容器的最后一个元素
• s.clear() //删除set容器中的所有的元素
• s.empty() 　　　//判断set容器是否为空
• s.insert() //插入一个元素
• s.erase() //删除一个元素
• s.size() 　　　　//返回当前set容器中的元素个数

1.4案例

1.4.1 insert插入

#include <iostream>
#include <set>

using namespace std;

int main()
{
        set<int> s;
        s.insert(1);
        s.insert(5);
        s.insert(4);
        s.insert(2);
        cout << "Test 1" << endl;
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;
        
        s.insert(2); //set只允许相同的值出现一次，要插入相同的值用multiset
        cout << "Test 2" << endl;
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;
        return 0;
}

• 结果

Test 1
1 2 4 5
Test 2
1 2 4 5

1.4.2 erase和clear删除

#include <iostream>
#include <set>

using namespace std;

int main()
{
        set<int> s;
        s.insert(1);
        s.insert(5);
        s.insert(4);
        s.insert(2);
        s.insert(3);
        s.insert(9);
        s.insert(8);
        cout << "Test 1" << endl;
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;
        
        s.erase(4); //根据元素删除
        cout << "Test 2" << endl;
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;
        
        set<int>::iterator ita = s.begin();
        s.erase(ita); //删除迭代器指向位置的元素
        cout << "Test 3" << endl;
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;

        set<int>::iterator itb = s.begin();
        ita = s.begin();
        itb++;
        s.erase(ita,itb);//删除区间[ita,itb)的元素
        cout << "Test 4" << endl;
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;

        s.clear(); //删除所有元素
        cout << "Test 5" << endl;
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;

        return 0;
}

• 结果

Test 1
1 2 3 4 5 8 9
Test 2
1 2 3 5 8 9
Test 3
2 3 5 8 9
Test 4
3 5 8 9
Test 5

1.4.3 find查找

#include <iostream>
#include <set>

using namespace std;

int main()
{
        set<int> s;
        s.insert(1);
        s.insert(5);
        s.insert(4);
        s.insert(2);
        if (s.find(2) != s.end())
        {
                cout << "2 is existent" << endl;
        }
        else
        {
                cout << "2 is non-existent" << endl;
        }
        if (s.find(3) != s.end())
        {
                cout << "3 is existent" << endl;
        }
        else
        {
                cout << "3 is non-existent" << endl;
        }
        return 0;
}

• 结果

2 is existent
3 is non-existent

1.4.4 lower_bound()、upper_bound()、equal_range()

• s.lower_bound() 返回第一个大于或等于给定关键值的元素
• s.upper_bound() 返回第一个大于给定关键值的元素
• s.equal_range() 返回一对定位器，分别表示 第一个大于或等于给定关键值的元素 和 第一个大于给定关键值 的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于 s.end()

#include <iostream>
#include <set>

using namespace std;

int main()
{
        set<int> s;
        s.insert(1);
        s.insert(5);
        s.insert(4);
        s.insert(2);
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
                cout << *it << " ";
        }
        cout << endl;
        cout << "lower_bound & upper_bound test:" << endl;
        cout << "第一个大于或等于3的元素: " << *s.lower_bound(3) << endl;
        cout << "第一个大于或等于2的元素: " << *s.lower_bound(2) << endl;
        cout << "第一个大于2的元素: " << *s.upper_bound(2) << endl;

        cout << "equal_range test:" << endl;

        cout << "第一个大于或等于2的元素: " << *s.equal_range(2).first << endl;
        cout << "第一个大于2的元素: " << *s.equal_range(2).second << endl;
        return 0;
}

• 结果

1 2 4 5
lower_bound & upper_bound test:
第一个大于或等于3的元素: 4
第一个大于或等于2的元素: 2
第一个大于2的元素: 4
equal_range test:
第一个大于或等于2的元素: 2
第一个大于2的元素: 4

1.4.5判断是否为空

#include <iostream>
#include <set>
#include <functional>

using namespace std;

int main() 
{
    set<int > s;
    if (s.empty()) cout << "容器为空" << endl;
    s.insert(1);
    if (!s.empty()) cout << "容器不为空" << endl;

    if (s.count(1)) cout << "1在容器中" << endl;
    if (!s.count(2)) cout << "2不在容器中" << endl;
    return 0;
}

• 结果

容器为空
容器不为空
1在容器中
2不在容器中

1.4.6自定义函数，伪函数

• 尽管函数指针被广泛用于实现函数回调，但C++还提供了一个重要的实现回调函数的方法，那就是函数对象。
• functor，翻译成函数对象，伪函数，算符，是重载了“()”操作符的普通类对象。从语法上讲，它与普通函数行为类似。
• greater<>与less<>就是函数对象。

#include <iostream>
#include <set>
#include <functional>
using namespace std;

struct cmp 
{
    bool operator () (const int& a, const int& b) const
   {
        return a > b;
    }
};
set<int, cmp>s; //自定义排序函数构造set
void setprint(int cnt) {
    cout << "Test output :" << cnt << ":" << endl;
    for (set<int, cmp>::iterator it = s.begin(); it != s.end(); it++)
        cout << *it << " ";
    puts("");
    return;
}
int main() {
    s.insert(1);
    s.insert(2);
    s.insert(6);
    setprint(1);
    return 0;
}

• 结果

Test output :
6 2 1

1.5本章小结

• 容器set/multiset的使用方法
• 红黑树的变体，查找效率高，插入不能指定位置，插入时自动排序。
• functor的使用方法；
• 类似于函数的功能，可用来自定义一些规则，如元素比较规则。
• unordered_set和unordered_multiset，为set和multiset的无序版，使用时要包含头文件#include<unordered_set>

02. map/multimap容器

2.1 map/multimap简介

• map是标准的关联式容器，一个map是一个键值对序列，即(key,value)对。它提供基于key的快速检索能力。
• map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
• map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
• map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。
• multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持[]操作符。
• #include <map>

2.2 map/multimap构造函数

• map/multimap采用模板类实现，对象的默认构造形式：
• map<T1,T2> mapTT;
• multimap<T1,T2> multimapTT;
• 如：
• • map<int, char> mapA;
  • map<string,float> mapB;
• //其中T1,T2还可以用各种指针类型或自定义类型

2.3 map/multimap成员函数

• begin() 返回指向map头部的迭代器
• clear() 删除所有元素
• count() 返回指定元素出现的次数
• empty() 如果map为空则返回true
• end() 返回指向map末尾的迭代器
• equal_range() 返回特殊条目的迭代器对
• erase() 删除一个元素
• find() 查找一个元素
• get_allocator() 返回map的配置器
• insert() 插入元素
• key_comp() 返回比较元素key的函数
• lower_bound() 返回键值>=给定元素的第一个位置
• max_size() 返回可以容纳的最大元素个数
• rbegin() 返回一个指向map尾部的逆向迭代器
• rend() 返回一个指向map头部的逆向迭代器
• size() 返回map中元素的个数
• swap() 交换两个map
• upper_bound() 返回键值>给定元素的第一个位置
• value_comp() 返回比较元素value的函数

2.4使用案例

2.4.1插入

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() 
{
    map<int, string> mapStudent;
    //使用insert和pair插入
    mapStudent.insert(pair<int, string>(1, "student_one"));
    cout << "Test one" << endl;
    for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ":"<< iter->second << " ";
    }
    cout << endl;
    //使用insert函数插入value_type数据
    mapStudent.insert(map<int, string>::value_type(2, "student_two"));
    cout << "Test two" << endl;
    for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ":" << iter->second << " ";
    }
    cout << endl;
    //使用数组方式插入
    mapStudent[3] = "student_three";
    cout << "Test three" << endl;
    for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ":" << iter->second << " ";
    }
    cout << endl;
    return 0;
}

• 结果

Test one
1:student_one
Test two
1:student_one 2:student_two
Test three
1:student_one 2:student_two 3:student_three

• 注意：当然了第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的 插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用数组方式就不同了，它可以覆盖以前该关键字对应的值。
• 判断是否插入成功

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() 
{
    map<int, string> mapStudent;
    pair<map<int, string>::iterator, bool> Insert_Pair;
    Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_one"));
    if (Insert_Pair.second == true)
    {
        cout << "Insert Successfully" << endl;
    }
    else
    {
        cout << "Insert Failure" << endl;
    }
        
    Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_two"));
    if (Insert_Pair.second == true)
    {
        cout << "Insert Successfully" << endl;
    }
    else
    {
        cout << "Insert Failure" << endl;
    }
        
    map<int, string>::iterator iter;
    for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ' ' << iter->second << endl;
    }  
    return 0;
}

• 结果

Insert Successfully
Insert Failure
1 student_one

2.4.2查找

• count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了。
• find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器。

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() 
{
    map<int, string> mapStudent;
    mapStudent.insert(pair<int, string>(1, "student_one"));
    mapStudent.insert(pair<int, string>(2, "student_two"));
    mapStudent.insert(pair<int, string>(3, "student_three"));

    map<int, string>::iterator iter;
    iter = mapStudent.find(1);
    if (iter != mapStudent.end())
    {
         cout << "Find, the value is " << iter->second << endl;
    }
    else
    {
        cout << "Do not Find" << endl;
    }
    return 0;
}

• 结果

Find, the value is student_one

• lower_bound、upper_bound、equal_range函数用法
• Equal_range函数返回一个pair，pair里面第一个变量是Lower_bound返回的迭代器，pair里面第二个迭代器是Upper_bound返回的迭代器，如果这两个迭代器相等的话，则说明map中不出现这个关键字

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() 
{
    map<int, string> mapStudent;

    mapStudent[1] = "student_one";
    mapStudent[3] = "student_three";
    mapStudent[5] = "student_five";

    map<int, string>::iterator iter;
    iter = mapStudent.lower_bound(1);
    //返回的是下界1的迭代器  
    cout << iter->second << endl;

    iter = mapStudent.lower_bound(2);
    //返回的是下界3的迭代器  
    cout << iter->second << endl;

    iter = mapStudent.lower_bound(3);
    //返回的是下界3的迭代器  
    cout << iter->second << endl;

    iter = mapStudent.upper_bound(2);
    //返回的是上界3的迭代器  
    cout << iter->second << endl;

    iter = mapStudent.upper_bound(3);
    //返回的是上界5的迭代器  
    cout << iter->second << endl;

    pair<map<int, string>::iterator, map<int, string>::iterator> mappair;
    mappair = mapStudent.equal_range(2);
    if (mappair.first == mappair.second)
    {
        cout << "Do not Find" << endl;
    }  
    else
    {
        cout << "Find" << endl;
    }
    mappair = mapStudent.equal_range(3);
    if (mappair.first == mappair.second)
    {
        cout << "Do not Find" << endl;
    }
    else
    {
        cout << "Find" << endl;
    }   
    return 0;
}

• 结果

student_one
student_three
student_three
student_three
student_five
Do not Find
Find

2.4.3删除元素

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() 
{
    map<int, string> mapStudent;

    mapStudent.insert(pair<int, string>(1, "student_one"));
    mapStudent.insert(pair<int, string>(2, "student_two"));
    mapStudent.insert(pair<int, string>(3, "student_three"));
    mapStudent.insert(pair<int, string>(4, "student_four"));
    cout << "Test one" << endl;
    for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ":" << iter->second << " ";
    }
    cout << endl;

   //如果要删除1,用迭代器删除  
    map<int, string>::iterator iter;
    iter = mapStudent.find(1);
    mapStudent.erase(iter);
    cout << "Test two" << endl;
    for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ":" << iter->second << " ";
    }
    cout << endl;

    //如果要删除1，用关键字删除  
    int n = mapStudent.erase(2);//如果删除了会返回1，否则返回0  
    cout << "Test three" << endl;
    for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ":" << iter->second << " ";
    }
    cout << endl;
    //用迭代器，成片的删除  
    //一下代码把整个map清空  
    mapStudent.erase(mapStudent.begin(), mapStudent.end());
    cout << "Test four" << endl;
    for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first << ":" << iter->second << " ";
    }
    cout << endl;
    //成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合  
    return 0;
}

• 结果

Test one
1:student_one 2:student_two 3:student_three 4:student_four
Test two
2:student_two 3:student_three 4:student_four
Test three
3:student_three 4:student_four
Test four

2.4.4仿函数的应用

#include <iostream>  
#include <map>  
#include <string>  

using namespace std;

typedef struct tagStudentinfo
{
    int      niD;
    string   strName;
}Studentinfo, * PStudentinfo; //学生信息  

class sort
{
public:

    bool operator() (Studentinfo const& _A, Studentinfo const& _B) const
    {
        if (_A.niD > _B.niD)
            return true;
        if (_A.niD == _B.niD)
            return _A.strName.compare(_B.strName) < 0;
        return false;
    }
};

int main()
{   //用学生信息映射分数  
    map<Studentinfo, int, sort>mapStudent;
    map<Studentinfo, int>::iterator iter;
    Studentinfo studentinfo;
    studentinfo.niD = 1;
    studentinfo.strName = "student_one";
    mapStudent.insert(pair<Studentinfo, int>(studentinfo, 90));

    studentinfo.niD = 2;
    studentinfo.strName = "student_two";
    mapStudent.insert(pair<Studentinfo, int>(studentinfo, 80));

    studentinfo.niD = 3;
    studentinfo.strName = "student_three";
    mapStudent.insert(pair<Studentinfo, int>(studentinfo, 70));

    for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout << iter->first.niD << ":" << iter->first.strName << ":" << iter->second << endl;;
    }
}

• 结果

3:student_three:70
2:student_two:80
1:student_one:90

2.5本章小结

• 容器map/multimap的使用方法
• 红黑树的变体，查找效率高，插入不能指定位置，插入时自动排序。
• functor的使用方法；
• 类似于函数的功能，可用来自定义一些规则，如元素比较规则。
• unordered_map和unordered_multimap，为map和multimap的无序版，使用时要包含头文件#include<unordered_map>