C++STL堆栈与FORWARD_LIST

C++ STL stack vs forward_list(C++STL堆栈与FORWARD_LIST)

本文介绍了C++STL堆栈与FORWARD_LIST的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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

我的眼睛转向std::stackstd::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个字节的开销!

这篇关于C++STL堆栈与FORWARD_LIST的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:C++STL堆栈与FORWARD_LIST

基础教程推荐