Home
Welcome to the cpp-sort 1.16.0 documentation!
This wiki contains documentation about the library: basic documentation about the many sorting tools and how to use them, documentation about the additional utilities provided by the library, as well as a few tutorials about writing your own sorters or sorter adapters. This main page explains a few general things that didn't quite fit in other parts of the documentation.
For the simpler use cases, a good place to start is the quickstart page.
If you find a library feature which isn't documented, don't hesitate to open an issue. It generally means that we either need to hide it in a subnamespace or to let it available and document it.
Every library function provides the no-leak guarantee, which means that all the memory allocated by components of the library will automatically be deallocated, even when an exception is thrown. The library itself should never throw exceptions, except std::bad_alloc when memory couldn't be allocated: in the different parts of the documentation, algorithms whose space complexity is worse than O(1) can throw std::bad_alloc unless the documentation explicitly mentions that they can't.
If the library throws any other exception, it will likely come from user code. The main functions that are likely to throw exceptions are the following ones:
- User-defined comparison functions
- User-defined projection functions
- Move & swap operations of the objects to sort
- Operations of the iterators/containers passed to the algorithms
cpp-sort makes no guarantee about the state of the passed collection after an exception is thrown while an algorithm runs. It might result in several objects in a moved-from state if an exception is thrown while elements of the collection to sort have been moved to a temporary buffer.
cpp-sort strives to follow the standard library guidance when it comes to self-move and self-swap operations: when sorting a collection of T, the expectations are as follows:
- The algorithms in the library should never perform a blind self-move operation since there is no guarantee about the result of such an operation.
- However the different algorithms expect
Tto satisfy the C++20swappableconcept. This concepts requires that, for any valuexof typeT, the following code doesn't change the value ofx:This means that some of the library's algorithms can actually perform self-swap operations, and it is the responsibility of the author of classusing std::swap; swap(x, x);
Tto make sure that such code works as expected.
New in version 1.4.0
So far every algorithm in the library is deterministic: for a given input, one should always get the exact same sequence of operations performed. It was a deliberate choice not to use algorithms such as random pivot quicksort or random sampling algorithms.
The library does not contain multithreaded algorithms either for now, further guaranteeing reproducibility.
cpp-sort follows semantic versioning and provides the following macros in <cpp-sort/version.h> to check the current major, minor and patch versions:
CPPSORT_VERSION_MAJOR
CPPSORT_VERSION_MINOR
CPPSORT_VERSION_PATCHcpp-sort ships with a header that includes the forward declarations for the library's main components.
#include <cpp-sort/fwd.h>Including that header will provide forward declarations for sorters, fixed-size sorters, and sorter adapters.
Some old components undergo deprecation before being removed in the following major revisions of the library. Those components are marked as [[deprecated]] and thus will warn when used. You can silence the deprecation warnings by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS.
New in version 1.8.0
Some algorithms have assertions to guard against accidental logic issues (mostly in algorithms adapted from other projects), but they are disabled by default. You can enable these assertions by defining the preprocessor macro CPPSORT_ENABLE_ASSERTIONS. This new macro still honours NDEBUG, so assertions won't be enabled anyway if NDEBUG is defined.
A similar CPPSORT_ENABLE_AUDITS macro can be defined to enable audits: those are expensive assertions which are not enabled by CPPSORT_ENABLE_ASSERTIONS because they are too expensive, to the point that they might even change the complexity of some algorithms. When turning on audits, assertions are automatically enabled too, and internal uses of [[assume(...)]] and equivalent statements are turned into assertions. This macro also honours NDEBUG.
The macros CPPSORT_ENABLE_ASSERTIONS and CPPSORT_ENABLE_AUDITS can be configured directly from CMake by setting the eponymous options to ON. See the Tooling page for more information.
New in version 1.6.0
New in version 1.9.0: CPPSORT_ENABLE_AUDITS
New in version 1.15.0: CPPSORT_ENABLE_ASSERTIONS and CPPSORT_ENABLE_AUDITS can be defined with CMake options.
Changed in version 1.15.0: defining CPPSORT_ENABLE_AUDITS now automatically defines CPPSORT_ENABLE_ASSERTIONS.
When defined, the macro CPPSORT_USE_LIBASSERT makes internal assertions use libassert instead of the standard assert macro. This allows assertions to provide additional information when an assertion fires, notably by displaying a full stack trace, and optionally to decompose the asserted expressions. See the library's README for more information.
This option can be enabled from CMake by setting the CPPSORT_USE_LIBASSERT to ON. See the Tooling page for more information.
Note: the support for libassert is still experimental and has not been tested on all supported platforms. Errors are to be expected.
New in version 1.15.0
This wiki also includes a small section about the original research that happened during the conception of the library and the results of this research. While it is not needed to understand how the library works or how to use it, it may be of interest if you want to discover new things about sorting.
If you ever feel that this wiki is incomplete, that it needs more examples or more detailed explanation about stuff, you are welcome to report it and/or contribute.
Always keep in mind that even if the library does contain production-ready algorithms, many of them are also experimental algorithms taken straight from research papers and reimplemented from scratch. If you are only interested in usable algorithms, you should look at the ones analyzed in the benchmarks.
Hope you have fun!