[STL] list merge 函数
Copy From: http://blog.csdn.net/ysuliu/article/details/3497862STL list容器由于采用了双向迭代器，不支持随机访问，所以标准库的merge(), sort()等功能函数都不适用，list单独实现了merge()，sort()等函数。首先说一下merge() （以void merge(list& __x); 为例）按照
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, 故做此验证：
- #include <iostream>
- #include <list>
- #include <iomanip>
- using namespace std;
- int main()
- {
- // 有序数据
- int A1[]={1,2,3,4,5,6};
- int A2[]={2,4,6,8,9,10};
- // 无序数据
- int A3[]={1,2,3,4,6,9};
- int A4[]={5,6,7,8,9,2};
- //有序链表
- list<int> iL1(A1, A1+6);
- list<int> iL2(A2, A2+6);
- //无序链表
- list<int> iL3(A3, A3+6);
- list<int> iL4(A4, A4+6);
- iL1.merge(iL2);
- iL3.merge(iL4);
- list<int>::iterator it = iL1.begin();
- while(it!=iL1.end())
- {
- cout<<setw(3)<<*it++;
- }
- cout<<endl;
- it=iL3.begin();
- while(it!=iL3.end())
- {
- cout<<setw(3)<<*it++;
- }
- cout<<endl;
- system("pause");
- return 0;
- }
输出为：
- 1 2 2 3 4 4 5 6 6 8 9 10
- 1 2 3 4 5 6 6 7 8 9 9 2
可以看到合并的第一个list仍是有序的，第二个最后一个元素是2，无序。
得到结论：
当源list均有序时，得到的list仍是有序的
当源list无序时，得到的list不能保证有序，之所以这样说是因为，当list1的前两个元素即表现出无序时，合并后的结果将是直接把list2接到list1的后面。。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)