Skip to content

Latest commit

 

History

History
250 lines (195 loc) · 12.8 KB

README.md

File metadata and controls

250 lines (195 loc) · 12.8 KB

cpp-sort logo

Latest Release Conan Package Code Coverage Pitchfork Layout

It would be nice if only one or two of the sorting methods would dominate all of the others, regardless of application or the computer being used. But in fact, each method has its own peculiar virtues. [...] Thus we find that nearly all of the algorithms deserve to be remembered, since there are some applications in which they turn out to be best. — Donald Knuth, The Art Of Computer Programming, Volume 3

cpp-sort is a generic C++14 header-only sorting library. It revolves around one main generic sorting interface and provides several small tools to pick and/or design sorting algorithms. Using its basic sorting features should be trivial enough:

#include <array>
#include <iostream>
#include <cpp-sort/sorters/smooth_sorter.h>

int main()
{
    std::array<int, 5> arr = { 5, 8, 3, 2, 9 };
    cppsort::smooth_sort(arr);

    // prints 2 3 5 8 9
    for (int val: arr) {
        std::cout << val << ' ';
    }
}

The main features & the extra features

cpp-sort provides a full set of sorting-related features. Here are the main building blocks of the library:

Here is a more complete example of what can be done with the library:

#include <algorithm>
#include <cassert>
#include <forward_list>
#include <functional>
#include <vector>
#include <cpp-sort/adapters.h>
#include <cpp-sort/sorters.h>

int main()
{
    struct wrapper { 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 otherwise
    cppsort::hybrid_adapter<
        cppsort::pdq_sorter,
        cppsort::merge_sorter
    > sorter;

    // Sort li and vec in reverse order using their value member
    sorter(li, std::greater<>{}, &wrapper::value);
    sorter(vec, std::greater<>{}, &wrapper::value);

    assert(std::equal(
        li.begin(), li.end(),
        vec.begin(), vec.end(),
        [](const auto& lhs, const auto& rhs) { return lhs.value == rhs.value; }
    ));
}

Even when the sorting functions are used without the extra features, they still provide some interesting guarantees (ideas often taken from the Ranges TS):

  • They provide both an iterator and a range interface
  • When possible, they accept a custom comparator parameter
  • Most of them accept a projection parameter
  • They correctly handle proxy iterators with iter_swap and iter_move
  • They also work when iterators don't provide post-incrementation nor post-decrementation
  • The value types of the collections to be sorted need not be default-constructible
  • The value types of the collections to be sorted need not be copyable (only movable)
  • Stateless sorters can be converted to a function pointer for each overloaded operator()
  • Sorters are function objects: they can directly be passed as "overload sets" to other functions

You can read more about all the available tools and find some tutorials about using and extending cpp-sort in the wiki.

Benchmarks

The following graph has been generated with a script found in the benchmarks directory. It shows the time needed for heap_sort to sort one million elements without being adapted, then when it is adapted with either drop_merge_adapter or split_adapter.

Graph showing the speed difference between heap_sort raw, then adapted with split_adapter and drop_merge_adapter, when the number of inversions in the std::vector<int> to sort increases

As can be seen above, wrapping heap_sort with either of the adapters makes it adaptive to the number of inversions in a non-intrusive manner. The algorithms used to adapt it have different pros and cons, it is up to you to use either.

This benchmark is mostly there to show the possibilities offered by the library. You can find more such commented benchmarks in the dedicated wiki page.

Compiler support & tooling

Ubuntu builds status Windows builds status MacOS builds status

cpp-sort requires C++14 support, and should work with the following compilers:

  • g++7 or more recent.
  • clang++6.0 or more recent (with both libstdc++ and libc++).
  • The versions of MinGW-w64 and AppleClang equivalent to the compilers mentioned above.
  • Visual Studio 2019 version 16.8.3 or more recent, only with /permissive-. A few features are unavailable.
  • clang-cl corresponding the the Visual Studio version above.

The compilers listed above are the ones used by the CI pipeline, and the library is also tested with the most recent versions of those compilers on a regular basis. All the other compiler versions in-between are untested, but should also work. Feel free to open an issue if it isn't the case.

The features in the library might differ depending on the C++ version used and on the compiler extensions enabled. Those changes are documented in the wiki.

The main repository contains additional support for standard tooling such as CMake or Conan. You can read more about those in the wiki.

Thanks

I got a new car. I just need to put it together. They’re easier to steal piece by piece. — Jarod Kintz, $3.33

Even though some parts of the library are original research and some others correspond to custom and rather naive implementations of standard sorting algorithms, cpp-sort also reuses a great deal of code and ideas from open-source projects, often altered to integrate seamlessly into the library. Here is a list of the external resources used to create this library. I hope that the many different licenses are compatible. If it is not the case, please contact me (or submit an issue) and we will see what can be done about it: