std::vector redimensionner à la baisse

La norme C++ semble faire aucune déclaration au sujet des effets secondaires sur la capacité, soit par
resize(n), avec n < size(), ou clear().

Elle permet de faire une déclaration sur le coût amorti de push_back et pop_back - O(1)

Je peux envisager une mise en œuvre qui n'a l'habitude de tri de l'évolution de la capacité
ala PLC Algorithmes (par exemple, le double lors de l'élargissement, de réduire de moitié lorsque la diminution de size to < capacity()/4).
(Cormen Lieserson Rivest Stein)

Quelqu'un aurait-il une référence pour toute mise en œuvre des restrictions?

InformationsquelleAutor | 2009-07-20

c++resize std stdvector vector

43

Appel resize() avec une plus petite taille n'a pas d'effet sur la capacité d'un vector. Il ne sera pas libérer de la mémoire.

La norme idiome pour la libération de la mémoire à partir d'un vector est à swap() avec un vide temporaire vector: std::vector<T>().swap(vec);. Si vous souhaitez redimensionner à la baisse, vous aurez besoin de copier à partir de votre vecteur d'origine dans un local temporaire vecteur et le swap, le vecteur résultant de votre original.

Mise à jour: C++11 a ajouté une fonction membre shrink_to_fit() à cette fin, c'est un non-demande de liaison pour réduire capacity() à size().
- La façon dont je l'ai lu il demande à propos de l'impact sur l'utilisation de la mémoire - il demande expressément à ce que l'effet sur la capacité de redimensionner. La norme ne spécifie pas le résultat dans ce cas, mais la seule raison de demander, je pense, un désir de libérer de la mémoire inutilisée. Le swap temporaires truc, c'est le idiomatiques réalisation de cet objectif.
- La norme ne précise pas le résultat en ne spécifiant une diminution de la capacité() pour ces opérations. Donc il ne peut pas diminuer.
- Il y a quelques environnements où il est interdit d'allouer ou libérer de la mémoire après une première phase de "construction" de la phase. Les vecteurs sont utilisables dans cet environnement aussi longtemps que l'on peut être sûr de ne pas tenter d'allouer ou libérer de la mémoire au cours des opérations. Ainsi, cette question est pertinente dans cette situation (ce qui m'a amené ici).
InformationsquelleAutor mattnewport
24

En fait, la norme ne précise pas ce qui doit arriver:

C'est à partir de vector, mais le thème est le même pour tous les conteneurs (list, deque, etc...)

23.2.4.2 vecteur de la capacité [lib.vecteur.capacité]

void resize(size_type sz, T c = T());

6) Effets:
```
if (sz > size())
    insert(end(), sz-size(), c);
else if (sz < size())
    erase(begin()+sz, end());
else
    ; //do nothing
```
C'est-à-dire: Si la taille spécifiée pour resize est inférieur au nombre d'éléments, ces éléments seront effacées à partir du conteneur. Concernant capacity(), cela dépend de ce que erase() fait pour elle.

Je ne trouve pas dans la norme, mais je suis sûr que clear() est définie comme:
```
void clear()
{
    erase(begin(), end());
}
```
Par conséquent, les effets clear() a sur capacity() est également liée aux effets erase() a sur elle. Selon la norme:

23.2.4.3 vecteur modificateurs [lib.vecteur.modificateurs]
```
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
```
4) la Complexité: Le destructeur de T est appelé le nombre de fois égal au nombre des éléments effacés....

Cela signifie que les éléments seront détruits, mais le souvenir reste intact. erase() n'a pas d'effet sur la capacité, donc resize() et clear() également sans effet.
- resize la baisse est maintenant documenté comme équivalente à une série de pop_back() appels et de ne pas erase. Le fait de supprimer la garantie que la capacité ne va pas changer? (Voir stackoverflow.com/q/19941601/103167)
InformationsquelleAutor GManNickG
6

La capacité ne diminuera jamais. Je ne suis pas sûr si la norme indique explicitement, mais il est implicite: les itérateurs et les références à des éléments du vecteur ne doit pas être invalidé par resize(n) si n < capacity().

InformationsquelleAutor avakar

Comme je l'ai vérifié pour gcc (mingw) la seule façon de vecteur libre capacité est ce que mattnewport dit.
Swaping avec d'autres teporary vecteur.
Ce code permet de elle pour gcc.

template<typename C> void shrinkContainer(C &container) {
    if (container.size() != container.capacity()) {
        C tmp = container;
        swap(container, tmp);
    }
    //container.size() == container.capacity()
}

InformationsquelleAutor fantastory

Vous devez vous connecter pour publier un commentaire.