Optimized C++ ―最適化、高速化のためのプログラミングテクニック

112

6 章　動的変数割り当てを最適化する

このような性質、子と親の節点の添字を計算できて、左平衡木の表現が効率的だということは、

配列による木をヒープデータ構造の効率的な実装にする。

配列による木の表現は、平衡二分木として使うには、リンク付き表現より効率が劣ることがあ

る。

n

節点の平衡二分木には、平衡を取るアルゴリズムにもよるが、

2n

個の位置を配列に取る必

要がある。さらに、平衡を取る操作において、単にポインタを更新するのではなく、異なる配列位

置に節点をコピーする操作が必要だ。小さなプロセッサで節点サイズが大きい場合、コピー演算は

あまりにも高価になることがある。節点サイズが

3

ポインタより小さければ、配列による木の表

現の方が効率で優るだろう。

6.3.2.5

　両端キューの代わりにリングバッファを使う

std::deque

と

std::list

は、

FIFO

（先入先出）バッファとしてよく使われ、標準ライブラリに

は

std::queue

と呼ばれるコンテナアダプタがある。

両端キューは、英語では

deque

（

Double Ended Queue

）と呼ばれ、リングバッファでも実装さ

れる。リングバッファは、配列データ構造でキューの先頭と末尾は配列の添字で求められる。それ

ぞれの添字は、要素番号を配列長を法とするモジュロ演算で求める。リングバッファは、定数時間

の

push_back()

および

pop_front()

、ランダムアクセスイテレータを含めて、両端キューと同様の

性質を持つが、リングバッファでは、消費者が生産者に追随している限り、再割り当ての必要がな ...