7

我研究数据结构，我想问一下 STL 容器的等价物是什么。

例如

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

4 回答 4

7

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

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

我相信 STL 遵循这些实现。

于 2012-06-16T17:18:11.563 回答
2

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

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

于 2012-06-16T15:27:48.113 回答
1

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

map 和 multimap - 二叉搜索树

双端队列

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

在位集中

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

于 2012-06-16T15:24:07.490 回答
0 
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
于 2015-08-18T09:21:22.053 回答