【C++】容器篇(五)—— map和set的基本介绍

简介: 【C++】容器篇(五)—— map和set的基本介绍

序言:

在之前,我们已经对STL中的 序列式容器 进行了相关的学习。本期,我将给大家介绍的则是另外一类容器 —— 关联式容器 !!!




(一)容器回顾

在初阶阶段,我们已经接触过STL中的部分容器,比如:vector、list、deque、forward_list 等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别?

 

接下来,我先带大家回顾一下有关容器的一些基本知识,帮助大家唤醒一些“远古”的记忆!

容器可以用于存放各种类型的数据(基本类型的变量,对象等)的数据结构,都是模板类:分为顺序容器、关联式容器、容器适配器三种类型,三种类型容器特性分别如下:

 

💨【顺序容器】

容器并非排序的,元素的插入位置同元素的值无关。包含 vector、deque、list,具体实现原理如下:

(1)vector 头文件

  • 动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。

(2)deque 头文件

  • 双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(仅次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间)

(3)list 头文件

  • 双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

💨【关联式容器】

而本期将要介绍的 关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高


元素是排序的;插入任何元素,都按相应的排序规则来确定其位置;在查找时具有非常好的性能;

通常以平衡二叉树的方式实现。包含set、multiset、map、multimap,具体实现原理如下:

(1)set/multiset 头文件

  1. set 即集合。set中不允许相同元素,multiset中允许存在相同元素。

(2)map/multimap 头文件

  1. map与set的不同在于map中存放的元素有且仅有两个成员变量,一个名为first,另一个名为second;
  2. map根据first值对元素从小到大排序,并可快速地根据first来检索元素。

💨【容器适配器】

封装了一些基本的容器,使之具备了新的函数功能,比如把deque封装一下变为一个具有stack功

能的数据结构。这新得到的数据结构就叫适配器。包含stack,queue,priority_queue,具体实现原

理如下:

(1)stack 头文件

  • 栈是项的有限序列,并满足序列中被删除、检索和修改的项只能是最进插入序列的项(栈顶的
  • 项);
  • 后进先出

(2)queue 头文件

  • 队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行;
  • 先进先出

(3)priority_queue 头文件

  • 优先级队列。内部维持某种有序,然后确保优先级最高的元素总是位于头部。最高优先级元素总是第一个出列

(二)键值对

在C++中,键值对是一种常见的数据结构,它将一个唯一的键与一个值相关联。提供了一种高效的方式来存储和检索数据。该结构中一般只包含两个成员变量keyvalue,key代表键值,value表示与key对应的信息。

 

【场景】

比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该单词,在词典中就可以找到与其对应的中文含义.

 

键值对的定义可以采用不同的数据结构或语法表示,具体取决于所使用的编程语言或数据格式。

以下是一些常见的定义方式:

  • C++关联容器示例:
std::map<std::string, int> myMap;
myMap["apple"] = 10;
myMap["banana"] = 5;
  • JSON格式示例:
{
  "name": "John",
  "age": 30,
  "city": "New York"
}
  • Python字典示例:
my_dict = {"key1": "value1", "key2": "value2", "key3": "value3"}
  • JavaScript对象示例:
var myObject = { key1: "value1", key2: "value2", key3: "value3" };

【说明】

  1. 在以上示例中,“key1”、“key2"等都是键,对应的"value1”、"value2"等是对应的值;
  2. 你可以使用键值对来存储、访问和处理各种数据,根据具体编程语言和数据结构的不同,提供了丰富的函数和操作来操作和处理键值对。

而在SGI-STL中关于键值对的定义如下:

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    pair():
     first(T1())
    , second(T2())
    {}
    pair(const T1& a, const T2& b): 
    first(a)
    , second(b)
    {}
};

(三)树形结构的关联式容器

  1. 根据应用场景的不桶,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构;
  2. 树型结构的关联式容器主要有四种:map、set、multimap、multiset;
  3. 这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。

下面一依次介绍每一个容器:

 

1、set

1️⃣基本介绍

简单点来说 set是按照一定次序存储元素的容器,且set中的元素不可以重复。具体的大家可以参照文档进行相应的学习。

 

2️⃣set的使用

set的模板参数列表:

 

【说明】

  1. T: set中存放元素的类型,实际在底层存储<value, value>的键值对。
  2. Compare:set中元素默认按照小于来比较
  3. Alloc:set中元素空间的管理方式,使用STL提供的空间配置器管理

