【C++】-- STL之map和set详解(二)

简介: 【C++】-- STL之map和set详解

三、map

1.map特点

(1) map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。

(2)在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:

typedef pair<const Key, T> value_type;

(3) 在内部,map中的元素总是按照键值key进行比较排序的。

(4) map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。

(5) map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。

(6)map通常被实现为平衡二叉搜索树(红黑树)。

2.map类

(1)map类的构造

1. template < class Key,                                     // map::key_type,Key的类型
2. class T,                                       // map::mapped_type,value的类型
3. class Compare = less<Key>,                     // map::key_compare,比较器类型,默认小于,自定义类型需写函数指针或仿函数
4. class Alloc = allocator<pair<const Key,T> >    // map::allocator_type 空间配置器
5.            > class map;
6. 
7. //构造map
8. explicit map (const key_compare& comp = key_compare(),
9. const allocator_type& alloc = allocator_type());
10. 
11. 使用迭代器区间构造map
12. template <class InputIterator>
13. map (InputIterator first, InputIterator last,
14. const key_compare& comp = key_compare(),
15. const allocator_type& alloc = allocator_type());
16. 
17. //拷贝构造map
18. map (const map& x);

创建map对象:

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<iostream>
3. #include<map>
4. using namespace std;
5. 
6. int main()
7. {
8.     map<string, int> m;//创建一个map对象m
9.  //向m中插入pair
10. 
11.   map<string, int> m1(m.begin(), m.end);//用m的区间构造m1
12.   map<string, int> m2(m1);//用m1拷贝构造m2
13. 
14.   return 0;
15. }

(2)插入insert( )

1. pair<iterator,bool> insert (const value_type& val);//当val的first已存在时返回值pair的second为false,否则返回pair的second为true
2. 
3. iterator insert (iterator position, const value_type& val);//在map的指定位置插入pair
4. 
5. template <class InputIterator>
6. void insert (InputIterator first, InputIterator last);//在map中插入一段迭代器区间

①插入pair,由于此时map中没有足球,因此pair的second为true:

1.  bool b = m.insert(pair<string, int>("足球", 2)).second;
2.  cout << b << endl;
3. 
4.  m.insert (pair<string, int>("篮球", 6));
5.  m.insert (pair<string, int>("羽毛球", 3));
6.  m.insert (pair<string, int>("排球", 1));

make_pair对pair进行了包装,构造了pair对象:

1. template <class T1,class T2>
2. pair<T1,T2> make_pair (T1 x, T2 y)
3.   {
4. return ( pair<T1,T2>(x,y) );
5.   }

因此,在项目中,不展开命名空间时,都要指定std,make_pair要比pair写起来更简洁一些,对比以下两种写法:

1.  m.insert(std::pair<std::string, int>("网球", 7));
2.  m.insert(std::make_pair("网球", 7));

明显make_pair的写法更简洁。

②在map的指定位置插入pair

1.  map<string, int> m;
2.  //向m中插入pair
3.  m.insert (pair<string, int>("足球", 2));
4.  m.insert (pair<string, int>("篮球", 6));
5.  m.insert (pair<string, int>("羽毛球", 3));
6.  m.insert (pair<string, int>("排球", 1));
7. 
8.  //在m开始插入乒乓球
9.  map<string, int>:: iterator it = m.begin();
10.   m.insert(it, pair<string, int>("乒乓球",5));

监视:

③在map中插入一段迭代器区间

向m1中插入m从第二个位置开始到结束位置的区间:

1.  map<string, int> m1;
2.  m1.insert(++m.begin(), m.end());

监视:

这里少了篮球,说明m的第一个pair是<"篮球",6>。

(3)map遍历

auto在变量被定义并初始化之后编译器才能根据初始化表达式来推导auto的实际类型,所以在定义map对象时,不能使用auto关键字,在变量被定义并初始化之后可以使用auto关键字:

1.  map<string, int> m;
2. 
3.  m.insert(pair<string, int>("足球", 2));
4.  m.insert(pair<string, int>("篮球", 6));
5.  m.insert(pair<string, int>("羽毛球", 3));
6.  m.insert(pair<string, int>("排球", 1));
7.  m.insert(make_pair("网球", 7));
8. 
9. //map<string, int>::iterator mit = m.begin();
10.   auto mit = m.begin();//同map<string, int>::iterator mit = m.begin();
11.   while (mit != m.end())
12.   {
13.     cout << mit->first << ":" << mit->second<< endl;
14.     mit++;
15.   }
16.   cout << endl;

map本身有两个模板参数,会导致有些类型比较长,项目中可以用typedef简化命名:

