C++ forward_list用法詳解

2020-07-16 10:04:28
forward_list 容器以單連結串列的形式儲存元素。forward_list 的模板定義在標頭檔案 forward_list 中。fdrward_list 和 list 最主要的區別是:它不能反向遍歷元素;只能從頭到尾遍歷。

forward_list 的單向連結性也意味著它會有一些其他的特性:
  1. 無法使用反向疊代器。只能從它得到const或non-const前向疊代器,這些疊代器都不能解除參照,只能自增;
  2. 沒有可以返回最後一個元素參照的成員函數back();只有成員函數front();
  3. 因為只能通過自增前面元素的疊代器來到達序列的終點,所以push_back()、pop_back()、emplace_back()也無法使用。

forward_list 的操作比 list 容器還要快,而且佔用的記憶體更少,儘管它在使用上有很多限制,但僅這一點也足以讓我們滿意了。

forward_list 容器的建構函式的使用方式和 list 容器相同。forward_list 的疊代器都是前向疊代器。它沒有成員函數 size(),因此不能用一個前向疊代器減去另一個前向疊代器,但是可以通過使用定義在標頭檔案 iterator 中的 distance() 函數來得到元素的個數。例如:
std::forward_list<std::string> my_words {"three", "six", "eight"};
auto count = std::distance(std::begin(my_words),std::end(my_words));
// Result is 3
distance() 的第一個引數是一個開始疊代器,第二個引數是一個結束疊代器,它們指定了元素範圍。當需要將前向疊代器移動多個位置時,advance() 就派上了用場。例如:
std::forward_list<int> data {10, 21, 43, 87, 175, 351};
auto iter = std::begin(data);
size_t n {3};
std::advance(iter, n);
std::cout << "The " << n+1 << "th element is n << *iter << std::endl;
// Outputs 87
這並不神奇。advance() 函數會將前向疊代器自增需要的次數。這使我們不必去迴圈自增疊代器。需要記住的是這個函數自增的是作為第一個引數的迭代器,但是並不會返回它——advance() 的返回型別為 void。

因為 forward_list 正向連結元素,所以只能在元素的後面插入或黏接另一個容器的元素,這一點和 list 容器的操作不同,list 可以在元素前進行操作。因為這個,forward_list 包含成員函數splice_after() 和 insert_after(),用來代替 list 容器的 splice() 和 insert();顧名思義,元素會被黏接或插入到 list 中的一個特定位置。當需要在 forward_list 的開始處黏接或插入元素時,這些操作仍然會有問題。除了第一個元素,不能將它們黏接或插入到任何其他元素之前。

這個問題可以通過使用成員函數 cbefore_begin() 和 before_begin() 來解決。它們分別可以返回指向第一個元素之前位置的 const 和 non-const 疊代器。所以可以使用它們在開始位置插入或黏接元素。例如:
std::forward_list<std::string> my_words {"three", "six", "eight"}
std::forward_list<std::string> your_words {"seven", "four", "nine"};
my_words.splice_after(my_words.before_begin(), your_words, ++std::begin(your_words));
這個操作的效果是將 your_words 的最後一個元素黏接到 my_words 的開始位置,因此 my_words 會包含這些字串物件:"ninef"、"three"、"six"、"eight"。這時 your_words 就只剩下兩個字串元素:"seven"和"four”。

還有另一個版本的 splice_afler(),它可以將 forward_list<T> 的一段元素黏接到另一個容器中:
my_words.splice_after (my_words . before_begin () , your_words,++std::begin(your_words), std::end(your_words));
最後兩個疊代器引數,指定了第三個引數所指定的 fbrward_list<T> 容器的元素範圍。在這個範圍內的元素,除了第一個,其他的都被移到第一個引數所指定容器的特定位置。 因此,如果在容器初始化後執行這條語句,my_words 會包含"four"、"nine"、"three"、"six"、 "eight",your_words 僅僅包含"seven”。

另一個版本的 splice_after() 會將一個 forward_list<T> 容器的全部元素黏接到另一個容器中:
my_words.splice_after(my_words.before_begin(), your_words);
上面的程式碼會將 your_words 中的全部元素拼接到第一個元素指定的位置。

