std::forward_list是在C++11中引入的單向鏈表或叫正向列表。forward_list具有插入、刪除表項速度快、消耗內(nèi)存空間少的特點，但只能向前遍歷。與其它序列容器(array、vector、deque)相比，forward_list在容器內(nèi)任意位置的成員的插入、提取(extracting)、移動、刪除操作的速度更快，因此被廣泛用于排序算法。forward_list是一個允許在序列中任何一處位置以常量耗時插入或刪除元素的順序容器(sequence container)。forward_list可以看作是對C語言風格的單鏈表的封裝，僅提供有限的接口，和C中它的實現(xiàn)相比，基本上不會有任何開銷。當不需要雙向迭代的時候，與std::list相比，該容器具有更高的空間利用率。

forward_list的主要缺點是不能在常量時間內(nèi)隨機訪問任意成員，對成員的訪問需要線性時間代價；以及存儲鏈接信息需要消耗內(nèi)存，特別是當包含大量的小規(guī)模成員時。forward_list處于效率考慮，有意不提供size()成員函數(shù)。獲取forward_list所包含的成員個數(shù)需要用std::distance(_begin, _end)算法。forward_list中的每個元素保存了定位前一個元素及后一個元素的信息，不能進行直接隨機訪問操作。

Forward lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence. Forward lists are implemented as singly-linked lists; Singly linked lists can store each of the elements they contain indifferent and unrelated storage locations. The ordering is kept by the association to each element of a link to the next element in the sequence.

?Compared to other base standard sequence containers (array, vector and deque), forward_list perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of forward_lists and lists compared to these other sequence containers is that they lack direct access to the elements by their position;For example, to access the sixth element in a forward_list one has to iterate from the beginning to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).?

一個容器就是一些特定類型對象的集合。順序容器(sequential container)為程序員提供了控制元素存儲和訪問順序的能力。這種順序不依賴于元素的值，而是與元素加入容器時的位置相對應(yīng)。

??????? 標準庫中的順序容器包括：

??????? (1)、vector：可變大小數(shù)組。支持快速隨機訪問。在尾部之外的位置插入或刪除元素可能很慢。

??????? (2)、deque：雙端隊列。支持快速隨機訪問。在頭尾位置插入/刪除速度很快。

??????? (3)、list：雙向鏈表。只支持雙向順序訪問。在list中任何位置進行插入/刪除操作速度都很快。

??????? (4)、forward_list：單向鏈表。只支持單向順序訪問。在鏈表任何位置進行插入/刪除操作速度都很快。

??????? (5)、array：固定大小數(shù)組。支持快速隨機訪問。不能添加或刪除元素。

??????? (6)、string：與vector相似的容器，但專門用于保存字符。隨機訪問快。在尾部插入/刪除速度快。

??????? 除了固定大小的array外，其它容器都提供高效、靈活的內(nèi)存管理。我們可以添加和刪除元素，擴張和收縮容器的大小。容器保存元素的策略對容器操作的效率有著固定的，有時是重大的影響。在某些情況下，存儲策略還會影響特定容器是否支持特定操作。

??????? 例如，string和vector將元素保存在連續(xù)的內(nèi)存空間中。由于元素是連續(xù)存儲的，由元素的下標來計算其地址是非常快速的。但是，在這兩種容器的中間位置添加或刪除元素就會非常耗時：在一次插入或刪除操作后，需要移動插入/刪除位置之后的所有元素，來保持連續(xù)存儲。而且，添加一個元素有時可能還需要分配額外的存儲空間。在這種情況下，每個元素都必須移動到新的存儲空間中。

??????? list和forward_list兩個容器的設(shè)計目的是令容器任何位置的添加和刪除操作都很快速。作為代價，這兩個容器不支持元素的隨機訪問：為了訪問一個元素，我們只能遍歷整個容器。而且，與vector、deque和array相比，這兩個容器的額外內(nèi)存開銷也很大。

