歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> C++ 頭文件系列(forward_list)

C++ 頭文件系列(forward_list)

日期:2017/3/1 9:06:10   编辑:Linux編程

簡介

forwrad_list字面意思為前向列表,但實際上它是一種單向列表,只能從單一方向遍歷。

單向鏈表實現

forward_list內部是用單向列表實現的,並且設計該庫的時候就是以近乎手寫的單向鏈表的運行效率(時間上和空間上)為目的的。 這導致了它是唯一一個C++標准庫容器中沒有size成員函數的容器, 因為維護這樣一個信息會造成效率上的輕微損失。

作為單向鏈表,它有以下幾個屬性:

  • 潛在可能的非連續內存分配
  • 線性時間的元素位置獲取
  • 常數時間的元素插入、刪除、移動

與list的共性

因為它們的內部實現都是通過鏈表(不管是單鏈表還是雙鏈表),所以forwrd_list類模版具有一些與list相同的特殊函數:

  • splice_after
  • remove、remove_if
  • unique
  • merge
  • sort
  • reverse

與list的差異

明顯的,forward_list是單向鏈表,內部只維護了單向遍歷的信息。 因此,forward_list的迭代器是前向迭代器(forward intertor)。

除此之外,它們的插入操作也有明顯的不同,具體體現在傳入的迭代器上:

  • list::insert:在傳入的迭代器之前插入。
  • forward_list::insert:在傳入的迭代器之後插入。

我們來看,為什麼標准庫要放棄接口語義的一致性,采用不一樣的接口設計。

節點修改策略

單向 VS 雙向

典型的鏈表分單向和雙向,基本上每一個方向上都需要額外的空間來保存順序信息(即前一個和後一個元素)。 雙向鏈表保存有兩個方向的鏈接, 而單向鏈表只有一個方向。

節點修改

當涉及到鏈表節點的修改時,例如插入、移動等,問題就變得明顯了:對於鏈表來說,修改單個節點實際上涉及到3個節點的信息----當前節點、前驅節點lis、後繼節點(修改前後節點的前後節點的鏈接信息是必要的)。

但是,可以更簡單點:雙向鏈表的前驅和後繼信息可以間接地通過當前節點得到,因為當前節點有足夠的信息 。也就是說,在修改節點時,我只要傳入該節點就可以了;而單向鏈表單個節點可以通過鏈接信息獲得後繼節點

傳入前驅節點迭代器

實際上,forward_list庫做得更好,它的相關接口只需要我們傳入一個節點迭代器。 這些接口包括(分別對應常見的非after版本):

  • insert_after
  • emplace_after
  • erase_after

那麼這怎麼做到的呢? forward_list的策略是----傳入前驅節點的迭代器。 這樣一來,所有需要的節點信息都能夠直接間接地得到。 Great!

但是這也有一個問題:怎麼在頭部插入一個元素呢?畢竟頭節點沒有前驅節點。 哈哈,這就是為什麼這個類模版提供了兩個非常奇怪的函數, 它們是專門為上述三個函數提供服務的(-_-):

  • before_begin
  • before_cbegin

所以現在你也知道了,為什麼隨筆開頭的示意圖有一個灰色的節點了吧。ヽ(^o^)ノ

Copyright © Linux教程網 All Rights Reserved