【C++】学习笔记——map和set

简介: 【C++】学习笔记——map和set

十五、map和set

1. 关联式容器

我们已经接触过STL中的部分容器,比如:vectorlistdeque 等,这些容器统称为 序列式容器 。序列式容器底层的数据结构里面存储的是元素本身。

关联式容器也是用来存储数据的,与序列式容器不同的是,其 里面存储的是<key, value>结构的键值对 ,即底层的数据结构包含两个值,key代表键值value代表与key对应的信息

在数据检索时关联式容器比序列式容器效率更高。

而set和map就是STL中的 树形结构的关联式容器 。底层是平衡二叉树(红黑树)。

2. set的介绍

set文档

3. set的使用

使用set记得包含 set 头文件哦。

#include<iostream>
#include<set>
using namespace std;
void test01()
{
  set<int> s;
  s.insert(5);
  s.insert(2);
  s.insert(4);
  s.insert(1);
  s.insert(3);
  s.insert(2);
  s.insert(1);
  set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;
}
int main()
{
  test01();
  return 0;
}

对于 insert 的使用我们已经轻车熟路了。

我们发现结果跟插入的数据好像不匹配,这是因为set底层是平衡二叉树,自带排序属性,而且遇到重复的值不会再次插入,所以 set具有 排序 + 去重 的功能。

#include<iostream>
#include<set>
using namespace std;
void test03()
{
  set<int> s;
  s.insert(5);
  s.insert(2);
  s.insert(4);
  s.insert(1);
  s.insert(3);
  s.insert(2);
  s.insert(1);
  set<int>::iterator it = s.find(5);
  // 使用迭代器进行删除时必须保证迭代器有效
  s.erase(it);
  // 使用指定value进行删除,如果该值存在则删除,不存在不做任何处理
  s.erase(666);
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;
}
int main()
{
  test03();
  return 0;
}

当使用迭代器进行删除时确保迭代器有效,否则会报错。

#include<iostream>
#include<set>
using namespace std;
void test02()
{
  set<int> s;
  s.insert(5);
  s.insert(2);
  s.insert(4);
  s.insert(1);
  s.insert(3);
  s.insert(2);
  s.insert(1);
  set<int>::iterator it = s.find(5);
  if (it != s.end())
  {
    cout << "找到了" << endl;
  }
}
int main()
{
  test02();
  return 0;
}

find查找到元素会返回一个指向元素的迭代器,没找到则返回指向end()的迭代器。

count()会返回这个值有几个。

#include<iostream>
#include<set>
using namespace std;
void test04()
{
  set<int> s;
  s.insert(5);
  s.insert(2);
  s.insert(4);
  s.insert(1);
  s.insert(3);
  s.insert(2);
  s.insert(1);
  cout << s.count(1) << endl;
  cout << s.count(77) << endl;
}
int main()
{
  test04();
  return 0;
}

#include<iostream>
#include<set>
using namespace std;
void test05()
{
  set<int> s;
  s.insert(5);
  s.insert(2);
  s.insert(4);
  s.insert(1);
  s.insert(6);
  s.insert(2);
  s.insert(1);
  // lower_bound返回 容器里第一个 >= value的值
  auto start = s.lower_bound(3);
  // opper_bound返回 容器里第一个 > value的值
  auto finish = s.upper_bound(5);
  cout << *start << endl;
  cout << *finish << endl;
  // 迭代器区间删除
  s.erase(start, finish);
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;
}
int main()
{
  test05();
  return 0;
}

lower_bound返回 容器里第一个 >= value的值

opper_bound返回 容器里第一个 > value的值

4. multiset

multiset的用法与set基本一样,只是 multiset允许出现重复值

此时这里的返回值就有了意义,返回删除的元素个数。

当有重复值时,find返回的迭代器指向中序遍历的第一个要查找的值。

5. map的介绍

map文档

map底层其实是 pair 。而 pair 其实是一个类模板。

成员变量有两个,一个first,一个second,在map里,first一般存的是key,second存的是value

6. map的使用

使用map时记得包含 map 头文件哦。

#include<iostream>
#include<map>
using namespace std;
void test01()
{
  map<string, string> dict;
  dict.insert(pair<string, string>("sort", "排序"));
  dict.insert(pair<string, string>("string", "字符串"));
  dict.insert({ "apple", "苹果" });
  dict.insert(make_pair("sort", "排序"));
  map<string, string>::iterator it = dict.begin();
  while (it != dict.end())
  {
    // 两种获取key和value的方法
    cout << (*it).first << " " << it->second << endl;
    ++it;
  }
}
int main()
{
  test01();
  return 0;
}

