最近作ったライブラリの話

本記事は Aizu Advent Calendar 2021 の 9 日目の記事になります

adventar.org

はじめに

えー、当日になっても書くネタが決まってなかったので最近作った競技プログラミング用のライブラリを紹介していきたいと思います

とりあえず直近のものからいくつか選んで紹介していこうかなと思ったら、書いてる途中で以外に量がおおめになってしまったので一つだけ紹介します

ちなみにライブラリは GitHub で公開しています

GitHub - matumoto1234/library

reversed を作ってみた

さて、紹介するのは reversed になります

機能としては簡単なもので、渡された配列などを逆順にして返すものです

ここで突然ですがあなたに質問をします

Q. C++ で配列などを後ろからループで回したいときにどのようにループさせますか？

A. i を使ってやるだけ（代わりに答えさせていただきました）

まさしくそのとおりだと思います

自分は以下のようなコードをよく書きます

for (int i = array.size() - 1; i >= 0; i--) {
  // array[i] についての処理
}

これは正しく動きそうです

しかし、set や map などのインデックスによるランダムアクセスが許可されていないものはこの書き方をそのままなぞってしまうと思わぬ時間がかかってしまうことがあります

ループを回す方法としてはいくつかの手段があり、前から見ていくだけであれば以下のように範囲 for 文を使えば綺麗に書くことができます

for (auto key : set) {
  // key についての処理
}

後ろから見ていくとなると以下のようにイテレータを使うのが一般的かと思います

for (auto it = set.rbegin(); it != set.rend(); it++) {
  // it についての処理
}

この二つの方法を見比べて、明らかに後者の方が記述量が多いですよね

自分は範囲 for 文の書き方を知ってしまったら、イテレータを使った書き方はあまり書きたくないという気持ちが強まりまってしまいました（もう、もどれない...）

( ´・＿・`) < どうにかして範囲 for 文くらい簡単に逆順走査ができる良い方法もしくは関数などはないだろうか...

( ・`д・´) < それ boost にあるよ !!

そんなときに boost/range/adaptor/reversed の出番です¹
reversed に配列などを渡すと逆順に並び替えられて返ってきます

例えば、先ほどの set の逆順走査を以下のように書くことができます

for (auto key : set | reversed) {
  // key についての処理
}

boost/range/adaptor/reversed では、| 演算子をオーバーロードしており上記のようにきれいに書くことができました

かなり便利だと思います

注意点

ただ、注意点としてこの reversed という関数は要素を逆順にしたものをそのまま返しているわけではありません

auto set2 = set | reversed

としたときの set2 の型は
struct boost::range_detail::reversed_range<std::set<int>> になります

今回自作した reversed は単純に逆順にしたものが返ってきたらうれしいなーというお気持ちで作りました

どういうものにするか

reversed をどういう関数にしようかというお話です

とりあえず、先ほど出てきた set、map に対応させるとして vector や list にも対応できたらうれしいです

そして実は set や map、vector などは C++ ではコンテナと呼ばれていて区別されています

コンテナ一覧

array
deque
forward_list
list
vector
set
map
multiset
multimap
unordered_set
unordered_map
unordered_multiset
unordered_multimap
stack
queue
priority_queue

ということで、コンテナの要素を逆順にしたものを返すように作ろうと思います

より具体的にまとめると
reversed(v) := コンテナ v の要素を逆順にしたものを返す

というようになります

ただし、unordered_set、unordered_map などは今回扱いません（unordered なので）

`set` などに関する問題

ただ、ここで問題となってくるのが set や map の扱いです

set、map などの連想配列は平衡二分探索木を用いて実装されています
その際に比較関数を使用して要素を整列させており、それに従わなければ連想配列の機能を保てないため、逆順にするといった要素の並び替えが行えません

うー－－－－ん、どうしよう

散々困った末にたどり着いた結論は比較関数で場合分けするというものでした

set などを宣言するときに、テンプレートパラメータの第二引数に比較関数を渡すことができます

例えば、下記のような感じです

set<int, less<int>> a;
set<int, greater<int>> b;

// 比較関数を省略すると set<T, less<T>> が適応される
set<int> c;

そこで、比較関数が less だったときは greater にしてそれ以外だったときは less になっている set を返そうという方針にしました（map も同様です）

どう実装するか

C++ の標準で is_container だったり is_set だったりといった型を判別するものはないので自前で用意する必要があります

しかし、コンテナの種類は少ないので全種類オーバーロードを行うと個々の型に対しての操作も見やすくなり実装も楽です

基本的には以下のようになるかと思います

template <typename T, size_t N>
array<T, N> reversed(const array<T, N> &a) {
  array<T, N> res = a;
  reverse(res.begin(), res.end());
  return res;
}

template <typename T>
vector<T> reversed(const vector<T> &d) {
  vector<T> res = d;
  reverse(d.begin(), d.end());
  return res;
}

// こんな感じでたくさん書く

以下に書く map の実装は計算量を意識して less → greater と greater → less の操作はならし計算量 $ O(N) $ になるようにしました
それ以外 → less の計算量は $ O(N \log N) $ です（要素を逆順にするだけなのでもっといい方法がありそう...）

// less -> greater
template <typename T1, typename T2>
map<T1, T2, greater<T1>> reversed(const map<T1, T2, less<T1>> &m) {
  map<T1, T2, greater<T1>> res;
  for (const auto &p: m) {
    res.emplace_hint(res.begin(), p);
  }
  return res;
}

// greater -> less
template <typename T1, typename T2>
map<T1, T2, less<T1>> reversed(const map<T1, T2, greater<T1>> &m) {
  map<T1, T2, less<T1>> res;
  for (const auto &p: m) {
    res.emplace_hint(res.begin(), p);
  }
  return res;
}

// other -> less
template <typename T1, typename T2, typename Compare>
map<T1, T2, less<T1>> reversed(const map<T1, T2, Compare> &m) {
  map<T1, T2, less<T1>> res;
  for (const auto &p: m) {
    res.emplace(p);
  }
  return res;
}

最後に

こんな感じで書いていけば、晴れて reversed の完成です

逆順にするだけなのに、ここまでめんどくさいとは思わなかった...

それでも割と楽しかったので満足です

まだお時間に余裕のある人はおまけも見ていってください

おまけ

`is_container` を作ってみました

is_container というよりは、各コンテナの is_xxx が本命です

library/container-traits.hpp at master · matumoto1234/library · GitHub

こんなものを書くならオーバーロードするのと同じだろみたいなところはありますが...

なにはともあれ、これらを書いたことによって SFINAE で分岐できるようになりました

SFINAE というのは C++ の言語機能で Substitution Failure Is Not An Error の略称で「スフィネェ」と読みます

オーバーロードをする際にいくつも候補があるときに、エラーが起こったものをコンパイルエラーとするのではなく候補から除外するという機能です

それを使った reversed も書いてみましたが、オーバーロードのものと比べると理解しやすさと見通しの良さの点からかなり微妙な気がしてきています

library/reversed.hpp at master · matumoto1234/library · GitHub

boost は C++ の非標準ライブラリのことです↩