C++98でvectorを再実装する

42 C++

42Tokyo の課題でSTLコンテナの1つ、vectorを再実装しました。

この記事では、vectorの再実装で学んだことを書きます。

課題の概要と基礎知識について説明した後、vectorの実装で調査した内容、実装でハマったことについて説明します。

課題の概要

  • 規格
    • C++98。後の規格で非推奨になっても実装が必要。
  • 実装する内容
    • STLコンテナ：vector、map、stack（+ set）
      • カッコ内のコンテナを実装するとクリア時にボーナスが付きます。
      • イテレータも実装が必要になります。
      • vector<bool> を実装する必要はありません。
    • STLコンテナ以外：iterators_traits、reverse_iterator、equal、pairなど
      • この記事ではSTLコンテナ以外の詳細な実装は取り上げません。
  • 実行速度の制限
    • 実装元のSTLコンテナの20倍まで許容されます。
  • リファレンス

基礎知識

基礎知識の項目では、コンテナ、イテレータ、アルゴリズムについて説明します。

mapの記事 で説明したのとほぼ同じ内容です。すでにご存じの方は読み飛ばして問題ありません。

コンテナとイテレータとアルゴリズム

C++では以下の機能を使ってデータの扱いを共通化しています。

コンテナ、イテレータ、アルゴリズムの関係を図にすると、以下のようになります。

f:id:nafuka11:20211114225401p:plain:w540

コンテナ

コンテナは動的配列、連結リスト、辞書などのデータ構造を使ってオブジェクトを保持します。

コンテナには次の分類があります。

  • シーケンスコンテナ
    • 配列のような直線的なデータ構造。例：vector、list
  • 連想コンテナ
    • キーに基づいて探索可能なデータ構造。例：map、set
  • コンテナアダプタ
    • 他のコンテナを元にインターフェースを提供。例：stack

今回実装するのはシーケンスコンテナのvectorです。

イテレータ

コンテナの各要素には添字演算子やイテレータを使ってアクセスします。

イテレータがあることで、コンテナを使う側はコンテナの内部実装を知ることなくコンテナの各要素を操作できます。

操作方法

  • ポインタのように *iterator と * をつけるとその要素を参照できます。
  • ++iterator とすると、現在の要素から次の要素に進みます。
  • 後述するカテゴリによって、使える操作は異なります。

イテレータには5つのカテゴリがあり、それぞれで使える演算子が異なります。

vectorはランダムアクセスイテレータが提供されます。

ランダムアクセスイテレータは以下の操作を行えます。

操作 式
次の要素に進む ++iter, iter++
前の要素に戻る --iter, iter--
n個後/前の要素に進む/戻る iter+n, n+iter, iter-n, n-iter, iter+=n, iter-=n
イテレータの距離を返す iter-iter
n番目の要素にアクセスする iter[n]
要素の読み込み、書き込み（非constなら） *iter
クラスメンバの参照 iter->m
イテレータの比較 iter==iter, iter!=iter, iter<iter, iter>iter, iter<=iter, iter>=iter

アルゴリズム

アルゴリズムはイテレータを介してコンテナを操作できる関数を提供します。

例えば、以下の関数があります。

実装の流れ

まず、江添亮の入門C++ の「vectorの実装」を読んで実装の大まかな流れを掴みました。

江添亮の入門C++では、イテレータがポインタになっているため、イテレータの実装について調査しました。イテレータの実装は、reverse_iterator の実装が参考になりました。

各関数については、リファレンスと Clang、GCCのソースを参考に実装しました。

実装した内容

データ構造

vectorは固定長の配列にデータを追加・削除していきます。

データの数が配列の長さを超える場合、配列を再確保します。 再確保する長さは、現在の配列の長さ * 2 になります。

f:id:nafuka11:20211114223818p:plain:h200

メンバ変数

f:id:nafuka11:20211114224043p:plain:h240

3つのポインタとAllocatorを持ちます。

3つのポインタは、以下の要素へのポインタです。

  1. 配列の先頭要素（first）
  2. データの末尾 + 1の要素（last）
  3. 確保した領域 + 1の要素（capacity_last）

ポインタにすることで、引き算によって、データの要素数と領域を確保してる要素数を求められます。

Allocator（alloc）はメモリの確保/解放、オブジェクトの構築/破棄を行うためのクラスです。ユーザが独自に実装できるよう、クラスになっています。

関数の実装

リファレンス、ソースを参考に関数を実装していきます。

関数の実装にあたりハマった点について書きます。

コンストラクタの引数

C++98において vectorのコンストラクタの定義 は以下です。

// default
explicit vector (const allocator_type& alloc = allocator_type());
// fill
explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());
// range
template <class InputIterator>
         vector (InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type());
// copy
vector (const vector& x);

このまま実装すると、fillコンストラクタとrangeコンストラクタの引数が区別が付きません。

（テンプレート引数InputIteratorはイテレータでなくても良いため）

このため、課題で実装を指定されている enable_if と is_integral を使い、引数が整数型でないときだけ、rangeコンストラクタがオーバーロードの候補に入るようにしました。

  • Clang では enable_if を使っています。
    GCC では __is_integer という is_integral 相当の構造体を使って処理を切り替えています。

vector::insertでのconstruct or コピー

vector::insert でconstructするかコピーするかがありました。

配列の再確保が必要な場合、各要素をconstructします。 再確保が不要な場合、すでにconstructした要素はコピーし、constructしていない要素のみconstructします。

  • 42Tokyoの学生 dai65527 さんのテストを試しに実行してみて、このことに気づきました。

    github.com

要素追加/削除による実行速度

Clangではコンパイルフラグに -std=c++98 と指定しても、insert/eraseによる要素の移動に std::move を使用するようです。

今回の再実装では、規格がC++98と指定されておりstd::moveを使えません。要素の移動が多く発生すると実装元との速度差が20倍を超えてしまいます。

これはどうしようもない……と思うので、速度差が出ないようなテストを書きました。
具体的には、begin() ではなく end()/end()-1 にinsert/eraseするようにしました。

終わりに

vectorを実装して、コンテナとデータ構造の理解が深まりました。

C++98でvectorを実装することは課題以外にあまり無いと思うのですが、この記事が参考になれば幸いです。