C++ set map

1.set和map是什么

set和map是 C++ STL 提供的容器，用于高效的查找数据，底层采用红黑树实现，其中set是Key模型，map是Key-Value模型

set和map的基本使用较为简单，这里不再叙述，直接进入实现环节

2.set和map的底层实现

2.1 节点的定义

既然set和map的底层采用红黑树，那就少不了我们之前实现过的红黑树，直接搬过来复用

但我们实现的红黑树是Key-Value模型，难道要针对Key模型再copy一份红黑树，将节点里面的值修改成Key吗？

STL 中采用模板的方式，只需要一份红黑树，就能完成Key和Key-Value模型的统一

既然如何，红黑树节点的定义中，数据就不能只是key或pair对象，而应当是泛型，外部传递什么类型，数据就是什么类型

template<typename T>
struct RBTreeNode
{RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _col;
};// set.h
template<typename K>
class set
{
private:RBTree<K, K> _tree;
};// map.h
template<typename K, typename V>
class map
{
private:RBTree<K, std::pair<K, V>> _tree;
};

2.2 set和map的设计

同时，插入数据时，插入的值也应当为修改，此时，数据的比较就有问题了，之前的比较都是针对单一的key或pair进行比较，但红黑树这层并不知道外部传递给我的是一个什么类型的数据，只有set/map层知道传递的数据类型是什么，该如何进行数据的比较？

这里的解决方法是使用仿函数，在set/map层传递一个仿函数给红黑树层，该仿函数的功能用于取出key值，如果是set，那就直接取出key值，如果是map，那就取出pair中的first

// set.h
template<typename K>
class set
{
private:struct SetKeyOfT{const K& operator()(const K& key){return key;}};private:RBTree<K, K, SetKeyOfT> _tree;
};// map.h
template<typename K, typename V>
class map
{
private:struct MapKeyOfT{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};private:RBTree<K, std::pair<K, V>, MapKeyOfT> _tree;
};// RBTree.h
template<typename K, typename T, typename KeyOfT>
class RBTree
{
public:bool insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT kot;Node* cur = _root, * parent = nullptr;while (cur){if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else return false;}Node* newnode = new Node(data);if (kot(data) < kot(parent->_data)) parent->_left = newnode;else parent->_right = newnode;newnode->_parent = parent;// .......return true;}private:Node* _root = nullptr;
};

至此，set/map的整体框架建立完毕

set/map中，红黑树的定义时，还多传递了一个K类型，这样set有两个K类型，会不会很多余？

虽然插入数据不同的类型要采用不同的比较方式，但双方的查找操作都是根据key进行查找的，因此，多添加的K类型是为了方便map进行find操作的

2.3 迭代器

接下来，便是迭代器的设计了

在vector和list中，迭代器都是对指针的封装，再通过重载*和->运算符，达到屏蔽底层，上层统一遍历的效果

这里我们的设计思想也是一样的

template<typename T, typename Ref, typename Ptr>
struct __RBreeIterator
{typedef RBTreeNode<T> Node;typedef __RBreeIterator<T, Ref, Ptr> Self;__RBreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Node* _node;
};

唯一不同的是对于红黑树，++操作该如何实现？

红黑树的遍历要采用中序遍历才有意义，左子树 根 右子树

遍历到到某一节点时，如果左子树不为空，那么要一直遍历，直到左子树为空

左子树遍历完了，接下来访问根

根访问完了，如果右子树不为空，下一个应该访问右子树的最左节点

如果右子树为空，表明当前子树已经访问完了，此时，如果父亲是祖父的右子树，表明父亲的那颗子树也访问完了，要一直向上返回，直到当前节点是其父亲的左子树

template<typename T, typename Ref, typename Ptr>
struct __RBreeIterator
{typedef RBTreeNode<T> Node;typedef __RBreeIterator<T, Ref, Ptr> Self;// ...Self& operator++(){if (_node->_right != nullptr){_node = _node->_right;while (_node->_left) _node = _node->_left;}else{Node* parent = _node->_parent;while (parent && _node == parent->_right){_node = parent;parent = parent->_parent;}_node = parent;}return *this;}Node* _node;
};

set和map在 STL 中是双向迭代器，意味着能迭代器不仅支持++操作，也支持–操作，而–操作无非反过来遍历

Self& operator--()
{if (_node->_left != nullptr){_node = _node->_left;while (_node->_right) _node = _node->_right;}else{Node* parent = _node->_parent;while (parent && _node == parent->_left){_node = parent;parent = parent->_parent;}_node = parent;}return *this;
}

