Skip to content

1.5.0 — Roadtrip
Compare
Choose a tag to compare
@Morwenn Morwenn released this 17 Aug 10:32
1.5.0
da5aa9f
This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Learn about vigilant mode.

I spent the last two weeks enjoying a roadtrip through Scotland, watching the beautiful landscape while two good friends enjoyed driving the van on single-track roads. This feels pretty consistent with the previous Tartan release, and once again it gave me a boost of motivation to publish a cpp-sort release, so here we are.

New features

The highlight of this release is the ability for sorter adapters to accept stateful sorters: this is the first step required for supporting mutable sorters in the library (issue #104). This is useful to provide first-class support for sorters that are parametrized at construction time: for example imagine a counting_sorter taking min and max parameters at construction time to avoid having to look them up, it would still be possible to adapt such a sorter as follows:

auto sort1 = counting_sorter(0, 100); // NOT the cpp-sort sorter
auto sort2 = cppsort::out_of_place_adapter(sort1);
sort2(collection);

Several part of the library have been modified in order to support this feature. Here is an incomplete list of things that changed as a result:

  • Most of the library's sorter adapters can now adapt stateful sorters out-of-the-box. One notable exception is small_array_adapter for which I was unable to come up with a satisfying design.
  • Said sorter adapters now have a get() member function to retrieve a copy of the original sorter, except hybrid_adapter for which a single get() function wouldn't make sense since it adapts several sorters.
  • These sorter adapters now also work with sorters that aren't default-constructible.
  • sorter_facade was updated to handle stateful sorters: it can now be constructed with parameters which are forwarded to the sorter implementation, and it now only provides operators to convert the sorter to different of function pointers when said sorter is empty and default-constructible.

In order to work properly with sorter adapters, sorters are expected to be copy-constructible: adapters make a copy of the sorters they adapt. Additionally a sorter is expected to be empty and default-constructible for conversions to function pointers to work.

Under the hood, pretty much every single-sorter adapter inherits from the newly introduced utility::adapter_storage<Sorter> to store and retrieve the sorter they adapt. This class template implements three operations:

  • Construction from a sorter: unless the passed sorter is empty and default-constructible, it copies the passed sorter into its internals.
  • Retrieval of a sorter: if the sorter type it adapts is empty and default-constructible, then it returns a default-constructed instance of said sorter type, otherwise it returns a properly reference to the stored sorter whose const and reference qualifications depend on that of the adapter_storage instance.
  • Invocation of the wrapped sorter: adapter_storage::operator() forwards its parameters to the corresponding operator in the wrapped sorter (or to a default-constructed sorter) and returns the result of that operation.

If you need to write a sorter adapter that properly handles stateful sorters, then inheriting from adapter_storage is probably the simplest solution to correctly provide the full gamut of semantics described above.

Bug fixes

  • grail_sorter and tim_sorter now support comparison and projection function objects that aren't default-constructible.
  • Fix codegen issue with MinGW-w64 GCC 9.1, which sometimes triggered a segfault when using quick_merge_sorter (issue #151).

Improvements

Function objects from the comparators module have been improved in the following ways (issue #150):

  • The non-refined comparators are now transparent comparators: they have an is_transparent member type which allows them to be used in the standard library's ordered associative containers to compare heterogeneous types.
  • The module now exposes explicit names for the main comparator types: total_less_t, total_greater_t, natural_less_t, etc. to make them more usable where type names are needed.
  • natural_less is now able to compare heterogeneous types as long as they provide begin and end functions returning iterators that share a common value_type.

Other library improvements:

  • Several out-of-place merge functions used in the library have been improved, which could make the following tools slightly faster: block_sorter, grail_sorter, merge_sorter, split_sorter, verge_sorter and verge_adapter.
  • The internal move[_backward] algorithms have been rewritten to fallback to their std:: counterparts in more situations, which might make a good number of the library's algorithms faster when the std:: algorithms are optimized for specific iterators: this should notably be the case for libc++ std::deque iterators.
  • Further small optimizations for grail_sorter and tim_sorter.
  • If the global operator delete supports sized deallocation, then several allocating algorithms will take advantage of it.

Tooling

  • The conanfile.py recipe is better integrated with CMake, and notably uses the project's CMakeLists.txt install rules to package the library.
  • The generated CMake package version file is now architecture-independent.
  • The sanitizers should now fail fast when expected to.
  • The Windows builds now correctly work with incremental compilation in Travis.

Known bugs

I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

Assets 2