C++ STL 堆栈与 forward_list

C++ STL stack vs forward_list

我有一个用例，我需要按特定顺序存储一些 uint16_t 变量（尽管变量的实际类型不相关）。我决定转向STL寻找最适合我需要的容器。

容器中的物品可能会被取出来使用并放回容器中。机械师如何拥有一盒螺丝刀，而不是将螺丝刀放在口袋里。容器不需要对存储的对象进行任何排序，取出什么并不重要 - 唯一的要求是知道容器中是否还有任何东西。

我的眼睛转向std::stack和std::forward_list。它们都提供 O(1) 插入（仅更改前端元素）和 O(1) 弹出操作（同样，仅更改前端元素和 return 前一个前端）。问题是 - 我不知道它们在概念上有何不同。

我知道 std::stack 是一个适配器，它只是包装一个实际的 STL 容器（默认情况下 std::deque），因此它可能会有一些意外的开销，具体取决于被包装的容器。

我倾向于使用 std::forward_list，但我正在寻找同事的意见。如果您对此事有想法，请分享。

TLDR： 如果您只需要添加/删除最后一个元素，请使用 vector 或 stack。这是最快的选项并且开销最低。

长版：查找链表和动态数组之间的比较，例如这里：vector vs. list in STL

大部分讨论都是关于 std::list 但同样的原则也适用于 forward_list

开销和操作的简短说明

向量数据结构：

  • 1 个动态分配数组
  • 1 个整数给出使用的元素数
  • 1 个整数给出可用元素的数量（预分配大小）

（脚注：实际上不是计数器而是指针。我们不用担心）。

将一个元素追加到向量的末尾：

  1. 检查是否有 space 可用。如果不是，则重新分配一个两倍于当前大小的数组。因为向量增长到其大小的两倍（指数增长），所以这种情况非常罕见并且不会对性能产生太大影响。
  2. 将元素复制到数组中的索引
  3. 增加计数器

从向量末尾删除一个元素：

  1. 递减计数器。就是这样（除非你有析构函数）

内存开销： 24 个字节用于指针和计数器。 8字节为动态分配的数组。最坏情况下 50% 未使用的元素。

转发列表数据结构：

  • 1 个指向第一个元素的指针
  • 1 个指向最后一个元素的指针
  • 在每个元素中，1个指向下一个元素的指针

正向列表插入：

  1. 动态分配一个新元素（昂贵）
  2. 设置指针（便宜）

删除第一个元素：

  1. 将指针从第一个元素更改为第二个元素
  2. 取消分配元素（昂贵）

动态分配的计算开销比 vector 使用的任何东西都高得多。

内存开销：

  • 基本结构中的两个指针为 16 个字节
  • 每个元素 8 字节用于动态分配，8 字节用于指向下一个元素的指针，6 字节填充，因为分配器只能使用 8 字节的倍数

对于每使用 2 个字节的有效负载，与 vector 中的 2-for-2 最坏情况相比，有 22 字节的开销！