关联式容器

在之前的学习中，所学习的容器类型都是序列式容器，其底层是线性数据结构存储的是元素本身

本章所学习的是另一种容器关联式容器，关联就意味着元素与元素之间存在着某种关联；存储的是数据是 <key,value>结构的键值对，接下来学习什么是键值对

键值对

键值对用来表示具有一一对应关系的一种结构，此结构中一般只包括两个成员变量 key和 value；key代表键值， value代表与 key对应的信息；通过结构体pair进行定义

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

一般在进行对pair赋值并插入时，使用其另一种形式make_pair

树状结构关联式容器

根据应用场景的不同，STL实现了两种不同结构的管理式容器：树形结构和哈希结构；树形结构的关联式容器主要有四种： set, multiset, map, multimap。这四种容器都是以平衡搜索树作为底层结构来实现的。接下来对这些容器一一介绍

set

介绍

1. set是按照一定次序存储元素的
2. 在set中，只存放实值value，但在底层实际存放的是键值对<value,value>；插入元素时只需要插入实值value，不需要构造键值对
3. 元素不可以重复，且不允许修改
4. 元素默认按照小于进行比较
5. 底层由二叉搜索树实现

使用

模板参数列表

1. T：set中存放的元素的类型是T，既是key也是value
2. Compare:set中元素默认按照小于进行比较

int main()
{set<int>myset;myset.insert(5);myset.insert(5);myset.insert(3);myset.insert(4);myset.insert(1);myset.insert(0);myset.insert(0);for (auto e : myset){cout << e << " ";}cout << endl;auto pos = find(myset.begin(), myset.end(), 3);myset.erase(pos);for (auto e : myset){cout << e << " ";}return 0;
}

通过运行结果可以发现， set会自动对元素进行排序+去重

multiset

介绍

1. multiset是按照特定顺序存储元素的容器，元素可以重复
2. 其余的与set一致

使用

int main()
{multiset<int>myset;myset.insert(5);myset.insert(5);myset.insert(3);myset.insert(4);myset.insert(1);myset.insert(0);myset.insert(0);for (auto e : myset){cout << e << " ";}cout << endl;auto pos = find(myset.begin(), myset.end(), 3);myset.erase(pos);for (auto e : myset){cout << e << " ";}return 0;
}

通过结果可以发现，相比于set,multiset只是进行简单的排序，并不会进行去重操作

map

介绍

1. 关联式容器，按照 key的比较次序来存储由键值 key和值 value组成的键值对，通过成员类型 value_type,称为 pair

typedef pair<const key,T>value_type;

2. 键值 key用于排序和标识元素；值 value存储与键值关联的内容；两者的类型可能不同
3. 在内部，map中的元素总是按照键值key进行比较排序的，默认是按照小于进行排序的
4. map中存放的元素是键值对pair<key,value>
5. 支持下标访问，即可以通过键值key访问与之对应的value

使用

模板参数说明

1. Key：key的类型
2. T：value的类型
3. Compare：比较器，通过key进行比较

int main()
{map<string, string>dict;dict.insert(make_pair("east", "东"));dict.insert(make_pair("west", "西"));dict.insert(make_pair("south", "南"));dict.insert(make_pair("north", "北"));for (const auto& e : dict){cout << e.first << " " << e.second << endl;}return 0;
}

multimap

介绍

1. multimap是按照特定顺序存储键值对pair<key,value>的序列式容器，元素可以重复
2. 其余的与map一致

使用

统计球的次数

int main()
{string arr[] = { "篮球","羽毛球","乒乓球","羽毛球","乒乓球","羽毛球"， "羽毛球","乒乓球" };multimap<string, int>coutmap;for (auto& e : arr){auto it = coutmap.find(e);if (it == coutmap.end()){coutmap.insert(make_pair(e, 1));}else{it->second++;}}for (const auto& e : coutmap){cout << e.first << " " << e.second << endl;}return 0;
}

这里还有另一种方式进行统计，需要使用operator[]，使用之前，先介绍其原理，做到知其然知其所以然

下标访问返回值：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

