C++STL堆栈与FORWARD_LIST

我有一个用例，其中我需要以不特定的顺序存储一定数量的uint16_t变量(尽管变量的实际类型并不相关)。我已决定求助于STL来寻找最符合我需要的容器。

容器中的对象可以从容器中取出以供使用，然后放回容器中。在某种程度上，机械师可能只有一盒螺丝刀，而不是把螺丝刀放在口袋里。容器不需要对存储的对象执行任何分类，取出什么并不重要-唯一的要求是知道容器中是否还有任何东西。

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

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

我倾向于使用std::forward_list，但我正在寻求同事的意见。如果你对这件事有什么想法，请与我们分享。

---

解决方案

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

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

大部分讨论都是关于std：：List，但Forward_List也适用同样的原则

关于管理费用和运营的简短说明

矢量数据结构：

• 1个动态分配的数组
• 1个整数，表示使用的元素数
• 1个整数，表示可用元素的数量(预分配的大小)

(脚注：实际上不是计数器，而是指针。让我们不用担心那个)。

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

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

从向量的末尾删除元素：

1. 减少计数器。就是这样(除非你有析构函数)

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

转发列表数据结构：

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

正向列表插入：

1. 动态分配新元素(昂贵)
2. 设置指针(廉价)

删除第一个元素：

1. 将指针从第一个元素更改为第二个元素
2. 释放元素(开销)

动态分配的计算开销比向量使用的任何计算开销都高得多。

内存开销：

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

每使用2个字节的有效负载，与向量中2取2的最坏情况相比，有22个字节的开销！