[数据结构]-map和set-阿里云开发者社区

一、键值对

键值对是一种简单但强大的数据表示方式，通常用于构建关联关系。它由两部分组成：键（Key）和值（Value）。每个键都唯一地标识一个值。这种数据结构被广泛用于编程中的各种场景

举例来说，考虑一个电话簿，其中每个人的名字（键）都对应着他们的电话号码（值）。在这个例子中，名字就是键，电话号码就是值。这样的组织方式使得我们可以通过名字快速查找到对应的电话号码。

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)
{}
}

在map和set我们的都有键值对的运用，具体运用场景下面会一一道来，这里我们知要明白键值对有二个按键，都能唯一标识一个值。

二、set

1、set的基本知识

1. set是按照一定次序存储元素的容器

2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。

5. set在底层是用二叉搜索树(红黑树)实现的。

T: set中存放元素的类型，实际在底层存储的键值对。

Compare：set中元素默认按照小于来比较 Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

注意：

set中只放 value，但在底层实际存放的是由构成的键值对。

set中插入元素时，只需要插入value即可，不需要构造键值对。

set中的元素不可以重复(因此可以使用set进行去重)。

使用set的迭代器遍历set中的元素，可以得到有序序列。

set中的元素默认按照小于来比较

set中查找某个元素，时间复杂度为：log_2 n

2、set的使用

set的构造

函数声明	功能介绍
set (const Compare& comp = Compare(), const Allocator& = Allocator() );	构造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );	用[first, last)区间中的元素构造 set
set ( const set<key,compare,Allocator>& x );	set的拷贝构造

set的迭代器

set的容量

set修改操作

这些接口和前面的设计都非常类似，这里就不在一一分析了。

下面我们快速使用上面的接口，了解一下set

void test1()
{
  set<int> s;
  s.insert(4);
  s.insert(67);
  s.insert(2);
  s.insert(1);
  s.insert(55);
  s.insert(11);
  s.insert(5);
 
  for (auto v : s)
  {
    cout << v << " " ;
    v++;
  }
  cout << endl;
  auto it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
 
  /*auto pos = s.find(55);*/
  auto pos = find(s.begin(), s.end(), 55);
  if (pos != s.end())
  {
    s.erase(pos);
  }
  cout << s.erase(67) << endl;
  cout << s.erase(11) << endl;
 
  it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
 
  //s.count的功能和find类似
}

三、map

1、map的基本知识

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

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

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

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

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

6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

注意：

1. map中的的元素是键值对

2. map中的key是唯一的，并且不能修改

3. 默认按照小于的方式对key进行比较

4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列

5. map的底层为平衡搜索树(红黑树)，查找效率比较高O(log_2 N)

6. 支持[]操作符，operator[]中实际进行插入查找

2、map的使用

map的构造

函数声明	功能介绍
map()	构造一个空的map

map的迭代器

函数声明	功能介绍
begin()和end()	begin:首元素的位置，end最后一个元素的下一个位置
cbegin()和cend()	与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin()和rend()	反向迭代器，rbegin在end位置，rend在begin位置，其 ++和--操作与begin和end操作移动相反
crbegin()和crend()	与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改

map的容量与元素访问

函数声明	功能介绍
bool empty ( ) const	检测map中的元素是否为空，是返回 true，否则返回fals
size_type size() const	返回map中有效元素的个数
mapped_type& operator[] (const key_type& k)	返回去key对应的value

这里我们要特别的注意：

重载的[]不仅仅能够插入和修改元素还能查找元素。

map中元素的修改

快速上手map

void test1()
{
  map<string,string> dict;
  dict.insert(pair<string, string>("右", "right"));
  dict.insert(pair<string, string>("传说", "legend"));
  dict.insert(make_pair("字符串", "string"));
  dict["迭代器"] = "iterator";
 
  for (auto kv : dict)
  {
    cout << kv.first << ": " << kv.second << endl;
  }
 
  string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
  map<string, int> countMap;
  for (auto& e : arr)
  {
    auto it = countMap.find(e);
    if (it == countMap.end())
    {
      // 元素不存在，插入它并初始化计数为 1
      countMap.insert(make_pair(e, 1));
    }
    else
    {
      //元素以及存在递增
      it->second++;
    }
  }
 
  for (const auto& kv : countMap)
  {
    cout << kv.first << " " << kv.second << endl;
  }
}

这里我们用map就完美的实现了kv模型

这里我们特别注意map的插入和以前学习的数据结构不一样，不在是仅仅直接插入数据，这里插入的是一个pair<类型，类型>（"内容1","内容2"）

3、multiset和multimap

这二个容器的用法和前面一样，与set和map的区别是set和map里面的值都是不可重复的，而multiset和multimp里面是可以存放相同的值

4、oj的运用

为了加深对map和set的运用，为大家分享了二道oj题

