顺序容器 -forward list单链表

forward list单链表是C++11加入到STL的。

使用forward list，必须包含头文件<forward_list>

#include <forward_list>

这个头文件被定义在命名空间std内。

namespace std {
    template <typename T,typename Allocator = allocator<T> >
    class forward_list;
}

它的第一个参数T是任意类型,第二个参数默认不写。

forward list和数据结构中的单链表类似是一个行为受限的list(双向链表),只能"往前走不能回头",凡是list不提供的功能它都不提供。它的优点是内存用量较少(不需要保存回头的指针),行动也略快。

相比较list,forward list有以下约束:

• forward list只提供向前迭代器,而不是双向迭代器,因此它不支持反向迭代器。
• forward list没有指向尾元素的指针,所以forward list不提供处理"尾元素"的函数,如back,push_back和pop_back(太慢了)。
• forward list不提供size函数。可以自己实现。
• forward list是单链表,而插入和删除操作都需要依赖前一个节点。所以它的插入和删除类的函数都带一个后缀_after。例如insert_after替代insert。
• forward list插入和删除操作需要依赖前一个节点,所以它提供before_begin函数,返回第一个元素前面的位置。

除了上面这些差异,forward list的行为就像list。

• forward list不提供随机访问。若要访问第5个元素,必须从头到尾依次遍历过去。
• 插入和删除元素,速度都很快(前提是你已经指定了位置)。
• 插入和删除元素,不会造成"指向其它元素"的指针,引用和迭代器失效。

定义及初始化

下表列出定义forward list对象的常用初始化方法.

#include <iostream>
#include <forward_list>
using namespace std;

//输出l1的所有数据
void Show(const forward_list<int>& l1)
{
    for (auto& x : l1)
        cout << x << " ";
    cout << endl;
}

int main()
{
    forward_list<int> l1; //创建一个空的单链表
    forward_list<int> l2(2);//创建一个包含2个默认值的单链表
    forward_list<int> l3(3, 5);//创建一个包含3个5的单链表
    forward_list<int> l4{ 1,2,3,4 };//创建一个包含1,2,3,4的单链表
    forward_list<int> l5(l4);//创建一个和l4元素相同的单链表
    forward_list<int> l6 = l4;//同l5,创建一个和l4元素相同的单链表
    forward_list<int> l7(++l4.begin(), l4.end());//创建一个不包含l4第一个元素的单链表

    cout << "l1:"; Show(l1);
    cout << "l2:"; Show(l2);
    cout << "l3:"; Show(l3);
    cout << "l4:"; Show(l4);
    cout << "l5:"; Show(l5);
    cout << "l6:"; Show(l6);
    cout << "l7:"; Show(l7);

    return 0;
}

forward list常用迭代器

forward list只支持向前迭代器(forward iterator),不支持逆序迭代器和随机迭代器。所以STL中需要随机迭代器的算法不能用于forward list,例如sort。不过forward list自带sort算法。

forward list常用的迭代器如下:

注意before_begin()和cbefore_begin()并不代表forward list的一个合法位置,解引用这些位置会导致未定义的行为。也就是说,before_begin()不能用于STL的任何算法。

例如,利用迭代器访问forward list对象。

#include <iostream>
#include <forward_list>
#include <iterator>
using namespace std;

//利用distance函数求出单链表的长度size
template<typename T>
int forward_list_size(const forward_list<T>& l)
{
	return distance(l.begin(), l.end());//注意distance的时间复杂度为O(n)
	//distance 需要引入 <iterator> 文件
}

int main()
{
	forward_list<int> l1{ 1,2,3,4,5 };

	//利用迭代器输出l1的所有数据
	cout << "l1:";
	for (forward_list<int>::const_iterator it = l1.cbegin(); it != l1.cend(); ++it)
		cout << *it << " ";
	cout << endl;

	cout << "l1的长度:" << forward_list_size(l1) << endl;

	l1.insert_after(l1.before_begin(), 100);//在l1的最前面插入100
	//l1.push_front(100);//等同上面

	//利用迭代器修改链表的值
	for (auto it = l1.begin(); it != l1.end(); ++it) //把每个元素的值*2
		*it *= 2;

	//利用迭代器输出l1的所有数据
	cout << "l1:";
	for (auto it = l1.cbegin(); it != l1.cend(); ++it)
		cout << *it << " ";
	cout << endl;

	cout << "l1的长度:" << forward_list_size(l1);

	return 0;
}

说明: distance返回两个迭代器直接的距离。

difference_type distance(InputIterator _First, InputIterator _Last);
//返回第一个迭代器到第二个迭代器的距离,如果是随机迭代器时间为常数O(1),否则时间为线性O(n)。

forward list常用运算符

forward list类既支持常用的=,==,!=,< , >等运算符,也可以通过调用其成员函数来执行相应的操作。下面列举了其常用的操作。

#include <iostream>
#include <forward_list>
#include <iterator>
using namespace std;

