C++ STL学习笔记之Set、Map
2020 年 07 月 10 日 311 1835 字 暂无评论

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_setunordered_multiset,为setmultiset的无序版,使用时要包含头文件#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
  • multimapmap的区别: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函数返回一个pairpair里面第一个变量是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_mapunordered_multimap,为mapmultimap的无序版,使用时要包含头文件#include<unordered_map>

版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/106/



评论已关闭