えびちゃんの日記

えびちゃん（競プロ）の日記です。

std::lower_bound の罠について

どうやら罠らしいので書きます．

ざっくりはこのリプライツリーにあるんですが，より丁寧めに書いてみようと思います． このツリーだけで理解できる人は読まなくてもいい記事かもしれません．

罠

以下のコードの最悪計算量の見積もりを正しくできますか？

std::lower_bound(s.begin(), s.end(), x);

ただし，s, x の型は以下であって，s の要素数は \(n\) とします．

std::set<int> s;
int x;

答え合わせ

\(O(\log n)\) だったらうれしいですね．\(O(n)\) かかるんですが*1．

前提知識（イテレータ）

まず，s.begin() や s.end() で返ってくるものはイテレータと呼ばれていて，データ構造中の要素を見るものです*2． ポインタを知っている人は，ポインタを抽象化したものだと思っていいです．

リンク先の図にある矢印のようなものです． en.cppreference.com

イテレータ it で行える基本操作は以下のようなものです．

  • 今見ている要素の次の要素を見るようにする（++it）
  • 今見ている要素の値を返す（*it）
  • 二つのイテレータが同じものを見ているかを調べる（it1 == it2）
  • 二つのイテレータが異なるものを見ているかを調べる（it1 != it2）

これらの操作は，（ならし）定数時間で行えます*3．

また，データ構造の種類によっては，イテレータに対してもっと便利な操作が（ならし）定数時間でできます．

bidirectional iterator（双方向イテレータ）

  • 今見ている要素の前の要素を見るようにする（--it）

random-access iterator（ランダムアクセスイテレータ）

  • 今見ている要素の n 個次の要素を見るようにする（it += n）
  • 今見ている要素の n 個前の要素を見るようにする（it -= n）
  • n 個次の要素を見るイテレータを得る（it + n）
  • n 個前の要素を見るイテレータを得る（it - n）
  • 二つのイテレータの間の距離を求める（it2 - it1）

random-access iterator でないイテレータでも，以下のようにして同等な処理を行うことができますが，距離に対して線形時間かかってしまいます．

  • it += n: std::advance(it, n)
  • it -= n: std::advance(it, -n)
  • it + n: std::next(it, n)
  • it - n: std::prev(it, n)
  • it2 - it1: std::distance(it1, it2)

もしかすると，ここも強調するべきことなのかもしれません？ std::distance を使えば高速に差が求まると思って TLE してた人を前に見た記憶があるので．

前提知識（std::set）

よく使われるコンテナのイテレータとして，std::vector::iterator は random-access iterator の，std::set::iterator は bidirectional iterator の要件を満たします*4．

std::vector の内部構造は，いわゆるふつうの配列のようなものを想像してもらえばよくて，random-access iterator の操作が簡単に実現できることはわかると思います．

それで，std::set はどういう構造になっているかわかりますか？

（今までえびちゃんは全人類が平衡二分探索木のことを知っていると錯覚していました）

まず，std::set ができる主な操作を確認しておきます．

  • 要素 \(x\) を追加する．
  • 要素 \(x\) を削除する．
  • 要素 \(x\) が入っているか確認する．
  • 入っている全要素を列挙する．

列挙は \(O(n)\)，それ以外は \(O(\log n)\) 時間です．

初心者の人は，どういう構造でこれらが実現されるか想像したことがないのかもしれないんですよね．

ふつう*5，次のリンク先にあるような木構造になっています．

onlinejudge.u-aizu.ac.jp

この木構造を見ると，random-access iterator の操作（it += n など）が難しそうであることがわかると思います．

この部分の高速化について（追記）

実際には、各ノードに部分木のサイズを持たせることで、it += n の操作を \(O(\log(n))\) 時間で行うことは可能です。 ただし、この操作により、erase などの処理に \(\Theta(\log(n))\) 時間かかることになり、erase が amortized \(O(1)\) でできる要件（値ではなくイテレータを渡した場合）と両立できなくなってしまいます。

深さが最も大きいノードを選んで消すのを繰り返すことで、毎回 \(\Theta(\log(n))\) 時間かけさせることができるので、amortized \(O(1)\) は達成できていなさそうです。

ということで、標準の set にそれを期待するのは難しそうです。

（追記おわり）

（再追記）insert にコストを押しつければ erase は amortized \(O(1)\) という指摘を受け、そうじゃん...となりました。

というわけで，std::set::iterator は random-access iterator の要件を満たしていないことに納得してもらえたことにします．

解説

さて，C++ の標準関数では，イテレータによって区間を表し，その区間に対してアルゴリズムを適用するのが基本的です．

std::sort(first, last);  // [first, last) を昇順にソート
std::reverse(first, last);  // [first, last) を逆順に並べ直す
// ... 他にもいろいろ

std::lower_bound もイテレータによって表された区間に対して適用される関数です．

std::lower_bound(first, last, x);

ところで，std::lower_bound のような関数の内部において，イテレータに対して行える操作は前述した操作たちだけです． より具体的に述べると，「今見ている次の要素に移動する」は行えても「木構造で今見ている要素の左の子に移動する」のような操作は行えません．

そのため，std::set::iterator を渡しても木構造を生かした効率的な探索はできなくなってしまいます．

比較を行う回数はたかだか \(\log_2 n+O(1)\) 回である*6ことが保証されていますが，イテレータを移動させるためにコストがかかってしまいます． 具体的には \(O(n)\) 回のイテレータ移動が発生し，これにより \(O(n)\) 時間がかかってしまいます．

よい書き方

一方で，この木構造をぐっと見つめると，lower bound を求めることは簡単にできそうなことがわかりますね． 値の比較をしながら，左右の子の適切な方に進んでいくとよさそうです．

こうした機能は std::set が提供してくれていて，以下のようにして利用できます．

// std::lower_bound(s.begin(), s.end(), x);  // これの代わりに
s.lower_bound(x);  // こう

余談

std::sort は random-access iterator を要求しているんですよね．

双方向連結リストの std::list::iterator は random-access iterator ではないので std::sort に渡すことはできないんですが，std::list::sort が提供されており，以下のように書くことができます．

std::list<int> ls = input();
// std::sort(ls.begin(), ls.end());  // error
ls.sort();  // ok

うーんと思ったので，bidirectional iterator も要求しないソートを書いてみました．

atcoder.jp

それ以外にも縛りプレイをしていて，以下の要件を要求しないように意識しているつもりです*7．

  • DefaultConstructible
  • CopyConstructible
  • CopyAssignable

これらの要件が気になった人は調べてみると C++ に少し詳しくなれそうです．

en.cppreference.com

おわり

にゃん．おつかれさまでした．

*1:ちゃんとした言い方だと \(\Theta(n)\) な気がします．

*2:ここ，結局なんて言うべきかわからなかった．

*3:一回一回の操作では最悪時に対数時間かかったりするかもしれないけど，全体でかかった時間を平均すると定数時間とみなせることを指します．

*4:「前者は random-access iterator です」と書くのは適切でない気がしたけど，contiguous iterator の説明をするのも冗長になるだけかなと思った．

*5:仕様的には，明示的に平衡二分探索木であることを規定しているわけではなさそう．

*6:\(O(\log n)\) 回よりも厳しく規定されています．

*7:抽象化するにあたり，不要な要件を課さない方が汎用的でうれしい．競プロライブラリとしてそのことが役に立つことはあまりなさそうだけど，えびちゃんがうれしければそれで十分．