Autant que je sache, C ++ ne prend pas en charge un opérateur comme 'realloc (void *, size_t)' en langage C.
Cependant, std :: vector doit avoir un tampon pour contenir des données, et le tampon doit être développé ou compacté.
Alors, comment redimensionner le tampon de std :: vector sans la fonction 'realloc'?
Cela se fait-il simplement en allouant un nouveau tampon, en copiant ou en déplaçant tous les éléments et en détruisant le tampon précédent? Je pense que c'est inefficace.
4 Réponses :
Pour autant que je sache, C ++ ne prend pas en charge un opérateur comme 'realloc (void *, size_t)'
C ++ a std :: realloc . Mais il n'est pas (généralement?) Utilisé pour implémenter le redimensionnement du vecteur.
Alors, comment redimensionner le tampon de std :: vector sans la fonction 'realloc'?
En utilisant l'algorithme suivant:
Cela se fait-il simplement en allouant un nouveau tampon, en copiant ou en déplaçant tous les éléments et en détruisant le tampon précédent?
Oui.
Je pense que c'est inefficace.
Pourquoi pensez-vous cela? C'est exactement ce que fait realloc . Bien sûr, realloc peut parfois être capable d'ignorer la copie en fonction de la disposition de la mémoire, ce que ne peut généralement pas faire le vecteur. C'est un inconvénient malheureux du vecteur par rapport au tableau dynamique manuellement malloc até, mais ce n'est pas nécessairement un inconvénient significatif.
Il y a eu des propositions pour ajouter la prise en charge de la réallocation aux allocateurs standard, ce qui permettrait la même optimisation si elle était adoptée dans la norme: http://open-std.org/JTC1/SC22/WG21/docs/papers/2019/p0894r1.md
Il déplace le contenu, il ne le copie pas (appelle le constructeur de déplacement s'il y en a).
@MichaelChourdakis fait l'un ou l'autre selon le type d'élément.
Dans le cas d'un std::vector en théorie, il n'y a rien contre le fait qu'un équivalent de realloc soit utilisé en interne, mais en regardant l'implémentation pour g ++ (gcc version 6.3.0 20170516 / Raspbian):
template<typename _Alloc>
void
vector<bool, _Alloc>::
_M_reallocate(size_type __n)
{
_Bit_pointer __q = this->_M_allocate(__n);
iterator __start(std::__addressof(*__q), 0);
this->_M_impl._M_finish = _M_copy_aligned(begin(), end(), __start);
this->_M_deallocate();
this->_M_impl._M_start = __start;
this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
}
donc il est basé sur une nouvelle allocation puis copie puis désallocation
L'utilisation de realloc échouera, voir ma réponse ci-dessous.
@MichaelChourdakis remarque que ma réponse concerne le vecteur de bool, et je suppose que bool est TriviallyCopyable no ;-)?
Oui, si le type est un POD, cela fonctionnera. Mais ce n'est généralement pas le cas.
@MichaelChourdakis donc c'est le cas ici et " En théorie il n'y a rien contre le fait qu'un équivalent de realloc soit utilisé en interne " n'est pas faux, de toute façon vous DV ma réponse (je suppose que c'est vous)
L'OP n'a pas confiné son conteneur à bool, donc quiconque le voit peut supposer qu'il est en sécurité partout - rappelez-vous que beaucoup de débutants en C ++ liraient votre réponse comme un homme de haute réputation.
@MichaelChourdakis Je ne suis pas sûr de savoir comment te suivre, tu me DV parce que quelqu'un peut mal lire ma réponse? est-ce une blague? De là, la réputation ne protège pas contre l'erreur ^^
Je DV à cause de cela "En théorie, il n'y a rien contre le fait qu'un équivalent de réallocation est utilisé en interne" C'est incorrect.
@MichaelChourdakis c'est correct pour le vecteur
continuons cette discussion dans le chat .
@MichaelChourdakis pourquoi me proposez-vous d'aller dans le chat et de rester silencieux? grrr
std :: realloc n'est jamais utilisé à moins que le conteneur sache que les objets sont TriviallyCopiable.
Source: https://en.cppreference.com/w/cpp / memory / c / realloc
Parce que la réallocation peut impliquer une copie par octet (indépendamment de que ce soit pour étendre ou se contracter), seuls les objets de Les types à copier sont accessibles en toute sécurité dans la partie préservée de le bloc mémoire après un appel à realloc.
Certaines bibliothèques non standard définissent un trait de type "BitwiseMovable" ou "Relocatable", qui décrit un type qui n'a pas:
Si le conteneur ne peut pas savoir que les objets sont facilement copiables, l'utilisation de realloc pour étendre la mémoire peut entraîner des données corrompues.
Si is_trivially_copiable peut être utilisé sur le conteneur, alors oui, en utilisant realloc est possible. Sinon, cela entraînera un comportement indéfini.
Sinon, le conteneur a) crée une nouvelle mémoire, b) appelle le constructeur copy ou move des éléments pour les déplacer vers une nouvelle mémoire c) libère l'ancienne mémoire.
Parce qu'en C, tous les types sont facilement copiables.
La copiabilité triviale n'est pas le seul problème. L'implémentation devrait également savoir que l'allocateur donne un pointeur de malloc .
@eerorika, oui mais la famille d'implémentation de fonctions utiliserait la même classe de fonctions (par exemple, alloc de malloc, réallocation de realloc () etc., ou alloc de HeapAlloc et réallocation de HeapReAlloc) - Je suppose.
et la question est à ce sujet, ou équivalent ( push_back ...)
Je n'ai pas de DV mais je ne comprends pas la raison de ta réponse (même ce n'est pas faux :-))
@bruno. Intéressant. Il me semble que l'Op essaie de comprendre comment redimensionner un vecteur manuellement. Comment interprétez-vous la question?
La question concerne l'implémentation de vector :: resize, pas comment utiliser les opérations vectorielles pour en redimensionner un
Il crée une nouvelle mémoire, puis déplace les éléments (déplacement ou copie d'un appel constructeur). De plus, il y a HeapReAlloc (et un équivalent dans d'autres systèmes) qui se réallouerait si c'était la méthode. Même s'il utilisait realloc, à moins que les éléments ne satisfassent TriviallyCopyable, ils ne pourraient pas être copiés par memcpy.
"Autant que je sache, C ++ ne prend pas en charge un opérateur comme 'realloc (void *, size_t)' en langage C" - oui, c'est le cas. C ++ est compatible avec C à cet égard. Bien sûr, vous ne voulez certainement pas l'utiliser dans du code C ++.
Le problème avec
reallocest qu'il ne fonctionne que si la mémoire peut être augmentée sans changer la mémoire précédemment allouée et probablement utilisée. C'est la fragmentation de la mémoire et dépend du système d'exploitationTous les conteneurs standard qui n'ont pas un nombre fixe d'éléments (
std :: vector,std :: list, etc.) font des requêtes à un objet appelé allocateur, qui effectue le travail réel de gestion de la mémoire, via une interface définie. Les allocateurs et les conteneurs ont tendance à être assez soigneusement conçus pour les performances et l'exactitude par les auteurs de votre bibliothèque standard (ou fournisseur de compilateur). Avant de prétendre qu'ils sont inefficaces, écrivez votre propre code qui fait la même chose, faites-le fonctionner correctement et comparez. (Les débutants ont tendance à surestimer leur capacité à écrire un code efficace et correct).@Peter, en ce qui concerne les allocateurs, leur implémentation est assez simple. C'est le vecteur <> et les conteneurs eux-mêmes qui n'allouent pas tout le temps (ou allouent de manière exponentielle pour faire face à la croissance future). Les allocateurs appellent simplement la fonction new ou malloc ou dépendante du système d'exploitation et oui, il est possible de les implémenter plus efficacement (pools de mémoire, etc.).