接下来,我们简单的来使用下 set:

void test_set1()
{
  set<int> s1;
  s1.insert(3);
  s1.insert(1);
  s1.insert(4);
  s1.insert(2);
  s1.insert(1);
  s1.insert(2);
  set<int>::iterator it1 = s1.begin();
  while (it1 != s1.end())
  {
    cout << *it1 << " ";
    ++it1;
  }
  cout << endl;
}

输出展示:

 

 

【说明】

  1. 首先,我们可以使用迭代器对其进行操作;
  2. 其次,我们验证了上述所说的  set中的元素不可以重复,可以发现结果自动进行了去重的操作

紧接着,此时我们就会想,既然可以使用迭代器,那么我们就可以知道 范围for 也可以使用:

 


有的小伙伴可能不知道迭代器和范围for的联系,接下来我简单的描述一下:

迭代器 和 范围for循环 都是在 C++ 中用于遍历容器(如数组、向量、映射等)中的元素的工具。它们之间存在联系和互补关系。

  1. 迭代器:迭代器是一个对象,用于遍历容器中的元素序列。通过迭代器,可以逐个访问容器中的元素,并进行增加、删除、修改等操作。C++ 标准库提供了多种类型的迭代器,如 begin()end() 返回的迭代器可以表示容器的起始和结束位置。迭代器可以使用 * 运算符来访问当前位置的值,也可以使用 ++ 运算符来移动到下一个位置。
  2. 范围for循环:范围for循环是一种简洁的语法形式,用于遍历容器中的元素。它可以自动处理迭代器的创建和递增,并以一种更直观的方式对容器中的元素进行访问。范围for循环的语法是 for (element : container),其中 element 是用于存储当前元素的变量,container 是要遍历的容器。在每次循环迭代中,element 会被赋值为容器中的下一个元素,直到遍历完所有元素。

迭代器和范围for循环的联系在于,范围for循环在内部使用迭代器来实现对容器的遍历。范围for循环抽象了迭代器的创建和递增过程,使得代码更加简洁和易读。范围for循环适用于大多数情况下对容器进行遍历,并且不需要修改容器中的元素。而当需要更精细的控制和操作时,迭代器提供了更灵活的功能。


紧接着,在文档中介绍了 set中的元素不能在容器中修改。举例来验证一下:

【说明】

  1. 从上述图片中不难发现在C++的set容器中,元素不允许直接修改;
  2. set是一个有序的集合容器,它通常基于红黑树实现。红黑树是一种平衡二叉搜索树,用于维护元素的有序性。为了保持树的平衡和有序,set 中的元素在插入时按照特定规则被插入到合适的位置,并且不允许直接修改。
  3. 具体而言,当你在set 中插入一个元素时,该元素会被自动插入到正确的位置,以保持集合的有序性。红黑树的平衡性是通过左旋、右旋以及颜色调整等操作来维护的。直接修改元素的值可能导致元素位置不再准确,破坏了红黑树的性质,进而影响整个集合的有序性。
  4. 因此,在set 中,如果你需要修改一个元素,你需要先将该元素从集合中删除,然后再重新插入修改后的值。

【注意】

  • 如果你需要对集合中的元素进行频繁的修改操作,可能 set 并不是最适合的容器选择;
  • 相应地,可以考虑使用 unordered_set容器,它基于哈希表实现,并提供了快速的查找和修改元素的能力;
  • unordered_set中,元素的位置是根据哈希函数计算得到的,而不是通过有序性进行维护,因此允许直接修改元素的值。

接下来,再给大家介绍一下关于 查找元素是否存在的操作。

举例:

void test_set2()
{
  set<int> s1;
  s1.insert(3);
  s1.insert(1);
  s1.insert(4);
  s1.insert(2);
  s1.insert(1);
  s1.insert(2);
  int x;
  while (cin >> x)
  {
    auto ret = s1.find(x);
    if (ret != s1.end())
    {
      cout << "在" << endl;
    }
    else
    {
      cout << "不在" << endl;
    }
  }
}

输出显示:

 

  • 除了上述方法,我们还可以使用 count函数来进行操作。具体如下:
if (s1.count(x))
{
  cout << "在" << endl;
}
else
{
  cout << "不在" << endl;
}

