Redimensionnement de std::vector

Bonjour,

AVant de programmer ma propre solution, j’aimerais savoir s’il existe un moyen pour que je sois prévenu quand un std::vector se redimensionne. En d’autres termes quand, pour un std::vector v, &v[0] change d’adresse. Et évidemment, si possible, sans être obligé de comparer les adresses à chaque push_back.

Evidemment je peux bien utiliser .reserve pour réserver de l’espace à l’avance, mais je ne peux jamais vraiment être sûr à 100% que la capacité que j’aurai réservée ne sera jamais dépassée.

Je compile en C++14.

Merci pour vous réponses.

Tu peux vérifier, avant d’effectuer un push_back, que la capacité est supérieure à la taille, autrement une reallocation va avoir lieu.

Sinon, essaie d’éviter de stocker des adresses de variables faisant partie d’un vector, stocke quelque chose de plus durable, comme la position de l’élément.

Tu peux vérifier, avant d’effectuer un push_back, que la capacité est supérieure à la taille, autrement une reallocation va avoir lieu.

Sinon, essaie d’éviter de stocker des adresses de variables faisant partie d’un vector, stocke quelque chose de plus durable, comme la position de l’élément.

Sur le fond tu as raison, et c’est ce que je pensais faire; jusqu’à ce que je me rende compte que je n’ai pas d’autre choix que de prendre des pointeurs.

Le contexte ? Je suis en train de m’amuser à faire mon mini-langage de programmation (oui, encore). J’en suis au stade où je tente d’implémenter les fermetures (donc c’est plus si mini que ça). Je dois partir, je vous en dirai plus dans la soirée.

Attention, un redimensionnement ne provoque pas forcement de changement d’adresse (cf. realloc).

Pourquoi faire? Pourquoi as-tu besoin de savoir s’il y a eu un redimensionnement ?

Attention, un redimensionnement ne provoque pas forcement de changement d’adresse (cf. realloc).

Je croyais que realloc était banni en C++ ? Parlons de changement d’adresse plutôt que de redimensionnement alors, puisque c’est ce que je cherche en réalité.

Pourquoi faire? Pourquoi as-tu besoin de savoir s’il y a eu un redimensionnement ?

Parce que je prends un pointeur &v[n] et que je le stocke pour pouvoir le réutiliser plus tard. ET évidemment ce pointeur devient invalide s’il y a changement d’adresse. être prévenu à ce moment-là me permettrait de changer le pointeur pour le refaire pointer correctement, genre ptr = ptr + nouvelle_adresse - ancienne_adresse.

Pour en donner plus sur le fond du pourquoi, je suis en train de m’amuser à faire mon mini langage de programmation, et j’en suis au stade où j’essaye d’implémenter les fermetures (closures). Avant de réinventer la roue avec mon propre simili de std::vector, j’aurais juste aimé savoir s’il y avait une solution standard à mon petit problème.

Le vector en question où je voudrais être prévenu des changements d’adresse, c’est une pile d’exécution de la VM.

De manière simple, une valeur capturée par une fermeture plus communément appelée upvalue, tant qu’on est dans le scope, c’est un pointeur qui pointe sur une valeur plus bas dans la pile. Jusque-là on s’en sort facilement en stockant la position dans la pile. Là où ça se complique c’est qu’en fait je découvre qu’une upvalue peut parfaitement référencer une valeur se trouvant sur une autre pile….

Attention, un redimensionnement ne provoque pas forcement de changement d’adresse (cf. realloc).

Je croyais que realloc était banni en C++ ?

Son usage est très risqué. Mais std::vector n’utilise pas realloc (en tout cas pas ceux de libstdc++ ou libc++) car c’est un concept que les conteneurs ne comprennent pas. Actuellement, une nouvelle allocation = un nouveau segment de mémoire où déplacer les valeurs. Avec realloc, il ne faut pas le faire, sauf s’il y a vraiment eu reallocation, malheureusement, le fonctionnement de realloc tel que présent dans le standard C n’est pas compatible avec les objets non POD du C++.