??????? deque是一個更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。與string和vector類似，deque支持快速的隨機訪問。與string和vector一樣，在deque的中間位置添加或刪除元素的代價(可能)很高。但是，在deque的兩端添加或刪除元素都是很快的，與list或forward_list添加刪除元素的速度相當。

??????? forward_list和array是新C++標準增加的類型。與內(nèi)置數(shù)組相比，array是一個種更安全、更容易使用的數(shù)組類型。與內(nèi)置數(shù)組類似，array對象的大小是固定的。因此，array不支持添加和刪除元素以及改變?nèi)萜鞔笮〉牟僮鳌orward_list的設(shè)計目標是達到與最好的手寫的單向鏈表數(shù)據(jù)結(jié)構(gòu)相當?shù)男阅堋Ｒ虼?#xff0c;forward_list沒有size操作，因為保存或計算其大小就會比手寫鏈表多出額外的開銷。對其他容器而言，size保證是一個快速的常量時間的操作。

??????? 通常，使用vector是最好的選擇，除法你有很好的理由選擇其他容器。

??????? 以下是一些選擇容器的基本原則：

??????? (1)、除法你有很好的理由選擇其他容器，否則應(yīng)該使用vector；

??????? (2)、如果你的程序有很多小的元素，且空間的額外開銷很重要，則不要使用list或forward_list；

??????? (3)、如果程序要求隨機訪問元素，應(yīng)使用vector或deque；

? ? ? ? (4)、如果程序要求在容器的中間插入或刪除元素，應(yīng)使用list或forward_list；

(5)、如果程序需要在頭尾位置插入或刪除元素，但不會在中間位置進行插入或刪除操作，則使用deque；

(6)、如果程序只有在讀取輸入時才需要在容器中間位置插入元素，隨后需要隨機訪問元素，則：首先，確定是否真的需要在容器中間位置添加元素。當處理輸入數(shù)據(jù)時，通常可以很容器地向vector追加數(shù)據(jù)，然后再調(diào)用標準庫的sort函數(shù)來重排容器中的元素，從而避免在中間位置添加元素。如果必須在中間位置插入元素，考慮在輸入階段使用list，一旦輸入完成，將list中的內(nèi)容拷貝到一個vector中。

如果你不確定應(yīng)該使用哪種容器，那么可以在程序中只使用vector和list公共的操作：使用迭代器，不使用下標操作，避免隨機訪問。這樣，在必要時選擇使用vector或list都很方便。

一般來說，每個容器都定義在一個頭文件中，文件名與類型名相同。即，deque定義在頭文件deque中，list定義在頭文件list中，以此類推。容器均定義為模板類。

順序容器幾乎可以保存任意類型的元素。特別是，我們可以定義一個容器，其元素的類型是另一個容器。這種容器的定義與任何其他容器類型完全一樣：在尖括號中指定元素類型(此種情況下，是另一種容器類型)。

除了順序容器外，標準庫還定義了三個順序容器適配器：stack、queue和priority_queue。適配器(adaptor)是標準庫中的一個通用概念。容器、迭代器和函數(shù)都有適配器。本質(zhì)上，一個適配器是一種機制，能使某種事物的行為看起來像另外一種事物一樣。一個容器適配器接受一種已有的容器類型，使其行為看起來像一種不的類型。

下面是從其他文章中copy的std::forward_list測試代碼，詳細內(nèi)容介紹可以參考對應(yīng)的reference：