输出显示:

 


2、multiset

1️⃣ 基本介绍

multiset 对比 set,multiset是按照特定顺序存储元素的容器,其中元素是可以重复

2️⃣ multiset的使用

void test_set3()
{
  multiset<int> s1;
  s1.insert(3);
  s1.insert(1);
  s1.insert(4);
  s1.insert(2);
  s1.insert(1);
  s1.insert(2);
  multiset<int>::iterator it1 = s1.begin();
  while (it1 != s1.end())
  {
    cout << *it1 << " ";
    ++it1;
  }
  cout << endl;
}

输出显示:

 

此时,对于在 set中进行的查找操作,在multiset中该如何表现呢?(因此存在重复的情况)

void test_set3()
{
  multiset<int> s1;
  s1.insert(3);
  s1.insert(1);
  s1.insert(4);
  s1.insert(1);
  s1.insert(2);
  s1.insert(1);
  s1.insert(2);
  s1.insert(1);
  multiset<int>::iterator it1 = s1.begin();
  while (it1 != s1.end())
  {
    cout << *it1 << " ";
    ++it1;
  }
  cout << endl;
  // 多个key,find中序的第一个key
  auto ret = s1.find(1);
  while (ret != s1.end() && *ret == 1)
  {
    cout << *ret << " ";
    ++ret;
  }
  cout << endl;
}

输出显示:

 

【说明】

需要注意的是,multiset 中的元素是按键的自然顺序存储的。当存在多个相同的键时,它们按照插入的顺序存储在容器中。使用 find 方法仅返回指向中序遍历的第一个key,而不能一次性找到所有具有相同键的元素。

其次,除了上述的操作之外,multiset 还可以使用 count函数来统计元素出现的次数:

 

对于其他的操作,在这里就不做过多的介绍。大家结合文档我相信各位都可以看懂的!!!


 

3、map

1️⃣基本介绍

 

【说明】

  1. 在正式的学习之前,先要了解在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容;
  2. 键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:

2️⃣ map的使用

【说明】

  1. key: 键值对中key的类型
  2. T: 键值对中value的类型
  3. Compare: 比较器的类型,map中的元素是按照key来比较的,缺省情况下按照小于来比较,一般情况下(内置类型元素)该参数不需要传递,如果无法比较时(自定义类型),需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
  4. Alloc:通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器
  5. 注意:在使用map时,需要包含头文件

接下来,我们简单的来使用下 map:

void test_map1()
{
  map<string, string> dict;
  dict.insert(make_pair("insert", "排序"));
  dict.insert(make_pair("count", "计数"));
  dict.insert(make_pair("find", "查找"));
  dict.insert(make_pair("string", "字符串"));
  dict.insert(make_pair("swap", "交换"));
  map<string, string>::iterator dt1 = dict.begin();
  while (dt1 != dict.end())
  {
    cout << (*dt1).first << " ";
    ++dt1;
  }
  cout << endl;
}

输出显示:

【说明】

请注意,指针形式的输出在实际编码中可能不常见。通常,可以直接访问 std::pair 对象的成员变量,并以合适的方式打印出所需的内容。例如,cout << dt1->first << " "; cout << (*dt1).first << " "; 是等效的。

  • 具体如下:

 


接下来,带大家看个例子,让大家更加深入的理解:

【说明】

  • 在 C++ 的map容器中,每个键(key)都是唯一的。当你尝试插入一个已经存在的键时,插入操作会失败;
  • map是一个关联容器,它按照键的顺序对元素进行排序,并且保持唯一键的特性。当你插入一个新的键值对时,map会自动根据键的顺序将其插入到合适的位置,如果已经存在相同的键,则插入失败。

接下来,我给大家讲一下 operator[] 。首先我先用一下这个,让大家直观的感受:

void test_map2()
{
  string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };
  map<string, int> countMap;
  for (auto& e : arr)
  {
    countMap[e]++;
  }
  for (auto& kv : countMap)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
}

输出结果:

 

接下来,带大家详解这个operator[] :

 

【解释】

在给定的代码中,this 是一个指向当前对象的指针(或引用),make_pair(k, mapped_type()) 创建一个键为 k,值为默认构造的 mapped_type 类型对象的 std::pair 对象。接下来,通过调用 insert 方法将这个 std::pair 对象插入到容器中,并获取插入结果的迭代器。

