list网上实例

list的函数共有五大类：定义及初始化，增加删除元素，访问元素，返回迭代器，其他

#include <string>
#include <vector> 
#include <list>
#include <conio.h>
#include<iostream>
using namespace std;  
void PrintListInt(list<int>& param)
{
    for (list<int>::iterator iter=param.begin();iter!=param.end();iter++)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;    
}
void PrintListString(list<string>& param)
{
    for (list<string>::iterator iter=param.begin();iter!=param.end();iter++)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;    
}
//定义及初始化；没有返回值，或void
void test0()
{ 
    list<int> first(4);//定义并初始化4个0
    PrintListInt(first);//0 0 0 0
    list<int> second(3,88);//定义并初始化3个88
    PrintListInt(second);//88 88 88 
    first.assign(4,90);//assign赋值  //4个90
    second.assign(first.begin(),first.end());//second拷贝first
    int arr[]={23,45,56};
    second.assign(arr,arr+2);
    PrintListInt(second);//23 45 (没有56，者说明assign赋值是[begin,end),而不是[begin,end])
    second.assign(0,0);//清空second
    PrintListInt(second);//为空  
}
//增加删除元素；返回值是void,除erase()的返回值是iterator外
void test1()
{ 
    list<int> first(3,8);
    first.push_back(6);//增加一个元素在list末端
    first.push_front(2);//增加一个元素在list前端
    PrintListInt(first);//2 8 8 8 6
    first.pop_back();//删除list末端元素
    first.pop_front();//删除list前端元素
    PrintListInt(first);//8 8 8 
    first.insert(first.begin(),5);//在前端添加一个元素,不可以first.begin()+1;但vector<int>ve(4);ve.insert(ve.begin()+1,4);却可以
    first.insert(first.end(),2,9);//在末端添加两个元素，同上，end()-2不可以，但vector的end()-2可以
    PrintListInt(first);//5 8 8 8 9 9
    list<int>second;
    second.insert(second.end(),first.begin(),first.end());//second赋值first
    PrintListInt(second);//5 8 8 8 9 9

    second.erase(second.begin());//删除前端元素，参数不能为second.begin()+1,当然也不能为second.end();若要删除第二个元素，则可通过++second.begin(),或iterator，然后iterator++
    PrintListInt(second);//8 8 8 9 9 
    second.erase(second.begin(),second.end());//全部删除
    PrintListInt(second);//为空

    first.remove(77);//删除77这个不存在的元素 
    PrintListInt(first);//5 8 8 8 9 9
    first.remove(8);//删除所有的8这个元素
    PrintListInt(first);//5 9 9
    if (!first.empty()) 
        first.clear();//全部清除
    PrintListInt(first);//为空 
    //在list的函数insert(),erase()的函数参数时（iterator+2）是不可以的，只可以通过不停地iterator++；这一点与vector的insert(),erase()不同，可以通过iterator+2来很方便的删除任意位置的元素。因为它们存储的内存地址不一定连续的，所以不能通过iterator+、-N来访问第N个元素，只能通过iterator++来逐一访问,甚至量iterator=iterator+1都不行
    //由于list是双向链表，所以比线性表vector多提供了增加删除元素的函数，push_front(),pop_front(),remove(),remove_if()
}
//访问获取元素；返回值是Type T
void test2()
{ 
    list<int> first;
    for(int i=0;i<5;i++)
        first.push_back(i);
     cout<<first.front()<<endl;//0 返回前端元素的引用
     cout<<first.back()<<endl;//4 返回末端元素的引用
    //由于list是双向链表，所有没有像线性表vector那样提供下标索引，at()来提供方便的数据访问函数
}
//返回迭代器；返回值是iterator，或reverse_iterator
void test3()
{ 
    list<int> first;
    for(int i=0;i<5;i++)
        first.push_back(i); 
     cout<<*first.begin()<<endl;//0 不可以 cout<<*first.end()<<endl;不然会崩溃
     cout<<*first.rbegin()<<endl;//4 不可以cout<<*first.rend()<<endl;不然会崩溃
     for(list<int>::iterator it=first.begin();it!=first.end();it++)
         cout<<*it<<" ";//0 1 2 3 4
     cout<<endl;
     list<int>::reverse_iterator reIt=first.rbegin();
     while(reIt!=first.rend())
     {
         cout<<*reIt<<" ";//4 3 2 1 0
         reIt++;//记住是++，因为他是rbegin中的begin
     }
     cout<<endl;
     //与vector提供的函数相同begin(),end(),rbegin(),rend();不同的iterator不可以+N
} 
//其他
void test4()
{ 
    list<string> ve(2);
    cout<<ve.size()<<endl;//2 
    cout<<ve.max_size()<<endl;//134217727(string),10737441823(int)
    ve.resize(7);
    cout<<ve.size()<<endl;//7 
    //与vector不同的是少了capacity(),reserve()获取容量，设置容量

    list<int> first;
    for(int i=0;i<5;i++)
        first.push_back(i); 
    first.reverse();//逆序
    PrintListInt(first);//4 3 2 1 0
    list<int>second(2,9);
    second.swap(first);//两个list之间交互数据
    PrintListInt(first);//9 9
    PrintListInt(second);// 4 3 2 1 0
    first.sort();
    second.sort();//排序(从小到大)
    PrintListInt(second);//0 1 2 3 4
    first.merge(second);//second合并到first中，之后second为空。这里需要注意的是：在调用合并函数merge()之前，first和second都必须是从小到大的排序的
    PrintListInt(first);//0 1 2 3 4 9 9
    PrintListInt(second);//为空
    first.unique();//使唯一，删除相同的数据
    PrintListInt(first);//0 1 2 3 4 9
    //比vector多提供了逆序reverse(),排序sort(),和并merge()，使唯一unique()等数据处理的函数
} 
//遍历list
void test5()
{ 
    list<int> vec;
    for (int i=0;i<10;i++)
    {
        vec.push_back(i);
    } 

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

    list<int>::reverse_iterator reIter;
    for (reIter=vec.rbegin();reIter!=vec.rend();reIter++) 
        cout<<*reIter<<" ";//9 8 7 6 5 4 3 2 1 0
    cout<<endl;

    vec.reverse();
    list<int>::reverse_iterator reveIter=vec.rbegin();
    while(reveIter!=vec.rend())
    {
        cout<<*reveIter<<" ";//0 1 2 3 4 5 6 7 8 9
        reveIter++;
    }
    cout<<endl;    
} 
void Test(char h)
{
    cout<<"press key===="<<h<<endl;
    switch(h)
    { 
    case '0':  test0();break;
    case '1':  test1();break;
    case '2':  test2();break;
    case '3':  test3();break;
    case '4':  test4();break;
    case '5':  test5();break; 
    case 27:
    case 'q':exit(0);break; 
    default:cout<<"default "<<h<<endl;break;
    }
}
void main()
{
    while(1)
    {
        Test(getch());
    } 
}