#include "forward_list.hpp"
#include <iostream>
#include <forward_list>
#include <array>
#include <functional>
#include <cmath>///
// reference: http://www.cplusplus.com/reference/forward_list/forward_list/
template<class Container>
static Container by_two(const Container& x)
{Container temp(x);for (auto& x : temp) x *= 2;return temp;
}// a predicate implemented as a function:
static bool single_digit(const int& value) { return (value<10); }// a predicate implemented as a class:
class is_odd_class
{
public:bool operator() (const int& value) { return (value % 2) == 1; }
} is_odd_object;// a binary predicate implemented as a function:
static bool same_integral_part(double first, double second)
{return (int(first) == int(second));
}// a binary predicate implemented as a class:
class is_near_class
{
public:bool operator() (double first, double second){return (fabs(first - second)<5.0);}
} is_near_object;int test_forward_list_1()
{
{ // forward_list::forward_list: Constructs a forward_list container object,// initializing its contents depending on the constructor version usedstd::forward_list<int> first;                      // default: emptystd::forward_list<int> second(3, 77);              // fill: 3 seventy-sevensstd::forward_list<int> third(second.begin(), second.end()); // range initializationstd::forward_list<int> fourth(third);            // copy constructorstd::forward_list<int> fifth(std::move(fourth));  // move ctor. (fourth wasted)std::forward_list<int> sixth = { 3, 52, 25, 90 };    // initializer_list constructorstd::cout << "first:"; for (int& x : first)  std::cout << " " << x; std::cout << '\n';std::cout << "second:"; for (int& x : second) std::cout << " " << x; std::cout << '\n';std::cout << "third:";  for (int& x : third)  std::cout << " " << x; std::cout << '\n';std::cout << "fourth:"; for (int& x : fourth) std::cout << " " << x; std::cout << '\n';std::cout << "fifth:";  for (int& x : fifth)  std::cout << " " << x; std::cout << '\n';std::cout << "sixth:";  for (int& x : sixth)  std::cout << " " << x; std::cout << '\n';
}{ // forward_list::assign: Assigns new contents to the forward_list container,// replacing its current contents, and modifying its size accordinglystd::forward_list<int> first;std::forward_list<int> second;first.assign(4, 15);                           // 15 15 15 15second.assign(first.begin(), first.end());     // 15 15 15 15first.assign({ 77, 2, 16 });                  // 77 2 16std::cout << "first contains: ";for (int& x : first) std::cout << ' ' << x;std::cout << '\n';std::cout << "second contains: ";for (int& x : second) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::before_begin: Returns an iterator pointing to the position before the first element in the container.// forward_list::cbefore_begin: Returns a const_iterator pointing to the position before the first element in the container.std::forward_list<int> mylist = { 20, 30, 40, 50 };mylist.insert_after(mylist.before_begin(), 11);mylist.insert_after(mylist.cbefore_begin(), 19);std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::begin: Returns an iterator pointing to the first element in the forward_list container.// forward_list::cbegin: Returns a const_iterator pointing to the first element in the container.// forward_list::end: Returns an iterator referring to the past-the-end element in the forward_list container// forward_list::cend: Returns a const_iterator pointing to the past-the-end element in the forward_list containerstd::forward_list<int> mylist = { 34, 77, 16, 2 };std::cout << "mylist contains:";for (auto it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;for (auto it = mylist.cbegin(); it != mylist.cend(); ++it)std::cout << ' ' << *it;   // cannot modify *itstd::cout << '\n';
}{ // forward_list::clear: Removes all elements from the forward_list container (which are destroyed),// and leaving the container with a size of 0std::forward_list<int> mylist = { 10, 20, 30 };std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';mylist.clear();mylist.insert_after(mylist.before_begin(), { 100, 200 });std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::emplace_after: The container is extended by inserting a new element after the element at position.// This new element is constructed in place using args as the arguments for its construction.// forward_list::emplace_front: Inserts a new element at the beginning of the forward_list, right before its current first element.// This new element is constructed in place using args as the arguments for its construction.std::forward_list< std::pair<int, char> > mylist;auto it = mylist.before_begin();it = mylist.emplace_after(it, 100, 'x');it = mylist.emplace_after(it, 200, 'y');it = mylist.emplace_after(it, 300, 'z');std::cout << "mylist contains:";for (auto& x : mylist)std::cout << " (" << x.first << "," << x.second << ")";std::cout << std::endl;mylist.emplace_front(10, 'a');mylist.emplace_front(20, 'b');mylist.emplace_front(30, 'c');std::cout << "mylist contains:";for (auto& x : mylist)std::cout << " (" << x.first << "," << x.second << ")";std::cout << '\n';
}{ // forward_list::empty: Returns a bool value indicating whether the forward_list container is empty, i.e. whether its size is 0std::forward_list<int> first;std::forward_list<int> second = { 20, 40, 80 };std::cout << "first " << (first.empty() ? "is empty" : "is not empty") << std::endl;std::cout << "second " << (second.empty() ? "is empty" : "is not empty") << std::endl;
}{ // forward_list::erase_after: Removes from the forward_list container either a single element (the one after position) or a range of elements std::forward_list<int> mylist = { 10, 20, 30, 40, 50 };// 10 20 30 40 50auto it = mylist.begin();                 // ^it = mylist.erase_after(it);              // 10 30 40 50//    ^it = mylist.erase_after(it, mylist.end()); // 10 30//       ^std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::front: Returns a reference to the first element in the forward_list container.std::forward_list<int> mylist = { 2, 16, 77 };mylist.front() = 11;std::cout << "mylist now contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::insert_after: The container is extended by inserting new elements after the element at positionstd::array<int, 3> myarray = { 11, 22, 33 };std::forward_list<int> mylist;std::forward_list<int>::iterator it;it = mylist.insert_after(mylist.before_begin(), 10);          // 10//  ^  <- itit = mylist.insert_after(it, 2, 20);                          // 10 20 20//        ^it = mylist.insert_after(it, myarray.begin(), myarray.end()); // 10 20 20 11 22 33//                 ^it = mylist.begin();                                             //  ^it = mylist.insert_after(it, { 1, 2, 3 });                        // 10 1 2 3 20 20 11 22 33//        ^std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::max_size: Returns the maximum number of elements that the forward_list container can holdstd::forward_list<int> mylist = { 2, 16, 77 };std::cout << "mylist max size:" << mylist.max_size() << std::endl;
}{ // forward_list::merge: Merges x into the forward_list by transferring all of its elements at their respective ordered positions// into the container (both containers shall already be ordered)// forward_list::sort: Sorts the elements in the forward_list, altering their position within the containerstd::forward_list<double> first = { 4.2, 2.9, 3.1 };std::forward_list<double> second = { 1.4, 7.7, 3.1 };std::forward_list<double> third = { 6.2, 3.7, 7.1 };first.sort();second.sort();first.merge(second);std::cout << "first contains:";for (double& x : first) std::cout << " " << x;std::cout << std::endl;first.sort(std::greater<double>());third.sort(std::greater<double>());first.merge(third, std::greater<double>());std::cout << "first contains:";for (double& x : first) std::cout << " " << x;std::cout << std::endl;
}{ // forward_list::operator=: Assigns new contents to the container, replacing its current contentsstd::forward_list<int> first(4);      // 4 intsstd::forward_list<int> second(3, 5);   // 3 ints with value 5first = second;                        // copy assignmentsecond = by_two(first);                // move assignmentstd::cout << "first: ";for (int& x : first) std::cout << ' ' << x;std::cout << '\n';std::cout << "second: ";for (int& x : second) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::pop_front: Removes the first element in the forward_list container, effectively reducing its size by one.std::forward_list<int> mylist = { 10, 20, 30, 40 };std::cout << "Popping out the elements in mylist:";while (!mylist.empty()) {std::cout << ' ' << mylist.front();mylist.pop_front();}std::cout << '\n';
}{ // forward_list::push_front: Inserts a new element at the beginning of the forward_list, right before its current first element.// The content of val is copied (or moved) to the inserted elementusing namespace std;forward_list<int> mylist = { 77, 2, 16 };mylist.push_front(19);mylist.push_front(34);std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::remove: Removes from the container all the elements that compare equal to val.// This calls the destructor of these objects and reduces the container size by the number of elements removedstd::forward_list<int> mylist = { 10, 20, 30, 40, 30, 20, 10 };mylist.remove(20);std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::remove_if: Removes from the container all the elements for which Predicate pred returns true.// This calls the destructor of these objects and reduces the container size by the number of elements removed.std::forward_list<int> mylist = { 7, 80, 7, 15, 85, 52, 6 };mylist.remove_if(single_digit);      // 80 15 85 52mylist.remove_if(is_odd_object);     // 80 52std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::resize: Resizes the container to contain n elementsstd::forward_list<int> mylist = { 10, 20, 30, 40, 50 };// 10 20 30 40 50mylist.resize(3);             // 10 20 30mylist.resize(5, 100);        // 10 20 30 100 100std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::reverse: Reverses the order of the elements in the forward_list container.std::forward_list<int> mylist = { 10, 20, 30, 40 };mylist.reverse();std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::splice_after: Transfers elements from fwdlst into the container inserting them after the element pointed by position.std::forward_list<int> first = { 1, 2, 3 };std::forward_list<int> second = { 10, 20, 30 };auto it = first.begin();  // points to the 1first.splice_after(first.before_begin(), second);// first: 10 20 30 1 2 3// second: (empty)// "it" still points to the 1 (now first's 4th element)second.splice_after(second.before_begin(), first, first.begin(), it);// first: 10 1 2 3// second: 20 30first.splice_after(first.before_begin(), second, second.begin());// first: 30 10 1 2 3// second: 20// * notice that what is moved is AFTER the iteratorstd::cout << "first contains:";for (int& x : first) std::cout << " " << x;std::cout << std::endl;std::cout << "second contains:";for (int& x : second) std::cout << " " << x;std::cout << std::endl;
}{ // forward_list::swap: Exchanges the content of the container by the content of fwdlst,// which is another forward_list object of the same type. Sizes may differstd::forward_list<int> first = { 10, 20, 30 };std::forward_list<int> second = { 100, 200 };std::forward_list<int>::iterator it;first.swap(second);std::swap(first, second);std::cout << "first contains:";for (int& x : first) std::cout << ' ' << x;std::cout << '\n';std::cout << "second contains:";for (int& x : second) std::cout << ' ' << x;std::cout << '\n';
}{ // forward_list::unique: Remove duplicate valuesstd::forward_list<double> mylist = { 15.2, 73.0, 3.14, 15.85, 69.5,73.0, 3.99, 15.2, 69.2, 18.5 };mylist.sort();                       //   3.14,  3.99, 15.2, 15.2, 15.85//  18.5,  69.2,  69.5, 73.0, 73.0mylist.unique();                     //   3.14,  3.99, 15.2, 15.85//  18.5,  69.2,  69.5, 73.0mylist.unique(same_integral_part);  //  3.14, 15.2, 18.5,  69.2, 73.0mylist.unique(is_near_object);      //  3.14, 15.2, 69.2std::cout << "mylist contains:";for (double& x : mylist) std::cout << ' ' << x;std::cout << '\n';
}{ // Performs the appropriate comparison operation between the forward_list containers lhs and rhs.std::forward_list<int> a = { 10, 20, 30 };std::forward_list<int> b = { 10, 20, 30 };std::forward_list<int> c = { 30, 20, 10 };if (a == b) std::cout << "a and b are equal\n";if (b != c) std::cout << "b and c are not equal\n";if (b<c) std::cout << "b is less than c\n";if (c>b) std::cout << "c is greater than b\n";if (a <= b) std::cout << "a is less than or equal to b\n";if (a >= b) std::cout << "a is greater than or equal to b\n";
}{ // get forward_list elements sizestd::forward_list<int> a = { 10, 20, 30 };size_t size = std::distance(a.begin(), a.end());std::cout << "a size: " << size << std::endl;
}return 0;
}

GitHub： https://github.com/fengbingchun/Messy_Test

總結(jié)

以上是生活随笔為你收集整理的C++11中std::forward_list单向链表的使用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。