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

[Sylvain Togni]

Sous Visual 2008 pour enlever les vérifications en release il faut définir _SECURE_SCL=0.

[Gwindor]

Je travaille avec Visual 2003.

Si j'ai bien compris, par défaut, l'opérateur [] est identique à la fonction at(), lorsque on lance l'application depuis visual ?

Mais si on lance l'application hors de visual, alors l'opérateur [] est optimisé ?

[Goten]

En fait l'opérateur [] ne vérifie pas si tu dépasses la taille de ton conteneur... (hormis sous vc apperemment...) alors que at() le fait lui. Ce qui fait que at() est un peu plus lent que l'opérateur [].. car il vérifie à chaque fois que tu estbien à l'intérieur du tableau et pas hors limite;

[Gwindor]

En fait l'opérateur [] ne vérifie pas si tu dépasses la taille de ton conteneur... (hormis sous vc apperemment...) alors que at() le fait lui. Ce qui fait que at() est un peu plus lent que l'opérateur [].. car il vérifie à chaque fois que tu estbien à l'intérieur du tableau et pas hors limite;

Oui oui j'avais bien compris les choses comme ça.
Ce que je me demande, c'est si je compile mon application avec VC++, et que je la lance hors de visual, est-ce que l'opérateur [] fera des vérifications ou pas.

[yan]

Oui oui j'avais bien compris les choses comme ça.
Ce que je me demande, c'est si je compile mon application avec VC++, et que je la lance hors de visual, est-ce que l'opérateur [] fera des vérifications ou pas.

oui sauf si tu le desactive. Sous 2003, y as forte chance que ce soit quasiment la même chose

[loufoque]

Le comportement de operator[] est indéfini si l'index n'est pas dans le vecteur.
Terminer le programme avec une erreur ou lancer une exception sont des comportements possibles.
Néanmoins, terminer le programme est une bien meilleure idée s'il doit s'agir d'une option désactivable. C'est ce que fait libstdc++ en mode debug.

[Gwindor]

Rien ne vaut un petit test.

Executé en dehors de visual. La différence est flagrante. Cela dit il faudrait vraiment être un malade pour faire autant d'accès dans un programme.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include "stdafx.h"
#include <vector>
#include <iostream>
 
using namespace std;
 
 
int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> myVect(1000);
 
	for(int i=0; i<10000000; i++)
	{
		for(int j=0; j<1000; j++)
		{
			//myVect.at(j);	// -> 19 secondes
			myVect[j];	// -> moins de 1 seconde
		}
	}
 
	return 0;
}

[Sylvain Togni]

Moins de 1 seconde c'est parce que le compilateur a supprimé les deux boucles vu qu'elles ne font rien d'observable. Avec at() non plus elles ne font rien d'ailleurs mais ça le compilo n'est pas encore assez intelligent pour le remarquer.