逐步进行分析：

1. make_pair(k,mapped_type())，根据键值k和实值类型相同的临时对象mapped_type()创建一个元素
2. insert(make_pair(k,mapped_type()))，将该元素插入到map中去，这里还需要了解到插入操作会返回一个pair,第一个元素是迭代器，指向插入的新元素或者键值重复的旧元素；第二个元素标识着插入的成功与否

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

3. (this->insert(make_pair(k,mapped_type()))).first，取得插入返回 pair中的第一个元素，即迭代器，指向插入的元素
4. (*((this->insert(make_pair(k,mapped_type()))).first)).second，对迭代器进行解引用，获得一个 map元素，由键值 key和实值 value组成的 pair取得其第二个元素，也就是实值

对上面的代码进行修改

int main()
{string arr[] = { "篮球","羽毛球","乒乓球","羽毛球","乒乓球","羽毛球" ，"羽毛球","乒乓球" };map<string, int>coutmap;for (auto& e : arr){coutmap[e]++;}for (const auto& e : coutmap){cout << e.first << " " << e.second << endl;}return 0;
}

底层容器

前面的set/multiset/map/multimap有个共同特点：底层都是通过二叉搜索树来实现的，二叉搜索树本身也存在着缺陷，如果插入值不够随机，或者经过某些插入或删除操作导致二叉搜索树失去平衡，造成搜寻效率低的情况，因此set/map的底层结构是对二叉搜索树进行了平衡处理的平衡树来实现的

AVL树

概念

加上了平衡条件的二叉搜索树，要求任何节点的左右子树高度差最多是1，可以降低树的高度，从而减少平均搜索长度

一颗AVL树或者空树，具有以下性质

1. 它的左右子树都是AVL树
2. 左右子树的高度差的绝对值不超多1（-1/0/1）

操作

节点定义

template<class K,class V>
struct AVLTreenode
{pair<K, V> _kv;AVLTreenode<K, V>* _left;AVLTreenode<K, V>* _right;AVLTreenode<K, V>* _parent;int _bf;//平衡因子AVLTreenode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

这里引进了一个新的概念平衡因子，简单来说就是：右子树的高度减去左子树的高度得到的结果就是该节点的平衡因子

插入

AVL树在插入元素方面与二叉搜索树大致相同，除了需要对平衡因子进行处理之外；所以插入的过程分为两步：1.按照二叉搜索树的方式插入新节点；2.调节平衡因子

插入新节点

bool insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new node(kv);return true;}node* parent = nullptr;node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if(cur->_kv.first > kv.first){parent = cur;cur = cur->left;	}else{return false;}}cur = new node(kv);if (parent->_kv.first > kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//更新平衡因子
}

更新平衡因子

1. 插入节点在右，parent->_bf++
2. 插入节点在左，parent->_bf--

if (cur == parent->_left)
{parent->_bf--;
}
else
{parent->_bf++;
}

父节点的平衡因子更新过后，是否需要继续向上更新的依据是：子树的高度是否发生变化

1. parent->_bf==0，说明插入之前父节点就空缺了左右节点其中一个parent->_bf==-1/parent->_bf==1，而插入之后刚好补全了空缺；也就是说子树并没有发生变化，不需要继续向上更新

if (parent->_bf == 0)
{break;
}

2. parent->_bf==1/parent->_bf==-1，说明插入之前左右子树的高度一样，插入之后其中一边变得更高；由于子树的高度发生了变化，所以需要向上更新

else if (parent->_bf == 1 || parent->_bf == -1)
{cur = parent;parent = parent->_parent;
}

3. parent->_bf==2/parent->_bf==-2，说明插入之前左右子树就已经一边高一边低；插入之后平衡已经被破坏，需要就地处理->旋转

旋转

旋转的核心思想：
使这颗子树的高度差不超过1；旋转过程中继续保持它是二叉搜索树；更新子节点的平衡因子；使子树的高度与插入之前保持一致

根据父节点的平衡因子和插入节点的平衡因子旋转的情景大志分为4种：

1. parent->_bf==2&&cur->_bf==1

