map和set 的封装_python map封装

引入

对于map和set的引入，我们用一道在程序中常见的问题解决：
给定一个数组int arr[]={1,2,1,3,1,4,1,5,5,2,3,4,5};，给出以下问题的解决方案：

1. 找出出现次数最多的元素
2. 去除数组中重复的元素，并输出（任意顺序）

这些问题在没有学习map和set之前并没有很好的解决方法（但是map和set并不是唯一的解决方法），第二个问题：之前我们解决的方法一般就开辟一个新数组tmp，遍历arr中所有元素，对于arr中任意元素遍历tmp数组如果元素在tmp中未出现就插入。第一个问题，只需将数组类型改成一个结构体，该结构体包含一个元素和他出现的次数，则在最后一步如果arr中元素已经出现在tmp中，就改变tmp中该元素对应结构体的次数。

我们发现arr在tmp中插入时每一次都要遍历一遍tmp数组，是否能提升查找效率呢？

所以我们现在需要一个容器：

• 该容器中不存在重复元素
• 该容器中查找一个元素效率要高

key-value模型

key-value模型适用于上面的问题1，每一个元素（key）和他出现的次数（value）一 一对应，但是每次查找tmp数组，都是以key为依据查找。
举个例子：一个英汉字典就是典型的key-value模型，英文（key）是你搜索的依据，中文（value）是查找的内容，两者一一对应

map和set底层

有一个数据结构完美符合上面我们需要容器的两个条件——红黑树。首先红黑树不能插入重复元素，所以可以做到去重的效果。又因为满足二叉搜索树所以查找效率比高。而且比二叉搜索树稳定。所以map和set的底层采用的是红黑树

set

set存储元素的类型为key，容器中将该类型定义为value_type

set的几个重要接口

---

• insert

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

  注意insert的返回值是一个pair类型，first是插入元素的迭代器（如果val在set中不存在返回插入新元素的迭代器，如果在set中存在返回set中值为val的那个元素的迭代器），second代表是否插入成功

---

• operator++
  由于set底层采用的是红黑树，迭代器++则采用的是树的中序遍历，所以遍历的结果应该是一个有序数组

---

map

map中存储的元素的类型是：pair<key,value>,容器中将该类型定义为value_type

map几个重要的接口

---

• insert

  pair<iterator,bool> insert (const value_type& val);
  template <class P> 
  pair<iterator,bool> insert (P&& val);
  1
  2
  3

  返回值
  注意insert的返回值是一个pair类型，first是插入元素的迭代器（如果val在set中不存在返回插入新元素的迭代器，如果在set中存在返回set中值为val的那个元素的迭代器），second代表是否插入成功

---

• find

  iterator find (const key_type& k);
  const_iterator find (const key_type& k) const;
  1
  2

  返回值
  如果找到了返回该元素的迭代器，找不到返回map::end()

---

• operator[]

  mapped_type& operator[] (const key_type& k);
  mapped_type& operator[] (key_type&& k);
  1
  2

  这里mapped_type是我们map中存储元素类型pair<key,value>中的value
  这个运算符重载给我们map的使用带来了巨大的方便，map[key]和(map.insert(key,value()).first)->second是等价的。

---

• operator++
  由于map底层采用的是红黑树，迭代器++则采用的是树的中序遍历，所以遍历的结果应该是一个有序数组

---

map和set的封装

我们对于map和set封装始终是在红黑树的基础上进行封装的，红黑树的代码可以参考blog红黑树
红黑树的代码接下来的封装都是在这个代码的基础上进行修改的！
封装的结构为：

这里以map的封装为例： map的封装弄明白了，set就非常简单了
首先需要将红黑树的节点模板改一下：

这里修改后使得树节点里面存储的是ValueType类型，ValueType类型实际上就是修改前pair<K,V>，我们可以发现ValueType实际上就是我们在外层插入时插入时传进去的类型

template <class ValueType>
    struct TreeNode{}；
    
template <class K, class ValueType, class GetKey>    
class RBTree{};
1
2
3
4
5

那么问题来了：

• 已经传入了ValueType为什么要传入K？
  传入Key类型只是作为返回值类型，因为find函数参数为const K& x，仅此而已。

---

• 红黑树在插入搜索时需要比较key值，节点里面存储的是ValueType，如何比较？
  有些同学会认为很简单，直接(ValueType)x.second不就行了？这样确实可以，但是没有考虑一个问题set也需要使用这份红黑树代码作为底层，如果用上面的代码，set中的ValueType和K是同一个类型，这时就会出现错误。
  我们的解决方法是使用仿函数Get_key来取出ValueType中的Value，让上层来决定如何取出方法。这就是仿函数的妙处

剩下来只需要将红黑树中函数封装到上层map中就可以了

#include "RedBlackTree.h"
#include <utility>

namespace sht
{
    template <class Key, class Value>
    class map
    {

        struct Get_Key_From_ValueType
        {
            Key operator()(const std::pair<Key, Value> &v)
            {
                return v.first;
            }
        };

    public:
        typedef std::pair<const Key, Value> ValueType;    //注意这里定义的ValueType是实际树节点里面存的内容
        typedef typename sht::RBTree<Key, ValueType, Get_Key_From_ValueType>::iterator iterator;
        typedef typename sht::RBTree<Key, ValueType, Get_Key_From_ValueType>::const_iterator const_iterator;
        
        
        
        std::pair<iterator,bool> insert(const std::pair<Key, Value> x)
        {
            return tree.insert(x);
        }


        Value&  operator [](const Key& x)
        {
            auto ret = tree.insert(std::make_pair(x, Value()));
            return (ret.first)->second;
        }

        const_iterator begin() const // 常量迭代器
        {
            return tree.begin();
        }

        const_iterator end() const
        {
            return tree.end();
        }

        iterator begin() // 普通迭代器 ： 注意普通迭代器的key也是无法修改的
        {
            return tree.begin();
        }

        iterator end()
        {
            return tree.end();
        }

    private:
        sht::RBTree<Key, ValueType, Get_Key_From_ValueType> tree;
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

这里map还有一个设计的技巧如果是const对象，那么begin和end要返回const迭代器，这里重载了begin和end函数（参考这篇blog）。这个设计很巧妙