ex 13.31 为什么按字典升序添加的值使用sort也会调用swap

[hexinzhe]

我自己定义的vector,加了几个元素,结果按顺序添加的元素(如"11","22")也会调用swap输出语句
vectorv1;
v1.emplace_back("11");
v1.emplace_back("22");
sort(v1.begin(),v1.end());

并且输出后发现顺序与添加进去的顺序并没有改变.swap用在哪里了?

[hexinzhe]

另外,我问的一直是c++primer的问题,我想问一下那个labels怎么添加的?

[pezy]

swap用在哪里了?

用在向 vector 拷贝赋值时。

我想问一下那个labels怎么添加的?

[hexinzhe]

但是如果将sort注释掉的话,不会输出swap语句

[pezy]

嗯，刚才说的不对，这里都是拷贝构造，不存在赋值的问题。

问题的关键是 std::sort 采用的算法，最典型的，如快排，显然即使已经排好序，也是需要 swap 操作的。

[hexinzhe]

把输出语句加到赋值运算符里发现是调用了赋值运算符,不想纠结这个了,管他怎么实现.
但没想清为什么说快排
即使已经排好序，也是需要 swap 操作

[pezy]

你试着从算法的角度去想一想。

几乎没有一个排序算法，是上来先判断给定的数组是否有序的。std::sort 的算法很复杂，但基本上是以快排和归并排序为基础的。

如果你对这两个排序算法不了解的话，请看看维基百科：快速排序 和 归并排序

[hexinzhe]

其实sort应该并不是用的swap,而是赋值操作,赋值操作符又调用了swap.如果假定std::sort是快排的话,进行赋值的操作应该是定义枢纽的时候了.不过赋值的话确实太常见了,也不奇怪了

[loveleon]

@pezy 我的理解是，sort会调用operator<进行bool判断，如果为真，就会调用自定义的swap函数（如果定定义了HasPtr类型的<运算符），交换两个HasPtr的成员变量。这里operator=也是有调用的。所以，还是存在赋值运算符调用，应该是在sort内部。参见下代码：https://github.com/loveleon/My-Cpp-Primer/blob/master/ch13/ex13_31.cpp

[loveleon]

@hexinzhe 通过测试，sort应该是调用了swap(HasPrt &,HasPtr),至于赋值运算符什么时候调用，这个可能还是@pezy说的sort算法内部比较复杂？ 所以，这2二者的先后调用顺序，可能是先调用自定义的swap，然后是赋值。

[ender233]

还是不要去想sort内部是怎么实现的了，因为根据数据量和分布用了大量不同的排序算法。

1. 数据量少, 快排的优势体现不了, 好, 那就用插入排序
2. 数据量大的时候, 快排比较给力, 好, 用快排
3. 初始数据分布不好的话, 快排时间复杂度会恶化到O(n2), 好, 上自省排序, 分割次数达到一定值的时候, 改成堆排序.

你看看这用了多少，这还是STL, 随便拿一个非标准的STL, 那实现的更是变态(基本上根据你实际传入的类型和迭代器类型各种型別判断)，会有很多种处理分支。

所以，使用的时候也不要想那么多，接口定义传入啥，满足约束即可.

Type requirements
-RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator.
-The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.
-Compare must meet the requirements of Compare.