make_pair是一个模板函数,跟pair那种写法没区别。

map同样具有 排序 + 去重 的功能,排序的依据是map的 key

#include<iostream>
#include<map>
using namespace std;
void test02()
{
  map<string, string> dict;
  dict.insert(make_pair("sort", "排序"));
  dict.insert(make_pair("string", "字符串"));
  dict.insert(make_pair("sort", "xxxx"));
  for (auto& e : dict)
  {
    cout << e.first << " " << e.second << endl;
  }
}
int main()
{
  test02();
  return 0;
}

此时第三个插入并不会插入,也不会更新。

map的其他成员函数基本没啥大的变化,我们不再赘述。

7. multimap

multimap跟map的区别与multiset与set的区别类似。

#include<iostream>
#include<map>
using namespace std;
void test03()
{
  multimap<string, string> dict;
  dict.insert(make_pair("sort", "排序"));
  dict.insert(make_pair("string", "字符串"));
  dict.insert(make_pair("sort", "xxxx"));
  dict.insert(make_pair("sort", "排序"));
  for (auto& e : dict)
  {
    cout << e.first << " " << e.second << endl;
  }
}
int main()
{
  test03();
  return 0;
}

此时就可以插入重复值了。(排序时只看key)

8. map中重载的operator[]

map的普通统计次数:

#include<iostream>
#include<map>
using namespace std;
void test04()
{
  string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","西瓜","香蕉","草莓" };
  map<string, int> countMap;
  for (auto& e : arr)
  {
    // 查找
    map<string, int>::iterator it = countMap.find(e);
    // 有则数量+1
    if (it != countMap.end())
    {
      it->second++;
    }
    // 没有则插入
    else
    {
      countMap.insert(make_pair(e, 1));
    }
  }
  for (auto& e : countMap)
  {
    cout << e.first << " " << e.second << endl;
  }
}
int main()
{
  test04();
  return 0;
}

当key存在时,operator[]可以返回这个key所映射的value的引用。

operator[]的访问原型:

map的insert函数返回一个pair,第二个数据代表是否插入成功,如果成功(第一次出现)则返回 true 。第一个数据代表指向这个key的迭代器(已经存在的或新插入的)。

所以上面的统计次数代码可以改成:

#include<iostream>
#include<map>
using namespace std;
void test05()
{
  string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","西瓜","香蕉","草莓" };
  map<string, int> countMap;
  for (auto& e : arr)
  {
    pair<map<string, int>::iterator, bool> ret;
    ret = countMap.insert(make_pair(e, 1));
    // 已经存在
    if (ret.second == false)
    {
      // 迭代器指向的value + 1
      ret.first->second++;
    }
  }
  for (auto& e : countMap)
  {
    cout << e.first << " " << e.second << endl;
  }
}
int main()
{
  test05();
  return 0;
}

所以operator[]的访问就跟insert差不多,插入的value是类型的默认构造值。所以上面的统计代码也可以写成:

#include<iostream>
#include<map>
using namespace std;
void test06()
{
  string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","西瓜","香蕉","草莓" };
  map<string, int> countMap;
  for (auto& e : arr)
  {
    countMap[e]++;
  }
  for (auto& e : countMap)
  {
    cout << e.first << " " << e.second << endl;
  }
}
int main()
{
  test06();
  return 0;
}

于是,插入也可以写成这样:

void test07()
{
  map<string, string> dict;
  // 插入
  dict["sort"];
  // 查找
  cout << dict["sort"] << endl;
  // 修改
  dict["sort"] = "xxx";
  // 插入 + 修改
  dict["apple"] = "苹果";
}

未完待续

目录
相关文章
|
3月前
|
C++
c++学习笔记07 结构体
C++结构体的详细学习笔记07,涵盖了结构体的定义、使用、数组、指针、嵌套、与函数的交互以及在结构体中使用const的示例和解释。
39 0
|
1月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
2月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
37 6
【数据结构】map&set详解
|
1月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
36 1
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
36 5
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
|
2月前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
2月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
|
2月前
|
安全 C语言 C++
C++学习笔记
C++学习笔记
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。