STL 容器的数据结构等价物

Question

我研究数据结构，我想问一下STL容器相当于什么。

例如

• 向量 = 动态数组
• 队列=队列
• 堆栈=堆栈
• priority_queue = 堆
• 列表=链表
• 集合=树
• slist = 单链表
• 位向量=向量布尔
• 地图=对
• 双端队列 = ?
• 多重集 = ?
• 多重映射 = ?
• 哈希集=？
• 哈希映射=？
• hash_multiset = ?
• hash_multimap = ?
• 哈希=？
• 位集 = ?

Answer 1

关于C++标准库容器，标准本身尽量不过多提及实现。然而，对插入、删除、查找、范围插入等复杂性的非常具体的限制意味着大多数实现对容器使用相同类型的数据结构。关于你的一些例子：

• std::list : 双重链表
• std::set、std::multiset、std::map、std::multimap：自平衡 二叉树，通常是红黑树。
• hash_*：C++11提供了unordered_set、unordered_map和multi 兄弟姐妹。这些是哈希表。
• bitset：固定大小数组

我相信STL遵循这些实现。

Answer 2

我认为将 std::map<> 限定为“对”是不正确的。实际上，有一个名为 std::pair<> 的utility，它实际上只是一对。 std::map<> 存储唯一键和非唯一值的方式使得可以使用类似于数组的语法，其索引可以是数字类型，也可以不是数字类型。

编辑：将“容器”更正为“实用程序”，感谢 juanchopanza。

Answer 3

集合和多重集合-二叉搜索树

map 和 multimap - 二叉搜索树

双端队列 - 双端队列

hash*

容器是作为哈希表实现的哈希关联容器。 例如。

hash_map

包含使用哈希表查找的

pair<key,value>

。

在位集中

the individual elements are accessed as special references which mimic bool elements

Answer 4

vector = dynamic array  

queue = queue

stack = stack

priority_queue = priority queue based on binary heap 
                 priority_queue can be implemented using 
                 1. sorted array
                 2. sorted list ( unrolled list, skip list etc)
                 3. any other heap like Fibonacci heap, binomial heap

list = doubly linked list 

set = set based on AVL Tree ( usually ) 
      can implemented using any other binary balancing tree like 
      1. Binary Search Tree
      2. Red black Tree
      3. Splay Tree

slist = single linked list

map = map based on Red Black Tree ( usually ) 
      where every node is 'pair' structure
      can implemented using any other binary balancing tree like 
      1. Binary Search Tree
      2. AVL Tree
      3. Splay Tree

deque = deque

hash_set = set implemented using hash

hash_map = hash table

hash = 'Not Available', used as functor

Answer 5

C++ 标准并未对容器强加特定的数据结构，而是定义了一组要求。这意味着实现必须仅满足上述要求，这些要求主要涉及不同操作的时间复杂度、引用稳定性和迭代器失效，才能被视为符合标准。

但是，某些要求和性能期望的结合迫使大多数库（libc++、libstdc++、MSVC）为每个容器使用特定的数据结构。

• std::array

  ：固定大小数组

• std::vector

  ：动态大小数组

• std::deque

  ：哈希数组树

• std::forward_list

  ：单链表

• std::list

  ：双向链表

• std::set

  /

  std::map

  ：自平衡BST（红黑树）

• std::unordered_set

  /

  std::unordered_map

  ：哈希表（分离链哈希表）