如何在现代 C++ 中实现经典的排序算法? [英] How to implement classic sorting algorithms in modern C++?

查看:33
本文介绍了如何在现代 C++ 中实现经典的排序算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

来自 C++ 标准库的 std::sort 算法(及其表亲 std::partial_sortstd::nth_element)是在大多数实现中更多基本排序算法的复杂和混合合并,例如选择排序、插入排序、快速排序、合并排序,或堆排序.

The std::sort algorithm (and its cousins std::partial_sort and std::nth_element) from the C++ Standard Library is in most implementations a complicated and hybrid amalgamation of more elementary sorting algorithms, such as selection sort, insertion sort, quick sort, merge sort, or heap sort.

这里和姐妹网站(例如 https://codereview.stackexchange.com/)上有许多与错误、复杂性相关的问题以及这些经典排序算法实现的其他方面.提供的大多数实现都由原始循环、使用索引操作和具体类型组成,并且在正确性和效率方面通常很难分析.

There are many questions here and on sister sites such as https://codereview.stackexchange.com/ related to bugs, complexity and other aspects of implementations of these classic sorting algorithms. Most of the offered implementations consist of raw loops, use index manipulation and concrete types, and are generally non-trivial to analyse in terms of correctness and efficiency.

问题:如何使用现代 C++ 实现上述经典排序算法?

Question: how can the above mentioned classic sorting algorithms be implemented using modern C++?

  • 没有原始循环,但结合了来自
  • 的标准库的算法构建块
  • 迭代器接口和使用模板代替索引操作和具体类型
  • C++14 风格,包括完整的标准库,以及语法降噪器,例如 auto、模板别名、透明比较器和多态 lambda.莉>
  • no raw loops, but combining the Standard Library's algorithmic building blocks from <algorithm>
  • iterator interface and use of templates instead of index manipulation and concrete types
  • C++14 style, including the full Standard Library, as well as syntactic noise reducers such as auto, template aliases, transparent comparators and polymorphic lambdas.

注意事项:

  • 有关排序算法实现的更多参考,请参阅维基百科罗塞塔代码http:///www.sorting-algorithms.com/
  • 根据Sean Parent 的约定(幻灯片 39),原始循环是一个 for 循环,比两个函数与一个运算符的组合更长.所以 f(g(x));f(x);g(x);f(x) + g(x); 不是原始循环,selection_sort 中的循环也不是原始循环插入排序如下.
  • 我遵循 Scott Meyers 的术语,将当前的 C++1y 表示为 C++14,并将 C++98 和 C++03 都表示为 C++98,所以不要为此向我发火.
  • 正如@Mehrdad 在评论中所建议的那样,我在答案末尾提供了四种实现作为实时示例:C++14、C++11、C++98 和 Boost 以及 C++98.
  • 答案本身仅以 C++14 的形式呈现.在相关的地方,我表示各种语言版本不同的句法和库差异.
  • for further references on implementations of sorting algorithms see Wikipedia, Rosetta Code or http://www.sorting-algorithms.com/
  • according to Sean Parent's conventions (slide 39), a raw loop is a for-loop longer than composition of two functions with an operator. So f(g(x)); or f(x); g(x); or f(x) + g(x); are not raw loops, and neither are the loops in selection_sort and insertion_sort below.
  • I follow Scott Meyers's terminology to denote the current C++1y already as C++14, and to denote C++98 and C++03 both as C++98, so don't flame me for that.
  • As suggested in the comments by @Mehrdad, I provide four implementations as a Live Example at the end of the answer: C++14, C++11, C++98 and Boost and C++98.
  • The answer itself is presented in terms of C++14 only. Where relevant, I denote the syntactic and library differences where the various language versions differ.

推荐答案

算法构建块

我们首先从标准库中组装算法构建块:

Algorithmic building blocks

We begin by assembling the algorithmic building blocks from the Standard Library:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

  • 迭代器工具,例如非成员 std::begin()/std::end() 以及 std::next() 仅在 C++11 及更高版本中可用.对于C++98,这些需要自己编写.boost::begin()/boost::end() 中有 Boost.Range 的替代品,boost::next() 中有 Boost.Utility 的替代品).
  • std::is_sorted 算法仅适用于 C++11 及更高版本.对于 C++98,这可以通过 std::adjacent_find 和手写函数对象来实现.Boost.Algorithm 还提供了一个 boost::algorithm::is_sorted 作为替代.
  • std::is_heap 算法仅适用于 C++11 及更高版本.
    • the iterator tools such as non-member std::begin() / std::end() as well as with std::next() are only available as of C++11 and beyond. For C++98, one needs to write these himself. There are substitutes from Boost.Range in boost::begin() / boost::end(), and from Boost.Utility in boost::next().
    • the std::is_sorted algorithm is only available for C++11 and beyond. For C++98, this can be implemented in terms of std::adjacent_find and a hand-written function object. Boost.Algorithm also provides a boost::algorithm::is_sorted as a substitute.
    • the std::is_heap algorithm is only available for C++11 and beyond.
    • C++14 提供透明比较器的形式std::less<> 对它们的参数进行多态操作.这避免了必须提供迭代器的类型.这可以与 C++11 的 默认函数模板参数结合使用来创建单一重载,用于将 < 作为比较的排序算法和具有用户定义的比较函数对象的排序算法.

      C++14 provides transparent comparators of the form std::less<> that act polymorphically on their arguments. This avoids having to provide an iterator's type. This can be used in combination with C++11's default function template arguments to create a single overload for sorting algorithms that take < as comparison and those that have a user-defined comparison function object.

      template<class It, class Compare = std::less<>>
      void xxx_sort(It first, It last, Compare cmp = Compare{});
      

      在 C++11 中,可以定义一个可重用的模板别名来提取一个迭代器的值类型,它给排序算法的签名添加了轻微的混乱:

      In C++11, one can define a reusable template alias to extract an iterator's value type which adds minor clutter to the sort algorithms' signatures:

      template<class It>
      using value_type_t = typename std::iterator_traits<It>::value_type;
      
      template<class It, class Compare = std::less<value_type_t<It>>>
      void xxx_sort(It first, It last, Compare cmp = Compare{});
      

      在 C++98 中,需要编写两个重载并使用冗长的typename xxx::type 语法

      In C++98, one needs to write two overloads and use the verbose typename xxx<yyy>::type syntax

      template<class It, class Compare>
      void xxx_sort(It first, It last, Compare cmp); // general implementation
      
      template<class It>
      void xxx_sort(It first, It last)
      {
          xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
      }
      

      • 另一个语法精妙之处在于,C++14 有助于通过多态 lambdas(带有像函数模板参数一样推导出来的 auto 参数)来包装用户定义的比较器.
      • C++11 只有单态 lambda,需要使用上述模板别名 value_type_t.
      • 在 C++98 中,要么需要编写一个独立的函数对象,要么求助于冗长的 std::bind1st/std::bind2nd/std::not1 类型的语法.
      • Boost.Bind 使用 boost::bind_1/_2 占位符语法改进了这一点.
      • C++11 及更高版本也有 std::find_if_not,而 C++98 需要 std::find_ifstd::not1 围绕一个函数对象.
        • Another syntactical nicety is that C++14 facilitates wrapping user-defined comparators through polymorphic lambdas (with auto parameters that are deduced like function template arguments).
        • C++11 only has monomorphic lambdas, that require the use of the above template alias value_type_t.
        • In C++98, one either needs to write a standalone function object or resort to the verbose std::bind1st / std::bind2nd / std::not1 type of syntax.
        • Boost.Bind improves this with boost::bind and _1 / _2 placeholder syntax.
        • C++11 and beyond also have std::find_if_not, whereas C++98 needs std::find_if with a std::not1 around a function object.
        • 目前还没有普遍接受的 C++14 风格.无论好坏,我都密切关注 Scott Meyers 的有效现代 C++ 草案 和 Herb Sutter 的改进的 GotW.我使用以下风格推荐:

          There is no generally acceptable C++14 style yet. For better or for worse, I closely follow Scott Meyers's draft Effective Modern C++ and Herb Sutter's revamped GotW. I use the following style recommendations:

          • Herb Sutter 的 几乎总是自动" 和 Scott Meyers 的 首选自动而不是特定类型声明" 建议,其简洁性是无与伦比的,尽管有时它的清晰度是有争议.
          • Scott Meyers 的 在创建对象时区分 (){}" 并始终选择花括号初始化 {} 而不是旧的带括号的初始化 ()(为了回避通用代码中所有最棘手的解析问题).
          • Scott Meyers 的 比 typedef 更喜欢别名声明".无论如何,这对于模板来说是必须的,并且在任何地方使用它而不是 typedef 可以节省时间并增加一致性.
          • 我在某些地方使用 for (auto it = first; it != last; ++it) 模式,以便允许对已经排序的子范围进行循环不变检查.在生产代码中,在循环内的某处使用 while (first != last)++first 可能会稍微好一些.
          • Herb Sutter's "Almost Always Auto" and Scott Meyers's "Prefer auto to specific type declarations" recommendation, for which the brevity is unsurpassed, although its clarity is sometimes disputed.
          • Scott Meyers's "Distinguish () and {} when creating objects" and consistently choose braced-initialization {} instead of the good old parenthesized initialization () (in order to side-step all most-vexing-parse issues in generic code).
          • Scott Meyers's "Prefer alias declarations to typedefs". For templates this is a must anyway, and using it everywhere instead of typedef saves time and adds consistency.
          • I use a for (auto it = first; it != last; ++it) pattern in some places, in order to allow for loop invariant checking for already sorted sub-ranges. In production code, the use of while (first != last) and a ++first somewhere inside the loop might be slightly better.

          选择排序不会以任何方式适应数据,所以它的运行时间总是O(N²).但是,选择排序具有最小化交换次数的特性.在交换项目成本很高的应用程序中,选择排序非常好可能是首选算法.

          Selection sort does not adapt to the data in any way, so its runtime is always O(N²). However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

          要使用标准库实现它,重复使用 std::min_element 来查找剩余的最小元素,并使用 iter_swap 将其交换到位:

          To implement it using the Standard Library, repeatedly use std::min_element to find the remaining minimum element, and iter_swap to swap it into place:

          template<class FwdIt, class Compare = std::less<>>
          void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
          {
              for (auto it = first; it != last; ++it) {
                  auto const selection = std::min_element(it, last, cmp);
                  std::iter_swap(selection, it); 
                  assert(std::is_sorted(first, std::next(it), cmp));
              }
          }
          

          请注意,selection_sort 已将已处理的范围 [first, it) 排序为其循环不变量.与std::sort 的随机访问迭代器相比,最低要求是前向迭代器.

          Note that selection_sort has the already processed range [first, it) sorted as its loop invariant. The minimal requirements are forward iterators, compared to std::sort's random access iterators.

          细节省略:

          • 选择排序可以通过早期测试优化 if (std::distance(first, last) <= 1) return;(或者对于前向/双向迭代器:if (first == last || std::next(first) == last) return;).
          • 对于双向迭代器,上面的测试可以结合区间[first, std::prev(last))上的循环,因为最后一个元素是保证是最少的剩余元素,不需要交换.
          • selection sort can be optimized with an early test if (std::distance(first, last) <= 1) return; (or for forward / bidirectional iterators: if (first == last || std::next(first) == last) return;).
          • for bidirectional iterators, the above test can be combined with a loop over the interval [first, std::prev(last)), because the last element is guaranteed to be the minimal remaining element and doesn't require a swap.

          尽管它是具有 O(N²) 最坏情况时间的基本排序算法之一,插入排序 是当数据接近排序(因为它是自适应)或当问题规模很小(因为它的开销很低).由于这些原因,并且因为它也稳定,插入排序通常用作递归基本情况(当问题规模较小时)用于更高开销的分而治之排序算法,例如合并排序或快速排序.

          Although it is one of the elementary sorting algorithms with O(N²) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead). For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

          用标准库实现insertion_sort,重复使用std::upper_bound来查找当前元素需要去的位置,并使用std::rotate 将输入范围内的剩余元素向上移动:

          To implement insertion_sort with the Standard Library, repeatedly use std::upper_bound to find the location where the current element needs to go, and use std::rotate to shift the remaining elements upward in the input range:

          template<class FwdIt, class Compare = std::less<>>
          void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
          {
              for (auto it = first; it != last; ++it) {
                  auto const insertion = std::upper_bound(first, it, *it, cmp);
                  std::rotate(insertion, it, std::next(it)); 
                  assert(std::is_sorted(first, std::next(it), cmp));
              }
          }
          

          请注意,insertion_sort 已将已处理的范围 [first, it) 排序为其循环不变量.插入排序也适用于前向迭代器.

          Note that insertion_sort has the already processed range [first, it) sorted as its loop invariant. Insertion sort also works with forward iterators.

          细节省略:

          • 插入排序可以通过早期测试进行优化 if (std::distance(first, last) <= 1) return;(或者对于前向/双向迭代器:if (first == last || std::next(first) == last) return;) 和区间 [std::next(first), last) 上的循环,因为保证第一个元素就位,不需要轮换.
          • 对于双向迭代器,可以使用标准库的std::find_if_not用反向线性搜索代替查找插入点的二分查找代码>算法.
          • insertion sort can be optimized with an early test if (std::distance(first, last) <= 1) return; (or for forward / bidirectional iterators: if (first == last || std::next(first) == last) return;) and a loop over the interval [std::next(first), last), because the first element is guaranteed to be in place and doesn't require a rotate.
          • for bidirectional iterators, the binary search to find the insertion point can be replaced with a reverse linear search using the Standard Library's std::find_if_not algorithm.

          四个现场示例(C++14强>C++11C++98 和 BoostC++98) 用于以下片段:

          Four Live Examples (C++14, C++11, C++98 and Boost, C++98) for the fragment below:

          using RevIt = std::reverse_iterator<BiDirIt>;
          auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
              [=](auto const& elem){ return cmp(*it, elem); }
          ).base();
          

          • 对于随机输入,这给出了 O(N²) 次比较,但对于几乎已排序的输入,这改进为 O(N) 次比较.二分查找总是使用 O(N log N) 比较.
          • 对于较小的输入范围,线性搜索更好的内存局部性(缓存、预取)也可能会支配二分搜索(当然应该对此进行测试).
            • For random inputs this gives O(N²) comparisons, but this improves to O(N) comparisons for almost sorted inputs. The binary search always uses O(N log N) comparisons.
            • For small input ranges, the better memory locality (cache, prefetching) of a linear search might also dominate a binary search (one should test this, of course).
            • 如果仔细实施,快速排序 是健壮的并且具有 O(N log N) 预期的复杂度,但是 O(N²) 最坏情况的复杂度可以用对抗性选择的输入数据触发.当不需要稳定排序时,快速排序是一种很好的通用排序.

              When carefully implemented, quick sort is robust and has O(N log N) expected complexity, but with O(N²) worst-case complexity that can be triggered with adversarially chosen input data. When a stable sort is not needed, quick sort is an excellent general-purpose sort.

              即使对于最简单的版本,使用标准库实现快速排序也比其他经典排序算法要复杂得多.下面的方法使用一些迭代器实用程序来定位输入范围 [first, last)middle element 作为主元,然后使用两次对 std 的调用::partition(它们是 O(N))将输入范围三路划分为分别小于、等于和大于所选主元的元素段.最后对元素小于和大于主元的两个外部段进行递归排序:

              Even for the simplest versions, quick sort is quite a bit more complicated to implement using the Standard Library than the other classic sorting algorithms. The approach below uses a few iterator utilities to locate the middle element of the input range [first, last) as the pivot, then use two calls to std::partition (which are O(N)) to three-way partition the input range into segments of elements that are smaller than, equal to, and larger than the selected pivot, respectively. Finally the two outer segments with elements smaller than and larger than the pivot are recursively sorted:

              template<class FwdIt, class Compare = std::less<>>
              void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
              {
                  auto const N = std::distance(first, last);
                  if (N <= 1) return;
                  auto const pivot = *std::next(first, N / 2);
                  auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
                      return cmp(elem, pivot); 
                  });
                  auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
                      return !cmp(pivot, elem);
                  });
                  quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
                  quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
              }
              

              然而,快速排序要获得正确和高效是相当棘手的,因为必须针对生产级代码仔细检查和优化上述每个步骤.特别是,对于 O(N log N) 复杂度,pivot 必须导致输入数据的平衡分区,这对于 O(1) 主元,但如果将主元设置为输入范围的 O(N) 中值,则可以保证这一点.

              However, quick sort is rather tricky to get correct and efficient, as each of the above steps has to be carefully checked and optimized for production level code. In particular, for O(N log N) complexity, the pivot has to result into a balanced partition of the input data, which cannot be guaranteed in general for an O(1) pivot, but which can be guaranteed if one sets the pivot as the O(N) median of the input range.

              细节省略:

              • 上述实现特别容易受到特殊输入的影响,例如对于风琴管"输入1、2、3、...、N/2、...,它具有O(N^2)复杂度3, 2, 1(因为中间总是比所有其他元素都大).
              • median-of-3 来自 从输入范围中随机选择的元素 防止几乎排序的输入,否则复杂性会恶化到O(N^2).
              • 3-way partitioning(分隔小于、等于到并大于枢轴),如对 std::partition 的两次调用所示,并不是实现此结果的最有效的 O(N) 算法.
              • 对于随机访问迭代器,可以通过使用std的中值枢轴选择来保证O(N log N)复杂度::nth_element(first, middle, last),然后递归调用quick_sort(first, middle, cmp)quick_sort(middle, last, cmp).
              • 然而,这种保证是有代价的,因为 std::nth_elementO(N) 复杂性的常数因子可能比O(1) 复杂度为 3 的中值枢轴,然后是 O(N)std::partition 的调用(即对数据进行缓存友好的单次前向传递).
              • the above implementation is particularly vulnerable to special inputs, e.g. it has O(N^2) complexity for the "organ pipe" input 1, 2, 3, ..., N/2, ... 3, 2, 1 (because the middle is always larger than all other elements).
              • median-of-3 pivot selection from randomly chosen elements from the input range guards against almost sorted inputs for which the complexity would otherwise deteriorate to O(N^2).
              • 3-way partitioning (separating elements smaller than, equal to and larger than the pivot) as shown by the two calls to std::partition is not the most efficient O(N) algorithm to achieve this result.
              • for random access iterators, a guaranteed O(N log N) complexity can be achieved through median pivot selection using std::nth_element(first, middle, last), followed by recursive calls to quick_sort(first, middle, cmp) and quick_sort(middle, last, cmp).
              • this guarantee comes at a cost, however, because the constant factor of the O(N) complexity of std::nth_element can be more expensive than that of the O(1) complexity of a median-of-3 pivot followed by an O(N) call to std::partition (which is a cache-friendly single forward pass over the data).

              如果使用 O(N) 额外空间无关紧要,那么 merge sort 是一个很好的选择:它是唯一的稳定 O(N log N) 排序算法.

              If using O(N) extra space is of no concern, then merge sort is an excellent choice: it is the only stable O(N log N) sorting algorithm.

              使用标准算法实现很简单:使用一些迭代器实用程序来定位输入范围的中间 [first, last) 并将两个递归排序的段与 std 组合起来::inplace_merge:

              It is simple to implement using Standard algorithms: use a few iterator utilities to locate the middle of the input range [first, last) and combine two recursively sorted segments with a std::inplace_merge:

              template<class BiDirIt, class Compare = std::less<>>
              void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
              {
                  auto const N = std::distance(first, last);
                  if (N <= 1) return;                   
                  auto const middle = std::next(first, N / 2);
                  merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
                  merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
                  std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
              }
              

              合并排序需要双向迭代器,瓶颈是std::inplace_merge.请注意,在对链表进行排序时,归并排序只需要 O(log N) 额外空间(用于递归).后一种算法由标准库中的 std::list::sort 实现.

              Merge sort requires bidirectional iterators, the bottleneck being the std::inplace_merge. Note that when sorting linked lists, merge sort requires only O(log N) extra space (for recursion). The latter algorithm is implemented by std::list<T>::sort in the Standard Library.

              堆排序很容易实现,执行一个O(N log N) 就地排序,但不稳定.

              Heap sort is simple to implement, performs an O(N log N) in-place sort, but is not stable.

              第一个循环,O(N)heapify"阶段,将数组放入堆顺序.第二个循环,O(N log N)排序"阶段,重复提取最大值并恢复堆顺序.标准库使这变得非常简单:

              The first loop, O(N) "heapify" phase, puts the array into heap order. The second loop, the O(N log N) "sortdown" phase, repeatedly extracts the maximum and restores heap order. The Standard Library makes this extremely straightforward:

              template<class RandomIt, class Compare = std::less<>>
              void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
              {
                  lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
                  lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
              }
              

              如果您认为使用 std::make_heapstd::sort_heap 是作弊",您可以更深入一层并按照以下方式自己编写这些函数std::push_heapstd::pop_heap 分别为:

              In case you consider it "cheating" to use std::make_heap and std::sort_heap, you can go one level deeper and write those functions yourself in terms of std::push_heap and std::pop_heap, respectively:

              namespace lib {
              
              // NOTE: is O(N log N), not O(N) as std::make_heap
              template<class RandomIt, class Compare = std::less<>>
              void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
              {
                  for (auto it = first; it != last;) {
                      std::push_heap(first, ++it, cmp); 
                      assert(std::is_heap(first, it, cmp));           
                  }
              }
              
              template<class RandomIt, class Compare = std::less<>>
              void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
              {
                  for (auto it = last; it != first;) {
                      std::pop_heap(first, it--, cmp);
                      assert(std::is_heap(first, it, cmp));           
                  } 
              }
              
              }   // namespace lib
              

              标准库将push_heappop_heap 指定为复杂度O(log N).但是请注意,[first, last) 范围内的外循环导致 O(N log N) 对于 make_heap 的复杂性,而 std::make_heap 只有 O(N) 复杂度.对于 heap_sort 的整体 O(N log N) 复杂度,这无关紧要.

              The Standard Library specifies both push_heap and pop_heap as complexity O(log N). Note however that the outer loop over the range [first, last) results in O(N log N) complexity for make_heap, whereas std::make_heap has only O(N) complexity. For the overall O(N log N) complexity of heap_sort it doesn't matter.

              细节省略:O(N) 实现 <代码>make_heap

              这里有四个现场示例(C++14C++11C++98 和 BoostC++98) 在各种输入上测试所有五种算法(并不意味着详尽或严格).请注意 LOC 的巨大差异:C++11/C++14 需要大约 130 个 LOC,C++98 和 Boost 190 (+50%) 和 C++98 需要超过 270 (+100%).

              Here are four Live Examples (C++14, C++11, C++98 and Boost, C++98) testing all five algorithms on a variety of inputs (not meant to be exhaustive or rigorous). Just note the huge differences in the LOC: C++11/C++14 need around 130 LOC, C++98 and Boost 190 (+50%) and C++98 more than 270 (+100%).

              这篇关于如何在现代 C++ 中实现经典的排序算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