C++ 如何在forward_list尾部插入元素？

写了一个demo，楼主可以参考下，先遍历到end()前一个迭代器，后插入元素。

#include<iostream>

#include<forward_list>

using namespace std

// push element to forward_list from rear

void m_push_rear(forward_list<int> &a,int x)

{

    if(a.empty())

        a.push_front(x)

    else{

        forward_list<int>::iterator it = a.begin()

        forward_list<int>::iterator pre = a.begin()

        while(1){

            pre = it++

            if(it == a.end())

                break

        }

        a.insert_after(pre,x)

    }

}

// print all element in forward_list

void printall(forward_list<int> a)

{

    while(!a.empty()){

        cout<<a.front()<<endl

        a.pop_front()

    }

}

int main()

{

    forward_list<int> a

    a.push_front(10)

    a.push_front(12)

    cout<<"Before:"<<endl

    printall(a)

    m_push_rear(a,44)

    a.push_front(55)

    cout<<"After:"<<endl

    printall(a)

    return 0

}

所有容器类都共享公共的接口，不同容器按不同的方式进行扩展，这个公共接口使得学习容器更加容器。我们基于这种容器所学习的内容也都适用于其他容器。每种容器都提供了不同的性能和功能权衡

一个容器就是一些特定类型对象的集合。顺序容器为程序员提供了控制元素存储顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器的位置相对应。

所谓的顺序容器是指，在内存中数据存储有一定顺序。数据结构中的顺序容器有：可变数组、队列、数组、链表、栈。

c++ 标准库中的顺序容器提供了快速顺序访问元素的能力。但是这些容器在一下方面都有不同的性能折中

标准库中顺序容器主要有：

c++ 标准库中的容器是经过精心优化设计过的。性能通常会是同类数据结构中最好的。现代c++ 程序应该使用标准库容器，而不是原始的数据结构（如内置数组）

通常使用vector 是最好的选择，除非你有很好的理由选择其他容器

一下是一些选择容器的基本原则:

如果你不确定该使用哪种容器，可以在程序中只使用vector 和list公共的 *** 作，不使用下标 *** 作，使用迭代器，避免随机访问

迭代器是访问容器中元素的公共接口

所有迭代器都通过解引用运算符来实现这个 *** 作。标准库中的所有迭代器都定义了递增运算符，从当前元素移动到下一个元素。部分容器的迭代器也定义了递减运算符，用于从一个元素移动到上一个元素

一个迭代器范围是由一对迭代器来表示的。两个迭代器分别指向同一个容器的元素或者尾元素之后的位置。

如果两个迭代器满足以下两个条件，则这两个迭代器构成一个迭代器范围：

如果两个迭代器构成一个迭代器范围，则：

每个容器都定义了多个类型，我们已经使用了其中的3种：size_type、iterator、const_iterator

除了正向的迭代器，容器库还提供了反向遍历容器的迭代器，反向迭代器就是一种反向遍历容器的迭代器。与正向迭代器相比各种 *** 作的含义也都发生了颠倒。例如对一个反向迭代器执行++ *** 作，会得到上一个元素。

剩下的就是类型别名了。通过类型别名，我们可以在不了解容器中元素类型的情况下使用它，如果需要元素类型可以使用容器的value_type ，如果需要元素类型的一个引用可以使用reference或者const_reference。

begin 和 end *** 作生成一个指向容器中第一个元素和尾元素之后位置的迭代器范围。 begin 和 end 有多个版本。带r的版本返回反向迭代器，带c的版本返回const型迭代器

可以将一个容器初始化为另一个容器的拷贝

将一个新容器创建为另一个容器的拷贝的方法有两种：可以直接拷贝整个容器，或者拷贝由一个迭代器对指定的元素范围

为了创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配。当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。而且新容器和原容器中的元素类型也可以不同，只要能将拷贝的元素转化为要初始化的容器的元素类型即可

在新标准中我们对一个容器进行列表初始化

标准库array在定义之处就应该给出具体的大小，而且后续不允许修改它的大小

我们不能直接对内置数组执行拷贝或者对象赋值 *** 作，但是array对象允许

我们直接使用 = 运算符来将一个容器赋值为另一个容器的拷贝，但是要求容器类型完全相同，array也支持这种 *** 作

顺序容器(array除外)还定义了一个assign的成员，assign *** 作用参数所指定的元素替换左边容器中的所有元素

可以使用swap交换两个容器中的内容，要求两个容器类型完全相同。除了array外，swap不对任何元素进行拷贝、删除或者插入 *** 作，可以保证在常量时间内完成

每个容器都有三大与大小相关的 *** 作。

除了无序容器外的所有容器都支持关系运算符

关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素

比较的过程与比较string大小的过程类似

容器的相等运算符实际上是使用元素的 == 运算符实现比较的。而其他关系是使用元素的 < 运算符

使用这些 *** 作时必须记得不同类型的容器使用不同的元素分配策略，而这些策略直接影响性能。

