【c++】set、map用法详解

set、map用法详解

• 1. 关联式容器
• 2. 键值对
• • 2.1 ：pair
  • 2.2：make_pair
  • 3. 树形结构的关联式容器
  • • 3.1：set
    • • 构造函数
      • find()
      • erase()
      • insert()
      • count()
      • lower_bound()
      • upper_bound()
      • 3.2：multiset
      • 3.3：map
      • • 构造函数
        • insert()
        • operator[]
        • 3.4：multimap
        • 4. 在Oj中的使用
        • • 4.1：前K个高频单词
          • 4.2：两个数组的交集I

            1. 关联式容器

            1. 序列式容器：vector、list、deque、forward_list等这些容器统称为序列式容器，底层是线性序列的数据结构，存储的是元素本身。插入方式一般为push。
            2. 关联式容器：set、map、multiset、multimap等这些容器统称为关联式容器，也是用来存储数据，但存储的是结构的键值对，数据检索的效率比序列式容器高。插入方式一般为insert。

            2. 键值对

            2.1 ：pair

            概念：用来表示具有一一对应关系的一种结构，这种结构中一般存储两个成员变量key和value，key表示键值，value表示与key对应的信息。eg:英汉词典、单词的个数。

            • pair中的first为key，second为value。

              2.2：make_pair

              • 概念：是一种可用来构造pair类型对象的函数模板。
              • 参数x用来初始化pair中第一个元素的值，参数y用来初始化pair中第二个元素的值。make_pair(x, y)返回值为pair(x, y)，为匿名对象。

                3. 树形结构的关联式容器

                1. STL中总共有两种不同结构的管理式容器：树形结构和哈希结构。
                2. 树形结构的关联式容器主要有四种：set、multiset、map、multimap，共同特征：底层为平衡二叉树(红黑树），容器中的元素是有序序列。

                3.1：set

                1. set是按特定顺序存储唯一元素的容器。使用迭代器遍历set中的元素，进行中序遍历，可以得到一个有序序列。
                2. set具有排序+去重的功能。set中元素必须不能重复，可以用set进行去重。set中元素类型为const T，所以set中的元素不能被修改，但可以在容器中插入或者删除他们。
                3. set中元素value就是key，所以set在插入元素时，只需要插入value即可，不需要构造键值对。与map、multimap不同，map、multimap中存储的是键值对，set中只存储value，但在底层中实际存放的是由构成的键值对。
                4. 在默认情况下，set中仿函数为less，元素是按照小于来比较，元素呈升序进行排序。set在底层使用平衡二叉搜索树(红黑树)来实现，所以set查找某个元素时，时间复杂度为O(logn)。
                5. set容器通过key访问单个元素的速度通常比unordered_set容器慢，允许根据顺序直接对子集进行迭代，即：因为set的有序性，当你迭代一个set时，会按照元素被添加到集合中的顺序看到它们。

                构造函数

                set s1；

                • 功能：无参构造。构造空的set。

                  set s2( InputIterator first, InputIterator last ) ；

                  • 功能：迭代器区间构造。构造与[first, last)范围一样多元素的对象。

                    set s3(const set& s2) ；

                    • 功能：拷贝构造函数。

                      #pragma once#define _CRT_SECURE_NO_WARNINGS 1#include#includeusing namespace std;int main(){set s1;  //无参构造//注意set:排序 + 去重int a[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; set s2(a, a + sizeof(a) / sizeof(int));  //迭代器区间构造set s3(s2);  //拷贝构造auto it = s2.begin();while (it != s2.end()) //用迭代器进行遍历，中序遍历，升序序列{cout cout int a[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; setcout cout cout int a[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; setcout int a[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; setcout cout int a[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; setcout cout int a[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; setcout cout int a1[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; setcout  10, 11, 10, 8, 6 };s1.insert(a2, a2 + sizeof(a2) / sizeof(int));for (auto& e : s1){cout int a1[] = { 6, 3, 4, 2, 1, 6, 4, 5, 2}; setcout int a1[] = { 6, 3, 4, 2, 1, 6, 6, 4, 4, 5, 2}; multisetcout cout cout map {"sort", "排序"},{"left", "左"}, {"remove", "去除"}, {"right", "右"} };mapcout cout map "appeal", "吸引" };m.insert(p);  //有名对象m.insert(pair "big", "大的" });//c++98m.insert(make_pair("thing", "事情")); //make_pair构造pair类型对象for (auto& e : m){cout mapcout cout //统计水果的个数map "苹果", "香蕉", "梨子", "苹果", "苹果", "香蕉", "草莓" };for (auto& e : a) {auto it = m1.find(e);  //方法1if (it != m1.end())it-second++;elsem1.insert({ e, 1 });}for (auto& e : m1){cout m2[e]++;  //方法2}for (auto& e : m2){cout pair {"sort", "排序"}, {"left", "左"}, {"right", "右"},{"sort", "xxx"} ,{"left", "???"} };multimapcout cout cout public:    template    public:        bool operator()(const T& p1, const T& p2)        {            return p1.second  p2.second || (p1.second == p2.second && p1.first