从二叉树到 STL：揭开 set 容器的本质与用法
前言：
上次介绍完二叉搜索树后，更新中断了一段时间，先向大家致歉。最近学习状态有些起伏，但我正在努力调整，相信很快会恢复节奏。今天我们继续深入探讨——关联容器，它在算法和工程中都非常常见和重要。
1.之前的遗漏
我之前写的二叉搜索树其实没有写完，我仅仅写了一个节点只能存储一个值的二叉搜索树。在我们日常的工作中，这种树的使用率其实还是比较低的。最受欢迎的是里面存储两个值的二叉搜索树，这个可以类比Python中的字典。相信学过python的读者对此不陌生，字典其实存放了一对值，分别是Key和Value，类比英文字典中的英语和汉字，我们通过英文（Key）来找到对应的中文（Value）。这其实才是我们常使用到的二叉搜索树，下面我通过举例来帮助各位理解这两棵树的区别。
1.1.Key搜索场景
举个例子，现在很多小区配有地下停车库。业主的车牌号会录入系统中，车辆进入时由系统识别并判断是否允许进入。这就是典型的 Key 搜索场景 —— 只需根据一个关键字（车牌号）进行查找。
1.2.Key/Value搜索场景
还是以我们的生活举例，如今我们进入各大商场的时候，如果开车的话难免会需要停进商场专用的停车场，此时这就是停车场计费系统，我们需要录入两个值：车子的车牌号以及入场时间，记录好之后，当车辆想要离开停车场的时候，就会通过车牌（Key）来进行系统中管理的车辆信息进行检索，检索成功后会根据当前的时间减去入场的时间计算出车辆在停车场呆过的时间，从而计算出需要交付的金额。这边是Key/Value的搜索场景，Key其实不是关键，其中的Value才是关键，Key更像是一个标识符，我们通过这个符号来进行真正数据的获取。所以可以看出，它在我们日常的生活中使用的频率更大。
1.3.Key/Value类型的二叉搜索树的源码
由于难度不大，小编就不讲其中的细节了，其实它和上篇我们讲述的Key类型的二叉搜索数一样，只不过多了一个Value而已。
#include<iostream> #include<vector> using namespace std; template<class K, class V> struct BSTNode { // pair<K, V> _kv; K _key; V _value; BSTNode<K, V>* _left; BSTNode<K, V>* _right; BSTNode(const K& key, const V& value) :_key(key) , _value(value) , _left(nullptr) , _right(nullptr) {} }; template<class K, class V> class BSTree { typedef BSTNode<K, V> Node; public: BSTree() = default; BSTree(const BSTree<K, V>& t) { _root = Copy(t._root); } BSTree<K, V>& operator=(BSTree<K, V> t) { swap(_root, t._root); return *this; } ~BSTree() { Destroy(_root); _root = nullptr; } bool Insert(const K& key, const V& value) { if (_root == nullptr) { _root = new Node(key, value); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return nullptr; } bool Erase(const K& key) { Node* parent = nullptr; 