题1：

代码实现：

class Solution {
public:
    struct compare
    {
        bool operator()(const pair<int, string>& l, const pair<int, string>& r)
        {
            return l.first > r.first;
        }
    };
 
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for (auto& str : words)
        {
            countMap[str]++;
        }
 
        vector<pair<int, string>> v;
 
        //将map去重后的元素入v
        for (auto& kv : countMap)
        {
            v.push_back(make_pair(kv.second, kv.first));
        }
        //排序
        stable_sort(v.begin(), v.end(), compare());
 
        vector<string> vv;
 
        for (int i = 0; i < k; i++)
        {
            vv.push_back(v[i].second);
        }
        return vv;
    }
};

题2：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //用set排序+去重
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());
 
        auto it1 = s1.begin();
        auto it2 = s2.begin();
 
        vector<int> v;
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 == *it2)
            {
                v.push_back(*it1);
                it1++;
                it2++;
            }
            else if(*it1 < *it2)
            {
                it1++;
            }
            else
            {
                it2++;
            }
        }
        
        return v;
    }
};

四、map和set的模拟实现

上面我们说了map和set的底层实现是红黑树，前面文章也模拟实现了红黑树，但是为了更加契合map和set的功能，我们还需要对红黑树进行改造。

1、红黑树迭代器

红黑树的迭代器基本框架：

template<class T,class Ref,class Ptr>
struct _RBTreeIterator
{
  typedef RBTreeNode<T> Node;
  typedef _RBTreeIterator<T,Ref,Ptr> Self;
  typedef _RBTreeIterator<T, T&, T*> iterator;
  Node* _node;
  
};

这里大家可能会有疑惑的是为什么要重命名二个模板类型不一样的_RBTreeIterator，self 是表示迭代器自身的类型，而 iterator 是公开接口的迭代器类型。这样由利用不同编程场景的适应

*(解引用)和->(成员访问运算符)

Ref operator*()
{
  return  _node->_data;
}
 
Ptr operator->()
{
  return &(_node->_data);
}

对于 *我们应该返回的是当前节点中的数据，对于->返回的是存放当前节点数据的地址。

operator++()和 operator--()

对于红黑树的++操作，就是指向比当前节点更大的树，但是对于一课红黑树来说是存在二种情况的

如果右子树存在，就找右子树的最小

如果右子树不存在，

情况1：如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点。

情况2：如果当前节点是其父节点的左子树,那下一个节点就是其父节点，

代码实现：

Self& operator++()
{
  //如果右子树存在，就找右子树的最小
  if (_node->_right)
  {
    Node* min = _node->_right;
    while (min->_left)
    {
      min = min->_left;
    }
    //找到了右树的最小
    _node = min;
  }
  else
  {
    Node* cur = _node;
    Node* parent = cur->_parent;
    //找到一个节点是其父节点的左孩子，或者到达根节点
    //如果当前节点是其父节点的左子树,那下一个节点就是其父节点
    //如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点
    while (parent && cur == parent->_right)
    {
      cur = cur->_parent;
      parent = parent->_parent;
    }
    _node = parent;
  }
  return *this;
}

