ADMIS_Walker のぶろぐ: C++ で複数の std::vector<T> を１つの std::vector<T> を基準にソートする

概要

  C++ で複数の std::vector<T> を１つの std::vector<T> を基準に sort する場合を考える ※1．こうした場合，通常 std::vector<T> に含まれる値を構造体や，std::pair<T>, std::tuple<T> に入れ替えてから std::sort() で並び替える．ここで，sort された結果を，構造体や，std::pair<T>, std::tuple<T> のまま取り扱いたい場合は問題ない．一方で，構造体や，std::pair<T>, std::tuple<T> を，再び std::vector<T> に変換したい場合は，データ構造ごとに別々の実装が必要でコードは煩雑となり，計算コストも増える．
  この計算コスト削減の観点では，基準となる std::vector<T> の sort 順序を保存しておき，保存結果を元に残る std::vector<T> する方法が考えられる．この考えは，例えば Stack overflow で取り上げられている ※2．
  この投稿では，計算コストを加味した上で，さらにコードを簡略化する方法を紹介する． C++ のテンプレートの再帰展開を応用すると，これまで煩雑だった処理を１行で記述できるようになる．

※1. 具体例としては，一方の std::vector<T> が ID を持っており，もう一方の std::vector<T> が対応する文字列を持っている場合に， ID を基準として 2 つの std::vector<T> を並び替えたい状況が考えられる．
※2. 例えば，StackOverflow に紹介されている． Sorting multiple vectors based on a reference vector

提案する実装

C++ のテンプレートの再帰展開を応用し，複数の std::vector<T> を１つの std::vector<T> を基準としてソートする．この際，引数の std::vector<T> が１つの場合は別に定義し，余分な sort 順序保存用の std::vector<T> を作らないようにする．

namespace sstd{
    template <typename T> inline void sort   (std::vector<T>& rhs){ std::sort(rhs.begin(), rhs.end());                    }
    template <typename T> inline void sort_gr(std::vector<T>& rhs){ std::sort(rhs.begin(), rhs.end(), std::greater<T>()); }
    
    class sstd_mult_vec_sort{
    private:
    public:
        std::vector<uint> idx;
        sstd_mult_vec_sort(uint size): idx(size) {}
        ~sstd_mult_vec_sort(){}
    };
    
    template<typename T>
    inline void _sort(const class sstd_mult_vec_sort& s, std::vector<T>& head){
        std::vector<T> head_tmp(head.size());
        for(uint i=0; i<s.idx.size(); ++i){
            head_tmp[i] = head[s.idx[i]];
        }
        std::swap(head_tmp, head);
    }
    template<typename Head, typename... Tail>
    inline void _sort(const class sstd_mult_vec_sort& s, Head&& head, Tail&&... tail){
        sstd::_sort(s, std::forward<Head>(head));
        sstd::_sort(s, std::forward<Tail>(tail)...);
    }
    template<typename Head, typename... Tail>
    inline void sort(Head&& head, Tail&&... tail){ // Ascending: 昇順: 0, 1, 2, ...
        class sstd_mult_vec_sort s(head.size());
        std::iota(s.idx.begin(), s.idx.end(), 0);
        std::sort(s.idx.begin(), s.idx.end(), [&](uint lhs, uint rhs) -> bool { return head[lhs] < head[rhs]; });
        
        sstd::_sort(s, std::forward<Head>(head));
        sstd::_sort(s, std::forward<Tail>(tail)...);
    }
    template<typename Head, typename... Tail>
    inline void sort_gr(Head&& head, Tail&&... tail){ // Descending: 降順: 9, 8, 7, ...
        class sstd_mult_vec_sort s(head.size());
        std::iota(s.idx.begin(), s.idx.end(), 0);
        std::sort(s.idx.begin(), s.idx.end(), [&](uint lhs, uint rhs) -> bool { return !(head[lhs] < head[rhs]); });
        
        sstd::_sort(s, std::forward<Head>(head));
        sstd::_sort(s, std::forward<Tail>(tail)...);
    }
}

動作サンプル

./main.cpp

#include <sstd/sstd.hpp>

int main(){
    std::vector<int>         v1_sorting_seed = {1, 3, 5, 2, 4};
    std::vector<std::string> v2              = {"one", "three", "five", "two", "four"};
    std::vector<std::string> v3              = {"1", "3", "5", "2", "4"};
    std::vector<std::string> v4              = {"a", "c", "e", "b", "d"};
    std::vector<std::string> v5              = {"A", "C", "E", "B", "D"};

    sstd::sort(v1_sorting_seed, v2, v3, v4, v5);

    sstd::printn(v1_sorting_seed);
    sstd::printn(v2);
    sstd::printn(v3);
    sstd::printn(v4);
    sstd::printn(v5);
}

実行結果

v1_sorting_seed = [1 2 3 4 5]
v2 = ["one" "two" "three" "four" "five"]
v3 = ["1" "2" "3" "4" "5"]
v4 = ["a" "b" "c" "d" "e"]
v5 = ["A" "B" "C" "D" "E"]

まとめ

この投稿では，C++ で複数の std::vector<T> を１つの std::vector<T> を基準としてソートする場合に，これまでより簡潔かつ使い回せる実装を紹介した．

付録

収録ライブラリ

この投稿の実装は，拙ライブラリ sstd の math に実装されている．

ADMIS_Walker のぶろぐ

2022年5月28日

C++ で複数の std::vector<T> を１つの std::vector<T> を基準にソートする

0 件のコメント:

コメントを投稿