保留插入顺序的 tsl::ordered

我们知道在javascript以及Python 3.6+中，所有的dict都保留了插入顺序。但在 C++中，无论是std::map还是std::unordered_map，都没有保留插入顺序。当遍历时，std::map得到的是一个根据键值排序的有序序列，而std::unordered_map则基本是乱序。

tsl::ordered_map弥补了该特性，它有兼容std::map的 API ，同时又确保了在begin()到end()循环时，保留了插入时的顺序。其代码在。该地址还实现了tsl::ordered_set，一个保留插入顺序的set实现。

但为之而妥协的是：

• 删除会导致iterator失效，更接近于std::vector。
• 删除的效率是O(n)，而且有一个非常大的系数。但查找键值和插入仍保留了O(1)的性能。

在实现上，基本是一个unordered_map和std::vector的混合结构。其中std::vector按照插入顺序保存pair<K, V>，unordered_map则维护了一个 hash 表（即保存了在std::vector里的索引以及 hash 值）。

在大多数应用中，基本只有查找和添加，删除的操作很少。因此，在大多数情况下，该实现都有很好的性能。该库的缺陷是知名度一般，可能有潜在 bug。