帮酷LOGO
  • 显示原文与译文双语对照的内容
Additional sorting algorithms for C++14

  • 源代码名称:cpp-sort
  • 源代码网址:http://www.github.com/Morwenn/cpp-sort
  • cpp-sort源代码文档
  • cpp-sort源代码下载
  • Git URL:
    git://www.github.com/Morwenn/cpp-sort.git
  • Git Clone代码到本地:
    git clone http://www.github.com/Morwenn/cpp-sort
  • Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/Morwenn/cpp-sort
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
  • Latest ReleaseBuild StatusLicenseCode Coverage

    如果只有一或者两种排序方法能够支配所有其他的,不管应用程序或者使用的计算机是什么,它都很好。 但事实上,每种方法都有自己独特的优点。 因此,我们发现几乎所有的算法都值得记住,因为有些应用程序是最好的,它们是最好的。 ,计算机编程艺术,卷 3

    cpp排序是一个通用的C++14头排序库。 它围绕一个主要的通用排序接口,提供了几个小工具来挑选和/或者设计排序算法。 使用它的基本排序功能应该足够简单:

    #include<array>#include<iostream>#include<cpp-sort/sort.h>intmain()
    {
     std::array<int, 5u> arr = { 5, 8, 3, 2, 9 };
     cppsort::sort(arr);
     // prints 2 3 5 8 9for (int val: arr) {
     std::cout <<val <<'';
     }
    }
    主要功能&附加功能

    排序实际上提供了一组完整的排序相关特性。 以下是库的主要构造块:

    下面是一个更完整的示例,说明如何使用该库:

    #include<algorithm>#include<cassert>#include<forward_list>#include<functional>#include<iterator>#include<vector>#include<cpp-sort/adapters.h>#include<cpp-sort/sorters.h>intmain()
    {
     structwrapper { int value; };
     std::forward_list<wrapper> li = { {5}, {8}, {3}, {2}, {9} };
     std::vector<wrapper> vec = { {5}, {8}, {3}, {2}, {9} };
     // When used, this sorter will use a pattern-defeating quicksort// to sort random-access collections, and a mergesort otherwiseusing sorter = cppsort::hybrid_adapter<
     cppsort::pdq_sorter,
     cppsort::merge_sorter
    > ;
     sorter sort;
     // Sort li and vec in reverse order using their value membersort(li, std::greater<>{}, &wrapper::value);
     sort(vec, std::greater<>{}, &wrapper::value);
     assert(std::equal(
     std::begin(li), std::end(li),
     std::begin(vec), std::end(vec),
     [](auto& lhs, auto& rhs) { return lhs.value == rhs.value; }
     ));
    }

    即使没有额外功能使用排序函数,它们仍然提供了一些有趣的保证( 从范围TS的想法。):

    • 它们同时提供一个迭代器和一个范围接口
    • 如果可能,他们接受定制的比较器参数
    • 其中大多数都接受投影参数
    • 它们使用 iter_swapiter_move 正确处理代理迭代器
    • 当迭代器不提供日志增量或者 post-decrementation时,它们也工作
    • 要排序的集合的值类型不必是默认构造函数
    • 要排序的集合的值类型不必是 copyable ( 只可以移动)
    • 可以将无状态排序器转换为每个重载的operator()的函数指针
    • 排序器是函数对象:它们可以直接作为"重载集"传递给其他函数

    你可以阅读更多关于可用工具的信息,并在中找到关于使用和扩展cpp排序的一些教程。

    基准测试

    下面的图已经生成,并在benchmark目录中找到了一个脚本。 它显示了排序算法所需的时间,将一百万个已经拖动的std::array<int, N>的大小分为 0到 15. 比较了排序小数组时通常使用的排序器:

    small shuffled int arrays

    这些结果是用 MINGW G++ 6.1.0生成的,编译器选项 -std=c++1z -O2 -march=native 。 这个基准测试只是一个例子,让这个简介看起来不错。 你可以在专用wiki页面中找到更多的注释基准。

    命令行编译器支持

    当前的cpp排序需要C++14支持,并且只使用g++5和 clang++3 。8 或者更高版本的这些编译器。 到目前为止,构建矩阵+ 主测试提供以下支持:

    • 在Linux上使用g++5和 clang++3 。8
    • 使用 Xcode 8在OSX上工作
    • 使用 MinGW-w64 g++5在 Windows 上工作
    • 同时使用libstdc++和 libc+ +
    • 在Linux和OSX上通过Valgrind检查,每个经过测试的编译器
    • 通过 G++ 和 clang+ + 在Linux上传递未定义的杀毒检查
    • 通过 clang+ + 在Linux上检查地址消毒器

    上次尝试它时,MSVC 2017无法使用。 C++14分支的未来开发将尝试保持与上面列出的编译器版本兼容。 上面没有列出一些消毒测试,不是因为它们触发错误,而是因为我不能让它们正确构建。

    储存库还包含实验性的C++17分支需要最新版本的G++ 和 clang++,而且可能需要更多的最新版本,直到两个编译器的C++17支持足够稳定。 值得注意的是,当新语言和标准库功能取代了一些实用程序头时,针对C++14分支编写的代码不能被保证使用;这些更改会被记录在文件头上。 C++17分支具有比C++14分支更多的特性,并且将在某个时间点有一些重要特性,例如正确处理执行策略,以实现并行排序算法。 在后来的某些时候,C++17分支可以能成为主分支,C++14分支只接收 Bug 修复和小更新。

    长期目标是使库随着 C++ 标准进化,C++14和C++17分支之间的差异也将在未来的分支之间存在。 一些诸如概念和标准范围之类的特性可能会塑造图书馆的未来。

    谢谢

    我买了辆新车。 我只需要把它放在一起。 他们容易被撕成碎片。 - Jarod Kintz,$3.33

    library是一些标准排序算法,而其他一些则与开放源代码项目的实现相对应,通常是经过修改的,以集成到库中的代码。 下面是用于创建这里库的外部资源的列表。 我希望许多不同的许可证兼容。 如果不是这种情况,请联系我( 或者提交一个问题),我们将看到什么可以做的事情,对它:

    • insertion_sorterpdq_sorter 使用的一些算法来自Orson的模式失败快速排序。 基准测试的某些部分也来自于那里。

    • tim_sorter 使用的算法来自实现的Goro ( gfx )的Timsort

    • spread_sorter 使用的三种算法来自 Steven Ross Boost.Sort MODULE 。

    • utility::as_function 和几个投影增强的helper 算法来自的niebler范围v3库中的Eric 。 代理迭代器。定制点和投影等几个想法也来自于该库或者相关文章和标准 C++ 建议。

    • ska_sorter 使用的算法来自于实现的Malte of他自己的ska_sort 算法。

    • drop_merge_sorter 使用的算法来自 Wielgosik C++ reimplementation ( ernerfeldt drop-merge-sort )的Emil

    • 许多增强标准算法直接从它们在 libc++ 中的对应项修改,增强了处理投射和代理迭代器的。

    • 库内部使用了一个 inplace_merge 函数,它可以与前向迭代器一起工作。 它的实现采用由Dudziński和Dydek提出的合并算法,并由Alexander和 Paul McJones在他们的图书编程语言编程元素Elements中实现。

    • 本文采用 smooth_sorter 算法直接从算法的实现中直接调整了dijkstra所使用的dijkstra 。

    • block_sorter 所使用的算法已经从 bonzaithepenguin WikiSort的

    • grail_sorter 使用的算法已经从 mrrl GrailSort的中修改,因此名称是。

    • sorting_network_sorter 使用的算法 0到 16已经用 perl Algorithm::Networksort MODULE 生成。

    • sorting_network_sorter 和 18使用的算法 17对称和进化found网络排序优化( 传感器) published使用对称和进化搜索,以最小化排序网络,通过Valsalam和 Miikkulainen 。

    • sorting_network_sorter,20,21,24,和 28使用的算法已经被发现并建议由Bert的SorterHunter项目 。 你可以以在他的网站上找到最多最多 32个输入网络的已经知排序网络的完整列表。

    • sorting_network_sorter 使用的一些优化来自讨论讨论 StackOverflow,并通过文章 来支持Optimized优化的排序库

    • 用于绘制排序网络的LaTeX 脚本是 sortingnetwork.tex的版本,稍微适合于 0-based,并从上到下绘制网络。




    Copyright © 2011 HelpLib All rights reserved.    知识分享协议 京ICP备05059198号-3  |  如果智培  |  酷兔英语