新C++(10):Map\Set的封装

news/2024/4/25 13:22:21/文章来源:https://blog.csdn.net/RNGWGzZs/article/details/129192303

"湖人总冠军"

一、Map\Set的介绍

Set是C++标准库中的一种关联容器。所谓关联容器就是通过键（key）来读取和修改元素。与map关联容器不同，它只是单纯键的集合。
取自这里
Map是STL 的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。
取自这里

说下map内部数据的组织，map内部自建一颗红黑树（一种非严格意义上的平衡二叉树），这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。
取自这里

在map、set没出来之前呢，我们存储数据常用的都是顺序表、链表、栈队列等这些都被称为"序列式容器"。如果我们想要存储一些关联式键值对，例如"名字:身份证号","商品名称:商品数量"等等以这样数值建立起来的<Key,Value>模型，在数据检索时比序列式容器效率更高。

二、封装Map、Set

(1)红黑树

我们先来看看STL源码中，是如何处理结点的值。

    template<class Value>struct RBTreeNode{RBTreeNode<Value*> _left;RBTreeNode<Value*> _right;RBTreeNode<Value*> _parent;Value _data;Color _color;RBTreeNode(const Value& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_color(RED){}};

我们之前实现的Node结点都是<K,V>模型，为什么源码中会这样声明了呢？在之后封装的时候会解答。

(2)红黑树类

同样，我们先拿源码来看看~

Key:键值
Value:值
KeyOfValue:取键值里的值

这里有几个疑问:

为什么还会需要传Key这个参数?

为什么难道我们在Value里找不到Key值嘛？

为什么需KeyOfValue?

假设我们使用map，传入的一定是一个"pair值",那么map的数值传入到底层红黑树这一层，是传递给Key，还是Value呢？当然是Value！(之后会解答) 而我们比较的是键值(key)还是值(value)？是键值(key),所以我们传入键值与这个传入Value有必然的关联吗？肯定是没有的。

上述问题也就能够简略地回答这么设计的两个疑问。
那为什么需要KeyOfValue呢？因为C++中pair内置的"比较重载"很恶心，它不仅仅只会比较kv.first,还会比较kv.second。但是，我们只需要注意pair中的first。

    template<class K,class Value,class KeyOfValue>class RBTree{typedef RBTree<Value> Node;KeyOfValue kot;//.....}

(3)红黑树迭代器

    template<class Value,class Ref,class Ptr>struct __RBTreeIterator__{typedef __RBTreeIterator__<Value, Ptr, Ref> Self;typedef __RBTreeIterator__<Value, const Value&, const Value*> const_iterator;typedef __RBTreeIterator__<Value, Value&, Value*> iterator;typedef RBTreeNode<Value> Node;Node* _node;__RBTreeIterator__(const Node& node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};

那么如何进行++、--呢？

Self& operator++(){if (_node->_right){//1.找到 右子树的最左节点Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else{//2.向上调整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* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}}

const迭代器与非const迭代器的转换:

在STl中，存在这样的转换。但是我们模拟实现的这一部分却不支持这样。那么如何理解源码那一份拷贝构造的代码呢？

        __RBTreeIterator__(const iterator& it):_node(it._node){}

(4)Map\Set封装

不过在这之前，我们已经实现了一份红黑树的迭代器，我们正好可以继续完善原RBTree的代码,

    template<class K,class Value,class KeyOfValue>class RBTree{public:typedef RBTreeNode<Value> Node;//普通迭代器 const迭代器typedef __RBTreeIterator__<Value, Value&, Value*> iterator; typedef __RBTreeIterator__<Value, const Value&, const Value*> const_iterator;protected:KeyOfValue kot;      //比较函数public:iterator begin(){//找左节点Node* left = _root;while (left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* left = _root;while (left->_left){left = left->_left;}return const_iterator(left);}const_iterator end()const{return const_iterator(nullptr);}

Set:

    template<class K>class Set{public:struct  SetKeyOfValue{bool operator()(const K& key){//如果是set的Key 直接返回就行了return key;}};//typename是向编译器声明 把类部类里的模板 当成一个对象typedef typename RBTree<K, K, SetKeyOfValue>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfValue>::const_iterator const_iterator;iterator begin()const{return _set.begin();}iterator end()const{return _set.end();}std::pair<iterator, bool> insert(const K& key){//std::pair<typename RBTree<K, K, SetKeyOfValue>::iterator, bool> ret = _set.Insert(key);auto ret = _set.Insert(key);return std::make_pair(ret.first, ret.second);}private:RBTree<const K, K, SetKeyOfValue> _set;};

map;

    template<class K,class V>class Map{public:struct MapKeyOfValue{const K& operator()(const std::pair<K,V>& kv){return kv.first;}};typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfValue>::iterator iterator;typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfValue>::const_iterator const_iterator;std::pair<iterator, bool> insert(const std::pair<K, V>& kv){return    _map.Insert(kv);}V& operator[](const K& key){//auto ret = _map.Insert(make_pair(key, V()));std::pair<typename RBTree<K,std::pair<K,V>,MapKeyOfValue>::iterator,bool> ret = _map.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<const K, std::pair<const K, V>, MapKeyOfValue> _map;};

(5)map、set调用过程

虽然画起来错综、杂糅，但是如果真的理解到了其实也还好。

三、测试

我们分别对set、map进行测试。

    void TestSet(){std::cout << "TestSet" << std::endl;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()){std::cout << *it << " ";++it;}std::cout << std::endl;}void TestMap(){std::cout << "Map For Test" << std::endl;std::string arr[] = { "苹果","苹果", "苹果", "梨儿","梨儿","西瓜","西瓜" };Map<std::string, int> CountMap;for (auto e : arr){CountMap[e]++;}for (auto& kv : CountMap){std::cout << kv.first << ":" << kv.second << std::endl;}}