对于红黑树的--操作：情行可以对比++操作的分类完成

  Self& operator--()
  {
    //左子树存在
    if (_node->_left)
    {
      //找左子树中最大
      Node* max = _node->_left;
      while (max->_right)
      {
        max = max->_right;
      }
      _node = max;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      //cur在parent的左
      while (parent && cur == cur->left)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
  }

其他细节的完善，逻辑都比较简单，可以参考下面代码自行完成：

//红黑树的迭代器
template<class T,class Ref,class Ptr>
struct _RBTreeIterator
{
  typedef RBTreeNode<T> Node;
  typedef _RBTreeIterator<T,Ref,Ptr> Self;
  typedef _RBTreeIterator<T, T&, T*> iterator;
  Node* _node;
  
  //构造函数
  _RBTreeIterator(Node* node)
    :_node(node)
  {}
 
  // const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器
  _RBTreeIterator(const iterator& s)
    :_node(s._node)
  {}
  Ref operator*()
  {
    return  _node->_data;
  }
 
  Ptr operator->()
  {
    return &(_node->_data);
  }
 
  Self& operator++()
  {
    //如果右子树存在，就找右子树的最小
    if (_node->_right)
    {
      Node* min = _node->_right;
      while (min->_left)
      {
        min = min->_left;
      }
      //找到了右树的最小
      _node = min;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      //找到一个节点是其父节点的左孩子，或者到达根节点
      //如果当前节点是其父节点的左子树,那下一个节点就是其父节点
      //如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
 
  Self& operator--()
  {
    //左子树存在
    if (_node->_left)
    {
      //找左子树中最大
      Node* max = _node->_left;
      while (max->_right)
      {
        max = max->_right;
      }
      _node = max;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      //cur在parent的左
      while (parent && cur == cur->left)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
  }
  bool operator!=(const Self&s)const
  {
    return _node != s._node;
  }
 
  bool operator==(const Self& s)const
  {
    return _node == s._node;
  }
};

对于之前写的红黑树，我们还做一些变更比如insert的返回值不是简单判断是否插入成功，而是返回一个键值对，返回是当前插入节点的迭代器，并判断是否插入成功。

红黑树完整实现：

#pragma once
 
enum Colour
{
  RED,
  BLACK,
};
 
template<class T>
struct RBTreeNode
{
  T _data;
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  Colour _col;
 
  RBTreeNode(const T& data)
    :_data(data)
    , _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _col(RED)
  {}
};
 
//红黑树的迭代器
template<class T,class Ref,class Ptr>
struct _RBTreeIterator
{
  typedef RBTreeNode<T> Node;
  typedef _RBTreeIterator<T,Ref,Ptr> Self;
  typedef _RBTreeIterator<T, T&, T*> iterator;
  Node* _node;
  
  //构造函数
  _RBTreeIterator(Node* node)
    :_node(node)
  {}
 
  // const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器
  _RBTreeIterator(const iterator& s)
    :_node(s._node)
  {}
  Ref operator*()
  {
    return  _node->_data;
  }
 
  Ptr operator->()
  {
    return &(_node->_data);
  }
 
  Self& operator++()
  {
    //如果右子树存在，就找右子树的最小
    if (_node->_right)
    {
      Node* min = _node->_right;
      while (min->_left)
      {
        min = min->_left;
      }
      //找到了右树的最小
      _node = min;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      //找到一个节点是其父节点的左孩子，或者到达根节点
      //如果当前节点是其父节点的左子树,那下一个节点就是其父节点
      //如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
 
  Self& operator--()
  {
    //左子树存在
    if (_node->_left)
    {
      //找左子树中最大
      Node* max = _node->_left;
      while (max->_right)
      {
        max = max->_right;
      }
      _node = max;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      //cur在parent的左
      while (parent && cur == cur->left)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
  }
  bool operator!=(const Self&s)const
  {
    return _node != s._node;
  }
 
  bool operator==(const Self& s)const
  {
    return _node == s._node;
  }
};
 
 
// map->RBTree<K, pair<const K, V>, MapKeyOfT> _t;
// set->RBTree<K, K, SetKeyOfT> _t;
template<class K, class T, class KeyOfT>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef  _RBTreeIterator<T,T&,T*> iterator;
  typedef  _RBTreeIterator<T, const T&,const T*> const_iterator;
 
 
  iterator begin()
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
 
    return iterator(left);
  }
  const_iterator begin()const
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
 
    return iterator(left);
  }
 
  iterator end()
  {
    return iterator(nullptr);
  }
 
 
  const_iterator end() const
  {
    return iterator(nullptr);
  }
 
  pair<iterator,bool> Insert(const T& data)
  {
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_col = BLACK;
      return make_pair(iterator(_root),true);//返回根位置的迭代器，并且插入成功
    }
 
    KeyOfT kot;
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (kot(cur->_data) < kot(data))
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (kot(cur->_data) > kot(data))
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return make_pair(iterator(cur),false);
      }
    }
 
    cur = new Node(data);
    Node* newnode = cur;//保存插入节点位置
    cur->_col = RED;
    if (kot(parent->_data) < kot(data))
    {
      parent->_right = cur;
      cur->_parent = parent;
    }
    else
    {
      parent->_left = cur;
      cur->_parent = parent;
    }
 
    while (parent && parent->_col == RED)
    {
      Node* grandfater = parent->_parent;
      if (parent == grandfater->_left)
      {
        Node* uncle = grandfater->_right;
        // 情况一  uncle存在且为红
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfater->_col = RED;
 
          cur = grandfater;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_left)
          {
            // 情况二
            RotateR(grandfater);
            parent->_col = BLACK;
            grandfater->_col = RED;
          }
          else
          {
            // 情况三
            RotateL(parent);
            RotateR(grandfater);
            cur->_col = BLACK;
            grandfater->_col = RED;
          }
 
          break;
        }
      }
      else // (parent == grandfater->_right)
      {
        Node* uncle = grandfater->_left;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfater->_col = RED;
 
          cur = grandfater;
          parent = cur->_parent;
        }
        else
        {
          //   g                
          //      p
          //         c
          if (cur == parent->_right)
          {
            RotateL(grandfater);
            parent->_col = BLACK;
            grandfater->_col = RED;
          }
          else
          {
            //   g                
            //      p
            //   c
            RotateR(parent);
            RotateL(grandfater);
            cur->_col = BLACK;
            grandfater->_col = RED;
          }
 
          break;
        }
      }
    }
 
    _root->_col = BLACK;
 
    return make_pair(iterator(newnode),true);
  }
 
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
 
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
 
    Node* ppNode = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
 
 
    if (ppNode == nullptr)
    {
      _root = subR;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subR;
      }
      else
      {
        ppNode->_right = subR;
      }
 
      subR->_parent = ppNode;
    }
  }
 
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
 
    parent->_left = subLR;
    if (subLR)
    {
      subLR->_parent = parent;
    }
 
    Node* ppNode = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
 
    //if (_root == parent)
    if (ppNode == nullptr)
    {
      _root = subL;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
 
      subL->_parent = ppNode;
    }
  }
 
  void Inorder()
  {
    _Inorder(_root);
  }
 
  void _Inorder(Node* root)
  {
    if (root == nullptr)
      return;
 
    _Inorder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _Inorder(root->_right);
  }
 
  bool Check(Node* root, int blackNum, const int ref)
  {
    if (root == nullptr)
    {
      //cout << blackNum << endl;
      if (blackNum != ref)
      {
        cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
        return false;
      }
 
      return true;
    }
 
    if (root->_col == RED && root->_parent->_col == RED)
    {
      cout << "违反规则：出现连续红色节点" << endl;
      return false;
    }
 
    if (root->_col == BLACK)
    {
      ++blackNum;
    }
 
    return Check(root->_left, blackNum, ref)
      && Check(root->_right, blackNum, ref);
  }
 
  bool IsBalance()
  {
    if (_root == nullptr)
    {
      return true;
    }
 
    if (_root->_col != BLACK)
    {
      return false;
    }
 
    int ref = 0;
    Node* left = _root;
    while (left)
    {
      if (left->_col == BLACK)
      {
        ++ref;
      }
 
      left = left->_left;
    }
 
    return Check(_root, 0, ref);
  }
 
