- unordered系列关联式容器介绍
- unordered系列关联式容器和map/set的区别
- unordered系列关联式容器的使用
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。
unordered系列关联式容器和map/set的区别
unordered系列关联式容器底层使用的是哈希表，尽管两者在使用上区别不大，但是性质上还是有一些差异
- unordered系列容器迭代器遍历元素是无序的，而map和set系列迭代器遍历是有序的
- unordered系列容器在查找速度上更快，查找的时间复杂度可达到O(1)
- unordered系列容器在空间占用上要优于map和set系列
- unordered系列容器底层是哈希表，哈希表的建立比较耗费时间
unordered系列关联式容器的使用
在使用上，unordered系列关联式容器和map/set基本一致，具体参考
map和set的基本使用
但是由于底层结构的不同，两者的使用还是有一些差异
- 在使用迭代器遍历时，map/set走的是红黑树的中序遍历，所以访问是有序的，而哈希表则没有这个性质，遍历是无序的
- 由于哈希表的性质，unordered系列关联式容器并不支持反向迭代器
