Discussion :

[camboui]

Bonjour en ce lundi matin
Je ne connais pas <deque>. Je ne vois pas trop ce qu'il apporte de plus que vector, les méthodes d'accès étant très semblables.
Dans quels cas utiliser deque plutôt que vector ? La FAQ ne m'aide pas à trancher.
En général vector semble plus efficace sauf s'il change souvent de taille dans de fortes proportions, auquel cas deque serait plus adapté (je comprend que vector alloue un seul block de mémoire pour tous ses éléments, alors que ces derniers sont répartis par block avec deque ?).
Merci.

[ram-0000]

Le principal avantage de deque est qu'il permet de l'insertion et la suppression aussi bien en tête que en queue.

Il est très couteux de faire une insertion ou une suppression en tête avec un vector

[Arzar]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
class deque
		: public _Deque_val<_Ty, _Ax>
	{	// circular queue of pointers to blocks

Une deque contient un tableau dynamique de pointeur vers des tableaux dynamiques de taille fixe (les blocs). Donc oui, deque est une sorte d'intermédiaire entre le vecteur, entièrement contigu, et la liste, entièrement fragmentée.

Le problème c'est qu'on ne peut pas tuner la taille des blocs. Il aurait pourtant suffit d'un bête paramètre template... Et le pire c'est que la taille par défaut est... étrange.
Sous MSVS :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
#define _DEQUESIZ	(sizeof (_Ty) <= 1 ? 16 \
	: sizeof (_Ty) <= 2 ? 8 \
	: sizeof (_Ty) <= 4 ? 4 \
	: sizeof (_Ty) <= 8 ? 2 : 1)	/* elements per block (a power of 2) */

Donc il suffit que T fasse plus de 8 malheureux octets pour que la deque se transforme... en liste.

Sous GCC :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
   *  @brief This function controls the size of memory nodes.
   *  @param  size  The size of an element.
   *  @return   The number (not byte size) of elements per node.
   *
   *  This function started off as a compiler kludge from SGI, but seems to
   *  be a useful wrapper around a repeated constant expression.  The '512' is
   *  tunable (and no other code needs to change), but no investigation has
   *  been done since inheriting the SGI code.
  */
  inline size_t
  __deque_buf_size(size_t __size)
  { return __size < 512 ? size_t(512 / __size) : size_t(1); }

On-met-512-parce-que-SGI-met-512...

[3DArchi]

Bonjour,
deque :

Therefore they provide a similar functionality as the one provided by vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence and not only at its end. On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.

Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.

Donc comme dit Arzar : un étrange croisement entre une liste et un vecteur...

[Jean-Marc.Bourguet]

Bonjour,
deque :

Donc comme dit Arzar : un étrange croisement entre une liste et un vecteur...

Ce n'est pas une croisement entre une liste et un vecteur, c'est plutot un vecteur avec un niveau d'indirection ou on perd la continuite mais on gagne sur le push_front, l'absence de reallocation, la moindre sensibilite a la fragmentation de la memoire.

C'est que j'utilise quand j'ai besoin d'un adressage direct mais pas de la continuite et que j'ai pas de raisons de faire une analyse/des mesures (en passant, sur les cas pratiques ou j'ai mesure, j'y gagnais parfois, j'y perdais parfois, ca depend des motifs d'adressage).

[camboui]

Et bien merci
Je suis parfois surpris par la richesse des réponses alors que je les aurais cru basiques
Ça change des laconiques réponses "boost et débrouille-toi avec"

Somme toute, je ne risque pas d'utiliser deque très souvent car:
-vector possède une méthode reserve (je peux souvent prédire à l'avance sa taille, ou une borne de celle-ci);
-je n'ai pas grand besoin d'un push ou pop front.

Le jour où j'aurais besoin d'une file genre fifo, je suppose que deque sera indiqué. Mais, comme le souligne arzar, c'est assez débile qu'on ne puisse pas choisir la taille des blocks sous-jacents.

Par ailleurs, stack est une sorte de cas particulier de deque (du moins sous Visual C++).
J'utilise souvent des vector à la place de stack (en considérant la fin du vector comme le sommet de la pile). Je vais continuer d'autant plus qu'avec stack on ne peut pas consulter le contenu de la pile, uniquement le sommet (enfin il me semble).

Merci encore.

[3DArchi]

Ce n'est pas une croisement entre une liste et un vecteur, c'est plutot un vecteur avec un niveau d'indirection ou on perd la continuite mais on gagne sur le push_front, l'absence de reallocation, la moindre sensibilite a la fragmentation de la memoire.

C'est que j'utilise quand j'ai besoin d'un adressage direct mais pas de la continuite et que j'ai pas de raisons de faire une analyse/des mesures (en passant, sur les cas pratiques ou j'ai mesure, j'y gagnais parfois, j'y perdais parfois, ca depend des motifs d'adressage).

Un croisiement au sens où ça ressemble à un vecteur mais ça a plutôt l'air d'être implémentée comme une liste (le tableau de tableau). Bon, certes le vocabulaire est un peu approximatif...

[Jean-Marc.Bourguet]

Un croisiement au sens où ça ressemble à un vecteur mais ça a plutôt l'air d'être implémentée comme une liste (le tableau de tableau). Bon, certes le vocabulaire est un peu approximatif...

Il n'y a pas d'acces en O(n) mais en O(1). L'insertion est en O(n) et pas en O(1). C'est bien plus proche d'un tableau que d'une liste.y