出于纯粹的实践目的，我开始在现代C ++中以标准库样式的方式（即在迭代器上使用模板）实现不同的排序算法。这是我的冒泡排序版本。

我确实没有想要审查代码的任何特定标准，但是感谢我可以得到的任何提示，包括性能，编码风格，表达能力等。

整个实现都位于文件bubble_sort.h中：

#pragma once

#include <utility>

template<typename Iterator, typename Comparator>
void bubble_sort(Iterator begin, Iterator end, Comparator cmp) {
    bool swapped;
    do {
        swapped = false;
        for (auto i = begin + 1; i != end; ++i) {
            auto& val0 = *i;
            auto& val1 = *(i - 1);
            if (cmp(val0, val1)) {
                std::swap(val1, val0);
                swapped = true;
            }
        }
    } while (swapped);
}

template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, [] (const typename Iterator::value_type& v0,
                const typename Iterator::value_type& v1) { return v0 < v1; });
}


作为参考，我还提供了一个包含main-方法的文件供您参考。随机std::vector的小unsigned的升序和降序：

#include <random>
#include <vector>
#include <iostream>

#include "bubble_sort.h"

int main() {
    std::vector<unsigned> vec;
    std::default_random_engine engine;
    std::uniform_int_distribution<unsigned> distribution(0, 10000);
    for (std::size_t i = 0; i < 100; ++i) {
        unsigned num = distribution(engine);
        std::cout << num  << ' ';
        vec.push_back(num);
    }
    std::cout << "\n\n";

    bubble_sort(vec.begin(), vec.end());

    for (unsigned e : vec) {
        std::cout << e << ' ';
    }
    std::cout << "\n\n";

    bubble_sort(vec.begin(), vec.end(), [] (unsigned v0, unsigned v1) {
            return v0 > v1;
        });

    for (unsigned e : vec) {
        std::cout << e << ' ';
    }
    std::cout << '\n';
}


#1 楼

我建议将函数放在命名空间中。

for (auto i = begin + 1; i != end; ++i) {

通过执行begin + 1，您需要Iterator是RandomAccessIterator，而您只需要一个ForwardIterator。改用std::next：

for (auto i = std::next(begin); i != end; ++i) {


还可以使用std::next(begin, 1)来明确表示。

类似地，当您执行*(i - 1)时，您要求Iterator一个RandomAccessIterator。用std::prev替换它仍然需要Iterator是BidirectionalIterator。除非您认为这是一个合理的要求（对于某些版本的Bubblesort，它将使它更加有效），请不要这样做。您可以跟踪这两个）：

for (auto i = begin, inext = std::next(begin); inext != end; ++i, ++inext) {
    auto& val0 = *inext;
    auto& val1 = *i;
    // ...


虽然我们在讨论迭代器类别，但是在需要的迭代器类别之后命名Iterator很有用，因此FwdIter或ForwardIterator更好的名称。



template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, [] (const typename Iterator::value_type& v0,
                const typename Iterator::value_type& v1) { return v0 < v1; });
}




而不是手动写出比较器，请使用std::less。我会使用std::less<>，但如果愿意的话，也可以使用std::less<typename std::iterator_traits<Iterator>::value_type>。

template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, std::less<>{});
}


实际上，除了这样做，您还可以将默认参数放在另一个重载上bubble_sort：

template<typename Iterator, typename Comparator = std::less<>>
void bubble_sort(Iterator begin, Iterator end, Comparator cmp = {})


通过这种方式可以想到两个优点：


更少的代码（只有一个）函数定义）
避免ADL问题



template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, std::less<>{});
}
的一个问题

bubble_sort(begin, end, ...)可以激活ADL。如果说Iterator是mylibrary::vector<int>::iterator，并且如果我在名称空间bubble_sort中写了一个mylibrary，则此bubble_sort调用可能会调用mylibrary名称空间中的一个，而不是我们想要的名称空间。 。根据经验，编写通用代码时，请避免使用不合格的函数调用，例如bubble_sort(begin, end, ...)；而是使用命名空间::bubble_sort(begin, end, ...)对其进行限定。