Parlons de changement d’adresse plutôt que de redimensionnement alors, puisque c’est ce que je cherche en réalité.

Pourquoi faire? Pourquoi as-tu besoin de savoir s’il y a eu un redimensionnement ?

Parce que je prends un pointeur &v[n] et que je le stocke pour pouvoir le réutiliser plus tard. ET évidemment ce pointeur devient invalide s’il y a changement d’adresse.

Je suppose que garder une référence sur le vecteur + une position n’irait pas non plus ? Comment fais-tu pour garantir que la pile existe toujours ? J’ai l’impression qu’il y a une espèce de pointeur partagé qui rentre en jeu. Si c’est le cas, ajouter un partage avec la position devrait suffire.

Après le seul moyen de savoir exactement quand il y a une nouvelle allocation est de remplacer l’allocateur du conteneur par un qui implémente une fonction allocate pour faire un système de signaux. Il faudrait aussi regarder la doc pour savoir quels sont les types membres à ajouter pour qu’il fonctionne bien dans ton cas. Tout ce qui n’est pas implémenté utilise implicitement le comportement par défaut (voir std::allocator_traits).

Après, tu peux utiliser autre chose que vector comme une liste de tableau de 64 entrés (ou plus) ou un vector de unique_ptr<T[n]>. Ainsi, une nouvelle allocation n’invalide pas l’ancienne, mais c’est un peu plus difficile à manipuler.

Tu peux toujours encapsuler ton vector dans une classe dont la seule responsabilité serait de tester si l’adresse change (ou programmer une fonction pour).

ça m’étonnerait pas que ça soit un UB (arithmétique de pointeurs avec des objets qui ne sont pas du même "bloc").

genre ptr = ptr + nouvelle_adresse - ancienne_adresse.

ça m’étonnerait pas que ça soit un UB (arithmétique de pointeurs avec des objets qui ne sont pas du même "bloc").

Théoriquement c’est pas faux… mais en pratique je ne vois pas pourqoi ça ne marcherait pas, au pire avec un cast en int64_t pour être sûr qu’il n’y aura pas de débordement.

Ceci dit je peux toujours le réécrire ptr = nouvelle_adresse + (ptr - ancienne_adresse), et là plus aucun risque normalement (vu qu’on a pointeur + (pointeur - pointeur) = pointeur + entier). De toute façon je ne suis plus à un UB près, j’ai déjà du code très borderline à certains endroits, et bien pire que ça… genre cast de pointeur de fonction, union possédant des méthodes, placement new/delete/new[]/delete[], …

Je suppose que garder une référence sur le vecteur + une position n’irait pas non plus ? Comment fais-tu pour garantir que la pile existe toujours ?

Avec une référence sur le vecteur + une position, j’ai aussi essayé, mais je n’ai pas réussi, car j’ai l’impression que je ne sais pas toujours vraiment de quelle fil vient un pointeur donné. Par contre pour l’existance de la pile je n’ai rien à craindre.

L’upvalue peut être dans deux états: ouverte ou fermée. Tant qu’on est dans le scope elle est ouverte et elle pointe dans la pile. Dès qu’on quitte le scope, ce qui correspond aussi au moment où on dépile la valeur, l’upvalue est fermée, c’est-à-dire qu’on prend sa valeur actuelle et on va la stocker ailleurs en-dehors de toute pile d’exécution. Donc on n’a jamais de valeur qui n’existe plus.

Après le seul moyen de savoir exactement quand il y a une nouvelle allocation est de remplacer l’allocateur du conteneur par un qui implémente une fonction allocate pour faire un système de signaux. Il faudrait aussi regarder la doc pour savoir quels sont les types membres à ajouter pour qu’il fonctionne bien dans ton cas. Tout ce qui n’est pas implémenté utilise implicitement le comportement par défaut (voir std::allocator_traits).

Je vais aller voir de ce côté-ci, merci. JE n’ai encore jamais utilisé d’allocateur.

