C++中的forward_list是一种前向链表,是一种序列容器,可以在任何位置高效地插入和删除元素,它和list的区别是它只有前向指针,对于只需要单向迭代器就能完成的操作,使用forward_list比list有较高的存储效率。

forward_list包含在<forward_list>头文件中,它是一个类模板,因此在定义forward_list类的对象时,需要指明容器需要保存的对象的类型(除特殊情况外,本文均以int类型为例)。forward_list是C++11标准中的内容,需要支持C++11标准的编译器来编译。

构造与析构

  1. forward_list() 默认构造函数,构造一个空的容器,不包含任何元素;
  2. forward_list(size_type n, value_type &val) 填充构造函数,构造一个含有n个val的容器;
  3. forward_list(iterator first, iterator last) 范围构造函数,构造一个包含[first, last)的容器;
  4. forward_list(const forward_list<value_type> &x) 复制构造函数,构造一个与x相同的容器;
  5. forward_list(forward_list<value_type> &&x) 移动构造函数,如果指定的分配器与x相同,则直接引用x中的内容,而不是逐个分配;
  6. forward_list(initializer_list<value_type> il) 初始化列表构造函数;
  7. ~forward_list() 析构函数,释放内存并销毁对象。
#include <forward_list>
using std::forward_list;
int main()
{
    forward_list<int> fl1; // 空容器
    forward_list<int> fl2(4, 1); // 4个1
    forward_list<int> fl3(fl2.begin(), fl2.end()); // 和fl2相同
    forward_list<int> fl4(fl3); // 和fl3相同
    forward_list<int> fl5(std::move(fl4)); // 执行后fl4为空
    forward_list<int> fl6({1, 2, 3, 4});
    return 0;
}

迭代器

  1. before_begin() 返回第一个元素之前的迭代器,这个迭代器不可以被解引用,而是用于在容器前面插入元素;
  2. begin() 返回第一个元素的迭代器;
  3. end() 返回最后一个元素后面的迭代器(而不是最后一个元素);
  4. cbefore_begin()、cbegin()、cend() 表示对应的常量(const)迭代器。
#include <iostream>
#include <forward_list>
using std::cout;
using std::endl;
using std::forward_list;
 
int main()
{
    forward_list<int> fl({1, 2, 3, 4});
    cout << "The forward_list contains:";
    for(auto it = fl.begin(); it != fl.end(); ++it)
        cout << ' ' << *it;
    cout << endl;
    return 0;
}
/*
The forward_list contains: 1 2 3 4
*/

容量相关

  1. max_size() 返回在当前的系统环境下,容器最多可以容纳的元素个数,但并不一定可以达到这么多;
  2. empty() 若容器为空则返回true,否则返回false。

元素访问

  1. front() 返回第一个元素的引用。

增删元素

  1. assign(…) 为容器重新赋值;(使用…表示有多种参数不同的函数,在代码中给出示例)
  2. emplace_front(Args&&… args) 使用args构造并在容器前插入元素,没有返回值;
  3. push_front(value_type &val) 在容器前增加元素;
  4. pop_front() 删除第一个元素;
  5. emplace_after(const_iterator it, Args&&… args) 在指定位置后构造并插入元素,返回新元素的迭代器;
  6. insert_after(…) 在指定位置后插入元素,返回插入的最后一个元素的迭代器;
  7. erase_after(…) 删除下一个位置的元素,返回删除元素的下一个迭代器;
  8. swap(forward_list<value_type &f) 交换容器的内容;
  9. clear() 清空容器;
  10. resize(size_type n, const value_type &val) 将容器大小置为n,若当前比n小,则使用val填充,若当前比n大,则只保存前n个元素。
#include<iostream>
#include<forward_list>
 
using std::cout;
using std::endl;
using std::forward_list;
 
void show(forward_list<int> &fl)
{
    for(auto i : fl)
        cout << ' ' << i;
    cout << endl;
}
int main()
{
    forward_list<int> fl({1, 2, 3, 4});
 
    // assign:
    forward_list<int> fl2(2, 0);
    cout << "Before assign, the elements in fl2 are: ";
    show(fl2);
    auto it = fl.begin();
    ++it;
    // assign(InputIterator first, InputIterator last)
    fl2.assign(it, fl.end()); // 2 3 4
    // assign(size_type n, const value_type &val)
    fl2.assign(4, 0); // 4个0
    // assign(initializer_forward_list<value_type> il)
    fl2.assign({3, 2, 1}); // 3 2 1 (C++11)
    cout << "After assign, the elements in fl2 are: ";
    show(fl2);
 
    // 带有emplace的函数可参见vector,此处不再赘述
    // https://blog.kedixa.top/2016/cpp-container-vector/
    // 注意emplace 和emplace_after的区别
 
    // insert_after
    // insert_after(const_iterator it, const value_type &val)
    fl2.insert_after(fl2.before_begin(), 4); // 4 3 2 1
    // insert_after(const_iterator it, size_type n, const value_type &val)
    fl2.insert_after(fl2.begin(), 2, 0); // 4 0 0 3 2 1
    // insert(const_iterator it, InputIterator first, InputIterator last)
    fl2.insert_after(fl2.before_begin(), fl.begin(), fl.end()); // 1 2 3 4 4 0 0 3 2 1
    // insert_after(const_iterator it, value_type &&val)
    // 将val移动(move)到it位置,关于移动语义暂不讨论,省略
    // insert_after(const_iterator it, initializer_list<value_type> il)
    fl2.insert_after(fl2.before_begin(), {5});
    cout << "After insert, the elements in fl2 are: ";
    show(fl2);
 
    // erase_after
    // erase_after(const iterator it) 删除it指向的内容
    fl2.erase_after(fl2.begin());
    // erase_after(const_iterator first, const_iterator last) 删除区间(first, last)
    fl2.erase_after(fl2.begin(), fl2.end()); // 注意fl2.begin()本身没有被删除
    cout << "After erase, the elements in fl2 are: ";
    show(fl2);
 
    // swap
    fl2.swap(fl); // 1 2 3 4
    cout << "After swap, the elements in fl are: ";
    show(fl);
 
    // resize
    fl2.resize(7, 10);
    cout << "After swap and resize, the elements in fl2 are: ";
    show(fl2);
 
    fl2.clear(); // 清空容器
    if(fl2.empty()) cout << "After clear, fl2 is empty.\n";
    return 0;
}
/*
Before assign, the elements in fl2 are:  0 0
After assign, the elements in fl2 are:  3 2 1
After insert, the elements in fl2 are:  5 1 2 3 4 4 0 0 3 2 1
After erase, the elements in fl2 are:  5
After swap, the elements in fl are:  5
After swap and resize, the elements in fl2 are:  1 2 3 4 10 10 10
After clear, fl2 is empty.
*/