旋转的具体操作：将节点6的左节点调整到节点5的右节点上；节点5变成节点6的左节点；节点6作为根指向ppnode

//左旋
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;}parent->_bf = subR->_bf = 0;
}

2. parent->_bf == -2 && cur->_bf == -1

旋转具体操作：将节点3的右节点调整到节点6的左节点上；节点6变成节点3的右节点；节点3作为根节点指向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 (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = parent->_bf = 0;
}

3. parent->_bf == -2 && cur->_bf == 1

旋转操作：以节点3为轴点，进行左单旋，将节点6的左节点调整到节点3的右节点上；节点3变成节点6的左节点，节点6变成节点9的左节点；以节点9为轴点，进行右单旋，将节点6的右节点调整到节点9的左节点上；节点9变成节点6的右节点；节点6变成根节点指向ppnode

//左右双旋
void RotateLR(node* parent)
{node* subL = parent->_left;node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//subLR左子树新增节点if (bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}//subLR右子树新增节点else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}//subLR自己是新增节点else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}
}

4. parent->_bf == 2 && cur->_bf == -1

旋转操作：以节点9为轴点，进行右单旋，将节点6的右节点调整到节点9的左节点上；节点9变成节点6的右节点，节点6变成节点3的右节点；以节点3为轴点进行左单旋，将节点6的左节点调整为节点3的右节点；节点3变成节点6的左节点，节点6变成根节点指向ppnode

//右左双旋
void RotateRL(node* parent)
{node* subR = parent->_right;node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);//subRL右子树新增节点if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}//subRL右子树新增节点else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = -1;}//subRL本身就是新增节点else if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

红黑树（RBTree）

概念

AVL树之外，另一个颇具历史被广泛运用的平衡二叉树就是红黑树RBTree，所谓红黑树，不仅是一个二叉搜索树，而且必须满足以下规则

1. 每个节点不是红色就是黑色
2. 根节点为黑色
3. 如果节点为红，其子节点必须为黑（注意，这里并不没有说明不可以是连续的黑色）
4. 任意节点至树尾端的路劲，所含有的黑节点数必须相同

最长路径不超过最短路径的二倍
最长路径：黑红相间的路径
最短路径：全为黑色

根据规则4，新增节点必须是红色

节点的设计

红黑树有红黑两种颜色，并且拥有左右子节点，节点的设计如下

enum Color
{RED,BLACK,
};
template<class K,class V>
struct RBTreenode
{pair<K, V> _kv;RBTreenode<K, V>* _left;RBTreenode<K, V>* _right;RBTreenode<K, V>* _parent;Color _col;RBTreenode(const pair<K, V>& kv):_kv(kv),_col(RED),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

迭代器的设计

红黑树的迭代器属于双向迭代器，各种操作都类似于list，较为特殊的就是++和--，这两个操作完全依据红黑树的节点的排列法则

先处理++，根据红黑树的中序遍历：左子树-根-右子树
如果右子树不为空，可直接到右子树中寻找键值最小的节点便是根节点++之后的节点

如果右子树不存在，并且此时节点还是父节点的右节点，向上找到的祖先便是++之后的节点；如果此时节点是父节点的左节点，那么父节点便是++之后的节点

--操作于此相同

这里还需要注意一点的是红黑树的迭代器中存在着构造函数
当普通迭代器调用时，权限缩小，此时是拷贝构造；当const迭代器调用时，此时是构造函数

_RBTreeIterator(const iterator& s):_node(s._node)
{}

迭代器的完整代码如下

template<class T>
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){}_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;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

结构

红黑树本质是二叉搜索树，每个节点存储的数据是键值对pair<key,value>，键值key唯一标识节点不可修改，实质value保存信息可以修改；

STL规定，begin()和end()代表一段前闭后开的区间，对红黑树进行中序遍历之后，可以得到有序序列，因此：begin()可以放在红黑树中最小节点的位置，end()可以放在最大节点的下一个位置（这里直接设置为空指针）

begin()

iterator begin()
{node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);
}

end()