Après, tu peux utiliser autre chose que vector comme une liste de tableau de 64 entrés (ou plus) ou un vector de unique_ptr<T[n]>. Ainsi, une nouvelle allocation n’invalide pas l’ancienne, mais c’est un peu plus difficile à manipuler.

std::unique_ptr<T[n]> ? Il n’y a pas de std::unique_array et pas de risque de conflit entre new/delete et new[]/delete[] ? Cela dit je ne suis pas sûr que ça résoudrais mon problème, car ça voudrait dire que je ne pointe plus forcément toujours sur la dernière valeur, ce qui ne va pas non plus.

JE viens de tomber sur boost::stable_vector, je suis en train de me demander si ça ne résoudrait pas mon problème en fait; mais on dirait que le déficit de performances est quand même assez important d’après ce qu’ils en disent.

Si tu es gêné par les invalidations, et ne peut anticiper le nombre d’éléments réservés, c’est que tu ne manipules pas les bonnes choses. Repasse soit à des indices, ou ajoute une indirection (vector<ptr>), ou pars sur un conteneur fait de noeuds qui pourrit les caches comme les listes.

Les bidouilles à recalculer les déplacements & cie ne mènent à rien de bon.

J’ai trouvé ce qu’il fallait pour faire un allocateur personnalisé, voici une implémentation basique.

Par contre je me suis rendu compte en le faisant que ça ne pourrait pas marcher. Le callback est appelé après que le nouveau bloc est alloué, mais avant que les objets soient déplacés. Du coup, le callback fait du travail au mieux dans le vide (écrasées juste après), ou pire sur des données incorrectement initialisées.

template<class T, class F = std::function<void(const T*, const T*, size_t, size_t)>> struct callback_allocator {
typedef T value_type;
typedef T* pointer;
F callback;
T* lastPtr;
size_t lastSize;
callback_allocator (const F& cb): callback(cb), lastPtr(nullptr), lastSize(0)  {}
T* allocate (size_t newSize, const T* hint = nullptr) {
T* newPtr = new T[newSize];
callback(lastPtr, newPtr, lastSize, newSize);
lastPtr = newPtr;
lastSize = newSize;
return newPtr;
}
void deallocate (T* ptr, size_t n) {
delete[] ptr;
}
};

Si tu es gêné par les invalidations, et ne peut anticiper le nombre d’éléments réservés, c’est que tu ne manipules pas les bonnes choses. Repasse soit à des indices, ou ajoute une indirection (vector<ptr>), ou pars sur un conteneur fait de noeuds qui pourrit les caches comme les listes.

Une indirection supplémentaire, ça ne me plaît pas trop, surtout que pour le type T des éléments du vector, sizeof(T)==sizeof(void*).

ET passer à std::list ça me plaît encore moins. Je parle de pile d’exécution mais en fait j’ai besoin d’un accès aléatoire rapide.

Bon… en l’absence de solution qui me satisfasse vraiment, j’ai finalement fait ma propre version du vector customisé qu’il me fallait:

