Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

P0100: Comparison in C++ #18

Closed
3 of 13 tasks
Morwenn opened this issue Oct 28, 2015 · 4 comments
Closed
3 of 13 tasks

P0100: Comparison in C++ #18

Morwenn opened this issue Oct 28, 2015 · 4 comments

Comments

@Morwenn
Copy link
Owner

Morwenn commented Oct 28, 2015

P0100, Comparison in C++, is a proposal to enhance comparisons in C++, which may directly affect sorting algorithms and related features. Among the future improvements are the following ones:

  • Make versions of algorithms that take trinary comparators.
  • Transition algorithms to use trinary comparators by default.

Since cpp-sort is all about sorting, these ideas may be interesting to improve the library. That said, I don't want to change anything before an actual design is proposed to alter the algorithms in the standard library to handle three-way comparators. Once such a design has been proposed and validated, I'll start updating cpp-sort so that it matches the new design.

Among the changes proposed or implied by P0100, here is what could be used to improve cpp-sort, and a bunch of interesting questions:

  • Three-way comparators may be used to implement a three-way partitioning quicksort.
  • Three-way comparators may be used to implement a proper wrapper for std::qsort (mostly used to show how other algorithms are better though).
  • These comparators may reduce the number of not compare(x, y) used to either make sorts stable or make them more efficient with equivalent values.
  • The implementation of grail_sort already uses some kind of three-way comparator, but one that almost always perform more operations than it should. Standard three-way comparators would be better for sure.
  • Do we want to default the comparators to total_order, if possible so that the results are a bit more deterministic?
  • How to make actually efficient orders for built-in types? The trivial way is far from fast and there doesn't seem to be dedicated builtin function for three-way comparison around. Also the steps needed to perform a weak or partial orders on floating point numbers really slow down the whole thing (especially if we default everything to total_order).

Lots of things to think through, but it may be interesting in the end :)


As always, here we go with a list of features to implement:

  • Introduce the enumerations partial_ordering, weak_ordering and total_ordering.
  • Introduce the customization points partial_order, weak_order and total_order.
  • Provide all the required orders for built-in types.
  • Introduce the customization points partial_less, partial_unordered, partial_greater, weak_less, weak_equivalence, weak_greater, total_less, total_equal and total_greater.
  • Provide optimized versions for built-in types.
  • Take advantage of std::string::compare.
  • Provide type traits so that algorithms can be used with trinary comparators.
  • Change three_way_compare so that it can adapt both binary and trinary comparators. Make it take an order and 4 functions objects corresponding to <, >, <= and >=, which could possibly be optimized. If these function objects are not provided by the user, default them to generic function generating the comparison from the order function.
  • Optimize it for the new standard orders.
  • Adapt... every algorithm so that they can accept either predicates or trinary comparators (recode them with three_way_compare and transform everything with it).
  • Complete the testsuite.
  • Update the documentation.
  • Update the bubble_sorter example (it might get tricky).
@Morwenn Morwenn changed the title P0100R0: how it may affect cpp-sort in the future P0100: how it may affect cpp-sort in the future Nov 17, 2015
@Morwenn Morwenn added the future label Nov 23, 2015
@Morwenn Morwenn changed the title P0100: how it may affect cpp-sort in the future P0100: Comparison in C++ Nov 23, 2015
@Morwenn Morwenn removed the future label Mar 13, 2016
@Morwenn
Copy link
Owner Author

Morwenn commented Mar 13, 2016

This was tagged as a future issue since it assumed that the work would be too big without a standard implementation. Actually reimplementing what was thoroughly described in the proposal was a matter of hours. This is still a huge piece of work, especially adapting the algorithms and providing the right tools to users, but we don't have to wait for C++19 or C++20 to start implementing it.

Update: on the other hand, I realize that I am not sure how P0100 plans to handle algorithms and this is a bit troubling. I'm tempted to add the future label back.

@Morwenn
Copy link
Owner Author

Morwenn commented Jul 31, 2016

Implement total_less, total_greater, weak_less, weak_greater, partial_less and partial_greater as customization points in the master branch in a new comparators module. The comparators natively handle integral and floating point numbers, but rely on user-provided functions for everything else.

The partial_unordered, weak_equivalence and total_equal functions only have sense in this library if the *_order functions are provided too. The rest of the features will have to wait for the ideas in P0100 to be clear before being implemented. Adding the future label back until then.

@Morwenn
Copy link
Owner Author

Morwenn commented Mar 24, 2018

Not sure what to do with that issue anymore: half of the problems are solved with the new C++20 operator<=> and related comparison features. I don't think I that I want to provide more C++14 features that will get deprecated by better standard features in C++20.

I'm keeping the issue open for now but probably won't implement the features as proposed.

@Morwenn Morwenn mentioned this issue Feb 22, 2019
5 tasks
@Morwenn
Copy link
Owner Author

Morwenn commented Feb 22, 2019

This issue has been surperseded by #145 which restates the challenges of adapting the library to three-way comparison with the tools we're getting in C++20.

@Morwenn Morwenn closed this as completed Feb 22, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant