数据结构STL容器的等价物

Question

我研究数据结构,我想问一下STL容器的等价物.

例如

• vector =动态数组
• queue = queue
• stack = stack
• priority_queue =堆
• list =链表
• set = tree
• slist =单链表
• bit_vector = vector bool
• map = pair
• deque =？
• multiset =？
• multimap =？
• hash_set =？
• hash_map =？
• hash_multiset =？
• hash_multimap =？
• 哈希=？
• bit_set =？

Answer 1

考虑到C++标准库容器,标准本身试图不要过多地谈论实现.但是,对插入,删除,查找,范围插入等复杂性的非常具体的限制意味着大多数实现对容器使用相同类型的数据结构.关于你的一些例子:

• std :: list:双向链表
• std :: set,std :: multiset,std :: map,std :: multimap:自平衡二叉树,通常为红黑树.
• hash_*:C++ 11提供了unordered_set,unordered_map和多兄弟.这些是哈希表.
• bitset:固定大小的数组

我相信STL遵循这些实现.