何年も前にstd::mapに格納されているkey群を指定量だけ一気にずらしたいと思い、slidable_mapとでも呼べるデータ構造を考えました。つまり格納されているkeyが1,5,8だとしてそれぞれを+2だけずらし3,7,10としたいわけです。愚直に個々のkeyを修正すればコストはO(N)掛かります。しかしこの場合は全要素をずらしているのでmapとは別にスライド値を格納する変数を用意し併せて使うことでO(1)に出来ます。
しかしこの方法はmapの指定位置からのkeyだけをずらしたい場合には使えません。そこでslidable_mapの出番です。slidable_mapは赤黒木をベースにしてkeyの値を親のノードのkeyからの相対値で保持します。これにより全ノードのkeyを修正せずとも好きな範囲のkeyをO(logN)でずらすことが可能になります。方法は木の上からずらしたい位置に線を引きそれを挟んでジグザグにkeyを修正していきます。
mapのkeyは0,1,3,5,7,8,10の様に見えますが実際には親ノードとの相対値として格納しています。
8以降のkeyを+3ずらし0,1,3,5,7,11,13にする場合、8のkeyを+3ずらし+6とします。この親ノードの修正により7のkeyが+3の影響を受けるため-3ずらし-4とします。
デメリット
iteratorからkey本来の値を得るには木の一番上までたどる必要がありO(logN)のコストが掛かる。そのためstd::pairをインターフェイスに使うのは無理がある。
とっくの昔に誰か考えていそうではあります。
実装する際にはまず普通の赤黒木を作ってからのほうがいいかもしれません。一気に作ってデバッグでかなり苦労したので。