forward_list 和 list —樣都有成員函數 sort() 和 merge(),它們也都有 remove()、remove_if() 和unique(),所有這些函數的用法都和 list 相同。我們可以嘗試在一個範例中演示 forward_list 的操作。容器會包含一些代表矩形盒子的 Box 類物件。下面是 Box 類的標頭檔案中的內容:
// Defines the Box class for Ex2_06
#ifndef BOX_H
#define BOX_H
#include <iostream>                              // For standard streams
#include <utility>                               // For comparison operator templates
using namespace std::rel_ops;                    // Comparison operator template namespace

class Box
{
private:
    size_t length {};
    size_t width {};
    size_t height {};

public:
    explicit Box(size_t l = 1, size_t w = 1, size_t h = 1) : length {l}, width {w}, height {h} {}
    double volume() const { return length*width*height; }
    bool operator<(const Box& box) { return volume() < box.volume(); }
    bool operator==(const Box& box) { return length == box.length&& width == box.width&&height == box.height; }

    friend std::istream& operator>>(std::istream& in, Box& box);
    friend std::ostream& operator<<(std::ostream& out, const Box& box);
};

inline std::istream& operator>>(std::istream& in, Box& box)
{
    std::cout << "Enter box length, width, & height separated by spaces - Ctrl+Z to end: ";
    size_t value;
    in >> value;
    if (in.eof()) return in;

    box.length = value;
    in >> value;
    box.width = value;
    in >> value;
    box.height = value;
    return in;
}

inline std::ostream& operator<<(std::ostream& out, const Box& box)
{
    out << "Box(" << box.length << "," << box.width << "," << box.height << ")  ";
    return out;
}
#endif
utility 標頭檔案中的名稱空間 std::relops 包含一些比較運算子的模板。如果一個類已經定義了 operator<() 和 operator==(),那麼在需要時,這個模板會生成剩下的比較運算子函數。

Box 類有三個私有成員,它們定義了 Box 物件的整體尺寸。帶預設值的建構函式提供了一個無參建構函式,當在容器中儲存 Box 物件時,需要使用它;沒有初始化的元素由這種元素預設的建構函式生成。內聯的友元函數過載了流的提取和插入運算,這顯然包含標準輸入輸出流。

每次以三個輸入值為一組,在讀入第一個輸入值後,operator>>() 函數會通過呼叫流物件的 eof() 函數來檢查是否讀到 EOF。當輸入 Ctrl+Z 或從檔案輸入流中讀到檔案結束符時,標準輸入流會被設定為 EOF。當這些發生時會結束輸入,然後返回一個流物件,EOF 狀態會繼續保持,因此呼叫程式可以檢測到這個狀態。

下面是一個在 forward_list 容器中儲存 Box 物件的範例:
// Working with a forward list
#include <algorithm> // For copy()
#include <iostream> // For standard streams
#include <forward_list> // For forward_list container
#include <iterator> // For stream iterators
#include "Box.h"
// List a range of elements
template<typename Iter>
void list_elements(Iter begin, Iter end)
{
    size_t perline {6};                            // Maximum items per line
    size_t count {};                               // Item count
    while (begin != end)
    {
        std::cout << *begin++;
        if (++count % perline == 0)
        {
            std::cout << "n";
        }
    }
    std::cout << std::endl;
}

int main()
{
    std::forward_list<Box> boxes;
    std::copy(std::istream_iterator<Box>(std::cin), std::istream_iterator<Box>(), std::front_inserter(boxes));

    boxes.sort();                                    // Sort the boxes
    std::cout << "nAfter sorting the sequence is:n";
    // Just to show that we can with Box objects - use an ostream iterator
    std::copy(std::begin(boxes), std::end(boxes), std::ostream_iterator<Box>(std::cout, " "));
    std::cout << std::endl;

    // Insert more boxes
    std::forward_list<Box> more_boxes {Box {3, 3, 3}, Box {5, 5, 5}, Box {4, 4, 4}, Box {2, 2, 2}};
    boxes.insert_after(boxes.before_begin(), std::begin(more_boxes), std::end(more_boxes));
    std::cout << "After inserting more boxes the sequence is:n";
    list_elements(std::begin(boxes), std::end(boxes));

    boxes.sort();                                    // Sort the boxes
    std::cout << std::endl;
    std::cout << "The sorted sequence is now:n";
    list_elements(std::begin(boxes), std::end(boxes));

    more_boxes.sort();
    boxes.merge(more_boxes);                         // Merge more_boxes
    std::cout << "After merging more_boxes the sequence is:n";
    list_elements(std::begin(boxes), std::end(boxes));

    boxes.unique();
    std::cout << "After removing successive duplicates the sequence is:n";
    list_elements(std::begin(boxes), std::end(boxes));

    // Eliminate the small ones
    const double max_v {30.0};
    boxes.remove_if([max_v](const Box& box){ return box.volume() < max_v; });
    std::cout << "After removing those with volume less than 30 the sorted sequence is:n";
    list_elements(std::begin(boxes), std::end(boxes));
}
執行結果為:

