42Tokyo の課題でSTLコンテナの1つ、mapを再実装しました。
この記事では、mapの再実装で学んだことを書きます。
課題の概要、コンテナ・イテレータ・アルゴリズムの基礎的知識について説明した後、mapの実装について説明します。
課題の概要
- 規格
- C++98。後の規格で非推奨になっても実装が必要。
- 実装する内容
- リファレンス
- 実装にあたり、cplusplus.com と cppreference.com を参照することができます。
基礎知識
C++では以下の機能を使ってデータの扱いを共通化しています。
コンテナ
コンテナは動的配列、連結リスト、辞書などのデータ構造を使ってオブジェクトを保持します。
コンテナには次の分類があります。
- シーケンスコンテナ
- 配列のような直線的なデータ構造。例：list、vector
- 連想コンテナ
- キーに基づいて探索可能なデータ構造。例：map、set
- コンテナアダプタ
- 他のコンテナを元にインターフェースを提供。例：stack
今回実装するのは連想コンテナの1つ、mapです。
mapはkeyとvalueのpairを持ち、keyからvalueを取り出すことができます。
イテレータ
コンテナの各要素には添字演算子やイテレータを使ってアクセスします。
イテレータがあることで、コンテナを使う側はコンテナの内部実装を知ることなくコンテナの各要素を操作できます。
操作方法
- ポインタのように
*iteratorと、*をつけるとその要素を参照できます。 ++iteratorとすると、現在の要素から次の要素に進みます。- 後述するカテゴリによって、使える操作は異なります。
イテレータには5つのカテゴリがあり、それぞれで使える演算子が異なります。
mapは双方向イテレータが提供されます。
双方向イテレータは以下の操作を行えます。
| 操作 | 式 |
|---|---|
| 次の要素に進む | ++iter, iter++ |
| 前の要素に戻る | --iter, iter-- |
| 要素の読み込み、（非constなら）書き込み | *iter |
| クラスメンバの参照 | iter->m |
| イテレータの比較 | iter==iter, iter!=iter |
アルゴリズム
アルゴリズムはイテレータを介してコンテナを操作できる関数を提供します。
例えば、以下の関数があります。
やったこと
データ構造
データ構造は課題で特に指定がありません。
今回はClang、GCCと同じく赤黒木にしました。
実装の詳細はスライドにまとめましたので、こちらを参照ください。
『アルゴリズムイントロダクション』を参考に実装しています。
赤黒木は左と右を間違えると簡単にバグります。
bashの再実装の課題 の時と同じくdotファイルを生成して、ノードの色と位置関係を確認するようにしました。
mapを実装するには単に赤黒木を実装するだけでなく、イテレータにも対応する必要があります。
イテレータ
実装方法
イテレータは iterator を継承して実装しました（iteratorはC++17から非推奨）。
リファレンスを見ても、イテレータは実装依存なため詳しく書かれていません。このため、reverse_iterator を参考に実装しました。
インクリメントとデクリメント
++ で次の要素、-- で前の要素に進みます。
mapは要素を順序づけており、先頭の要素はキーが最小、末尾の要素はキーが最大になります。
次の要素は今よりもキーが大きい要素、前の要素は今よりもキーが小さい要素です。
次の要素の探索（ ++ ）は、今の要素に右の子があるかどうかで処理が異なります。
右の子がある場合：右の子から最小（左端）の要素が次の要素です。
右の子がない場合：今の要素が親の右の子である限り、親をたどります。たどった要素の親が次の要素です。
-- は、 ++ の左右を逆にした処理です。
beginとend
mapは begin()、end()で先頭の要素、末尾 + 1の要素を参照するイテレータを返します。
begin() と end() の計算量は定数時間である必要があります。このため木がbeginとendに相当するノードを覚えておく必要があります。
ClangとGCCで実現方法が異なります。
Clang
Clangでは、endはダミーノードで、ダミーノードの左の子がrootになります。
end-11 からイテレータを ++ すると、右の子がないので、親をたどってendに到達します。
GCC
GCCでは、headerというダミーノードを持ち、親がroot、左の子がbegin、右の子がend-1を指します。headerがendに相当します。
Clangのように、rootの親をendにすることで、end-1から ++ するとendにたどり着きます。
面白いのはendの親はrootであることです。
これにより、ClangとGCCでは end() を ++ した時の挙動が異なります。
Clangでは、endの親はNULLなのでSegmentation Faultになります。
GCCでは、endから右の子end-1へ行き、そこから最小（左端）の要素になります。
ハマったこと
allocator::rebind
mapのテンプレート引数で指定できるallocatorは pair<const Key, T> を確保するために使われます。
木のノードではありません。木のノードを確保するためには、allocator::rebind を使って異なる型を確保するクラスを取り出す必要があります。
実装するために以下のことをしました。
赤黒木のクラスに、
allocator<pair>からallocator<赤黒木のノード>にallocatorをrebindする型を宣言する
以下のように定義しました。typedef typename Allocator::template rebind<rb_node<T> >::other node_allocator_type;rb_nodeは赤黒木のノードのクラスです。typedef、typename、templateについて説明します。赤黒木のコンストラクタで
allocator<pair>を受け取ってallocator<赤黒木のノード>にrebindした型のオブジェクトをメンバ変数にセットする。
insert with hint
insert with hintは map::insert のオーバーロードです。
cplusplus.com によると以下のように定義されています。
iterator insert (iterator position, const value_type& val);
C++98とC++11以降の動作
insert with hintはC++98とC++11以降で動作が異なります。
C++98では、positionが挿入する要素の前の場合、挿入時間が最適化されます。
C++11以降では、挿入要素に続く要素をpositionが指している場合、挿入時間が最適化されます。
何故そのような変更がされたかは以下のページが分かりやすいです。
C++98の実装だと、multimapのような重複要素を許すコンテナの場合、先頭要素の前に要素を挿入できない問題があったそうです。
実装方法
GCCのソース を参考に実装しました。
valとposition及びposition前後の要素の大小関係を比較し、挿入できるなら挿入します。挿入できない場合、通常のinsertになります。
おそらくこれはC++11な実装なのかなと思います。
C++98な実装が見つけられたら良かったのですが、今回見つけられませんでした。
keyとvalueの比較
lower_boundなどkeyからiteratorを取り出す際、keyとvalue（pair）の比較が必要になります。
ClangとGCCで対処方法が異なります。
Clangは、keyとvalueを比較できる関数オブジェクト（
__map_value_compare）を使って比較。GCCは、pairからkeyを取り出す関数オブジェクト（
_Select1st）を使い、pairからkeyを取り出してkey_compare。
GCCの実装だとset等、別のコンテナを実装するときに新たな関数オブジェクトを実装する必要があるため、Clangを参考にした実装をすることにしました。
参考URL・書籍
赤黒木
GCCの赤黒木の実装について
allocator::rebind