基数排序(radix sort）是属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O ( d(n+radix ) )，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法（比较性排序法的时间复杂度下限是O（n log n））。

基本思路（载自百科）：

解法 
　　基数排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。 
　　以LSD为例，假设原来有一串数值如下所示： 
　　73, 22, 93, 43, 55, 14, 28, 65, 39, 81 
　　首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 
　　0 
　　1 81 
　　2 22 
　　3 73 93 43 
　　4 14 
　　5 55 65 
　　6 
　　7 
　　8 28 
　　9 39 
　　接下来将这些桶子中的数值重新串接起来，成为以下的数列： 
　　81, 22, 73, 93, 43, 14, 55, 65, 28, 39 
　　接着再进行一次分配，这次是根据十位数来分配： 
　　0 
　　1 14 
　　2 22 28 
　　3 39 
　　4 43 
　　5 55 
　　6 65 
　　7 73 
　　8 81 
　　9 93 
　　接下来将这些桶子中的数值重新串接起来，成为以下的数列： 
　　14, 22, 28, 39, 43, 55, 65, 73, 81, 93 
　　这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。 
　　LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。 

代码示例：

#include<iostream>

using namespace std;

const int MAXSIZE=10;

int main(){
	int data[MAXSIZE]={43,12,54,23,14,65,21,90,33,86};//先初始化数组
	int tmp_queue[MAXSIZE][MAXSIZE]={0};
	int order[MAXSIZE]={0};

	int i;

	cout<<"排序前数组顺序为："<<endl;
	
	for(i=0;i<MAXSIZE-1;i++)//输出原始的数组
		cout<<data[i]<<" ";
	cout<<data[i]<<endl;

	int n=1,k;
	int lsd,flag=1;

	while( n <= MAXSIZE){
		for(i=0 ;i<MAXSIZE;i++){//按照排序码的大小，将数据分配到不同的队列中
			lsd=((data[i]/n)%10);
			tmp_queue[lsd][order[lsd]++]=data[i];
		}

		n*=10;//选择的排序码向高位移动一位
		k=0;
		int j;

		cout<<"\n第"<<flag++<<"趟分配和收集后的数据顺序为:"<<endl;
		for( i=0;i<MAXSIZE;i++){
				if( order[i] != 0){
					for( j=0;j<order[i];j++){
						data[k]=tmp_queue[i][j];
						cout<<data[k++]<<" ";
					}
				}
				order[i]=0;//重新将数组长度标记为0 以便下一次循环时候使用
		}
	}

	cout<<"\n\nLSD基数排序法结束后的数据顺序为:"<<endl;
	for(i=0;i<MAXSIZE-1;i++)
		cout<<data[i]<<" ";
	cout<<data[i]<<endl;//输出最后一个数据
	return 0;
}

运行结果：

基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
　　基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。

欢迎转载，但请留下足迹！

前段时间，在插上带 tf 卡的读卡器的情况下打开了我的 mac 主机，之后我便陷入了一连串的麻烦之中~

平时开机都是很正常的，这次却意外的在屏幕上显示出了黑底白字的一串英文：

reboot and select proper boot device.

大意也就是叫我选择一个可以被启动的设备来重启。

我也按照文字提示做了，我拔掉了插入 tf 卡的读卡器，然后就重启了。

可即便如此，重启了以后还是之前的老样子，依然给我打印出那段文字。

就这么的搞了几次，弄得我有些心烦了，于是便拆开主机箱果断地给主板放放电，让它领教一下我的厉害。。

可我就是没想到因为这么草率的一个举动，就让我白白忙活了好几天，直到今天下午才把系统给修复回来。

说说当时的情况吧，放电了以后我匆匆忙忙地就盖好了机箱盖儿重启了，

可我等来的不是用户登陆界面，而是无止尽的白色背景缺苹果。。

后来我终于还是妥协了，我不再进主分区的系统了，我试着看能不能进入恢复分区的系统

（这个分区里面也有一个 mac 系统，用来做主分区 mac 系统的修复用~）

可是在我试了几次过后，还是失望了，主分区和恢复分区里面的两个 mac 系统竟然都进不去了~

分析一番后我怀疑是放电过后 bios 设置被还原回初始状态了，否则再怎么出问题，恢复分区里的 mac 也没理由进不去的。

同事们也给我支招，说要把 bios 里面的 ahci 选项给开启，于是我便跑到 bios 设置里面找啊找，

找了很久几乎都把 ami 的 bios 设置翻了个遍，还是没能找到带 ahci 字样的相关选项。

这之后我便进入了很长一段时间的摸索阶段，偶然在网上看到有人说有些主板默认就是开启了 ahci 选项的，即便找不到它。。。。

查阅资料了好一段时光我才获悉这完全就是误导！！！

首先我查的是 ami 的 bios 怎么开启 ahci ，找到了有用的资料，然后我知道是在南桥芯片的设置里面的。

因为我在 bios 里面鼓捣了很久，印象中南桥芯片的设置里面压根就没看到有设置 ahci 的那个选项。。

经过刻苦的搜索，我又获得了一些有用的讯息：

1。与 ahci 设置相关的封装在南桥芯片里面的硬件名叫 ich7 什么的

（有 ich5，ich6，ich7，ich7r，ich8，等等）

2。并不是所有的 ich 都支持 ahci，包括 ich5，ich6，ich7 就不支持 ahci

3。我查阅了我所使用硬盘的参数，发现我的南桥里面正是使用的 ich7

综上所述，我的南桥芯片设置里面找不到 ahci 相关的设置就不奇怪了，因为在里面的 ich7 压根儿就不支持 ahci 的功能啊~

好吧，既然不支持，那怎么才能让他支持起  ahci 模式来呢？

mac os x lion 跑起来必须要  ahci 的支持，而我的机器在正常运作的时候确实是能够运行 lion 系统的，

那么我就推断出一定是有方法能够让主板提供对 ahci 的支持的。。。

然后又是漫长的搜索了，功夫不负有心人，我找到了一个叫天缘的博客，

里面介绍了一种安装 ahci 驱动的法子，当时很开心满以为找到解决方法了，

可后来操作实施的时候却碰到了问题， 那个 ahci 驱动根本就不能装到 ich 7 里面，

原因是这样的，天缘介绍的方法有一个替换文本的操作，替换的文本就是  ich 的设备编号，可是我找不到 ich7 的编号。。

之后我又仔仔细细地看了一遍天缘写的那篇文章，它里面确实提到那种安装 ahci 驱动的方法是不能应用与 ich 7 的。

就这样我又空欢喜了一场，再次回到不知所措的状态。。。

转机是这么来的，之前和卖给我 mac 机器的技术支持人员交流了一下，

当时并没有将这个问题给解决下来，他的建议是叫我交 150 块钱重装系统

我挺犹豫的，有如下几个原因：

1。路途遥远，机器运来运去的，麻烦不说，还容易损坏，而且我也没有邮寄主机箱的经历。

2。150块钱安装费也不是一个小数字，还是有些不舍，话说我自己如果能解决这个问题的话，不仅能省钱还能学到东西。

3。盘里面的数据安全问题，我并不希望数据毁掉或者泄露掉~

正是由于上述的几个原因，我并没有按照客服技术人员说的去做~

但是后来我折腾了两日实在没耐性弄下去了，于是我想到客服的员工不仅仅只有那一位，

还有一个最大的老板在里面，而且他的旺旺一般都是在线的，何不去试试手气呢？

老板就是老板，霸气，没有客服打杂工的那种市侩，而且我自己也摸索了很长一段时间，

一针见血的就提出了自己的推测 —— 断电后 bios 里面的某个设置被弄错了，导致无法正常进入主分区和恢复分区的 mac 系统~

老板的实力刚刚的，第二句话就给出了我解决方案 —— 在 bios 设置里面将 USB 设置的 high-speed 改为 full-speed，

当时还觉得挺奇怪的，mac 不能正常启动和 usb 设置有半毛钱的关系么？

不过虽然觉得奇怪，我还是照老板说的做了，三下五除二连接好我的 mac 机器，进入 bios 设置将 USB 选项更改了一下，

完了以后重启电脑，口中不断地默念“God bless me!”，神奇的一幕出现了，我心爱的 mac 终于回复了正常。。

那一刻我简直是激动地热泪盈眶，终于弄好了，终于可以干事了，简直是太好了~

虽然系统正常的恢复了过来，但是作为一次惨痛的经历，这无时无刻不提醒着我，

一定要知之为知之，方能在以后再次碰到此类问题的时候不手忙脚乱~

第一个疑问便是—— 难道不启动主板的 ahci 选项也能正常跑起  mac lion 来？

结合我之前修复系统的过程中所查阅的一些资料来思考一番，我觉得可能存在如下的一中可能：

即便主板上没有设置 ahci 的选项，即便在没有 ahci 选项的情况下默认不是 ahci 模式，

也可以通过高层操作系统中的驱动支持来弥补这块空缺！

我是有依据的，因为之前我在 csdn 的下载频道里面看到过类似，“黑苹果 + 免 ahci 驱动” 的资源~

我还下载了一个看了一看，其实就是一个 kext 结尾的 mac os 驱动文件，名为 AppleIntelIPIIXATA.kext、ATAPortInjector.kext

然后我猜想我的黑苹果扩展驱动目录中也应该存在这些驱动文件。

奇怪的是我没有找到这些驱动文件，但是通过我所查找到的资料，也有提到还存在其他的驱动文件是提供 ahci 弥补功能的，

诸如

  PC 上安装Mac OS X(四)——安装雪豹

 这篇资料中所提到的：IOAHCIBlockStorageinjector.kext 和 AppleAHCIPort.kext 

这两个文件也是起到弥补 ahci 设置缺失的功能的

看到这里时我又跑到 mac 系统的扩展驱动目录（SLE——/System/Library/Extensions、EE——/Extras/Extensions）

里面找了一下，这次总算是有所斩获了 —— 

在 SLE 目录下我找到了 AppleAHCIPort.kext 文件，

在 EE 目录下我找到了 IOAHCIBlockStorageinjector.kext 文件， 

很吻合上面那篇资料里面所说到的情形，作者果然还是所言非虚啊~

下面手打 360doc 里面自己觉得有价值的一段文字：

导致五国的原因有很多很多，比如“你的 cpu 不支持64位和 sss3 指令集” 或者某个 kext 冲突之类的。

如果是前者，问题还算好解决。只要在 bootThink 图形界面中按 f8，输入 -x32 启动即可；

另外，对于某些只支持32位的 kext 也要使用这种方式来启动；

还有，也可以键入 cpus = 1（强制多核 cpu 使用单核）试试可不可以启动。

如果是后者，我们就要输入 -v 启动啰唆模式（Verbose）来看看问题出在哪里了。

举个粒子，输入 -v 启动之后会出现一大堆的 代码，暂时不去管他，最后他会停止在某处。

找到  panic 这个词，我们可以在这下面看到问题所在 。panic 原本是 恐慌的意思，

在这里表示系统遇到致命错误。假设错误代码如下面所示，我们就知道问题处在 AppleIntelCPUPowerManagement，

查询一些资料就知道只要安装 NullCPUPowerManagement.kext 即可解决问题。

依次类推，其他问题也可以按照这个思路下去。