C++11

// <forward_list>
template < class T, class Alloc = allocator<T> > class forward_list;

正向列表(Forward list)是一个允许在序列中任何一处位置以常量耗时插入或删除元素的顺序容器(Sequence container)。

A forward_list is a container that supports forward iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically.

C++编程语言国际标准:ISO/IEC 14882:2011

容性特性

顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

单链表

容器中的每个元素保存了定位前一个元素及后一个元素的信息,允许在任何一处位置以常量耗时进行插入或删除操作,但不能进行直接随机访问(Direct random access)。

能够感知内存分配器的(Allocator-aware)

容器使用一个内存分配器对象来动态地处理它的存储需求。

  • T

    存储在容器中的元素的数据类型。

    在类模板内部,使用其别名为 value_type 的成员类型。

    Alloc

    容器内部用来管理内存分配及释放的内存分配器的类型。

    这个参数是可选的,它的默认值是 std::allocator<T>,这个是一个最简单的非值依赖的(Value-independent)内存分配器。 在类模板内部,使用其别名为 allocator_type 的成员类型。

  • 标准模板库(Standard Template Library,简称STL)中的正向列表容器采用的是单链表(Singly-linked lists)数据库构。单链表可以保存以不同且无关的储存位置容纳的元素。元素间的顺序是通过各个元素中指向下一个元素的链接这一联系维护的。

    该特点跟 std:: list 容器的有点相似:主要的区别就是 std:: list 的元素中不仅保存了指向下一个元素的链接,还保存了指向上一个元素的链接,这使得 std::list 允许双向迭代,但消耗更多的存储空间且在插入删除元素时会有稍高(Slight higher)的耗时。因此 std::forward_list 对象比 std::list 对象更高效,尽管它们只能正向迭代。

    增加或移动正向列表中的元素不会使指向它们的指针、引用、迭代器失效,只有当对应的元素被销毁时才会如此。

    相比较于其它的基本标准顺序容器(数组 std::array、向量 std::vector、双端队列 std::deque 等),正向列表通常在容器中已获得迭代器的任意位置处插入、获得(Extracting,提取)、移动元素等操作中表现出更出色的性能,对那些密集使用上述操作的算法,使用正向列表同样能提升性能,比如排序算法。

    双向链表(std::list)及正向链表(std:: forward_list)相比于其它顺序容器的主要缺点是它们不能够通过元素在容器中的位置直接访问(Direct access)元素。举个例子:如果想访问一个正向列表中的第六个元素,那么就必须从一个已知位置(比如开头或末尾)处开始迭代,这会消耗与两个位置之间距间相关的线性时间。而且它们还为保存各个元素间的链接信息消耗更多额外的内存(这点对由小尺寸元素组成而元素数较大的正向列表尤为明显)。

    Fast random access to list elements is not supported.

    C++编程语言国际标准:ISO/IEC 14882:2011

    forward_list 类模板是专为极度考虑性能的程序而设计的,它就跟自实现的C型单链表(C-style singly-linked list)一样高效。甚至为了性能,它是唯一一个缺少 size 成员函数的标准容器:这是出于其单链表的性质,如果拥有 size 成员函数,就必须消耗常量时间来维护一个用于保存当前容器大小的内部计数器,这会消耗更多的存储空间,且使得插入及删除操作略微降低性能。如果想获得 forward_list 的大小,可以使用 std::distance 算法且传递 forward_list::beginforward_list::end 参数,该操作的时间复杂度为 O(n)

    对任意列表(std::list)进行插入或删除元素操作需要访问插入位置前的元素,但对 forward_list 来说访问该元素没有常数时间(Constant-time)的方法。因为这个原因,对传递给清除(Erase)、拼接(Splice)等成员函数的范围参数作了修改,这些范围必须为开区间(即不包括末尾元素的同时也不包括起始元素)。

    Modifying any list requires access to the element preceding the first element of interest, but in a forward_list there is no constant-time way to acess a preceding element. For this reason, ranges that are modified, such as those supplied to erase and splice, must be open at the beginning.

    C++编程语言国际标准:ISO/IEC 14882:2011

  • 成员类型 定义
    value_type 第一个模板参数 T
    allocator_type 第二个模板参数 Alloc
    size_type 无符号整数类型(通常为 size_t
    difference_type 有符号整数类型(通常为 ptrdiff_t
    reference value_type&
    const_reference const value_type&
    pointer std::allocator_traits<Allocator>::pointer
    const_pointer std::allocator_traits<Allocator>::const_pointer
    iterator 正向迭代器
    const_iterator 常正向迭代器
  • (constructor) 创建 forward_list
    (destructor) 释放 forward_list​
    operator= 值赋操作

    Iterators:

    before_begin 返回指向容器起始位置前的迭代器(iterator
    begin 返回指向容器起始位置的迭代器
    end 返回指向容器末尾位置的迭代器
    cbefore_begin 返回指向容器起始位置前的常迭代器(const_iterator
    cbegin 返回指向容器起始位置的常迭代器
    cend 返回指向容器末尾位置的常迭代器

    Capacity:

    empty 判断是否为空
    max_size 返回 forward_list 支持的最大元素个数

    Element access:

    front 访问第一个元素

    Modifiers

    assign 将新的内容赋值给容器
    emplace_front  在容器开头构造及插入一个元素
    push_front 在容器开头插入一个元素
    pop_front 删除第一个元素
    emplace_after 构造及插入一个元素
    insert_after 插入元素
    erase_after 删除元素
    swap 交换内容
    resize 改变有效元素的个数
    clear 清空内容

    Operations:

    splice_after 使元素从一个正向列表移动到另一个正向列表
    remove 删除值为指定值的元素
    remove_if 删除满足指定条件的元素
    unique 删除重复值
    merge 合并已排序的正向列表
    sort 为容器中的所有元素排序
    reverse 反转元素的顺序

    Observers

    get_allocator 获得内存分配器
  • operator==、operator!=、operator<、operator<=、operator>、operator>= 关系操作符
    std::swap 交换两个正向列表的内容
  • <algorithm> 头文件中包含大量与 forward_list 容器相关的算法,常使用的有

    搜索算法std::adjacent_findstd::count
    std::count_ifstd::find
    std::find_ifstd::find_end
    std::find_first_ofstd::search
    std::search_nstd::equal
    std::mismatch
    二分查找(Binary search)std::lower_boundstd::upper_bound
    std::equal_rangestd::binary_search
    集合(Set)操作std::includesstd::set_difference
    std::set_intersectionstd::set_union
    std::set_symmetric_difference
    最大与最小std::min_elementstd::max_element
    字典序比较std::lexicographical_compare
    排列生成器std::next_permutation
    std::prev_permutation
    其它操作std::all_ofstd::any_ofstd::none_of
    std::for_eachstd::copystd::copy_if
    std::copy_nstd::copy_backward
    std::movestd::move_backward
    std::swap_rangesstd::iter_swap
    std::transformstd::replace
    std::replace_ifstd::replace_copy
    std::replace_copy_ifstd::fill
    std::fill_nstd::generate
    std::generate_nstd::remove
    std::remove_ifstd::unique
    std::unique_copystd::reverse
    ​std::reverse_copystd::rotate
    std::rotate_copystd::random_shuffle
    std::shufflestd::partition
    std::is_partitionedstd::stable_partition
    std::partition_copystd::merge

    具体内容详见各个功能函数。除了排序(std::sort 等)、堆操作(std::make_heapstd::sort_heap 等)、第n个元素(std::nth_element),适用于 std::vector 的例子基本上都适用于 std::forward_list,可以参考 vector 与算法 主题,该主题包含大量的代码示例

  • 综合

    下面这个例子简单地介绍了 forward_list 的常用使用方法。

    #include <iostream> 
    #include <forward_list>
    #include <numeric> 
    #include <algorithm> 
     
    namespace ClassFoo{
     
    using namespace std; 
    
    void ForwardListExample1(){
        forward_list<int> foo1; 
        forward_list<int>::iterator it; 
        
        //从前面向foo1容器中添加数据 
        foo1.push_front (2); 
        foo1.push_front (1); 
        foo1.push_front (14); 
        foo1.push_front (17); 
        
        //按从小到大排序
        foo1.sort();
        cout<<"foo1中的元素"<<endl; 
        for (it = foo1.begin(); it != foo1.end(); ++it) 
            cout << *it << " "; 
        cout << endl; 
        
        //使用STL的accumulate(累加)算法 
        int result = accumulate(foo1.begin(), foo1.end(),0); 
        cout<<"和为:"<<result<<endl; 
      
        //使用STL的max_element算法求foo2中的最大元素并显示 
        it=max_element(foo1.begin(),foo1.end()); 
        cout << "最大元素是: "<< *it <<endl; 
    }
    }
     
    int main() 
    { 
        ClassFoo::ForwardListExample1();
        return 0;
    } 

    输出

    foo1中的元素
    1 2 14 17
    和为:34
    最大元素是: 17

    一个有用的宏

    虽然 C++11 中已经开始支持初始化列表,但可能您的编译器还未支持(即使已经支持 C++11),此时,可以使用如下等效的解决方案。

    #define CLASSFOO_FORWARD_LIST(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::forward_list<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))

    可以这样使用:

    CLASSFOO_FORWARD_LIST(int,foo,{1,2,3,4,5,6,7});