iterator end()
{return iterator(nullptr);
}

插入

插入操作的返回值是键值对pair

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

红黑树是在二叉树搜索树的基础上加上其平衡条件，因此红黑树的插入可分两步：

1. 按照二叉搜索树的规则插入新节点

2. 检测新节点插入之后，红黑树的性质是否被破坏
   新增节点必须是红色的，如果双亲结点的颜色是黑色，则没有违反红黑树规则，不需要调整；如果双亲结点是红色，此时就违反了双亲结点的规则3不能有连续的红色节点，需要进行调整；根据叔叔节点的情况，调整的情景也分为3种：
   约定：新增节点为cur，父节点为p，祖父节点为g，叔叔节点为u

cur为红,p为红,g为黑,u存在且为红

调整操作：将父节点 p和叔叔节点 u改为黑色，祖父节点 g改为红色；将祖父节点 u作为新增节点，继续向上调整

cur为红,p为红,g为黑,u不存在/存在且为黑

调整操作：如果父节点 p是祖父节点 g的左节点，新增节点cur是父节点p的左节点，进行左单旋；相反，父节点 p是祖父节点 g的右节点，新增节点cur是父节点p的右节点，进行左单旋

以父节点 p为轴点进行左单旋；将父节点 p改为黑色，祖父节点 g改为红色；父节点 p作为新增节点继续向上调整

cur为红,p为红,g为黑,u不存在/存在且为黑

调整操作：如果父节点p是祖父节点g的左节点，新增节点cur是父节点p的右节点，则以父节点p为轴心进行左单旋；如果父节点p是祖父节点g的右节点，新增节点cur是父节点p的左节点，则以父节点p为轴心进行右单旋
以父节点p为轴心进行左单旋，转换成情景二进行调整

pair<iterator, bool>insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}node* parent = nullptr;node*newnode=node(cur);node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur),false);}}cur = new node(kv);node* newnode = cur;cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){node* grandfather = parent->_parent;if (parent == grandfather->_left){node* uncle = grandfather->_right;//情景1，叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col == uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//情景2RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//情景3RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);
}

红黑树模拟实现set与map

通过红黑树来模拟实现这两种容器，首先要解决的一个问题就是：set的节点中存储的数据是key(也是value)，而map中存储的是键值对pair<key,value>；所以在红黑树中先要修改节点中存储数据的类型，使得当模板根据不同的类型，实现不同的容器

节点改造如下

enum Color
{RED,BLACK,
};template<class T>
struct RBTreenode
{T _data;//数据类型RBTreenode<T>* _left;RBTreenode<T>* _right;RBTreenode<T>* _parent;Color _col;RBTreenode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};

节点修改之后，还会出现一个问题，在进行插入操作时，会将待插入节点的键值与根节点的键值进行比较，但是由于此时节点中的数据类型是data，如果是模拟实现set那么不会出现任何问题；如果是模拟实现map，编译器也不清楚data是表示键值还是实值，而且键值对pair中的比较大小的函数，并不是只比较键值大小

所以这时便需要想办法将键值对中的键值取出来；解决办法：在红黑树模板中加上一个模板参数KeyofT，创建仿函数；当实现set是data的是键值也是实值，当实现map时取出键值对pair中的键值即可

改造红黑树如下

//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;~RBTree(){......}iterator begin(){node* left = _root;while (left && 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->left;}return const_iterator(left);}const_iterator end() const{return const_iterator(nullptr);}pair<iterator, bool>insert(const T& data){......return make_pair(iterator(newnode), true);}private:node* _node = nullptr;
};

模拟实现map

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();}iterator end(){return _t.end();}const_iterator begin(){return _t.begin();}const_iterator end(){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 T, V>, MapkeyofT> _t;
};

模拟实现set

template<class K>
class set
{struct SetkeyofT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetkeyofT>::const_iterator iterator;typedef typename RBTree<K, K, SetkeyofT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pair<iterator, bool>insert(const K& key){pair<typename RBTree<K, K, SetkeyofT>::iterator, bool>ret = _t.insert();return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetkeyofT> _t;
};