其他操作

  1. splice_after(…) 从另一个链表剪下一段并拼接到容器中;
  2. remove(const value_type &val) 删除所有值为val的元素;
  3. remove_if(Predicate pred) 删除所有使谓词为真的元素;
  4. unique(…);
  5. merge(forward_list<value_type> &b, Compare cmp) 需要两个链表都是有序的,将该链表与b归并,函数返回后b容器为空,该函数可以指定比较函数;
  6. sort(Compare cmp) 将链表排序,若不指定排序函数,则按照operator<排序;
  7. reverse() 反转链表。
#include<iostream>
#include<forward_list>
 
using std::cout;
using std::endl;
using std::forward_list;
 
void show(forward_list<int> &fl)
{
    for(auto i : fl)
        cout << ' ' << i;
    cout << endl;
}
bool is_odd(int i)
{
    return i%2==1;
}
bool diff(int x, int y)
{
    return y - x == 1;
}
 
int main()
{
    forward_list<int> fl({1, 2, 3, 4});
    forward_list<int> fl2;
    // splice_after
    // splice_after(const_iterator it, forward_list &x) 将x的内容插入到迭代器it后面的位置
    fl2.splice_after(fl2.before_begin(), fl); // fl2: 1 2 3 4, fl为空
    fl.swap(fl2);
    // splice_after(const_iterator it, forward_list &x, const_iterator i) 将i后面的内容插入到it后面的位置
    fl2.splice_after(fl2.before_begin(), fl, fl.before_begin()); // fl2: 1, fl: 2 3 4
    // splice_after(const_iterator it, forward_list &x, const_iterator first, const_iterator last)
    // 将x的(first, last) 插入到 it后面的位置
    fl2.splice_after(fl2.begin(), fl, fl.begin(), fl.end());
    cout << "After splice, the elements in fl are: ";
    show(fl);
    cout << "After splice, the elements in fl2 are: ";
    show(fl2);
 
    // remove
    fl2 = forward_list<int>({1, 1, 2, 3, 4, 5});
    fl2.remove(1); // 2 3 4 5
    fl2.remove_if(is_odd); // 2 4
    cout << "After remove, the elements in fl2 are: ";
    show(fl2);
 
    // unique
    fl2 = forward_list<int>({1, 1, 1, 2, 2, 3, 4, 6, 7});
    // unique() 相邻的相同元素只保留一个
    fl2.unique(); // 1 2 3 4 6 7
    // unique(BinaryPredicate pred) 若pred(*it, *(it-1))返回真,则删除it指向的内容
    fl2.unique(diff);
    cout << "After unique, the elements in fl2 are: ";
    show(fl2);
 
    // merge
    fl.assign({1, 3, 5});
    fl2 = forward_list<int>({2, 4});
    fl2.merge(fl);
    cout << "After merge, the elements in fl2 are: ";
    show(fl2);
 
    // reverse
    fl2.reverse();
    cout << "After reverse, the elements in fl2 are: ";
    show(fl2);
 
    // sort
    fl2.sort();
    cout << "After sort, the elements in fl2 are: ";
    show(fl2);
    return 0;
}
/*
After splice, the elements in fl are:  2
After splice, the elements in fl2 are:  1 3 4
After remove, the elements in fl2 are:  2 4
After unique, the elements in fl2 are:  1 3 6
After merge, the elements in fl2 are:  1 2 3 4 5
After reverse, the elements in fl2 are:  5 4 3 2 1
After sort, the elements in fl2 are:  1 2 3 4 5
*/

总结

forward_list是一个单向链表,因此适用于只需要单向遍历就可以完成的任务。它支持快速向链表中插入元素,但首先需要知道这个位置的前一个元素才可以执行插入操作。

需要注意的是,forward_list没有提供获取容器大小的成员函数,因此,如果需要经常获取容器的大小可能会耗费很多时间,因为这需要遍历容器中的所有元素来计算。

0

发表评论

邮箱地址不会被公开。 必填项已用*标注