私房STL之list

一句话list:list是我们在数据结构中接触过的双向循环链表,应用有约瑟夫环;可见其空间非连续的,但可以动态扩充,效率很高,只是不支持随机访问,必须通过迭代器找到指定的元素。总的来说,list用起来比较顺手。

list_node

list的查找

按上述遍历元素的方法查找,复杂度为O(n)。STL算法实现了find(),可以在指定的迭代器始末寻找指定的元素。

......
list<int> il;

il.push_back(5);
il.push_back(98);
il.push_back(7);
il.push_back(20);
il.push_back(22);
il.push_back(17);

list<int>::iterator ite;
ite = find(il.begin(),il.end(),20);
cout << *ite << endl;/*20*/
......

list创建与遍历

STL中也为list实现了几个版本的构造函数:http://www.cplusplus.com/reference/stl/list/list/,有最简单缺省的版本。

list的遍历使用迭代器,如下:

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
	unsigned int i;
	list<int> il;

	il.push_back(5);
	il.push_back(98);
	il.push_back(7);
	il.push_back(20);
	il.push_back(22);
	il.push_back(17);

	list<int>::iterator ite;
	for(ite = il.begin(); ite != il.end(); ite++)
		cout << *ite << " ";
	cout << endl;

	return 0;
}

list在空间拓展的时候,没有经历vector式的空间倒腾,所以只要不earse元素,指向它ite是不会失效的。

list元素操作

list有提供pop_back,erase,clear,insert等实用的元素操作,不一一复述,给出有用的文档:http://www.cplusplus.com/reference/stl/list/

list排序

STL算法()实现的sort只适用于支持随机访问的数据,所以它不适用于list,list不支持随机访问。所以list内部实现了自己的sort,内部排序使用使用迭代版本的快排。

unsigned int i;
list<int> il;

il.push_back(5);
il.push_back(98);
il.push_back(7);
il.push_back(20);
il.push_back(22);
il.push_back(17);

list<int>::iterator ite;
for(ite = il.begin(); ite != il.end(); ite++)
	cout << *ite << " ";
cout << endl;

il.sort();

for(ite = il.begin(); ite != il.end(); ite++)
	cout << *ite << " ";
cout << endl;

return 0;

5 98 7 20 22 17
5 7 17 20 22 98
请按任意键继续. . .

建议

list使用轻松自如,硬伤是由于空间的个性(不连续),不能随机访问。

本文完 2012-10-16

捣乱小子 http://www.daoluan.net/

16 October 2012

disqus 可能被墙~