Discussion :

[sebkramm]

Bonjour,

Je suis confronté à quelque chose de surprenant avec le conteneur vector, et j'aurais besoin de l'avis d'experts es STL.

J'étais confronté à des temps d'exécution prohibitifs, et après vérification sur un cas simple (ci-dessous), j'ai pu vérifier ce que je subodorai : l'opérateur d'affectation ne copie pas la capacité du vecteur.

Exemple:

Code :

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

1
2
3
4
5
6
7
vector <int> a;
a.reserve(100);
cout << "capacity a = " << a.capacity() << endl;
 
vector <int> b;
b = a;
cout << "capacity b = " << b.capacity() << endl;

Affiche bien 100 pour a, mais 0 pour b !

Or, en toute logique, un opérateur d'affectation doit rendre identique les deux membres à gauche et à droite ! La STL serait-elle prise en défaut ? Ou est-ce l'implémentation que j'utilise qui a un problème (Mingw via DevCpp)? Ou alors quelque chose m'a échappé ?

Ca me pose un problème parce que je travaille avec des "listes de listes", implémentées sous la forme d'une classe "wrapper", qui enliste (via le conteneur "vector") des objets qui sont eux-mêmes des listes d'un objet. L'idée est d'éviter un tableau à deux dimensions, en améliorant les performances (du moins, c'est ce que je croyais naivement...)
De plus, mes listes primaires n'ont pas toutes le même nombre d'éléments.

Quand je crée ma liste de listes, j'ajoute ("push_back()") des objets de type liste, que j'ai préalablement dimensionné via "reserve()". Et quand ensuite je viens extraire ces listes pour y ajouter un élément, la capacité est de 0 au début ! Et le redimensionnement se faisant de façon automatique quand j'ajoute des élement et par puissance de deux (1,2,4,8, ...), ça me multiplie les recopie des objets enlistés, ralentissant considerablement le truc.

Pour l'instant, j'ai résolu le problème en ajoutant systématiquement lors de l'extraction d'une liste primaire un "reserve()" avec la valeur kivabien avant d'ajouter des élements, mais ça ne me plait pas trop. Je me demande si je ne vais pas laisser tomber le vector et me faire un bête tableau 2d "C-style", vu que le temps d'exécution est critique.

Sur le fond, ce comportement est-il normal ?

Merci pour vos avis.

[JolyLoic]

La copie est sensée copier le comportement observable, et la capacité est sensée dans une certain sens ne pas faire partie du comportement observable du vector. Il y a des cas d'utilisation où copier la capacité pourrait être néfaste aux perfs.

Par exemple, si on copie un tableau de (size 50 capacity 50) dans un autre de (size 0 capacity 55), vouloir une égalité de capacités demanderait une réallocation inutile. Surtout si l'utilisateur a volontairement dimensionné le second tableau car il sait qu'il va ajouter 5 élémetns à ceux du premier.

Autre cas : (10, 9999999999) copié vers (0, 0). 99% du temps, on voudra que le second ait une capacité de l'ordre de 10, pas plus. C'est même le seul moyen de réduire la capacité d'un vector actuellement (copie + swap).

C'est le problème d'une bibliothèque générique : Les choix de perfs ne peuvent pas être bons dans tous les cas d'usage possibles.

[sebkramm]

C'est le problème d'une bibliothèque générique : Les choix de perfs ne peuvent pas être bons dans tous les cas d'usage possibles.

Effectivement, je n'avais pas vu les choses sous cet angle, je comprends mieux. Merci pour la réponse qui clarifie les choses.

Et effectivement, en lisant de façon attentive la page:
http://www.cppreference.com/cppvecto...operators.html
on y lit:

Two vectors are equal if:
1. Their size is the same, and
2. Each member in location i in one vector is equal to the the member in location i in the other vector.

Ce qui montre bien que l'égalité de capacité n'est pas prise en compte dans la notion d'égalité. Donc l'opérateur d'affectation est correct avec cette définition là

En fait, j'ai trouvé un workaround simple : vu que mes listes primaires sont encapsulées dans une classe, dotée d'un opérateur d'affectation, j'ajoute le reserve dans celui-ci :

La classe (template):

Code :

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

1
2
3
4
5
6
7
8
template <class MMMM> class LIST_STL
{			
    protected:
        vector<MMMM> v;
    public :
        ...
 
}

et l'opérateur devient:

Code :

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

1
2
3
4
5
6
7
LIST_STL &operator = (const LIST_STL& src)
{
    v.clear();
    v = src.v;
    v.reserve( src.v.capacity() );
    return *this;
}

[sebkramm]

Oup, j'oubliais : merci pour ta réponse !

[yan]

Bonjour,
Attention dans ton operateur = doit etre dans cette ordre:

Code :

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

1
2
3
4
5
6
7
LIST_STL &operator = (const LIST_STL& src)
{
    v.clear();
    v.reserve( src.v.capacity() );//réserve la mémoire
    v = src.v;//copie les elements
    return *this;
}

Car dans ton code,tu te retrouve avec une alocation(si nécessaire) lors du égale et une autre avec recopie avec le reserve.

[sebkramm]

Tout à fait exact ! J'ai tapé un peu vite...
Merci.