评论

\ $ \ begingroup \ $
您对inext的使用引入了一个细微的错误。现在，排序将显示UB为空或1元素向量。
\ $ \ endgroup \ $
–FRob
17年7月7日在7:43
\ $ \ begingroup \ $
@FRob我相当确定我没有引入任何错误。空范围的错误已由另一个答案捕获，此版本的大小为1的范围没有问题
\ $ \ endgroup \ $
–贾斯汀
17年7月7日在7:46

#2 楼

速度

当然，我们都知道气泡排序是最慢的排序算法之一。然而，事实证明，在迭代完成而没有交换的情况下停止通常会增加所节省的开销。我使用以下代码进行了快速测试：

template<typename Iterator, typename Comparator>
void bs2(Iterator begin, Iterator end, Comparator cmp) {
    for (auto j=end; j != begin; --j) {
        for (auto i = begin + 1; i != j; ++i) {
            auto& val0 = *i;
            auto& val1 = *(i - 1);
            if (cmp(val0, val1)) {
                std::swap(val1, val0);
            }
        }
    }
}


运行速度提高了20-25％。当然，如果您实际上关心速度，则可能希望完全切换到另一种算法，但是如果要进行冒泡排序，那么您至少也可以使用始终最快的变体。还有另一个变体（通常称为摇摇排序），它在向上和向下迭代之间交替。通常，这仍然比较慢。

依赖迭代器的类型

要查找与迭代器关联的值类型，请使用： /> 
const typename Iterator::value_type&


我将使用：

std::iterator_traits<Iterator>::value_type


对于一个示例，这将使代码可以与raw一起使用指针作为“迭代器”，原始代码将不会，因为指针不会定义value_type成员。



1。当然，缺少像bogosort这样的发明是要尽可能慢地进行。


评论

\ $ \ begingroup \ $
我的印象是，对于很小的数据集或几乎是有序的数据，气泡排序实际上是可以的-或由于低开销而可能更可取。
\ $ \ endgroup \ $
– JWT
17年7月6日在9:45


\ $ \ begingroup \ $
@JWT，气泡分类有更好的变体，例如振动筛分类和梳状分类。气泡排序引入了一个问题，我相信它被称为乌龟和兔子。请注意，梳齿排序需要<=才能起作用。
\ $ \ endgroup \ $
–难以置信
17年7月6日在9:52


\ $ \ begingroup \ $
@jwt：否。对于冒泡排序几乎可以正常工作的任何情况，插入排序或选择排序都会更好。在这两种方法中，插入排序通常更可取，但是如果您要比较的对象比复制便宜得多（例如，具有很多附加数据的int键），则选择排序可能更好。
\ $ \ endgroup \ $
–杰里·科芬（Jerry Coffin）
17年7月6日在13:29
\ $ \ begingroup \ $
我会对您在测试时收集的实际数据非常感兴趣。当然，我看到的要尽早终止的要点是，对于几乎已订购的容器：假设您有大量的物品（比如说1000万个），但是其中只有一两个是乱序的。不及早终止将导致近一千万次重复迭代，这可能是一个巨大的速度杀手。当然，我知道由于优化等原因，在平均情况下尽早终止可能没有好处。
\ $ \ endgroup \ $
–本·斯特凡（Ben Steffan）
17年7月6日在14:31
\ $ \ begingroup \ $
关于使用std :: iterator_traits的观点非常好。我可能会切换到您的版本。
\ $ \ endgroup \ $
–本·斯特凡（Ben Steffan）
17年7月6日在14:33

#3 楼

std::swap(val1, val0);


此硬编码std::swap是用于交换的功能。 C ++还具有强大的（有时是令人困惑的）机制，可以在多个名称空间中搜索一个函数：依赖于参数的查找（ADL）。在参数的命名空间中找到swap函数，还可以将std::swap添加为“后备”：以及对这一问题的最佳答案（但不要对它是对问题要点的错误引用感到困惑）。该标准将其效果描述为“ std::iter_swap(&val1, &val0)”（其中swap(*a,*b)和a是b的参数），并进一步强加“可交换”的要求，该要求指出：对象t可与之交换当且仅当以下情况中的对象u：


