std::ranges::zip_viewを使ってsort_by_key関数のメンテ

概要

むかーしに書いたsort_by_key関数がmsvcのC++20環境で動作しなくなったので、C++23で導入されたranges::zip_viewを使って書き直しました.

sort_by_key

sort_by_key関数は、2個のコンテナを対象に取り片方のコンテナをソート用のキーとして扱い他方のコンテナはキーとして扱うコンテナに連動してソートするものです.

template<typename KeyIt, typename ValueIt>
void sort_by_key(
    KeyIt keys_first, KeyIt keys_last,
    ValueIt values_begin
);

例えば、Thrustやboost.computeで実装されています.

ただ、どちらも使用していない環境だったため映像奮闘記: C++で2種類のコンテナを同時にソートするやSorting two arrays simultaneouslyといった記事を参考にして車輪の再発明をしていました.

C++20になって

msvcのC++17あたりまではiter_swapをごにょごにょする程度で使えていたのですが、C++20にあげようとしたらコンパイル出来なくなってしまいました.

原因は、zip_iteratorとstd::iter_swapにあるように、ソートの最中に値を入れ替えるswap関数の実装として自前で用意したものを挟み込めない、というものでした.
std::tuple風のラッパを作ればよいのですが... 面倒さに負けて断念していました.

std::ranges::zip_view の登場

Visual Studio 2022 version 17.5 のリリースノートに、views::zipを実装したとの記載があったので試してみることにしました.

過去のしがらみがないのなら

const int N = 6;
int    keys[N] = { 1,   4,   2,   8,   5,   7 };
char values[N] = { 'a', 'b', 'c', 'd', 'e', 'f' };

std::ranges::sort(std::ranges::zip_view(keys, values));
// keys:   1  2  4  5  7  8
// values: a  c  b  e  f  d
std::ranges::sort(std::ranges::zip_view(keys, values), std::greater{});
// leus:   8  7  5  4  2  1
// values: d  f  e  b  c  a

これで、やりたいことが出来ます. 便利!!

しがらみがあるならば

もともと実装していたsort_by_key関数のインタフェースを変更したくなかったので、このような実装になりました.

template<typename KeyIt, typename ValueIt, typename Compare>
void sort_by_key(
    KeyIt keys_first, KeyIt keys_last,
    ValueIt values_begin,
    Compare comp
)
{
    auto r = std::views::zip(
        std::ranges::subrange(keys_first, keys_last),
	std::ranges::subrange(values_begin, values_begin + std::distance(keys_first, 
	keys_last))
	);
    using value_type = std::ranges::range_value_t<decltype(r)>;
    std::sort(
        r.begin(), r.end(),
	[comp](const value_type& left, const value_type& right) -> bool {
	    return comp(std::get<0>(left), std::get<0>(right));
	});
}

subrangeを使ってイテレータペアをRangeに

イテレータのペアをRangeとして扱うには、C++20から導入されたsubrangeを使います. (名前を見て、部分範囲を切り出す・参照するためのものだと思ってしばらく方法を見つけられなかった...)

zip_viewでまとめて後は...

イテレータペアをsubrangeを使ってRangeに出来たので、std::view::zipを使えば2つのRangeを1つにまとめることができます. あとは、sort関数に放り込めばおしまい. と上手くいかないのが悲しいところ.

C++03/14時代の関数オブジェクトどうする

昔から使っているコードなので、こんな感じの呼び出しをしてる箇所がありました.

static_assert(std::is_same_v<int, std::iter_value_t<decltype(key_it_b)>);
sort_by_key(key_it_b, key_it_e, value_it_b, std::less<int>());

既存コードの変更を避け、sort_by_key関数の中身を修正だけで対応するために比較用の関数オブジェクトをラムダ式でキャプチャして使うことにしました. こうしないと、関数オブジェクトにtuple(std::tuple<int &,char &>)が渡されてしまい引数の型がintではないのでコンパイルエラーになります.

おまけ

キー配列が構造体だったときのコード. プロジェクションを使ってtuple内にある構造体からキーを取り出しています.

struct s { int key; };
int main()
{
    const int N = 6;
    s      keys[N] = { s{1}, s{4}, s{2}, s{8}, s{5}, s{7} };
    char values[N] = { 'a',  'b',  'c',  'd',  'e',  'f' };

    std::ranges::sort(std::ranges::zip_view(keys, values), std::greater{}, [](auto&& v) -> auto&& {
        return std::get<0>(
            std::forward<decltype(v)>(v)
        ).key;
    });
}