位置インデックスによる要素へのアクセスは、STL両端キューで一定時間で実行できることを読みました。私の知る限り、deque 内の要素はいくつかの連続しない場所に格納される可能性があり、ポインター演算による安全なアクセスが排除されます。例えば：
abc->defghi->jkl->mnop
上記の両端キューの要素は、単一の文字で構成されています。1 つのグループの文字セットは、連続したメモリに割り当てられていることを示します (たとえば、abc はメモリの単一ブロックにあり、defhi は別のメモリ ブロックにあるなど)。特にアクセスする要素が2番目のブロックにある場合、位置インデックスによるアクセスを一定時間で行う方法を誰かが説明できますか? または、両端キューにブロックのグループへのポインタがありますか?
更新:または、両端キューの他の一般的な実装はありますか?
ウィキペディアからこの両端キューの実装を見つけました:
コンテンツを複数の小さな配列に格納し、必要に応じて先頭または末尾に追加の配列を割り当てます。小さい配列のそれぞれへのポインターを含む動的配列を保持することによって、インデックス付けが実装されます。
私はそれが私の質問に答えると思います。
のdequeデータは、固定サイズのベクトルのチャンクによって格納されます。
map(これもベクトルのチャンクですが、そのサイズは変わる可能性があります)
の主要部分のコードは次のdeque iteratorとおりです。
/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
typedef __deque_iterator<T, buff_size> iterator;
typedef T** map_pointer;
// pointer to the chunk
T* cur;
T* first; // the begin of the chunk
T* last; // the end of the chunk
//because the pointer may skip to other chunk
//so this pointer to the map
map_pointer node; // pointer to the map
}
の主要部分のコードは次のdequeとおりです。
/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
public:
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef __deque_iterator<T, buff_size> iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
typedef pointer* map_pointer;
// allocate memory for the chunk
typedef allocator<value_type> dataAllocator;
// allocate memory for map
typedef allocator<pointer> mapAllocator;
private:
//data members
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
}
deque以下に、主に 2 つの部分についてのコア コードを示します。
イテレータ
deque実現するランダム アクセスの方法
__deque_iterator)イテレータの主な問題は、++、 -- イテレータの場合、他のチャンクにスキップする可能性があることです (チャンクの端を指す場合)。たとえば、 、 、 の 3 つのデータ チャンクがchunk 1ありchunk 2ますchunk 3。
のpointer1開始点へのポインターchunk 2、演算子の--pointer場合は の終了点へのポインター、のchunk 1ようにpointer2.
以下に、の主な機能を示し__deque_iteratorます。
まず、任意のチャンクにスキップします。
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + chunk_size();
}
chunk_size()チャンクサイズを計算する関数は、ここでは単純化のために 8 を返すと考えることができることに注意してください。
operator*チャンク内のデータを取得する
reference operator*()const{
return *cur;
}
operator++, --
// インクリメントのプレフィックス形式
self& operator++(){
++cur;
if (cur == last){ //if it reach the end of the chunk
set_node(node + 1);//skip to the next chunk
cur = first;
}
return *this;
}
// postfix forms of increment
self operator++(int){
self tmp = *this;
++*this;//invoke prefix ++
return tmp;
}
self& operator--(){
if(cur == first){ // if it pointer to the begin of the chunk
set_node(node - 1);//skip to the prev chunk
cur = last;
}
--cur;
return *this;
}
self operator--(int){
self tmp = *this;
--*this;
return tmp;
}
self& operator+=(difference_type n){ // n can be postive or negative
difference_type offset = n + (cur - first);
if(offset >=0 && offset < difference_type(buffer_size())){
// in the same chunk
cur += n;
}else{//not in the same chunk
difference_type node_offset;
if (offset > 0){
node_offset = offset / difference_type(chunk_size());
}else{
node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
}
// skip to the new chunk
set_node(node + node_offset);
// set new cur
cur = first + (offset - node_offset * chunk_size());
}
return *this;
}
// skip n steps
self operator+(difference_type n)const{
self tmp = *this;
return tmp+= n; //reuse operator +=
}
self& operator-=(difference_type n){
return *this += -n; //reuse operator +=
}
self operator-(difference_type n)const{
self tmp = *this;
return tmp -= n; //reuse operator +=
}
// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
return *(*this + n);
}
deque要素の共通機能deque
iterator begin(){return start;}
iterator end(){return finish;}
reference front(){
//invoke __deque_iterator operator*
// return start's member *cur
return *start;
}
reference back(){
// cna't use *finish
iterator tmp = finish;
--tmp;
return *tmp; //return finish's *cur
}
reference operator[](size_type n){
//random access, use __deque_iterator operator[]
return start[n];
}
のメインコードを提供するこの質問も表示されますdeque
dequeが、サイズが大きくなるとそれ自体を再割り当てするリングバッファとして実装されている場合、インデックスによるアクセスは確かにO（1）です。std::vector
この標準は、そのような実装が意図されていたという証拠を提供します。少なくとも、複雑さの見積もりの標準に準拠しています。23.2.1.3 /4項および23.2.1.3/5項では、
dequeの最初または最後に挿入するには一定の時間が必要ですが、中央に挿入するにはdequeのサイズの線形時間が必要です
両端キューから要素を消去する場合、消去される要素から両端キューの終わりまでの距離と同じ数の代入演算子を呼び出すことがあります。
そしてもちろん、コンテナーとアルゴリズムの実装方法に関する独自のビジョンではなく、標準要件を信頼する必要があります。
この規格では、上記の2つのポイント以上が必要であることに注意してください。また、要素への参照は、両端キューの前後に挿入する間も有効である必要があります。これは、リングバッファに要素自体ではなく、実際の要素へのポインタが含まれている場合に満たすことができます。とにかく、私の答えは、複数の実装が特定の要件を満たす可能性があるという考えを示しています。