はじめに
この記事は、闇の力でスターリンソートした先駆者様 闇の力を駆使すればO(1)でスターリンソートなぞ容易いものよ に影響を受けて書いたものです。とても綺麗な実装で、少し手を加えれば、C++11 にも対応できそうなものでした！そこで、この記事では C++17 から追加された機能を使って書いた場合、どこまで直感的にかけるのかを試してみました！
スターリンソートとは
ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— やんぎん (@4116You) July 28, 2019
ソート順に並んでいない要素を粛清する、スピーディーでエキサイティングなアルゴリズムです！
実装
#include <utility>
#include <boost/hana/tuple.hpp>
#include <boost/hana/functional/arg.hpp>
#include <boost/hana/equal.hpp>
namespace hana = boost::hana;
// 最終的に tuple を作る際のヘルパー関数
template <auto ... args, auto ... i>
inline constexpr auto make_tuple_helper(std::index_sequence<i...>) noexcept
{
return hana::make_tuple(hana::arg<i>(args...)...);
}
// 実装です
// ソート済みの、1 ベースの index を返します
template <auto itr, auto end, auto ... args, auto ... result_indexes>
inline constexpr auto stalin_impl(std::index_sequence<result_indexes...>) noexcept
{
// 自明なものです
if constexpr (sizeof...(args) == 0) return std::index_sequence<>{};
// ストッパーです
else if constexpr (itr == end)
return std::index_sequence<result_indexes...>{};
// 次の要素の値が、現在の結果のインデックスの
// 最後が指す要素未満の場合に粛清します！
else if constexpr (hana::arg<hana::arg<sizeof...(result_indexes)>(result_indexes...)>(args...)
> hana::arg<itr + 1>(args...))
// 粛清して再帰！
return stalin_impl<itr + 1, end, args...>(
std::index_sequence<result_indexes...>{}
);
// そうでなければ、次の要素を同胞にして再帰！
else return stalin_impl<itr + 1, end, args...>(
std::index_sequence<result_indexes..., itr + 1>{}
);
}
// スターリンソートの関数
template <auto ... args>
inline constexpr auto stalin_sort() noexcept
{
return make_tuple_helper<args...>(
stalin_impl<1, sizeof...(args), args...>(std::index_sequence<1>{})
);
}
auto main() -> int
{
static_assert(stalin_sort<>() == hana::make_tuple()); // コンパイル時にソート完了！
static_assert(stalin_sort<0>() == hana::make_tuple(0));
static_assert(stalin_sort<2,3>() == hana::make_tuple(2, 3));
static_assert(stalin_sort<2,1,3>() == hana::make_tuple(2, 3));
static_assert(stalin_sort<2,1,3,3,2,5,6>() == hana::make_tuple(2,3,3,5,6));
}
解説のようなもの
stalin_sort（エントリ関数）
// スターリンソートの関数
template <auto ... args>
inline constexpr auto stalin_sort() noexcept
{
return make_tuple_helper<args...>(
stalin_impl<1, sizeof...(args), args...>(std::index_sequence<1>{})
);
}
テンプレート引数argsをソートします。そして、boost::hana::tupleにソート済みのものを入れて返します。boost::hana::tupleにした理由は、もともとboost::hana::argを使いたかったので、tupleもそれに合わせようと思ったからです。さらに、どうやらboost::hana::tupleはstd::tupleより速いらしいです。1
比較と粛清
// 実装です
// ソート済みの、1 ベースの index を返します
template <auto itr, auto end, auto ... args, auto ... result_indexes>
inline constexpr auto stalin_impl(std::index_sequence<result_indexes...>) noexcept
{
// 自明なものです
if constexpr (sizeof...(args) == 0) return std::index_sequence<>{};
// ストッパーです
else if constexpr (itr == end)
return std::index_sequence<result_indexes...>{};
// 次の要素の値が、現在の結果のインデックスの
// 最後が指す要素未満の場合に粛清します！
else if constexpr (hana::arg<hana::arg<sizeof...(result_indexes)>(result_indexes...)>(args...)
> hana::arg<itr + 1>(args...))
// 粛清して再帰！
return stalin_impl<itr + 1, end, args...>(
std::index_sequence<result_indexes...>{}
);
// そうでなければ、次の要素を同胞にして再帰！
else return stalin_impl<itr + 1, end, args...>(
std::index_sequence<result_indexes..., itr + 1>{}
);
}
ソート済みの、引数argsのインデックスを返します。インデックスが 1 から始まる理由は、boost::hana::argのインデックスが1から始まっているためです。ここで、boost::hana::argは、パラメーターパックの n 番目の要素を返す関数です。これを用いて要素同士の比較を行っています。また、C++17 の機能であるconstexpr ifを用いています。さらに、テンプレート引数のautoも C++17 の機能です。
テンプレート引数のitrとendは、テンプレート引数argsのイテレータのつもりです。この関数では、引数の数が 0 個のときには早期に結果を返しています。引数の数が 2 つ以上なら、テンプレート引数 現在の結果インデックスの最後の場所にあるitrの場所argsの要素 と、その次の itr + 1 の場所にある要素とを比較しています。もし itr + 1 の要素の方が大きければ、itr + 1を std::index_sequenceに追加し、再帰しています。そうでなければ、追加せずに粛清して、再帰しています... そして、itrがargsの最後のインデックスだった場合、パラメーターパックargs...のソート済みインデックスが入っているstd::index_sequenceを返しています。
展開して標準出力に表示する
もし、標準出力に表示する必要があれば、boost::hana::tapを用いて次のように書けます。
#include <boost/hana/tap.hpp>
constexpr auto result = stalin_sort<3, 1, 4, 1, 5>();
result | hana::tap<hana::tuple_tag>([](const auto& x) { std::cout << x; }); // 表示！
[追記]
と思ったのですが、実はboost::hana::tapは呼び出し順序が規定されていないため、tupleの要素の初めから順に表示させるためには、代わりにboost::hana::for_eachを用いてください！！
#include <boost/hana/for_each.hpp>
constexpr auto result = stalin_sort<3, 1, 4, 1, 5>();
hana::for_each(result, [](const auto& x){ std::cout << x; });
PR
プルリク出しました！
https://github.com/gustavo-depaula/stalin-sort/pull/88
[追記]
Merge されました！
まとめ
C++17 を使うと、分かりやすく、直感的に書けます！！C++20 にも期待が高まりますね！