template<class T, class F = std::function<void(const T*, const T*)>, class Alloc = std::allocator<T>> struct execution_stack {
T *base, *top, *finish;
Alloc allocator;
F callback;
inline execution_stack (const F& cb = nullptr, size_t initialCapacity = 4):  base(nullptr), top(nullptr), finish(nullptr), callback(cb) {
base = allocator.allocate(initialCapacity);
top = base;
finish = base+initialCapacity;
}
inline ~execution_stack () { allocator.deallocate(base, (finish-base) * sizeof(T)); }
void reserve (size_t newCapacity) {
if (newCapacity<=finish-base) return;
T* newBase = allocator.allocate(newCapacity);
memcpy(newBase, base, (top-base) * sizeof(T));
callback(base, newBase);
allocator.deallocate(base, (finish-base) * sizeof(T));
top = newBase + (top-base);
base = newBase;
finish = base + newCapacity;
}
inline void resize (size_t newSize) {
reserve(newSize);
top = base + newSize;
}
inline void push_back (const T& x) {
if (top==finish)  reserve(2 * (finish-base));
*top++ = x;
}
inline T& pop_back () {
if (top==base) throw std::out_of_range("pop an empty stack");
return *top--;
}
template<class I> void insert (T* pos, I begin, const I& end) {
size_t index = pos-base, len = std::distance(begin, end);
reserve( (top-base) + len);
pos = base+index;
memmove(pos+len, pos, (top-pos) * sizeof(T));
while(begin!=end) *pos++ = *begin++;
top += len;
}
inline void erase (T* begin, T* end) { 
memmove(begin, end, (top-end)*sizeof(T));
top -= (end-begin);
}
inline void insert (T* pos, const T& val) { insert(pos, &val, &val+1); }
inline void erase (T* pos) { erase(pos, pos+1); }
inline size_t size () { return top-base; }
inline T& at (int i) {
T* ptr = i<0? top+i : base+i;
if (ptr<base || ptr>=top) throw std::out_of_range(format("Index out of range: index=%d, size=%d", i, top-base));
return *ptr;
}
inline T& operator[] (int i) { return at(i); }
inline T* begin () { return base; }
inline T* end () { return top; }
inline T& back () { return operator[](-1); }
};

Tu alloues un buffer, mais ne le construit jamais. Les allocateurs ont 4 fonctions importantes:

• allocate/deallocate pour allouer la mémoire
• construct/destroy pour construire (placement new) et détruite (appel du destructeur) un objet.

Comme ici les objets ne sont ni construit ni détruit, la mémoire est dans un état indéfini. Par contre, insert fait appel au constructeur de copie et le code ferra n’importe quoi avec, par exemple, unique_ptr. Les fonctions mem* sont aussi incompatibles avec tous les objets qui ne sont pas des POD (possible que ce soit moins restrictif, à voir dans la doc pour chacune des fonctions).

Grossièrement, si T est un type non compatible avec le langage C, alors la classe va mal se comporter.

• allocate/deallocate pour allouer la mémoire
• construct/destroy pour construire (placement new) et détruite (appel du destructeur) un objet.

Comme ici les objets ne sont ni construit ni détruit, la mémoire est dans un état indéfini.

Le compilateur ne s’est pas plain de l’absence de construct et destroy quand j’ai essayé de faire mon propre allocateur. JE les ai bien vues dans la doc pourtant. Je n’ai pas tilté mais je comprends mieux pourquoi maintenant…. effectivement je n’utilise ma classe qu’avec un type POD, une union en l’occurence. L’union a pourtant des constructeurs.

Ca ne me pose pas de problème dans le cas présent du coup, mais il faudra que j’y repense si je l’utilise ailleurs. Bien joué.

EDIT: Je viens de voir sur cppreference.com que construct et destroy sont deprecated en C++17 et supprimés en C++20. La façon de faire aurait donc changé ?

Je te proposerais plutôt de réfléchir sur "Qu’est ce que j’en ai à faire que mon vector se redimensionne?" Si tu réfléchis à cette question tu verras que la réponse est "rien". Le vector vit sa vie, il redimensionne s’il a besoin de redimensionner. Le seul soucis, c’est l’invalidation des itérateurs, mais si tu dois faire face à ce soucis, c’est que tu as violé le SRP, donc évite de violer le SRP

EDIT: Je viens de voir sur cppreference.com que construct et destroy sont deprecated en C++17 et supprimés en C++20. La façon de faire aurait donc changé ?

En fait, tout ce qui est optionnel est déprécié dans la classe allocator, car il faut passer par allocator_traits pour s’en servir. Par contre, si un allocateur possède une des fonctions optionnelles, allocator_traits va l’utiliser. Dans le cas contraire, il y a une implémentation par défaut.

Comme cela faisait doublon avec les fonctions de std::allocator et qu’un utilisateur d’allocateur doit fonctionner avec un allocateur qui contient seulement allocate/deallocate, il a été décidé de supprimer les autres fonctions dans l’allocateur par défaut.

Merci pour ces précisions.