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
Handle sentinel parameters #20
Comments
Add sentinel support for sorters that don't require lots of modifications to get there: - cartesian_tree_sorter - counting_sorter - insertion_sorter - mel_sorter - selection_sorter
Add sentinel support for sorters that don't require lots of modifications to get there: - cartesian_tree_sorter - counting_sorter - insertion_sorter - mel_sorter - selection_sorter
Implement sentinel support in their simplest form for all sorters: compute the last iterator from the first and the sentinel, then send the resulting iterator pair to the implementation. Getting all sorters to work required to add sentinel support to the following components: - hybrid_adapter - split_adapter - drop_merge_adapter - sized_iterator
Implement sentinel support in their simplest form for all sorters: compute the last iterator from the first and the sentinel, then send the resulting iterator pair to the implementation. Getting all sorters to work required to add sentinel support to the following components: - hybrid_adapter - split_adapter - drop_merge_adapter - sized_iterator
At long last I'm making progress in this issue, now that Ranges-v3 is already history, the Ranges TS is no more, and most iterator and ranges improvements have been merged into C++20 and compiler and standard library support mostly caught up. By now this issue is the oldest still open issue in the library, dating back to the very first year of the project, which is quite something. Nostalgia aside, I am done adding basic sentinel support and tests for all sorters, sorter adapters and measures of presortedness in the library, modulo unseen bugs and missed components. Philosophically, I can consider that this part is done. However the story doesn't end there! The following points must be treated before I can close the issue:
Additionally, the following points can be the subject of follow-up development and features:
If automatic sentinel support is added to |
The Ranges TS introduces the notion of sentinels. A sentinel is an end iterator with a different type than the actual iterators; it shall be comparable to the other iterators and may be used to help the compiler generate better code.
We probably want to have such sentinel iterators at some point in cpp-sort. However, it will probably require lots of tricky SFINAE and modifying most of the available algorithms to get things right.
It is worth noting that the Ranges TS makes
sort
andstable_sort
return an iterator to the last element, which makes sense in the context of sentinels: when a couting/size sentinel is passed, the last iterator isn't known beforehand, so the algorithm returns it since it might be useful. This adds a new question: how do we handle adapters such ascounting_adapter
that already override the return type? Do we still override that return type, or do we return a tuple? The latter solution allows not to throw away information, so it might be preferred.The text was updated successfully, but these errors were encountered: