C++STL堆棧與FORWARD_LIST [英] C++ STL stack vs 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指向第一個元素的指針
- 1指向最后一個元素的指針
- 在每個元素中，有一個指向下一個元素的指針
正向列表插入：
- 動態分配新元素(昂貴)
- 設置指針(廉價)
刪除第一個元素：
- 將指針從第一個元素更改為第二個元素
- 釋放元素(開銷)
動態分配的計算開銷比向量使用的任何計算開銷都高得多。
內存開銷：
- 基本結構中兩個指針的16個字節
- 每個元素8字節用于動態分配，8字節用于指向下一個元素的指針，6字節填充，因為分配器只能處理8字節的倍數
每使用2個字節的有效負載，與向量中2取2的最壞情況相比，有22個字節的開銷！
這篇關于C++STL堆棧與FORWARD_LIST的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持IT屋！
