网页版
http://gamehevenhome.blogspot.tw/2015/08/c_4.html
C++实作无序容器的方法，且可接受重复的元素
此文是翻译文章。
上次我们介绍了Hash Table各种流行的方法，现在我们来考虑如果元素有重复，要怎么办
？ (unordered_multiset , unordered_multimap)
Hash Table跟重复元素，这是两个不同玩意，不要混在一起。两个基本问题要解决。
Hash的负载系数(load factor)是[所有元素]除以[所有桶子]，但因为重复元素会放在同
一个桶子。必须要重新设计负载系数，不然阵列会拼命长大，结果大多数桶子都是空 的
。
算法复杂度跟负载系数无关，而是跟桶子里面塞了多少东西有关。
补救负载系数(load factor)非常困难，因为规范对于负载系数定得太死。没有多少空间
可以作弊。一个细心的工程师会同时考虑最大桶子塞了多少东西以及平均每个桶子有多少
东西。我的选择是在节点上动手脚，遍历桶子的时候，可以快速的跳过重复的地方(规范
要求相同的元素必须放在一起)。跟不重复版本比较，我们希望时间效率一 样好！
Dinkumware libc++ , libstdec++ -V3函式库
对于重复元素，根本没做任何处理。
Boost.Unordered
有做一些设计，请看图
桶子b2里面有五个相同的元素。往前指的指标改成指向重复元素最后一个。利用这个反向
指标，可以把五个元素视为一个大节点。插入或删除的时候，先找到第一 个元素，利用
反向指标直接跳到第五个元素。省去了扫描的麻烦。
Boost.MultiIndex
与之前文章的设计类似，第一个节点要指回桶子，所以是特殊处理。其余节点如果是一样
的资料，就把反向指标串好。
定一个节点叫做X，下一个节点叫做Xn，前一个节点叫做Xp。
假设有多个元素重复，全部串在一起。
第一个叫做F
第二个叫做S
倒数第二个叫做P
倒数第一个叫做L
Sp=L
Pn=F
第二个元素，[往前指标]会指向最后节点。
倒数第二个元素，[往后指标]会指向最初节点。
推导一些特性
如果Xpnn == X，那就是桶子第一个节点
如果Xnpn == X，那就是桶子最后节点
如果相同元素>=3，串成一个集团，集团第一个节点条件是Xnp != X && Xnppn == X
如果相同元素>=3，串成一个集团，集团第二个节点条件是Xpn != X && Xppnn == X
如果相同元素>=3，串成一个集团，集团倒数第二个节点条件是Xnp != X && Xnnpp == X
如果相同元素>=3，串成一个集团，集团倒数第一个节点条件是Xpn != X && Xpnnp == X
所有特殊位置节点都可以侦测到。整个双向链结还是可以视为一个环状。插入删除节点都
可以在O(1)。遇到资料相同的集团，可以直接跳到头或是跳到尾，大幅 度加速。
插入元素的方法：
1.使用Hash先找到桶子。(常数时间)
2.检查桶子里面的每个元素，遇到集团的时候，只要检查集团第一个节点即可。(桶子大小
线性时间)
3.如果元素等于某个集团，把元素加入集团内。如果整个桶子没有相同元素，直接插入在
桶子的头端。
4.调整桶子的指标。
遇到重复元素集团的时候，直接用Xnp就可跳到集团最尾端。若重复元素的集团长度低于3
。则加速方法不适用。
删除元素的方法：
1.删除链结里面的元素，调整前后指标。
2.调整桶子的指标。
事实上实作非常复杂，因为在插入删除的时候，双向链结调整指标，必须要侦测到特殊状
态的指标。但是最后效能提升，遍历桶子不依赖桶子里面塞了多少元素，而 是看桶子里
面有多少集团。与不重复版本比较(set/map)，可以达到同样的效能。如果Hash算法良
好，插入就是O(1)。删除动作不用管考虑 Hash算法，一定是O(1)。