C++的标准模板库STL中实现的数据结构之链表std::list的分析与使用

时间:2021-07-29 13:52:43

摘要

本文主要借助对C++的标准模板库STL中实现的数据结构的学习和使用来加深对数据结构的理解,即联系数据结构的理论分析和详细的应用实现(STL),本文是系列总结的第二篇。主要针对线性表中的链表
STL std::list进行分析和总结。

引言

因为前段时间对台大的机器学习基石和技法课程进行了学习,发如今详细的实现中经常涉及到各种类型的数据结构,比方线性表、二叉树、图等。在使用这些数据结构时感到有些吃力,主要是对一些主要的数据结构理解的不够,所以趁着暑假假期,近期一段时间总会抽出时间复习一下数据结构,參考的教材是王立柱编著的《C/C++与数据结构》,在详细的应用中採用的是C++标准模板库STL中相应实现的数据结构,主要參考的是MSDN文档。

跟着教材的一步一步推进。如今已经复习完了链表一章节。详细的理论能够參看我的博文:http://blog.csdn.net/lg1259156776/article/details/47018813

本次关注点在list模板类的使用。

正文

回想动态数组类

上一篇总结STL vector动态数组类的时候忘记了对还有一种跟vector很类似的动态数组类deque进行说明。

以下对此进行一下补充。

STL deque类须要包括<deque>和使用std。支持在数组的开头和末尾插入或删除元素,而vector仅仅能在末尾插入或删除,即仅仅有push_back和pop_back。deque同意使用push_front和pop_front在开头插入和删除元素。其余的操作大致类似,不再赘述!

template <
class Type,
class Allocator=allocator<Type>
>
class deque
<span style="font-size:18px;">// deque_push_front.cpp
// compile with: /EHsc
#include <deque>
#include <iostream>
#include <string> int main( )
{
using namespace std;
deque <int> c1; c1.push_front( 1 );
if ( c1.size( ) != 0 )
cout << "First element: " << c1.front( ) << endl; c1.push_front( 2 );
if ( c1.size( ) != 0 )
cout << "New first element: " << c1.front( ) << endl; // move initialize a deque of strings
deque <string> c2;
string str("a"); c2.push_front( move( str ) );
cout << "Moved first element: " << c2.front( ) << endl;
}</span>

总结:在不知道须要存储多少个元素时,务必使用动态数组vector或deque。并牢记vector仅仅能使用push_back在一端扩容,而deque能够使用push_back和push_front在两端扩容。另外。訪问动态数组时,不要跨越其边界。

list 模板类

标准模板库以模板类std::list的方式向程序猿提供了一个双向链表。

双向链表的主要长处是插入和删除元素的速度快,且时间固定,不像顺序表那样须要移动元素。从C++ 11起,还能够使用单向链表std::forward_list,仅仅沿着一个方向遍历。

template <
class Type,
class Allocator=allocator<Type>
>
class list

list的特点

链表是一系列节点,每一个节点除了包括对象或data之外,还包括指向下一个或者上一个节点的指针。list类的STL实现同意在开头、末尾和中间插入元素,且所需的时间固定。

使用时包括<list>和std。

list的基本操作

实例化

list<int> listIntegers; list<float> listFloats;等等。要声明一个指向list中元素的迭代器,能够进行例如以下操作:

list<int> :: const_iterator iElementInSet; 还记得const_iterator吧,在上一篇vector的分析中讲到过。指向一个仅仅读的元素,假设要对容器中的内容进行改动,能够使用iterator来进行。另一些与vector一样的初始化操作,能够參考上一篇博文,兴许关于STL容器进行编程或者解说时。实例化的方式大致一样。这样的模式也将长期出现,兴许博文便不再多提。

在list开头或末尾插入或删除元素

跟deque类相似。採用push_front/pop_front和push_back/pop_back的方法。

在list中间插入或删除元素

list的特点之中的一个。上面讲过。在中间插入或删除元素所需的时间是固定的,使用函数insert()和erase()。

从上面的分析看,基本上全部的容器类(vector。list,deque...)所使用的方法模式都类似,这对于触类旁通的学习非常有帮助。

list元素的反转和排序

list的一个独到之处就是指向元素的迭代器在list的元素又一次排列或插入元素后仍然有效,为实现这样的特点,list提供了成员方法sort和reverse。尽管STL也提供了这两种算法(在算法类中<algorithm>)。且这些算法相同能够使用在list类上。