private:
  Node* _root = nullptr;
};

2、set.h模拟实现

#pragma once
 
#include"RBTree.h"
 
namespace pjb
{
  template<class K>
  class set
  {
    struct setKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
 
  public:
    //在C++中，typename 关键字通常用于表示一个依赖于模板参数的类型。在模板中，
    // 有时候编译器无法确定某个名字到底是一个类型还是一个值，这时候就需要使用 typename 
    // 来明确告诉编译器某个名字是一个类型。
    typedef typename RBTree<K, K, setKeyOfT>::iterator iterator;
    typedef typename RBTree<K, K, setKeyOfT>::iterator const_iterator;
 
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    const_iterator begin()const
    {
      return _t.begin();
    }
    const_iterator end()const
    {
      return _t.end();
    }
    pair<iterator,bool> insert(const K& key)
    {
      pair<typename RBTree<K, K, setKeyOfT>::iterator, bool> ret = _t.Insert(key);
      return pair<iterator, bool>(ret.first, ret.second);
      /*return _t.Insert(key);*/
    }
  private:
    RBTree<K, K, setKeyOfT> _t;
  };
 
  void test_set()
  {
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    set<int> s;
    for (auto e : a)
    {
      s.insert(e);
    }
 
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
 
    for (auto e : s)
    {
      cout << e << " ";
    }
    cout << endl;
  }
}

测试：

3、map.h模拟实现

#pragma once
#include"RBTree.h"
 
namespace pjb
{
  template<class K,class V>
  class map
  {
    struct MapKeyOfT
    {
      const K& operator()(const pair<const K, V>& kv)
      {
        return kv.first;
      }
    };
  public:
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
    iterator begin()
    {
      return _t.begin();
    }
    const_iterator begin()const
    {
      return _t.begin();
    }
 
    iterator end()
    {
      return _t.end();
    }
 
    const_iterator end()const
    {
      return _t.end();
    }
    pair<iterator,bool> insert(const pair<const K, V>& kv)
    {
      return _t.Insert(kv);
    }
    V& operator[](const K& key)
    {
      pair<iterator, bool> ret = insert(make_pair(key, V()));
      return ret.first->second;
    }
  private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  };
 
  void test_map()
  {
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    map<int, int> m;
    for (auto e : a)
    {
      m.insert(make_pair(e, e));
    }
 
    map<int, int>::iterator it = m.begin();
    while (it != m.end())
    {
      //it->first++;
      it->second++;
      cout << it->first << ":" << it->second << endl;
      ++it;
    }
    cout << endl;
 
    map<string, int> countMap;
    string arr[] = {"西游记","红楼梦","水浒传","三国演义","三国演义" ,"三国演义","水浒传" };
    for (auto& e : arr)
    {
      countMap[e]++;
    }
 
    for (auto& kv : countMap)
    {
      cout << kv.first << ":" << kv.second << endl;
    }
  }
 
}

测试:

[数据结构]-map和set