然后,通过解引用和成员访问操作符 .second(*((this->insert(make_pair(k, mapped_type ()))).first)).second 表达式从插入结果的迭代器中获取对应元素的值。

其实文档给的有一点太复杂了,在这里我给出简化的版本,供大家参考:

V& operator[](const K& key)
{
  pair<iterator, bool> ret = insert(make_pair(key, V()));
  return ret.first->second;
}

接下来,有了上述operator[] 这样的功能,我们就可以使用其进行插入操作了。具体如下:

当我们有这样的代码时:

dict["left"];     // 插入
dict["right"] = "右边"; // 插入+修改
dict["string"] = "(字符串)"; // 修改
cout << dict["string"] << endl; // 查找
cout << dict["string"] << endl; // 查找

输出展示:

接下来,我们通过调试看看:

 

【总结】

  • 1. map中的的元素是键值对
  • 2. map中的key是唯一的,并且不能修改
  • 3. 默认按照小于的方式对key进行比较
  • 4. map中的元素如果用迭代器去遍历,可以得到一个有序的序列
  • 5. map的底层为平衡搜索树(红黑树),查找效率比较高$O(log_2 N)$
  • 6. 支持[]操作符,operator[]中实际进行插入查找

4、multimap

1️⃣基本介绍

注意:multimap和map的唯一不同就是:map中的key是唯一的,而multimap中key是可以

重复的

 

2️⃣ multimap的使用

multimap中的接口可以参考map,功能都是类似的。

【注意】

  • 1. multimap中的key是可以重复的。
  • 2. multimap中的元素默认将key按照小于来比较
  • 3. multimap中没有重载operator[]操作(同学们可思考下为什么?)。
  • 4. 使用时与map包含的头文件相同:

 


(四)在OJ中的使用

 

1、前k个高频单词

692. 前K个高频单词

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> num;
        for(auto e : words)
            num[e]++;
        //按照单词出现次数的逆序存储单词及其对应的出现次数
        multimap<int, string, greater<int>> arry;
        for(auto e : num)
        {
            arry.insert(make_pair(e.second, e.first));
        }
        vector<string> res;
        auto it = arry.begin();
        for(int i = 0; i < k; i++)
        {
            res.push_back(it->second);
            it++;
        }
        return res;
    }
};

输出结果:

 


2、两个数组的交集

349. 两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
    
        vector<int> intersection;
    
        for (auto num : set1) {
            if (set2.find(num) != set2.end()) {
                intersection.push_back(num);
            }
        }
        return intersection;
    }
};

输出结果:


总结

以上便是关于 map和set 的全部知识。感谢大家的观看与支持!!!

 

相关文章
|
4天前
|
存储 安全 Java
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
|
4天前
|
存储 编译器 C++
C++:map&set 对红黑树的封装
C++:map&set 对红黑树的封装
11 1
|
4天前
|
存储 C++ 容器
C++:STL - set & map
C++:STL - set & map
16 4
|
4天前
|
调度 C++ 容器
【C++】手搓 list 容器
本文我们实现了STL库中重要的list 的模拟实现,其中最重要莫过于迭代器的封装类的书写,这是前所未有的操作(对于我来说,我是第一次使用这种结构)。通过list 的模拟实现也帮我们巩固了类与对象的知识,也强化了指针操作的思路。欢迎大家讨论分析。
13 1
|
4天前
|
存储 C++ 容器
【C++】vector容器初步模拟
我们初步完成了对vector 的模拟实现,但是依然有问题,比如不支持string等特殊类型。所以下一篇文章我们来一起完善一下。
14 0
【C++】vector容器初步模拟
|
4天前
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
10 1
|
4天前
|
存储 设计模式 算法
【C++/STL】stack和queue(容器适配器、优先队列、双端队列)
【C++/STL】stack和queue(容器适配器、优先队列、双端队列)
16 1
|
4天前
|
设计模式 安全 算法
【C++入门到精通】特殊类的设计 | 单例模式 [ C++入门 ]
【C++入门到精通】特殊类的设计 | 单例模式 [ C++入门 ]
18 0
|
2天前
|
测试技术 C++
C++|运算符重载(3)|日期类的计算
C++|运算符重载(3)|日期类的计算
|
4天前
|
C语言 C++ 容器
C++ string类
C++ string类
9 0