• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

C++STL堆栈与FORWARD_LIST

用户头像
it1352
帮助11

问题说明

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

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

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

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

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

正确答案

#1

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个字节的开销!

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /reply/detail/tancck
系列文章
更多 icon
同类精品
更多 icon
继续加载