STL之forward_list

  • 头文件及声明
    1
    2
    3
    4
    5
    6
    7
    8
    9
    /*
        C++11
    */
    #include <forward_list>
    namespace std
    {
        template <typename T, typename Allocator = allocator<T>>
        class forward_list;
    }
  • 内部结构及其特性

forward_list使用的内部结构是单链表，并且anchor节点只在首部，因此forward_list有以下的特点：
1.forward_list只支持前向迭代器，并非双向迭代器，并且不支持反向迭代器；

  1. forward_list不提供size()函数，可以使用算法distance()，如distance(l.begin(), l.end())，但是时间复杂度为线性；
  2. 不支持尾部的操作，如push_back()；
  3. 因为是单链表的缘故，无法提供insert(),只能提供insert_after()，因此很多具有after后缀的函数；
  4. forward_list提供了before_begin()和cbefore_begin()来反应anchor节点的位置，和after系列函数配合使用。
  • 搜索，移除，插入

因为要找到相应元素，必须保存前一个的位置。