C++(GNU)のdequeの実装はリンクドリストではなくチャンクへのマップあり[]アクセスが$O(1)$です。これを実装(ソースコード)から見ていきましょう。
はじめに
Python3のdequeの実装を調べる関連です。Pythonのdeque[i]参照が$O(N)$ですがC++は$O(1)$らしいです。本当でしょうか？libstdc++のdequeを読めば分かりそうです。調べてみましょう。
結論： C++のdeque実装はリンクドリストを用いていない(Pythonと異なる)。要素を配列として持つチャンクをマップと呼ばれる配列でポインタで管理する。このためチャンクへのアクセスとチャンク内の要素へのアクセスが高速に行えるので[]アクセスが$O(1)$である。ただし単一要素のpushの際に$O(N)$がかかることが時折ある。
この記事の内容は以下でも触れられているので参考にしてください。
概要
- 教科書的なdequeは各要素をダブルリンクドリストでつなげる。[i]へのアクセス$O(n)$かかる。
- PythonはPython3のdequeの実装を調べるで述べたように要素を
ブロックとしてまとめてダブルリンクドリストでつなげる。[i]へのアクセスはi/ブロックサイズかかるので$O(n)$のままである - C++のdequeはリンクドリストを一切使っていない。dequeは要素をまとめた複数の
チャンク(Python Dequeでいうブロック)へのポインタの配列マップを持つ。マップは配列であるためiブロック目の[j]個目のデータはmap[i]の[j]のようにアクセスできてこれはO(1)でアクセス可能。- この手法は要素の追加により時々マップのrealloc(実装上はreallocate_map)が必要になる。つまり、push_front()などがO(N)かかることがある。常ではない。size = map.size() * chunk_size以上のデータを入れるときには"mapを"reallocし現在のmap.size()のポインタアドレスをcopy()する必要がある。
イメージは以下の通りです。
- この手法は要素の追加により時々マップのrealloc(実装上はreallocate_map)が必要になる。つまり、push_front()などがO(N)かかることがある。常ではない。size = map.size() * chunk_size以上のデータを入れるときには"mapを"reallocし現在のmap.size()のポインタアドレスをcopy()する必要がある。
Pythonでは[13]が4ブロック目の1個目の要素であることが分かるので4回ブロックを辿ってアクセスします。
C++では$13/4 = 4$より4ブロック目であるmap[3]のブロックに即座にアクセスしそのブロックの[0]を辿るので高速にアクセスできます。
ソースコードを読む(へのリンク)
記事を分けました。
dequeの構造体
dequeを読む上ではそのdeque自身の構造体Deque_baseと、要素にアクセスされる際のイテレータである_Deque_iteratorがあることに注意します。
deque自身はチャンクに関するマップの情報と最初と最後（の次)の要素のポインタだけを持ちます。
イテレータは各要素を指します。イテレータは自分がマップのどの位置を指しているかのnodeを持ちます。
※ここではサイズを指定したdequeなどは考慮しません
class _Deque_base
{
// deque<T>自身の構造体
struct _Deque_impl_data
{
_Map_pointer map;// マップのポインタ。map[i]によりi個目のチャンクにアクセスする
size_t map_size; // 現在のマップ（チャンク数）のサイズ
iterator start; // 最初の要素のイテレータ
iterator finish; // 最後の要素の次のイテレータ
};
}
struct _Deque_iterator{
_Elt_pointer cur; // このチャンク内のどの位置にいるのかというindex
_Elt_pointer first;// このチャンクの最初の位置
_Elt_pointer last; // このチャンクの最後の位置
_Map_pointer node; // このイテレータが指す要素がどのチャンクにいるのか？
set_node(_Map_pointer new_node)
{
node = new_node;
first = *new_node;
last = first + (buffer_size());
}
}
dequeの初期化
dequeは要素数を指定せずに確保すると各チャンクの要素のサイズを512として8個のチャンクへのマップを用意します。つまり4096個の要素分を予約します。
ただし、startは真ん中のポインタから始まります。つまり、前に2048個, 後ろに2048個の要素がpushできる領域です。front, backのどちら側にpushが生じるかわからないためです。以降、reallocが生じる際にもstartは真ん中から始まります。
// dequeの生成時のマップの生成で呼ばれます
_Deque_base<_Tp, _Alloc>::initialize_map(size_t num_elements)
{
// deque(n)で呼ばれたのに必要なチャンクのサイズを確保しようとします。指定されていない場合は(0)であるのでmaxによりinitial_map_sizeになります
const size_t num_nodes = (num_elements / deque_buf_size(sizeof(_Tp)) + 1);
this->impl.map_size = std::max((size_t) initial_map_size, size_t(num_nodes + 2));
this->impl.map = allocate_map(this->impl.map_size);
// startは最初のノードではなく、真ん中(center)のノードを指します。これはfrontにもbackにもデータが追加されるためです
_Map_pointer nstart = (this->impl.map + (this->impl.map_size - num_nodes) / 2);
_Map_pointer nfinish = nstart + num_nodes;
create_nodes(nstart, nfinish);
this->impl.start.set_node(nstart);
this->impl.finish.set_node(nfinish - 1);
this->impl.start.cur = impl.start.first;
// finishはnが決まっている場合には最後のチャンクの確保した最後のポインタを指すわけではなく、最後の要素を示します。
this->impl.finish.cur = (this->impl.finish.first + num_elements % deque_buf_size(sizeof(_Tp)));
}
// マップのそれぞれの領域を確保します
_Deque_base<_Tp, _Alloc>::create_nodes(_Map_pointer nstart, _Map_pointer nfinish)
{
_Map_pointer cur;
for (cur = nstart; cur < nfinish; ++cur)
*cur = this->allocate_node();
}
}
...
// 以下はコードからの抜粋
#define _GLIBCXX_DEQUE_BUF_SIZE 512
enum { initial_map_size = 8 };
// initialize_map(size_t num_elements)なども参照のこと
deque.push_front(): 追加の例
要素を追加する際の処理を見てみましょう。push_frontは同一のチャンク内で伸ばせるかを判定し、同一チャンクないならばcurを++します。チャンク範囲外に出る場合はpush_front_auxを呼び新しいチャンクに移ります。push_front_auxではこのチャンクが用意していあるものの範囲外(=マップの拡張が必要である)場合にはマップのサイズを(pop_frontのケースでは)2倍にします。
push_front(const value_type& x)
{
// startの含まれるチャンクの頭がindex0より大きければそのチャンクに値を代入する
if (this->impl.start.cur != this->impl.start.first)
{
_Alloc_traits::construct(this->impl,this->impl.start.cur - 1,x);
--this->impl.start.cur;
}
// そうでない場合、startのチャンクを新しく確保しなければならない。
else push_front_aux(x);
}
// この関数はpush_front()時にdequeのfrontが含まれるチャンクの頭に"あまり"が残っていない時に呼ばれる
// つまり、より前の空間を確保してその最後にポインタを移動する必要がある
// Called only if impl.start.cur == impl.start.first.
void deque<_Tp, _Alloc>::push_front_aux(const value_type& t)
{
if (size() == max_size())
throw_length_error(...);
reserve_map_at_front();
// "マップ"の１つ前は使われていないので、イテレータとして初期化する
*(this->impl.start.node - 1) = this->allocate_node();
// deque自身のstartを指すノードを新しく確保したノードに変更する
this->impl.start.set_node(this->impl.start.node - 1);
// またdequeが書き込もうとするポインタを移動して値を入れる
this->impl.start.cur = this->impl.start.last - 1;
this->impl.construct(this->impl.start.cur, t);
}
deque[i]のアクセス
deque[i]とはdeque自身(_Deque_base)のstart(最初の要素のイテレータ)に対する[i]のアクセスです。
class deque : protected _Deque_base<_Tp, _Alloc>{
operator[](size_type n) const _GLIBCXX_NOEXCEPT
{
glibcxx_requires_subscript(n);
return this->impl.start[(n)];
}
}
イテレータ(_Deque_iterator)に対する[i]のアクセスがはthis(この場合start)に対する+演算であり、+=演算だと分かります。
struct _Deque_iterator{
// [i] は this + n
operator[]( n)
{ return *(*this + n); }
// this `+n`がどうなっているかというと、thisをコピーして `+= n`
operator+(const _Self& x, n)
{
_Self tmp = x;
tmp += n;
return tmp;
}
// では"+="どう実装されているか？
// thisはset_nodeでチャンク[i]を指定して、
// cur = そのチャンク内での位置であることに注意して読む
operator+=( n)
{
// offsetはそのチャンク内の位置 + n
const offset = n + (cur - first);
// これがチャンクの範囲内であれば、単にそのチャンク内の位置curにnを足せば良い
if (offset >= 0 && offset < (buffer_size()))
cur += n;
// そうでない場合はノードの移動が必要になる
else
{
// 何ノード進みたい（戻りたい）か？ 三項演算子は+ or -を判定する
node_offset = offset > 0 ? offset / (buffer_size()) : -((-offset - 1) / buffer_size()) - 1;
// 実際にノードを移動してそのノード内の位置を更新する
set_node(node + node_offset);
cur = first + (offset - node_offset * (buffer_size()));
}
return *this;
}
}
[i]へのアクセスはチャンク内の移動で済む場合はその分だけcurを動かします。チャンク外になる場合は何個のチャンクを移動するかnode_offsetを/で高速に求め、set_nodeで移動します。確保していあるチャンクへのポインタは配列であるため高速にアクセスできます。
(補足)dequeのmapのreallocate_map: マップの拡張など
マップがreallocされる場合の処理を見ます。reallocは必要な要素数$n$を指定して呼ばれます。1要素ごとの追加でマップが不足した際はマップを2倍にするように動作します。明示的に必要な要素数が指定された場合はその要素数分が格納できる最小の量を確保します。
// nodes_to_add個のchunkを足せるようなマップに再構成する
deque<_Tp, _Alloc>::reallocate_map(size_type nodes_to_add, bool add_at_front)
{
// 現在のマップのサイズを取得(e - s + 1)
const size_type old_num_nodes
= this->impl.finish.node - this->impl.start.node + 1;
// 新しいマップのサイズは += nodes_to_addにしたい
const size_type new_num_nodes = old_num_nodes + nodes_to_add;
_Map_pointer new_nstart;
// すでにdequeが"確保済み"のマップが、"新しく要求"されているサイズの2倍よりも大きい場合
// 注意： "e - s + 1" はあくまで"使用中"のマップの個数である。
// dequeが実際に確保しているマップのサイズは異なることに注意
if (this->impl.map_size > 2 * new_num_nodes)
{
// この場合はすでにallocateは行われているので、allocateしているが未使用の領域の使用を開始すればいい
// 先頭への追加かどうかで開始の"n"の位置を変える
new_nstart = this->impl.map + (this->impl.map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
// copy_backwardは後ろからメモリをコピーする。イテレータ.last()を含みうる場合は_backwardする
if (new_nstart < this->impl.start.node)
std::copy(this->impl.start.node,
this->impl.finish.node + 1,
new_nstart);
else
std::copy_backward(this->impl.start.node,
this->impl.finish.node + 1,
new_nstart + old_num_nodes);
}
else
{
// 新しくマップ向けのメモリを確保する必要がある。マップのメモリの増やし方は"2倍以上"である。
// もし要求されているノード数が最初から2倍以上なのであればその数だけ増やす。
// つまり、 1 -> 2 -> 4 -> 8と増えるわけでなく、4の時に+3が要求されたら7だけ増やす
size_type new_map_size = this->impl.map_size
+ std::max(this->impl.map_size,
nodes_to_add) + 2;
// new_mapにメモリを確保する
_Map_pointer new_map = this->allocate_map(new_map_size);
// 新しく確保したマップは真ん中から使い始める
new_nstart = new_map + (new_map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
std::copy(this->impl.start.node,
this->impl.finish.node + 1,
new_nstart);
deallocate_map(this->impl.map, this->impl.map_size);
// dequeの指すマップはポインタなので新しいマップのアドレスに差し替える
this->impl.map = new_map;
this->impl.map_size = new_map_size;
} /* else */
// deque自身のstart, endの指すノードを指定
this->impl.start.set_node(new_nstart);
this->impl.finish.set_node(new_nstart + old_num_nodes - 1);
}
まとめ
C++のdeque実装は要素を配列として持つチャンクのリンクドリストではなくマップと呼ばれる配列でポインタが管理されている。このためチャンクへのアクセスとチャンク内の要素へのアクセスが高速に行えるので[]アクセスが$O(1)$である。ただしpushの際にO(N)がかかることが時折ある。