C++STL--单向链表<forward_list>

头文件

#include<forward_list>
using namespace std;

基础用法

#include <iostream>

#include <forward_list>
using namespace std;

int main()
{
    forward_list<int> l; //构造空的单向链表
    //不提供size()的成员方法，使用算法distance()获取
    cout << l.max_size() << endl; //最大的元素个数

    forward_list<int> l2(5);                         //构造5个元素的单向链表，值为类型的默认值
    cout << "第一个元素值：" << *l2.begin() << endl; //最大的元素个数

    forward_list<int> l3(5, 111);                    //构造5个元素的单向链表，每个元素值为111
    cout << "第一个元素值：" << *l3.begin() << endl; //最大的元素个数

    forward_list<int> l4(l3);                        //拷贝构造
    cout << "第一个元素值：" << *l4.begin() << endl; //最大的元素个数

    //验证forward_list的内存结构(不连续)
    for (forward_list<int>::iterator it = l3.begin(); it != l3.end(); ++it)
    {
        cout << &(*it) << "    ";
    }
    cout << endl;

    return 0;

// 576460752303423487
// 第一个元素值：0
// 第一个元素值：111
// 第一个元素值：111
// 0x55555556d368    0x55555556d388    0x55555556d3a8    0x55555556d3c8    0x55555556d3e8   
}

迭代器使用

#include <iostream>

#include <forward_list>
using namespace std;

template <class T>
void Print(T begin, T end)
{
    for (T p = begin; p != end; ++p)
    {
        cout << *p << "     ";
    }
    cout << endl;
}

int main()
{
    forward_list<int> l3(5, 111);                    //构造5个元素的单向链表，每个元素值为111
    cout << "第一个元素值：" << *l3.begin() << endl; //最大的元素个数

    //验证迭代器类别,forward  iterator 前向迭代器
    cout << typeid(forward_list<int>::iterator::iterator_category).name() << endl;

    //前向迭代器 比 双向迭代器 功能更少一些，支持++、= 、！= 、 == 、 * ，不支持 --

    // 支持++    *   =
    forward_list<int>::iterator it = l3.begin();

    *(++it) = 222;
    *(++it) = 333;
    *(++it) = 444;
    *(++it) = 555; //指向最后一个

    ++it; //指向最后一个的下一个
    cout << "是否指向最后一个的下一个: " << (it == l3.end()) << endl;

    //--it;//不可以--，因为是单向的

    // const_iterator指向的元素不可赋值
    forward_list<int>::const_iterator it2 = l3.cbegin();
    //*it2 = 1;//const_iterator指向的元素不可赋值

    //正向遍历forward_list
    for (forward_list<int>::iterator it = l3.begin(); it != l3.end(); ++it)
    {
        cout << *it << "    ";
    }
    cout << endl;

    //没有反向的迭代器，不支持，因为是单向链表
    // forward_list<int>::reverse_iterator

    //验证Print ,迭代器带来的好处，让算法无需知道容器的细节
    Print<forward_list<int>::iterator>(l3.begin(), l3.end());
    return 0;
// --- 输出 ---
// 第一个元素值：111
// St20forward_iterator_tag
// 是否指向最后一个的下一个: 1
// 111    222    333    444    555    
// 111     222     333     444     555
}

增加、删除、插入元素

#include <iostream>

#include <forward_list>
using namespace std;

int main()
{
    forward_list<int> l;

    /* 温习一下单链表的插入
    pNew->next =  pHead ->next;//新节点的下一个指向插入前的第一个节点
    pHead ->next= pNew;//将头指针指向新节点
    */
    l.push_front(111); //从头部插入元素
    l.push_front(222); //从头部插入元素
    l.push_front(333); //从头部插入元素
    /*
       为什么没有insert_before() ？
     pInsert ->next;
     你无法知道当前节点的前一个节点的地址，所以，你就无法将前一个的pLast->next=pNew

     为什么insert_after()可以？
     pNew->next= pInsert->next;
     pInsert->next = pNew;
    */
    l.insert_after(l.begin(), 444); //在某个迭代器后面插入

    for (forward_list<int>::iterator it = l.begin(); it != l.end(); it++)
    {
        cout << *it << "    ";
    }
    cout << endl;

    //访问头结点
    cout << "front():  " << l.front() << endl;

    /* 温习一下单链表的删除
    pHead ->next= pDelete->next;//将头指针指向删除节点的下一个
    delete pDelete；//删除当前节点
    */
    l.pop_front(); //删除头结点

    /*
    为什么没有erase_before(),还是因为，你无法知道pDelete的前一个，
    你就无法将前一个的pLast->next= pDelete->next;

    为什么erase_after()可以?
    pTemp= pDelete->next;
    pDelete->next= pDelete->next->next;
    delete pTemp;
    */
    l.erase_after(l.begin()); //删除迭代器节点的下一个

    l.erase_after(l.begin(), l.end()); //删除迭代器区间

    l.clear(); //删除所有元素

    for (forward_list<int>::iterator it = l.begin(); it != l.end(); it++)
    {
        cout << *it << "    ";
    }
    cout << endl;
    return 0;
}

尝试运行LeetCode206.反转链表