规定迭代器的begin为红黑树的最左节点，end为空

template<typename K, typename T, typename KeyOfT>
class RBTree
{
public:typedef RBTreeNode<T> Node;typedef __RBreeIterator<T, T&, T*> iterator;iterator begin(){Node* left = _root;while (left && left->_left) left = left->_left;return iterator(left);}iterator end(){return iterator(nullptr);}// ...
}

而set/map，无论是插入操作，还是迭代器，无非是对红黑树的接口的封装罢了

// set.h
template<typename K>
class set
{
private:struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;bool insert(const K& key){return _tree.insert(key);}iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}private:RBTree<K, const K, SetKeyOfT> _tree;
};// map.h
template<typename K, typename V>
class map
{
private:struct MapKeyOfT{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;bool insert(const std::pair<K, V>& kv){return _tree.insert(kv);}iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}private:RBTree<K, std::pair<const K, V>, MapKeyOfT> _tree;
};

2.4 map中operator[]

STL 中map支持使用[]运算符进行value的修改，使用起来相当方便

实际上，其内部设计利用了insert操作，将insert的返回值修改为std::pair<iterator, bool>

使用[]时，会传递一个key值，希望拿到key对应value的引用，这样就能方便修改value

因此，可以在[]内部调用insert，如果key不存在则插入成功，返回新节点的迭代器 + true的pair对象，否则返回值中的pair的second为false，表示插入失败

template<typename K, typename V>
class map
{// ...
public:typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;V& operator[](const K& key){std::pair<iterator, bool> ret = this->insert(std::make_pair(key, V()));return ret.first->second;}// ...
};

2.5 拷贝构造 + 赋值重载

set和map都只有RBTree一个成员，直接调用红黑树的拷贝构造和赋值重载即可

template<typename K, typename T, typename KeyOfT>
class RBTree
{
public:typedef RBTreeNode<T> Node;typedef __RBreeIterator<T, T&, T*> iterator;typedef __RBreeIterator<T, const T&, const T*> const_iterator;~RBTree(){this->destroy(_root);_root = nullptr;}RBTree() = default;RBTree(const RBTree<K, T, KeyOfT>& t){_root = this->create(t._root);_root->_parent = nullptr;}RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){std::swap(_root, t._root);return *this;}// ...private:void destroy(Node* root){if (root == nullptr) return;destroy(root->_left);destroy(root->_right);delete root;root = nullptr;}Node* create(Node* root){if (root == nullptr) return nullptr;Node* newnode = new Node(root->_data);newnode->_col = root->_col;newnode->_left = create(root->_left);if (newnode->_left) newnode->_left->_parent = newnode;newnode->_right = create(root->_right);if (newnode->_right) newnode->_right->_parent = newnode;return newnode;}private:Node* _root = nullptr;
}

剩下的还有const迭代器和find的实现了，由于较为简单，不再详讲

**注意：**还有个细节，我们在传递红黑树的模板参数时，将第二个模板参数中的K加上了const

如果是set，那就是const K，如果是map，那就是pair<const K, V>，这是为了防止使用迭代器修改节点中的值，为什么不直接使用const迭代器呢？如果使用const迭代器，那么map中的Key和Value都不能修改，而map是要能支持修改Value的

2.6 测试

void Test_set()
{set<int> s;std::vector<int> v = { 1, 3, 2, 8, 11, 9, 4, 5, 7, 10, 6 };for (auto& e : v) s.insert(e);std::cout << "正向遍历: ";for (auto& e : s) std::cout << e << " ";std::cout << std::endl;std::cout << "反向遍历: ";set<int>::iterator it = s.find(11);while (it != s.end()){std::cout << *it << " ";--it;}std::cout << std::endl;std::cout << "拷贝构造: s2->";set<int> s2(s);for (auto& e : s2) std::cout << e << " ";std::cout << std::endl;std::cout << "赋值重载: ";set<int> s3(s);s3.insert(1);s3 = s;std::cout << "s3->";for (auto& e : s3) std::cout << e << " ";std::cout << "    s->";for (auto& e : s) std::cout << e << " ";
}

void Test_map()
{std::vector<std::string> v = { "apple", "tassel", "watermelon", "apple", "banana", "tassel", "orange", "apple" };map<std::string, int> m;for (auto& e : v) m[e] ++;for (auto& it : m){std::cout << it.first << " " << it.second << std::endl;}
}