モダンな闇の力でスターリンソート！


# はじめに

この記事は、闇の力でスターリンソートした先駆者様 [闇の力を駆使すればO(1)でスターリンソートなぞ容易いものよ](https://qiita.com/angeart/items/f43072e414f2ff8c7532) に影響を受けて書いたものです。とても綺麗な実装で、少し手を加えれば、C++11 にも対応できそうなものでした！そこで、この記事では C++17 から追加された機能を使って書いた場合、どこまで直感的にかけるのかを試してみました！

# スターリンソートとは

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる</p>&mdash; やんぎん (@4116You) <a href="https://twitter.com/4116You/status/1155619860027547648?ref_src=twsrc%5Etfw">July 28, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

ソート順に並んでいない要素を粛清する、スピーディーでエキサイティングなアルゴリズムです！

# 実装

```c++
#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));
}
```
[wandbox](https://wandbox.org/permlink/yhuR1Ujs6f6cucQo)

# 解説のようなもの

### stalin_sort（エントリ関数）

```cpp
// スターリンソートの関数
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]

### 比較と粛清

```cpp
// 実装です
// ソート済みの、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`を用いて次のように書けます。

```cpp
#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`を用いてください！！

```cpp
#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 されました！
![43414B91-58D9-4D10-8577-BF281E07E66B.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/195827/c592854a-0f24-6532-ef1c-14a094e900ec.png)


# まとめ
C++17 を使うと、分かりやすく、直感的に書けます！！C++20 にも期待が高まりますね！

[^1]: https://www.boost.org/doc/libs/1_61_0/libs/hana/doc/html/index.html より