std::tupleとstd::tieを使って複数の配列を一緒にソートする（配列の構造体 SoA のソート）

互いに関連付けられた複数の配列を一緒にソートしたい場合があります．

// SoAの例
std::vector<int> student_ids;
std::vector<std::string> names;
std::vector<int> math_scores;

// AoSの例
struct Student {
  int id;
  std::string name;
  int math_score
};

専門的には，SoA（Structure of Array：配列の構造体）と呼びます（かならずしも構造体とはなっていなくても）．一方，普通に構造体やクラスの配列になっている場合はAoS（Array of Structure：構造体の配列）と呼ばれます．

さて，このSoAのデータ構造をソートしたいと思います．上の例で言いうと，生徒番号を元に名前などのフィールドを一斉にソートしたいということです．最初からAoSを採用すれば余計な苦労はありませんが，歴史的な事情や効率の都合でSoAになっているとします．

そこで，C++11のstd::tupleを使って，SoAを内部的にAoSに変換してソートする関数を書いてみました．ポイントは，std::tieを使うとPythonの一括代入のようなことができるという点ですね．これは調べるまで知りませんでした．

template<class T, class...Args>
void TiedSort(std::vector<T> &a, std::vector<Args>&... args) {
  using tt = struct {
    T key;
    std::tuple<Args...> val;
  };
  std::vector<tt> vals(a.size());

  for (size_t i = 0; i < a.size(); i++) {
    vals[i].key = a[i];
    vals[i].val = std::make_tuple(args[i]...);
  }

  std::sort(std::begin(vals), std::end(vals), [](const tt& a, const tt& b) {
      return a.key < b.key;
    });
  
  for (size_t i = 0; i < a.size(); i++) {
    a[i] = vals[i].key;
    std::tuple<Args&...>(args[i]...) = vals[i].val;
  }
}

int main() {
  std::vector<int> student_ids = {3,2,5,1,4};
  std::vector<double> weights = {42.3, 34.6, 32.5, 51.2, 41.7};
  std::vector<double> heights = {1,1,1,1,1};
  
  TiedSort<int, double, double>(student_ids, weights, heights);
}

なお，SoAをソートする方法としては，インデックス配列を用意してそれをソートする方法（数学で言う置換：permutationを使う）方法もありますが，これだと一時領域が必要になりコピーのコストが増大するため低速でした．そのうちPAPIとかを使ってきっちり評価したいとは思いますが．

C++テンプレートテクニック 第2版