STL容器的数据结构等价物

Question

我正在学习数据结构，想问一下STL容器的相应等价物是什么。

例如：

• vector = 动态数组
• queue = 队列
• stack = 栈
• priority_queue = 堆
• list = 链表
• set = 树
• slist = 单向链表
• bit_vector = 布尔向量
• map = 对
• deque = 双端队列
• multiset = 多重集合
• multimap = 多重映射
• hash_set = 哈希集合
• hash_map = 哈希映射
• hash_multiset = 哈希多重集合
• hash_multimap = 哈希多重映射
• hash = 哈希表
• bit_set = 位集合

- demosthenes

---

deque = 双端队列。类似于可以向前插入元素的向量。multi_set = 允许包含多个相同值的集合；multi_map = 一个键可以有多个相关的值。map != pair，但是 map 容器的元素是成对出现的。 - Mahesh

std::hash 不是一个容器，而是一个函数对象。 - Steve Jessop

Steve：当你说它是一个函数对象时，你能更具体一些吗？ - Jay D

@Jay：嗯，std::hash是一个类模板。std::hash的实例化是类。这些类的实例是可调用的。因此，这三个模板、类和对象都可以合理地描述为“函数对象”。 - Steve Jessop

Answer 1

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

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

我认为STL遵循这些实现。

- juanchopanza

Answer 2

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

注：由于juanchopanza的提醒，已将“容器”更正为“实用程序”。

- ApplePie

---

严谨的注释：std::pair 不被视为容器，而是一个“实用工具”。 - juanchopanza

Answer 3

set 和 multiset - 二叉搜索树

map 和 multimap - 二叉搜索树

deque - 双端队列

hash* 容器是实现为哈希表的哈希关联容器。 例如，hash_map 包含使用哈希表查找的 pair<key, value>。

在 bitset 中

单独的元素可以访问特殊引用，这些引用模仿了 bool 元素

- nims

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

- Jai