Modern C++ can be easy as Python
Modern C++ is powerful but easy to write and read - if done good.
Sometimes I do programming tasks just for training (inspired by the Kata as described in Uncle Bobs Clean Coder book), and one of them is the quicksort algorithm.
I will not describe the algorithm itself here, a lot of people already have done this pretty well so there is no need to repeat it.
And of course both Python as well as C++ provide better and faster ways of sorting containers, even the quicksort algorithm I used
here is not the best one, but in my oppinion good understandable.
For a better implementation have a look at my quicksort with stl post.
My intention is to show that Python and Modern C++ are pretty similar, the last one may even be easier if you are confident with the
Iterator design pattern.
At first the Python implementation:
from typing import Sequence
def _swap(sequence:Sequence, left:int, right:int):
"""Swap `sequence[left]` with `sequence[right]`."""
sequence[left], sequence[right] = sequence[right], sequence[left]
def _partition(sequence:Sequence, lbound:int, rbound:int)->int:
"""
Partition `sequence` from `lbound` (start index) to `rbound` (stop index, included)
by using the rightmost element in it as pivot.
After leaving this function all elements in the given `sequence` range smaller than
the pivot will be placed left to it, all others right from it.
Returns the index of pivot in `sequence`.
"""
pivot = sequence[rbound]
left:int = lbound
right:int = rbound - 1
while left < right:
while sequence[left] > pivot:
left += 1
while right >= left and sequence[right] <= pivot:
right -= 1
if left < right:
_swap(sequence, left, right)
left += 1
right -= 1
if left == right and sequence[left] > pivot:
left += 1
if sequence[left] != pivot:
_swap(sequence, left, rbound)
return left
def _quicksort(sequence:Sequence, lbound:int, rbound:int):
"""Perform an inplace quicksort in `sequence` range from `lbound` to `rbound` index (both including)."""
if lbound < rbound:
pivot_index:int = _partition(sequence, lbound, rbound)
_quicksort(sequence, lbound, pivot_index - 1)
_quicksort(sequence, pivot_index + 1, rbound)
def quicksort(sequence):
"""Perform inplace quicksort in `sequence`"""
_quicksort(sequence, 0, len(sequence) - 1)
This looks pretty easy to read, now the C++20 implementation:
# include <algorithm>
/// Swap data from iterator `left` with `right`
auto _swap(auto left, auto right) {
auto tmp = std::move(*left);
*left = std::move(*right);
*right = std::move(tmp);
}
/** Partition from `lbound` (start iterator) to `rbound` (stop iterator) by using the element at `rbound` as pivot.
* After leaving this function all elements in the given range smaller than the pivot will be placed left to it,
* all others right from it.
* Returns an iterator to the pivot seperating the both partitions.
*/
auto _partition(auto&& lbound, auto&& rbound) {
auto pivot = *rbound;
auto left = lbound;
auto right = rbound - 1;
while (left < right) {
while (*left < pivot)
++left;
while ((right > left) && (*right >= pivot))
--right;
if (left < right) {
_swap(left, right);
++left;
--right;
}
}
if (left == right && *left < pivot)
++left;
if (*left != pivot)
_swap(left, rbound);
return left;
}
/** Perform an inplace quicksort from iterator `lbound` to `rbound` (both including).
* The iterators have to be contiguous (which is ensured by a constraint to `IteratorType`.
*/
template < std::contiguous_iterator IteratorType >
void quicksort(IteratorType lbound, IteratorType rbound) {
if (lbound < rbound) {
auto pivot_position = _partition(lbound, rbound);
quicksort(lbound, pivot_position > lbound ? pivot_position - 1 : pivot_position);
quicksort(pivot_position < rbound ? pivot_position + 1 : pivot_position, rbound);
}
}
/// Perform inplace quicksort in `sequence`
void quicksort(auto& sequence) {
quicksort(std::begin(sequence), std::end(sequence) - 1);
}
Using the std::contiguous_iterator
concept for the template parameter IteratorType
ensures that only contiguous iterators can be
passed to quicksort
(such as those from std::vector
, std::basic_string
or std::array
).
Passing an invalid (not contiguous iterator) type here will lead to a speaking error message
(instead of the confusing litanies SFINEA produces):
quicksort.cpp(54,3): message : The assigned restrictions are not fulfilled.
quicksort.cpp(32,12): message : The concept
"std::contiguous_iterator<std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>>" was evaluated as FALSE