STL deque un accès par index est O (1)?
https://stackoverflow.com/questions/2297164
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai lu que l'accès aux éléments de l'indice de position peut être fait en temps constant dans un STL deque. Pour autant que je sache, les éléments d'un deque peuvent être stockés dans plusieurs endroits non contigus, ce qui élimine l'accès en toute sécurité grâce à l'arithmétique des pointeurs. Par exemple:
ABC-> defghi-> jkl-> mnop
Les éléments de la file double est constitué au-dessus d'un seul caractère. L'ensemble de caractères dans un groupe indique qu'il est alloué dans la mémoire contiguë (par exemple abc est en un seul bloc de mémoire, defhi est situé dans un autre bloc de mémoire, etc.). Quelqu'un peut-il expliquer comment l'accès par index de position peut être fait en temps constant, surtout si l'élément à accéder est dans le deuxième bloc? Ou est-ce un deque ont un pointeur vers le groupe de blocs?
Mise à jour: Ou est-il une autre mise en œuvre commune pour un deque
La solution
J'ai trouvé cette implémentation deque de Wikipedia :
Le stockage contenu dans plusieurs tableaux plus petits, allouer des tableaux supplémentaires au début ou à la fin, au besoin. L'indexation est mis en oeuvre en maintenant un tableau dynamique contenant des pointeurs pour chacune des matrices plus petites.
Je suppose que cela répond à ma question.
Autres conseils
Les données sont stockées dans deque par chuncks de vecteur de taille fixe, qui sont
pointered par un map (qui est également une partie de vecteur, mais sa taille peut changer)
Le code principal d'une partie de la deque iterator est comme ci-dessous:
/*
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
}
Le code principal d'une partie de la deque est comme ci-dessous:
/*
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;
}
Ci-dessous je vais vous donner le code de base de deque, principalement sur deux parties:
-
iterator
-
Comment l'accès aléatoire une realize de
deque
1. itérateur (__deque_iterator)
Le principal problème de iterator est, quand ++, - iterator, il peut passer à un autre morceau (si ce pointeur vers le bord du morceau). Par exemple, il y a trois blocs de données: chunk 1, chunk 2, chunk 3
Les pointeurs de pointer1 au commencent de chunk 2, lorsque l'opérateur --pointer il pointeur vers la fin de chunk 1, de manière à la pointer2.
Ci-dessous je donnerai la fonction principale de __deque_iterator:
Tout d'abord, passez à tout morceau:
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + chunk_size();
}
Notez que, la fonction chunk_size() qui calcule la taille de morceau, vous pouvez penser qu'il retourne 8 pour simplifier ici.
operator* obtenir les données dans le bloc
reference operator*()const{
return *cur;
}
operator++, --
// formes de préfixe d'incrément
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);
}
2. éléments deque d'accès aléatoire
fonction commune de 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];
}
Vous voyez aussi cette question qui donne le code principal de deque
Une de l'application possible peut être un tableau dynamique de réseaux de const taille; un tel tableau de const taille peut être ajouté à l'une des extrémités lorsque plus d'espace est nécessaire. Tous les tableaux sont pleins, sauf, peut-être, pour la première et les derniers qui peuvent être en partie vide. Cela signifie connaître la taille de chaque tableau et le nombre des éléments utilisés dans le premier tableau, on peut facilement trouver une position d'un élément par index.
http: // CPP- tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html
