Copy From: http://blog.csdn.net/ysuliu/article/details/3497862

STL list容器由于采用了双向迭代器,不支持随机访问,所以标准库的merge(), sort()等功能函数都不适用,list单独实现了merge(),sort()等函数。首先说一下merge() (以void merge(list& __x); 为例)

按照函数声明的注释:

/**
       *  @brief  Merge sorted lists.
       *  @param  x  Sorted list to merge.
       *
       *  Assumes that both @a x and this list are sorted according to
       *  operator<().  Merges elements of @a x into this list in
       *  sorted order, leaving @a x empty when complete.  Elements in
       *  this list precede elements in @a x that are equal.
       */

 

它应该合并两个有序的list, 故做此验证:

  1. #include <iostream>
  2. #include <list>
  3. #include <iomanip>
  4. using namespace std;
  5. int main()
  6. {
  7.     // 有序数据 
  8.     int A1[]={1,2,3,4,5,6};
  9.     int A2[]={2,4,6,8,9,10};
  10.     
  11.     // 无序数据
  12.     int A3[]={1,2,3,4,6,9};
  13.     int A4[]={5,6,7,8,9,2};
  14.     
  15.     //有序链表 
  16.     list<int> iL1(A1, A1+6);
  17.     list<int> iL2(A2, A2+6);
  18.     
  19.     //无序链表
  20.     list<int> iL3(A3, A3+6);
  21.     list<int> iL4(A4, A4+6);
  22.     
  23.     iL1.merge(iL2);
  24.     iL3.merge(iL4);
  25.     
  26.     list<int>::iterator it = iL1.begin();
  27.     
  28.     while(it!=iL1.end())
  29.     {
  30.         cout<<setw(3)<<*it++;
  31.     }
  32.     cout<<endl;
  33.     it=iL3.begin();
  34.     while(it!=iL3.end())
  35.     {
  36.         cout<<setw(3)<<*it++;
  37.     }    
  38.     cout<<endl;
  39.     
  40.     system("pause");
  41.     return 0;
  42. }

输出为:

  1.   1  2  2  3  4  4  5  6  6  8  9 10
  2.   1  2  3  4  5  6  6  7  8  9  9  2

可以看到合并的第一个list仍是有序的,第二个最后一个元素是2,无序。

 

得到结论:

 

当源list均有序时,得到的list仍是有序的

当源list无序时,得到的list不能保证有序,之所以这样说是因为,当list1的前两个元素即表现出无序时,合并后的结果将是直接把list2接到list1的后面。。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