1.  typedef std::map<std::string, int> MAP;//简化map命名
2.  typedef std::pair<std::string, int> MAP_KV;//简化pair命名
3.  typedef std::map<std::string, int>::iterator MAP_IT;//简化迭代器命名
4. 
5.  MAP m;
6.  m.insert(MAP_KV("足球", 2));
7.  m.insert(MAP_KV("篮球", 6));
8.  m.insert(MAP_KV("羽毛球", 3));
9.  m.insert(MAP_KV("排球", 1));
10.   m.insert(MAP_KV("网球", 7));
11. 
12.     MAP_IT mit = m.begin();
13.   while (mit != m.end())
14.   {
15.     std::cout << mit->first << ":" << mit->second << std::endl;
16.     mit++;
17.   }
18.   std::cout << std::endl;

同set一样,map的key不允许修改

1.  typedef std::map<std::string, std::string> MAP;//简化map命名
2.  typedef std::pair<std::string, std::string> MAP_KV;//简化pair命名
3.  typedef std::map<std::string, std::string>::iterator MAP_IT;//简化迭代器命名
4. 
5.  MAP m;
6.  m.insert(MAP_KV("spring", "春天"));
7.  m.insert(MAP_KV("summer", "夏天"));
8.  m.insert(MAP_KV("autumn", "秋天"));
9.  m.insert(MAP_KV("winter", "冬天"));
10. 
11.   MAP_IT mit = m.begin();
12.   while (mit != m.end())
13.   {
14.     mit->first = "night";//修改key为night,报错
15.     mit++;
16.   }
17.   std::cout << std::endl;

报错:

但是map的value可以修改

先给中文翻译加上{ }

1.  MAP_IT mit = m.begin();
2.  while (mit != m.end())
3.  {
4.    mit->second.insert(0, "{");
5.    mit->second += "}";
6.    std::cout << mit->first << ":" << mit->second << std::endl;
7.    mit++;
8.  }
9.  std::cout << std::endl;

再给spring的中文翻译加上其他释义:

1.  auto ret = m.find("spring");
2. 
3.  mit = m.begin();
4.  if(ret != m.end())
5.  {
6.    std::string& str = ret->second;//用str作为ret->second的别名,因此控制的就是ret的second
7.    str.insert(str.size() - 1, "、温泉");
8.  }
9. 
10.   while (mit != m.end())
11.   {
12.     std::cout << mit->first << ":" << mit->second << std::endl;
13.     mit++;
14.   }
15.   std::cout << std::endl;

map也可以用来统计次数,比如找出大家最喜欢的球类,统计技术有3种方式:

第一种方式:找到就增加次数,否则就插入

1. //1.统计次数   
2.  string arr[] = { "篮球","足球","排球","羽毛球","足球","乒乓球","足球","排球","羽毛球","篮球","足球" };
3.  map<string, int> countMap;
4.  for (const auto& str : arr)
5.  {
6.    map<string, int>::iterator ret = countMap.find(str);
7.    if (ret != countMap.end())//找到了,只增加次数
8.    {
9.      ret->second++;
10.     }
11.     else//没找到就插入
12.     {
13.       countMap.insert(make_pair(str, 1));
14.     }
15.   }
16. 
17.   //2.找出大家最喜欢的球类
18.   for (const auto& e : countMap)
19.   {
20.     cout << e.first << ":" << e.second << endl;
21.   }

第二种方式:由于insert的返回值类型为pair<iterator, bool>,pair中的第二个值类型为bool,向map中插入时,如果map中已经有了,pair返回的第一个值为插入值所在节点的迭代器,第二个值就为false,否则pair返回的第一个值为插入值所在节点的迭代器,第二个值就为true。

pair<iterator,bool> insert (const value_type& val);

因此第二种方式根据插入的返回值pair的第二个值判断为true还是false,决定返回的pair的第一个值即迭代器的第二个值是否++:

1.  string arr[] = { "篮球","足球","排球","羽毛球","足球","乒乓球","足球","排球","羽毛球","篮球","足球" };
2.  map<string, int> countMap;
3. 
4. //先插入,如果str已经在map中,insert会返回str所在节点的迭代器,++次数即可
5.  for (const auto& str : arr)
6.  {
7.    //pair<map<string,int>::iterator,bool> ret = countMap.insert(make_pair(str, 1));//可用auto推导
8.    auto ret = countMap.insert(make_pair(str, 1));
9.    if (ret.second == false)
10.     {
11.       ret.first->second++;
12.     }
13.   }
14. 
15.   for (const auto& e : countMap)
16.   {
17.     cout << e.first << ":" << e.second << endl;
18.   }


相关文章
|
23天前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
81 10
|
10天前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
45 5
|
10天前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
31 1
|
19天前
|
算法 安全 Linux
【C++STL简介】——我与C++的不解之缘(八)
【C++STL简介】——我与C++的不解之缘(八)
|
12天前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
11 0
|
14天前
|
存储 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个高频单词等问题的解决方案。
29 6
【数据结构】map&set详解
|
17天前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
28 1
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
31 5
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21