C++的标准模板库STL中实现的数据结构之链表std::list的分析与使用
摘要
本文主要借助对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在开头插入和删除元素。其余的操作大致类似,不再赘述!
<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,只沿着一个方向遍历。
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>输出结果:
使用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>输出为:
对包含对象的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
相关文章
- C++ 使用 TinyXml 解析 XML 文件
- C++ 递归遍历文件夹内的所有文件
- C++ is-a关系
- 关注C++细节——C++11新标准之decltype的使用注意
- 基于c++11新标准开发一个支持多线程高并发的网络库
- 【侯捷】C++STL标准库与泛型编程(第二讲)
- 【侯捷】C++STL标准库与泛型编程(第一讲)
- 05 C++ - 作用域运算符(::)
- dll文件的c++制作
- c++中enum 如何使用
- 《C++编程剖析:问题、方案和设计准则》——第一章泛型编程与C++标准库1.1:vector的使用
- 《C和C++程序员面试秘笈》——1.10 标准头文件的结构
- 《C++面向对象高效编程(第2版)》——2.10 抽象数据类型—栈的实现
- 《C++编程惯用法——高级程序员常用方法和技巧》——1.3 请考虑边界条件
- 基于C++实现的记分板调度方法仿真【100010674】
- 关于链表中环的入口结点的两种解法(C/C++)
- C/C++ 标准输入输出重定向
- ISO C++标准委员会不是一个一般意义上权力机构,基本上愿意交会费,愿意自己出时间,出酒店机票,出提案,就可以申请加入。
- 为什么一定要调用 setlocale 呢? 因为在 C/C++ 语言标准中定义了其运行时的字符集环境为 "C" ,也就是 ASCII 字符集的一个子集。使用setlocal改变整个应用程序的字符集编码方式(wcstombs使用前要设置 setlocale (LC_ALL, "chs"); )
- C/C++ 调用标准库函数实现 std::string to std::wstring 相互字符集变换(转)
- C++ | 探究函数重载的原理:函数名修饰【基于Windows + Linux双系统】
- 81、【栈与队列】leetcode ——232. 用栈实现队列(C++版本)
- 27、【链表】按递增次序输出单链表(C++版)
- 标准C++ I/O库 迭代器让数据自由流动 V8
- 编程参考 - 各种C/C++语言标准库libc
- DELPHI中千万别直接使用CreateThread ,建议使用BeginThread(在C++中无大问题,可是到了DELPHI中情况就不一样了)