Enter box length, width, & height separated by spaces - Ctrl+Z to end: 4 4 5
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 6 5 7
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 2 2 3
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 12 3
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 3 3 4
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 3 3 3
Enter box length, width, & height separated by spaces - Ctrl+Z to end: ^Z
After sorting the sequence is:
Box(l,2,3) Box(2,2,3) Box(3,3,3) Box(3,3,4) Box(4,4,5) Box(6,5,7)
After inserting more boxes the sequence is:
Box(3,3,3) Box(5,5,5) Box(4,4,4) Box{2,2,2) Box(1,2,3) Box(2,2,3)
Box(3,3,3) Box(3,3,4) Box(4,4,5) Box(6,5,7)

The sorted sequence is now:
Box(l,2,3) Box(2,2,2) Box(2,2,3) Box(3,3,3) Box(3,3,3) Box(3,3,4)
Box (4,4,4) Box(4,4,5) Box(5,5,5) Box(6,5,7)
After merging more_boxes the sequence is:
Box(1,2,3) Box(2,2,2) Box(2,2,2) Box(2,2,3) Box(3,3,3) Box(3,3,3)
Box(3,3,3) Box(3,3,4) Box(4,4^4) Box(4,4,4) Box(4,4,5) Box(5,5,5)
Box(5,5,5) Box(6,5,7)
After removing successive duplicates the sequence is:
Box(1,2,3) Box(2,2,2) Box(2,2,3) Box (3,3,3) Box(3,3,4) Box(4,4,4)
Box(4,4,5) Box(5,5,5) Box(6,5,7)
After removing those with volume less than 30 the sorted sequence is:
Box(3,3,4) Box(4,4) Box(4,4,5) Box(5,5,5) Box(6,5,7)

函數模板 list_dements() 用來輸出由開始和結束疊代器指定的元素,每 6 個元素一行。這裡用來輸出 main() 中的 forward_list 的內容。在 main() 中,首先使用 copy() 演算法,以 istream_iterator<Box> 物件作為資料來源,以 front_inserter 作為資料存放地,從 cin 中讀入一些 Box 物件的尺寸。istream_iterator 會呼叫定義在 Box.h 中的函數 operator>>() 來讀取 Box 物件。

front_inserter 會呼叫容器的成員函數 push_front(),這是為 forward_list 所做的工作。對 boxes 容器中的元素進行排序後,我們會通過copy() 演算法將元素轉移到 ostream_iterator<Box> 物件中,然後輸出它們。這個疊代器會呼叫定義在 Box.h 中的函數 operator<<()。這裡有一個限制,我們無法控制每行元素輸出的個數。剩下的程式碼是用模板 list_elements() 輸出的範例。

另一個 forward_list 容器 more_boxes 的內容被插入到 boxes 容器的頭部。這是通過以函數 before_begin() 返回的疊代器作為插入位置,然後呼叫函數 insert_after() 來實現的。

下一步操作是對 boxes 中的元素進行排序,然後將 more_boxes 的內容合併到 boxes 中。這兩個容器在呼叫merge()前都必須先排序,因為只有在兩個容器都是升序時,這個操作才能正常進行。因為插入新元素,顯然會使 boxes 中出現一些重複的元素。呼叫 boxes 的函數 unique() 就可以消除連續重複的元素。

最後一個操作是呼叫 boxes() 的函數 remove_if() 來 刪除容器中的一些元素。由作為引數傳入的一元斷言來決定刪除哪些元素。這裡使用的是一個 lambda 表示式,如果元素體積小於 max_v,就返回 true。max_v 是從外部區域以值的方式捕獲的,因此外部區域和表示式內部的值可能不同。由輸出可以看出,所有的操作都符合預期。