每个顺序容器中都有一个front 函数，返回容器内第一个元素的引用。而除了forward_list 之外的所有顺序容器都有一个back成员函数。

另外可以使用at来访问随机位置的元素

记住，这些访问函数返回的都是引用

在对forward_list 进行增删 *** 作的时候，需要找到对应位置的前驱节点，而单向链表无法很容器的找到一个节点的前驱节点。因此对单向链表，提供了类似 insert_after、emplace_after、erase_after等 *** 作

可以使用resize 来增大或者缩小容器大小,如果是缩小容器大小，则指向被删除元素的迭代器、引用、指针都会失效

在向容器中添加元素后：

删除一个元素后，指向原来被删除元素的迭代器、指针和引用都会失效。

删除元素时尾后迭代器总是会失效

使用insert插入元素后可以保存返回的迭代器，然后用该迭代器进行迭代可以保证迭代器有效

不要保存end返回的迭代器

为了支持快速随机访问，vector 将元素连续存储。如果往容器中添加一个新元素时，发现容器空间已经不够了，就需要重新分配空间。并将已有元素逐一拷贝到新的内存空间中，然后添加新元素。

为了避免这种代价，标准库实现者采用了可以减少容器空间重新分配次数的策略。当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间

vector和string也提供了一些成员函数，允许我们与它的实现中内存分配部分互动。

一般来讲， vector 的实现采用的策略似乎是在每次需要分配新内容空间时将当前容量翻倍

除了顺序容器共同的 *** 作之外，string类还提供了一些额外的 *** 作。

这些 *** 作中的大部分要么是提供string类和C风格字符串之间的互相转换，要么是增加了允许我们用下标代替迭代器的版本。

标准库中提供了6个不同的搜索函数，每个函数有4中不同形式的重载版本。每个搜索 *** 作都返回string::size_type 值，表示匹配发生位置的下标。如果搜索失败返回一个名为string::npos 的static成员

compare函数用于比较两个大小字符串，与C标准库中的strcmp类似

适配器是标准库提供的一组概念，能使某种事物的行为看起来像另一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起来像另一种事物一样

标准库提供了三种适配器: stack、queue、priority_queue(优先级队列)

所有的适配器都要求容器具有添加和删除元素的能力。

stack 只要求类型容器具有 push_back、pop_back *** 作因此可以使用除了array 和 forward_list 之外的任何容器类型来进行构造

queue 要求容器类型具有 back、push_back、front、pop_back 因此它可以构造在list 或者deque之上但不能基于vector 构造

priority_queue 要求容器类型具有push_back、front、pop_back之外还要求容器具有随机访问的能力，所以它必须构造在vector之上

<hr />

① std::iterator_traits<Itr>::iterator_category() 前面须要添加typename，即：

sort_helper(beg, end, 

            typename std::iterator_traits<Itr>::iterator_category())

② sort_helper里面调用的sort应该是std::sort，否则namespace my中的sort_helper调用sort；而sort又调用sort_helper，相互调用了。。。。

template <typename For>

    void sort_helper(For beg, For end, std::forward_iterator_tag) {

        ...

        std::sort(v.begin(), v.end())

        std::copy(v.begin(), v.end(), beg)

        ...

    }

③ 最大的问题是sort_helper里面的这句：

  std::vector<decltype(*beg)> v{beg, end}

decltype() 这个返回的是一个引用，vector里不能｛直接｝放“引用”，结果会出现pointer to reference错误！！！。可修改如下：

typedef decltype(*beg) value_type

std::vector<typename For::value_type> v{beg, end}

修改后的完整代码如下：

#include <iostream>

#include <algorithm>

#include <forward_list>

#include <iterator>

#include <type_traits>

namespace my{

    template <typename Itr>

    void sort(Itr,Itr)

    template <typename Ran>

    void sort_helper(Ran beg, Ran end, std::random_access_iterator_tag) {

        std::sort(beg, end, std::less<decltype(*beg)>())

    }

    template <typename For>

    void sort_helper(For beg, For end, std::forward_iterator_tag) {

        typedef decltype(*beg) value_type

        std::vector<typename For::value_type> v{beg, end}            

        std::sort(v.begin(), v.end())

        std::copy(v.begin(), v.end(), beg)

    }

    

    template <typename Itr>

    void sort(Itr beg, Itr end) {

        sort_helper(beg, end, 

            typename std::iterator_traits<Itr>::iterator_category())

    }

}

int main(int argc, char const *argv[])

{

    std::forward_list<int> fl

    std::default_random_engine e

    std::uniform_int_distribution<> d(0, 100)

    for(int i = 0 i < 10 ++i){

        fl.push_front(d(e))

    }

    my::sort(fl.begin(), fl.end())

    for (auto item: fl) {

        std::cout << item << " "

    }

    std::cout << std::endl

    return 0

}

运行：

0 4 13 22 46 53 68 68 76 94

---