使用reverse()反转元素的顺序排列

list提供了成员函数reverse,没有參数,功能是反转list中元素的排列顺序:

<span style="font-size:18px;">// list_reverse.cpp
// compile with: /EHsc
#include <list>
#include <iostream> int main( )
{
using namespace std;
list <int> c1;
list <int>::iterator c1_Iter; c1.push_back( 10 );
c1.push_back( 20 );
c1.push_back( 30 ); cout << "c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout << " " << *c1_Iter;
cout << endl; c1.reverse( );
cout << "Reversed c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout << " " << *c1_Iter;
cout << endl;
}</span>

输出结果:

c1 = 10 20 30
Reversed c1 = 30 20 10

使用sort()对元素进行排序

list成员函数sort有两个版本号。一是没有參数,默认是升序排列。假设想降序排列,能够升序后採用reverse。还有一个版本号是接受一个二元谓词函数作为參数。制定排序的标准。比方以下一个二元谓词函数GeaterThan,指定的排序标准是降序排列

bool GeaterThan(const int& lsh, const int& rsh)

{

return(lsh > rsh);

}

<span style="font-size:18px;">// list_sort.cpp
// compile with: /EHsc
#include <list>
#include <iostream> int main( )
{
using namespace std;
list <int> c1;
list <int>::iterator c1_Iter; c1.push_back( 20 );
c1.push_back( 10 );
c1.push_back( 30 ); cout << "Before sorting: c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout << " " << *c1_Iter;
cout << endl; c1.sort( );
cout << "After sorting c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout << " " << *c1_Iter;
cout << endl; c1.sort( greater<int>( ) );
cout << "After sorting with 'greater than' operation, c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout << " " << *c1_Iter;
cout << endl;
}</span>

输出为:

Before sorting: c1 = 20 10 30
After sorting c1 = 10 20 30
After sorting with 'greater than' operation, c1 = 30 20 10

对包括对象的list进行排序及删除当中的元素

在实际应用非常少使用STL容器来存储整数,而是存储用户自定义的类型,比方类或结构等。那么这样的排序怎样做呢?

比方list中存储的是电话簿,当中每一个元素都是一个对象,包括名称、地址等内容,怎样确保能依照名称对其进行排序呢?

答案是採取下面两种方式之中的一个:

<1> 在list包括相应所属的类中,实现运算符<

<2> 提供一个排序二元谓词(一个函数。接受两个输入值,并返回一个bool值。指出第一个值是否比第二个值小)

在实际的sort调用中。首先推断有没有输入二元谓词,假设没有sort函数检查相应的list的对象元素中是否实现了运算符<。假设实现了则依照该运算符指定的排序标准进行排序。假设输入了二元谓词函数。则依照其标准进行排序。

在用remove进行删除的时候也是一样,仅仅须要提供给元素对象中的某一个变量。就能够直接删除全部的对象中该变量值相等的元素。

即remove函数须要提供一个匹配标准才行,在对象类中实现==运算符。就是为remove时提供的删除标准。比方电话簿中的名字,在类中实现一个例如以下所看到的的重载运算符==

bool operator == (const ContactItem& itemToCompare) const

{

return(itemToCompare.strContactsName == this->strContactsName);

}

forward_list模板类

从c++ 11之后,提供了forward_list来支持单向链表,包括头文件<forward_lsit>。用法与list非常类似,就好像vector与deque的关系。forward_list仅仅能沿着一个方向移动迭代器,且插入元素的时候仅仅能使用函数push_front(),而不能使用push_back。当然是用insert是能够在指定位置插入元素的。

总结

假设须要频繁的插入和删除元素,尤其是在中间插入或删除,应当使用std::list,而不是使用std::vector。由于在这样的情况下vector须要调整内部缓冲区大小。以支持数组语法。还需运行开销高昂的复制操作。而list仅仅需建立或断开链接。

对于使用list等STL容器存储其对象的类,别忘了在当中实现运算符<和==,以提供默认排序的标准和删除谓词。

当无需频繁插入和删除元素时。请不要使用list。使用vector和deque的速度要更快。假设不想依据默认标准进行删除或排序,别忘了给sort和remove提供一个谓词函数。

*************************************************************************************************************************************

2015-7-23