forward_list是一種序列容器.它允許對任何位置的常量時間的插入和刪除操作.
基本介紹
- 中文名：前向(單向)鍊表
- 外文名：forward list
forward_list是一種序列容器，它允許對任何位置的常量時間的插入和刪除操作。
forward_list實現為單向鍊表.鍊表中的每一個元素都存在於位置無關的存儲空間裡，他們的順序由每個元素的next指針決定。
forward_list和list在設計上的主要區別在於前者在內部只有一個指向下一個元素的指針；而對於後者，每個元素都有2個指針：一個指向下一個元素，一個指向前一個元素。 list可以高效地在兩個方向進行疊代,但是這樣的話每個元素會消耗更多的存儲空間，並且插入和刪除的時間開銷會稍微大一些。因此，儘管只能進行前向疊代，forward_list對象比list對象更高效。
和其他的標準序列容器(array,vector,deque)相比較的話，forware_list在任何位置的插入，刪除和移動操作會更快。因此在諸如sorting算法中會更傾向於使用它。
forward_list和list的一個最主要的缺點是無法直接通過位置訪問元素。例如為了訪問forward_list中的第六個元素，必須從第一個元素一個一個疊代到第六個元素。這個操作是線性複雜度的。位置距離起始點越長，就會消耗越多的時間。另外,forward_list也會消耗額外的記憶體來記錄每一個元素之間的指針信息。對於非常小的對象，這個消耗就會非常明顯。
forward_list類模板被設計得非常高效。它被設計得如同C語言的單向鍊表一樣，為了效率考慮，有意不提供size成員函式。因為如果要實現size成員函式的話，為了常量時間的考慮，就必須保持一個內部計數器記錄forward_list的大小。這會消耗額外的存儲空間，並且會讓插入，刪除操作變得更慢。為了獲得一個forward_list對象的大小，可以使用distance算法來計算begin和end之間的距離，這個操作是線性時間複雜度的。
