Discussion :

[Gwindor]

Bonjour,

Je me pose des questions au sujet de la complexité des opérations sur les vector.

En voici quelques unes :

• complexité de size()
• complexité de capacity()
• lors de la reallocation, quelle est la nouvelle taille ? le double de la capacité actuelle, la capacité actuelle +1 ?
• l'opérateur [] est-il beaucoup plus rapide que at() ?

Merci de m'éclairer !

[Laurent Gomila]

complexité de size()

O(1), c'est stocké.

complexité de capacity()

O(1), c'est stocké.

lors de la reallocation, quelle est la nouvelle taille ? le double de la capacité actuelle, la capacité actuelle +1 ?

C'est la taille courante multipliée par un facteur supérieur à 1 (probalement 1.5 ou 2 -- je pense que chaque implémentation est libre de choisir) ; bref ce n'est pas +1, donc la complexité amortie d'un push_back est bien en O(1).

l'opérateur [] est-il beaucoup plus rapide que at() ?

La fonction at() ne fait que tester si l'index est entre 0 et size() - 1.

[Gwindor]

pour ces réponses très précises.

[pyknite]

La fonction at() ne fait que tester si l'index est entre 0 et size() - 1.

La fonction at(x) permet de récuperer la valeur à la position x de ton vector, et surtout, il gère les dépassements... Si ton vector a une taille de 10 et que tu fais monvector.at(23) il va te retourner une erreur aulieu de te retourner n'importe quelle valeur qui traine dans la mémoire...

[yan]

La fonction at(x) permet de récuperer la valeur à la position x de ton vector, et surtout, il gère les dépassements... Si ton vector a une taille de 10 et que tu fais monvector.at(23) il va te retourner une erreur aulieu de te retourner n'importe quelle valeur qui traine dans la mémoire...

Sous visual, l'operateur [] le fait aussi mais tu peut l'enlever (je ne sais plus comment)

[Laurent Gomila]

Sous visual, l'operateur [] le fait aussi mais tu peut l'enlever (je ne sais plus comment)

Seulement en debug à mon avis.

[yan]

malheuresement non

Code :

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

1
2
3
4
5
6
7
8
9
 
#include <vector>
 
int main(int argc, char* argv[])
{
    std::vector<int> vect(10);
    for(int i=0;i<11;++i) vect[i];
	return 0;
}

donne en release

Microsoft Visual Studio C Runtime Library has detected a fatal error in testvectorr.exe.

lancé avec visual

testvectorr.exe has encountered a problem and needs to close. We are sorry for the inconvenience.

sans visual