在以下描述的上下文中评估表达式std::iter_swap和swap(t, u)时，表达式才有效[..]

评估swap(u, t)和swap(t, u)时，应确保通过重载分辨率[..]在候选集上选择了一个名为“交换”的二进制非成员函数，该候选集包括：两个swap(u, t)函数在swap [..]和
中定义的模板由依赖于参数的查找[..]


[N4296]§17.6.3.2/ 2,3


评论

\ $ \ begingroup \ $
@DanielJour谢谢。我不知道这个“把戏”（尽管事后看来，这似乎很明显）。
\ $ \ endgroup \ $
–本·斯特凡（Ben Steffan）
17年7月6日在14:27

#4 楼

我将添加此名称，因为没有人提及它：代码将在空范围内导致未定义的行为。

原因是i != end无法正常工作，因为i已使用i + 1初始化。

我建议只在开始时进行检查，如果std::distance(begin, end)小于2，则返回。

评论

\ $ \ begingroup \ $
理想情况下，使用std :: distance计算距离。
\ $ \ endgroup \ $
–Daniel Jour
17年7月6日在5:22
\ $ \ begingroup \ $
@DanielJour，我的意思是，但可能更明确一点是值得的。谢谢
\ $ \ endgroup \ $
–难以置信
17年7月6日在5:23
\ $ \ begingroup \ $
@Incomputable谢谢，我完全没有考虑过这种极端情况！
\ $ \ endgroup \ $
–本·斯特凡（Ben Steffan）
17年7月6日在14:26
\ $ \ begingroup \ $
@BenSteffan，我建议设置一个测试。只需在循环中创建新的随机向量，对其进行排序即可，使用大小为0到75'000的std :: is_sorted。上限的每次增加都会严重增加运行时间。这应该很容易设置。
\ $ \ endgroup \ $
–难以置信
17年7月6日在14:29
\ $ \ begingroup \ $
@Incomputable在什么情况下？我认为您的答案没有提及速度（或时间复杂度），也没有任何评论。
\ $ \ endgroup \ $
–本·斯特凡（Ben Steffan）
17年7月6日在14:39

#5 楼

我看不到其他人尚未发表评论的内容。但是，让我们来看看您的主要工具：

而不是成员函数，更喜欢使用std::begin()和std::end()。这将使您的代码保持通用性，以便如果您切换到对vec使用C数组，代码将继续起作用。

    bubble_sort(vec.begin(), vec.end());

    // Like this:
    bubble_sort(std::begin(vec), std::end(vec));


使用基于范围的循环时，请优先使用auto类型。这样，如果您更改容器的基础类型，则无需更改for循环，因为这将适应容器的内容。

    for (unsigned e : vec) {
        std::cout << e << ' ';
    }

    // Like this:
    for (auto const& e : vec) {
        std::cout << e << ' ';
    }


另一个有用的地方在lambda参数值中使用auto。

    bubble_sort(std::begin(vec), std::end(vec), [] (auto const& v0, auto const& v1) {
            return v0 > v1;
        });


评论

\ $ \ begingroup \ $
感谢您的评论。我只是将主方法编写为一个快速测试，而没有对良好的编码实践等给予过多关注。不过，我必须承认，我什至不知道存在非成员std :: begin和std :: end，因此至少可能会变得有用（我确实了解auto，但是我倾向于写在我看来，大多数类型名都没有，因为它使代码更易于阅读（不过，关于更改基础类型的观点当然是有效的）。
\ $ \ endgroup \ $
–本·斯特凡（Ben Steffan）
17年7月6日在14:38
\ $ \ begingroup \ $
@BenSteffan我同意您应该始终明确地键入（重要的地方）。对于类型无关紧要但可以推断出位置的位置，应保留auto的使用。 （基于范围和lambda最明显）。
\ $ \ endgroup \ $
–马丁·约克
17年7月6日在20:47