std :: string et son redimensionnement automatique de la mémoire

Question

Je suis assez nouveau pour C ++, mais je sais que vous ne pouvez pas utiliser la mémoire comme le bon gré mal gré std :: classe chaîne semble vous laisser faire. Par exemple:

std::string f = "asdf";
f += "fdsa";

Comment la poignée de classe de chaîne deviennent de plus en plus petit? Je suppose qu'il alloue un montant par défaut de la mémoire et si elle a besoin de plus, il news un plus grand bloc de mémoire et se copie sur à ce sujet. Mais ce ne serait pas assez inefficace d'avoir à copier toute la chaîne à chaque fois qu'il avait besoin de redimensionner? Je ne peux pas vraiment penser à une autre façon, il pourrait être fait (mais il est évident que quelqu'un a fait).

Et d'ailleurs, comment toutes les classes de stdlib comme vecteur, file d'attente, pile, etc poignée de plus en plus et de manière transparente le rétrécissement?

Answer 1

En général, il y a un algorithme de doublement. En d'autres termes, quand il remplit le tampon courant, il alloue un nouveau tampon qui est deux fois plus grand, puis copie les données actuelles sur. Il en résulte moins allouent / opérations de copie que l'alternative de plus en plus par un seul bloc d'allocation.

Answer 2

Votre analyse est correcte - il inefficace pour copier la chaîne à chaque fois qu'il a besoin de redimensionner. C'est pourquoi des conseils communs dissuade que motif d'utilisation. Utilisez la fonction reserve la chaîne pour lui demander d'allouer suffisamment de mémoire pour ce que vous l'intention pour entreposer. Ensuite, d'autres opérations rempliront cette mémoire. (Mais si votre indice se révèle être trop petit, la chaîne va encore croître automatiquement, aussi.)

Les conteneurs essayera aussi généralement pour atténuer les effets de réallocation fréquentes en allouant plus de mémoire que nécessaire. Un algorithme commun est que lorsqu'une chaîne trouve qu'il est hors de l'espace, il double la taille du tampon au lieu d'allouer au minimum nécessaire pour maintenir la nouvelle valeur. Si la chaîne est cultivé un caractère à la fois, cet algorithme doublement réduit la complexité de temps en temps linéaire amorti (au lieu du temps du second degré). Elle réduit également la sensibilité du programme à la fragmentation de la mémoire.

Answer 3

Bien que je ne connais pas la mise en œuvre exacte de std :: string, la plupart des structures de données qui doivent absorber la croissance de la mémoire dynamique le faire en faisant exactement ce que vous dites - allouer un montant par défaut de la mémoire, et si plus est nécessaire, alors créer un plus grand bloc et vous copier.

La façon dont vous contourner le problème de l'inefficacité évidente est d'allouer plus de mémoire que vous avez besoin. Le rapport de la mémoire utilisée: la mémoire totale d'un vecteur / string / liste / etc est souvent appelé (également utilisé pour les tables de hachage dans un sens légèrement différent) facteur de charge . Habituellement, il est un rapport 1: 2 - qui est, vous attribuez la mémoire que vous avez besoin deux fois. Lorsque vous manquez d'espace, vous attribuez une nouvelle quantité de mémoire deux fois votre montant actuel et l'utiliser. Cela signifie que au fil du temps, si vous continuez à ajouter des choses au vecteur / string / etc, vous devez copier sur l'élément de moins en moins (la création de la mémoire est exponentielle, et votre insertion de nouveaux éléments est évidemment linéaire), et donc le temps pris pour ce mode de gestion de la mémoire est pas aussi grand que vous pourriez penser. Les principes de Analyse Amorti, vous pouvez voir que l'insertion d'éléments de m dans un vecteur / string / liste à l'aide de cette méthode est que Big-Theta de m, ne m ² .