//输出l1的所有数据
void Show(const forward_list<int>& l1)
{
    for (auto& x : l1)
        cout << x << " ";
    cout << endl;
}

int main()
{
    forward_list<int> l1{ 1, 2, 3, 4, 5 };//创建包含1,2,3,4,5的单链表
    forward_list<int>l2;//创建空单链表

    l2 = l1;//把l1的所有元素赋值给l2
    cout << "l1:"; Show(l1);//输出l1所有元素值
    cout << "l2:"; Show(l2);//输出l2所有元素值

    if (l1 == l2)
        cout << "l1 == l2" << endl;

    l1.front() = 100;//把l1的第一元素改为100,等同下一行的代码
    //int& x = l1.front(); x = 100;//把l1的第一元素改为100
    cout << "l1:"; Show(l1);//输出l1所有元素值
    cout << "l2:"; Show(l2);//输出l1所有元素值

    if (l1 != l2)
        cout << "l1 != l2" << endl;

    if (l1 > l2)
        cout << "l1 > l2" << endl;
    else
        cout << "l1 <= l2" << endl;

    return 0;
}

forward list常用成员函数

下面列举forward list对象常用的成员函数。

注意:forward list不提供size函数,不提供尾部操作函数。

forward list特有成员函数

下面列举forward list特有的函数(相比vector)

merge特有成员函数

把两个单链表的元素进行合并。注意合并的前提是原来两个链表必须按照合并的方法有序。默认升序合并。

#include <iostream>
#include <forward_list>
#include <iterator>
using namespace std;

//输出l1的所有数据
void Show(const forward_list<int>& l1)
{
	for (auto& x : l1)
		cout << x << " ";
	cout << endl;
}

int main()
{
	forward_list<int>l1{ 2,4,6,8 }; //创建l1
	forward_list<int>l2{ 1,2,3,5,7,9 };//创建l2
	cout << "l1:"; Show(l1);//输出l1
	cout << "l2:"; Show(l2);//输出l2

	l1.merge(l2);//把l2合并到l1中
	cout << "把l2合并到l1中后" << endl;
	cout << "l1:"; Show(l1);//输出l1
	cout << "l2:"; Show(l2);//输出l2

	return 0;
}

合并的前提是原有的两个链表是"有序的"(按照排序的规则),如果不符合前提条件结果是未定义的。

emove特有成员函数 

void remove( const Type& _Val);//_Val需要删除的值

删除所有和_Val相同的值。

#include <iostream>
#include <forward_list>
#include <iterator>
using namespace std;

//输出l1的所有数据
void Show(const forward_list<char>& l1)
{
	for (auto& x : l1)
		cout << x << " ";
	cout << endl;
}

int main()
{
	//创建包含字符的单链表
	forward_list<char> l1{ 'a','b','c','a','b','c','d','a','b','c','d','e' };
	cout << "l1:"; Show(l1);

	l1.remove('a');//删除'a'
	cout << "l1删除a后" << endl;
	cout << "l1:"; Show(l1);

	return 0;
}

splice_after特有成员函数

链表连结,把一个链表的元素连结到另一个链表中。 请注意,1.插入点在第一个参数(迭代器)的后面;2.被插入的数据如果是迭代器也是从它后面的一个数据开始。

#include <iostream>
#include <forward_list>
#include <iterator>
using namespace std;

//输出l1的所有数据
void Show(const forward_list<int>& l1)
{
    for (auto& x : l1)
        cout << x << " ";
    cout << endl;
}

int main()
{
    forward_list<int> l1{ 10, 11 };
    forward_list<int> l2{ 20, 21, 22 };
    forward_list<int> l3{ 30, 31 };
    forward_list<int> l4{ 40, 41, 42, 43 };

    forward_list<int>::iterator first_iter;
    forward_list<int>::iterator last_iter;

    cout << "初始值:" << endl;
    cout << "l1:";    Show(l1);
    cout << "l2:";    Show(l2);
    cout << "l3:";    Show(l3);
    cout << "l4:";    Show(l4);

    //连结整个链表
    l2.splice_after(l2.before_begin(), l1);//在l2的前面连结l1
    cout << "把l1连结到l2的最前面后:" << endl;
    cout << "l1 = ";    Show(l1);
    cout << "l2 = ";    Show(l2);

    //连结一个元素
    l2.splice_after(l2.begin(), l3, l3.begin());
    cout << "把l3的第二个元素连结到l2的第一个值后:" << endl;
    cout << "l3:";    Show(l3);
    cout << "l2:";    Show(l2);

    //连结一个区间
    first_iter = l4.begin();
    last_iter = l4.end();
    ++first_iter; //第二个,从第三个开始连结过去
    l2.splice_after(l2.before_begin(), l4, first_iter, last_iter);
    cout << "把l4的区间数据连结到l2的最前面后:" << endl;
    cout << "l4 = ";    Show(l4);
    cout << "l2 = ";    Show(l2);

    return 0;
}