C++ で知ってみる動的配列

はじめに

私は業務で javascript 言語をメインで使っていて、配列を結構よく使う方だと思います。
javascript は一般的にある変数に [] をアサインする事で配列を生成出来て、その配列は基本可変長配列扱いになります。

あるロジックを組む時、配列は非常に頻繁に使われるデータ構造なので
その可変長配列の裏でどんな事が行われているか知りたくなりまして
そこについて調査した内容をこの記事で共有して行きたいと思います。

動的配列とは

動的配列は、ランダムアクセスが可能でサイズが可変のリストデータ構造であり、要素の追加や削除ができます。
色んなモダンなプログラミング言語は動的配列を標準ライブラリとして実装しています。
動的配列の特徴は、compile-time で決められた配列の容量が run-time でも固定される静的配列と違って
run-time で配列の容量が膨張されたり縮まれたりする配列で有ると言えます。

この記事で c++ 言語で具現された 動的配列 を debugging しながら run-time 行う動的配列容量の伸びを
heap メモリの変動とその動作に要るプロパティの変化をふまえて説明して行こうとします。

まずは以下のコードで int を type としてする TDArray オブジェクトを初期化します。

TDArray intArray(3);
TDArray intArray(3);

•   TDArray  ( const unsigned int Capacity )   : public

• • TDArray・親クラス TDABase を生成します。
  • TDArray クラスは動的配列を制御するに便利な utility 関数などを持ちます。
  • Capacity <- 動的配列の初期容量

TDArray の constructor で TDABase 親クラスの初期化を行います。

•   TDABase  ( const unsigned int Capacity )   : protected

• • TDABase クラスは動的配列が占めるメモリ空間の管理を担当します。
  • Capacity <- 動的配列の初期容量

TDABase は以下のメンバーを持ちます。

メンバー変数

     private:
         unsigned int mCapacity <- 動的配列の容量
         ElementType* mArr <- 動的配列を参照する pointer
     protected:
         unsigned int mSize <- 動的配列現在のサイズ
         bool mSorted <- 現在、動的配列がソートされているか

TDABase のメンバーを初期化して(2~3行目) Init を呼び出します。

•   Init  ( const unsigned int Capacity )   : private

• • heap メモリから ElementType 動的配列のメモリ空間を割り当てます。（3行目）
  • パラメータ Capacity を mCapacity にアサインします。（4行目）

これまで、以下のコード

TDArray intArray(3);
TDArray intArray(3);

によって heap メモリ空間に int type サイズ x 3 分のメモリが割り当てられ、
その空間を参照する pointer を TDABase のメンバー mArr が持ている状況になります。

Visual Studio IDE で確認すると、3行目の new ElementType[Capacity] は heap メモリへの割り当てが成功したら
その領域のアドレスを返却、ElementType* mArr にそのアドレスをアサインします。

new ElementType[Capacity] の結果 heap メモリ領域 0x00000191e6fa52d0 が割り当てられ、mArr がそのアドレスを持ちます。

続いて、以下の4行を実行します。

intArray.Push(3);
intArray.Push(6);
intArray.Push(9);
intArray.Push(12);
intArray.Push(3);
intArray.Push(6);
intArray.Push(9);
intArray.Push(12);

Push を4回呼び出します。
4つ目の iniArray.Push(12) を除いた3行の動きは以下になります。

• void   Push  ( const ElementType& Element )   : public

• • パラメータ Element を動的配列 mArr の要素にアサインします。（8行目）
  • mArr の要素が増えたので、mSize に 1 を足します。（9行目）

• intArray.Push(3) の実行
• intArray.Push(6) の実行
• intArray.Push(9) の実行

iniArray.Push(12) が実行された際の動きは Push メッソド 3行目の if 分岐にかかって、
ResizeTo メッソドを呼び出します。

• const bool   ResizeTo  ( const unsigned int NewCapacity )   : public

• • パラメータ NewCapacity 分の heap メモリ領域の再割り当てを行います。
  • 既存メモリ領域の値達を新しい領域に移動します。
  • 再割り当てが行った場合 true、さもなければ false を返します。
  • NewCapacity <- 動的配列の容量

まずは、mArr が参照するメモリ領域をそのままコピーするため mArr のアドレスを Temp にアサインします。
その後、Temp と NewCapacity をパラメーターで Move を呼び出します。

• void   Move  ( const ElementType* Temp , const unsigned int NewCapacity )   : private

• • NewCapacity 分の容量を持つメモリ空間を新しく割り当ててそのアドレスを mArr にアサインします。
  • Temp が参照するメモリ領域に有るデータ達を新しく割り当てた領域にコピーします。
  • Temp が参照するメモリ領域を解放します。

Move のロジックを debugging しながら説明致します。

• ３行目のメモリ再割り当てが行う直前 

• • mArr と Temp は同じメモリアドレス 0x000002714FC65450 を参照します。

• ３行目のメモリ再割り当てが行った直後 

• • 再割り当ての結果新しいメモリ領域 0x000002714FC63610 が割り当てられてそのアドレスを mArr が参照するようになります。

• ４行目 ~ ７行目の for の実行 

• • Temp が参照するメモリ領域が持っている値を順次的に mArr の新しい領域にコピーして移します。

• ８行目で Temp アドレスのメモリ解放 

• • 今から、古い動的配列が持っているデータ達は新しい方に移動されたので Temp を解放する事で以前の動的配列が使っていたメモリ領域を heap に返却します。

今までの流れでプログラム run-time の途中、３の容量を持っていた古い動的配列が既存容量の２倍 ６の容量を持つ伸びた新しい動的配列になりました。

まとめ

ここまで、c++ 言語で具現された 動的配列 を debug して run-time で動的配列が伸びる時
裏で行うメモリ管理を重点で動的配列が伸びる動作を説明致しました。

c++ 言語は動的配列を standard library std::vector で具現しています。
vector を使う時の practice の一つで reserve( site_type new_cap ) を上手く使う事がございます。
vector オブジェクトを生成したと共にその vector の想定の限り十分な容量(capacity)を reserve で確保して置く事を勧めています。
heap メモリ領域での割り当てはコストが高いプロセスで有って、既存の capacity を超えて要素を追加する事が多く行い
再割り当てが頻繁に行われるとその分パフォーマンスが落ちる、頻繁な再割り当ての事でメモリ破片化が起きてしまう事にもつながります。
 

すべてのデータ構造はメリットと同時にそれなりのデメリットも持っているのでケースによって適切なデータ構造を選択する心構えを
持って行く必要が有るのをもう一回振り返るきっかけになりました。