C++容器：forward_list – kedixa的博客

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

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

构造与析构

forward_list() 默认构造函数，构造一个空的容器，不包含任何元素；
forward_list(size_type n, value_type &val) 填充构造函数，构造一个含有n个val的容器；
forward_list(iterator first, iterator last) 范围构造函数，构造一个包含[first, last)的容器；
forward_list(const forward_list<value_type> &x) 复制构造函数，构造一个与x相同的容器；
forward_list(forward_list<value_type> &&x) 移动构造函数，如果指定的分配器与x相同，则直接引用x中的内容，而不是逐个分配；
forward_list(initializer_list<value_type> il) 初始化列表构造函数；
~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;
}

迭代器

before_begin() 返回第一个元素之前的迭代器，这个迭代器不可以被解引用，而是用于在容器前面插入元素；
begin() 返回第一个元素的迭代器；
end() 返回最后一个元素后面的迭代器（而不是最后一个元素）；
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
*/

容量相关

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

元素访问

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

增删元素

assign(…) 为容器重新赋值；（使用…表示有多种参数不同的函数，在代码中给出示例）
emplace_front(Args&&… args) 使用args构造并在容器前插入元素，没有返回值；
push_front(value_type &val) 在容器前增加元素；
pop_front() 删除第一个元素；
emplace_after(const_iterator it, Args&&… args) 在指定位置后构造并插入元素，返回新元素的迭代器；
insert_after(…) 在指定位置后插入元素，返回插入的最后一个元素的迭代器；
erase_after(…) 删除下一个位置的元素，返回删除元素的下一个迭代器；
swap(forward_list<value_type &f) 交换容器的内容；
clear() 清空容器；
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.
*/

其他操作

splice_after(…) 从另一个链表剪下一段并拼接到容器中；
remove(const value_type &val) 删除所有值为val的元素；
remove_if(Predicate pred) 删除所有使谓词为真的元素；
unique(…)；
merge(forward_list<value_type> &b, Compare cmp) 需要两个链表都是有序的，将该链表与b归并，函数返回后b容器为空，该函数可以指定比较函数；
sort(Compare cmp) 将链表排序，若不指定排序函数，则按照operator<排序；
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没有提供获取容器大小的成员函数，因此，如果需要经常获取容器的大小可能会耗费很多时间，因为这需要遍历容器中的所有元素来计算。

本文由kedixa发表于个人博客，转载请注明作者及出处。
本文链接：https://blog.kedixa.top/2016/cpp-container-forward_list/

构造与析构

迭代器

容量相关

元素访问

增删元素

其他操作

总结

发表回复 取消回复

发表回复取消回复