c++ 11 链表容器新增加了std::forward_list， 它与std::list有什么不同， 学习学习。

std::forward_list - cppreference.com

1. 定义

std::forward_list 是支持从容器中的任何位置快速插入和移除元素的容器。不支持快速随机访问。它实现为单链表，且实质上与其在 C 中的实现相比无任何开销。与 std::list 相比，此容器在不需要双向迭代时提供更好的存储空间效率。

在链表内或跨数个链表添加、移除和移动元素，不会使当前指代链表中其他元素的迭代器失效。然而，在从链表移除元素（通过 erase_after）时，指代对应元素的迭代器或引用会失效。

std::forward_list 满足容器 (Container) （但不包括 size 成员函数，且 operator== 的复杂度始终为线性）、知分配器容器 (AllocatorAwareContainer) 和序列容器 (SequenceContainer) 的要求。

成员类型

成员函数

2. 示例

• 初始化

#include <iostream>
#include <forward_list>

int main() {
    
    auto show = [](const char* str, const std::forward_list<int>& f) {
        std::cout <<str<< " : ";
        for (const auto& v : f) {
            std::cout << v << " ";
        }
        std::cout << std::endl;
    };

    std::forward_list<int> f1{1, 2, 3, 4, 5};
    show("f1", f1);
    std::forward_list<int> f2(f1);
    show("f2", f2);
    std::forward_list<int> f3 = f1;
    show("f3", f3);
    std::forward_list<int> f4;
    f4.assign(f1.begin(), f1.end());
    show("f4", f4);
    std::forward_list<int> f5;
    f5.assign({ 1, 2, 3, 4, 5 });
    show("f5", f5);
    std::forward_list<int> f6;
    f6.assign(5, 0);
    show("f6", f6);
    return 0;
}

• 迭代器

#include <iostream>
#include <forward_list>
#include <algorithm> 

int main() {
    
    std::forward_list<int> f1{1, 2, 3, 4, 5};
    {
        auto iter = f1.begin();
        iter++;
        //iter--; 错误
        //如名字所示, 只能向进，不能后退
    }

    //注意: 返回指向容器开头之前的迭代器
    //就是出现一个空的项， 在首项之前.
    for (auto iter = f1.before_begin(); iter != f1.end(); ++iter) {
        if (iter == f1.before_begin()) {
            //应处理一些初始化动作
            std::cout << "before_begin : ";
            continue;
        }
        std::cout << *iter << " ";
    }
    std::cout << std::endl;
    //打印输出 : 0 1 2 3 4 5

    //std::forward_list<int>::iterator
    for (auto iter = f1.begin(); iter != f1.end(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    //std::forward_list<int>::const_iterator iter
    for (auto iter = f1.cbegin(); iter != f1.cend(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;
    
    for (auto elem : f1) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::for_each(f1.begin(), f1.end(), [](int& elem) {
        std::cout << elem << " ";
    });
    std::cout << std::endl;
    return 0;
}
/*
before_begin : 1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
*/

• 其它

#include <iostream>
#include <forward_list>
#include <algorithm> 
#include <list>

int main() {
    
    auto show = [](const char* str, const std::forward_list<int>& f) {
        std::cout << str << " : ";
        for (const auto& v : f) {
            std::cout << v << " ";
        }
        std::cout << std::endl;
    };

    std::forward_list<int> lst;
    std::forward_list<int>::iterator iter;

    //添加元素
    //iter = lst.insert_after(lst.begin(), 2); //错误
    //iter = lst.emplace_after(lst.end(), 2); //错误
    //lst.begin() == lst.end(), 不能在空项插入.
    iter = lst.insert_after(lst.before_begin(), 2);
    iter = lst.emplace_after(iter, 3);
    lst.emplace_front(1);
    lst.push_front(0);
    show("add ", lst);
    
    //删除元素
    lst.pop_front();
    show("pop_front", lst);
    lst.erase_after(lst.begin());
    show("erase", lst);
    lst.remove(3);
    show("remove=3", lst);
    lst.remove_if([](int& x) {return x == 1; });
    show("remove_if=1", lst);

    lst.assign({1, 2, 3, 4, 5});
    lst.resize(10, 9);
    show("resize", lst);

    lst.unique();
    show("unique", lst);

    lst.reverse();
    show("reverse", lst);

    lst.sort();
    show("sort", lst);
    return 0;
}
/*打印输出
add  : 0 1 2 3
pop_front : 1 2 3
erase : 1 3
remove=3 : 1
remove_if=1 :
resize : 1 2 3 4 5 9 9 9 9 9
unique : 1 2 3 4 5 9
reverse : 9 5 4 3 2 1
sort : 1 2 3 4 5 9
*/

3. 总结

通过上面的了解， std::forward_list只是对单链表进行一个简单的封装， 追求的是空间效率、性能。 非必要还是使用std::list吧。

c++ 疑难杂症(10) std::initializer_list

c++ 疑难杂症(9) std::array

c++ 疑难杂症(8) std::multimap

c++ 疑难杂症(7) std::tuple

c++ 疑难杂症(6) std::map

c++ 疑难杂症(5) std::pair

c++ 疑难杂症(4) std:vector

c++ 疑难杂症(3) 模板特化

c++ 疑难杂症(2) std::move

c++ 疑难杂症(1) std::thread