Probleme avec std::map

**olive_le_malin** · 26/02/2007, 14h04

Bonjour,

je ne comprends pas pourquoi avec le code suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
	struct Test
	{
		int _a;
		int _b;
		Test(int a, int b) : _a(a), _b(b) {}
	};
 
	Test T(1, 2);
	std::map<int, Test> M;
	M[0] = T;

j'ai l'erreur :

error C2512: 'Test::Test' : no appropriate default constructor available
d:\program files\microsoft visual studio\vc98\include\map(93) : while compiling class-template member function 'struct Test &__thiscall std::map<int,struct Test,struct std::less<int>,class std::allocator<struct Test> >::operator [](const int

Alors que si je redéfinis mon constructeur de struct ainsi :

Code :

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

1
2
3
4
5
6
	struct Test
	{
		int _a;
		int _b;
		Test(int a=0, int b=0) : _a(a), _b(b) {}
	};

Je n'ai plus de problème.

Pourquoi faut-il absolument un constructeur par défaut ?

Merci par avance.

**Laurent Gomila** · 26/02/2007, 14h20

L'appel à l'opérateur [] de std::map construit un objet par défaut, puis renvoie celui-ci par référence ; c'est pour ça qu'il te demande un constructeur par défaut. Ceci-dit tu n'est pas obligé d'en fournir un, si tu insères ton objet autrement :

Code :

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

M.insert(std::make_pair(0, T));

**olive_le_malin** · 26/02/2007, 14h34

OK, alors il vaudrait peut être mieux que j'utilise map::insert ...
Le seul truc qui m'embete c'est que j'aurais voulu l'insérer même s'il existait déjà.

Merci beaucoup
@+

**deubelte** · 26/02/2007, 14h48

pour olive:
j'essaye de comprendre:
Test(int a=0, int b=0) : _a(a), _b(b) {}

que signifient : _a(a) ou _(b) ?

**Laurent Gomila** · 26/02/2007, 14h51

que signifient : _a(a) ou _(b) ?

C'est la liste d'initialisation, voir la FAQ pour plus de détails.

Le seul truc qui m'embete c'est que j'aurais voulu l'insérer même s'il existait déjà.

Dans ce cas, si la classe réelle le permet, définis un constructeur par défaut.
Sinon il faudra insérer de cette manière :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
std::map<int, Test>::iterator It = M.find(0);
 
if (It != M.end())
{
    // Clé déjà présente : on réaffecte
    It->second = T;
}
else
{
    // Clé inexistante : on insère
    M.insert(std::make_pair(0, T));
}

**olive_le_malin** · 26/02/2007, 15h13

Salut,

En supposant que je définisse un constructeur par défaut.
Si l'opérateur [] de map crée un objet par défaut, alors il va falloir aussi qu'il l'affecte avec celui passé en paramètre, et donc il faudrait aussi pour + de propreté définir le constructeur de copie et l'opérateur d'affectation, non ?

@+

**Laurent Gomila** · 26/02/2007, 16h54

et donc il faudrait aussi pour + de propreté définir le constructeur de copie et l'opérateur d'affectation, non ?

Bien sûr

Ici ceux générés par défaut sont corrects, mais si tu as une classe plus compliquée (genre qui gère une ressource brute) alors il faut définir tout ça.

**olive_le_malin** · 26/02/2007, 17h04

Et ... ouais !!

Bon ben je pense que je vais utiliser ta manière qui teste.

Mais pour savoir, disons que j'ai pas exactement une telle structure mais plutôt :

Code :

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

1
2
3
4
5
6
7
8
9
10
struct STest
{
unsigned long dwRef;
CIdent* pIdentity;
 
STest( unsigned long r=0, CIdent* pId=NULL):
   dwRef(r), pIdentity(pId) {
}
 
};

Ce n'est donc pas ma structure qui alloue pIdentity, elle ne fait qu'une affectation de pointeurs.
Je pense donc que, pour un tel cas, je peux m'éviter d'écrire les construct de copie et d'affectation, non ?

@+

**Laurent Gomila** · 26/02/2007, 17h23

C'est à toi de savoir si copier "bêtement" les deux membres de ta structure suffit, ou s'il faut faire un traitement spécial.
Ici si tu n'as pas à allouer / détruire / cloner / ... ton pointeur alors ce sera bon, oui.

**olive_le_malin** · 26/02/2007, 22h55

OK ! Donc tant que ma structure reste comme ça, je n'en ai pas besoin.

Par rapport à la solution que tu as proposée (avec un test pour savoir si la clé existe déjà), j'ai fait un essai.
Je redéfinis constructeur de copie et affectation, et je me rends compte que pour chaque appel de

Code :

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

M.insert(std::make_pair(0, T));

, j'ai 4 appels au constructeur de copie.
Je trouve ça fou,non ?

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct STest
{
	DWORD _dwRef;
	int* _pi;	
 
	STest(DWORD dwRef=0, int* pi=NULL):
		_dwRef(dwRef), _pi(pi)
	{
		cout << "constructeur" << endl;
	}
 
	STest& operator= (const STest& T)
	{
		cout << "operator=" << endl;
		if(this != &T)
		{
			this->_dwRef = T._dwRef;
			this->_pi = T._pi;
		}
		return *this;
	}
 
	STest(const STest& T)
	{
		cout << "copie" << endl;
		this->_dwRef = T._dwRef;
		this->_pi = T._pi;
	}
 
 
};
 
 
std::map<int, STest> M;
 
 
void f(int key, const STest& T)
{
	std::map<int, STest>::iterator It = M.find(key);
 
	if (It != M.end())
	{
		// Clé déjà présente : on réaffecte
		It->second = T;
	}
	else
	{
		// Clé inexistante : on insère
		M.insert(std::make_pair(key, T));
	}
 
	//M[key] = T;
}
 
 
 
int main() 
{ 
	int x = 1;
	int y = 2;
	int z = 3;
 
	cout << "Construction des 3 objets ..." << endl << endl;
	STest T1(1001, &x);
	STest T2(1002, &y);
	STest T3(1003, &z);
	cout << endl << endl;
 
	cout << "insertion1 ..." << endl << endl;
	f(x, T1);
	cout << "insertion2 ..." << endl << endl;
	f(y, T2);
	cout << "insertion3 ..." << endl << endl;
	f(x, T3);
 
	system("pause");

J'obtiens en sortie:

Construction des 3 objets ...
constructeur
constructeur
constructeur

insertion1 ...
copie
copie
copie
copie

insertion2 ...
copie
copie
copie
copie

insertion3 ...
operator=

Appuyez sur une touche pour continuer...

Je trouve que ça fait beaucoup d'appels au constructeur de copie.

Si j'utilise l'operateur[], en faisant :

Code :

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

1
2
3
4
void f(int key, const STest& T)
{
	M[key] = T;
}

Alors, en sortie, j'ai :

Construction des 3 objets ...
constructeur
constructeur
constructeur

insertion1 ...
constructeur
copie
copie
operator=

insertion2 ...
constructeur
copie
copie
operator=

insertion3 ...
operator=

Appuyez sur une touche pour continuer...

J'ai également essayé en faisant :

Code :

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

M.insert( std::map<int, STest>::value_type( key, T) );

Et là on s'affranchit des appels au constructeur de copie successifs avec make_pair et pair.

Quelle est donc la méthode la moins gourmande ?

@+

**Laurent Gomila** · 26/02/2007, 23h25

Honêtement je ne sais pas comment fonctionne std::map en interne lors d'une insertion (si ce n'est qu'il est généralement implémenté en terme d'arbre et qu'il peut y avoir pas mal de noeuds à bouger pour l'équilibrer), mais tu ne devrais pas chercher à mesurer ce genre de choses.

Si la copie de ta classe est coûteuse, alors stocke des pointeurs.

EDIT : c'est vrai qu'il y a std::pair qui fait déjà quelques copies.

**olive_le_malin** · 26/02/2007, 23h38

Salut,

merci pour tes réponses, qui plus est tardives.
Ok pour les pointeurs si c'est couteux.

Disons que dans mon cas, c'était pas vraiment couteux, mais je voulais bien comprendre ce qui était là derrière.

Sinon,appremment c'est en faisant :

Code :

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

M.insert( std::map<int, STest>::value_type( key, T) );

qu'on a le moins d'appels de copies, seulement 2.

Merci encore.

**Laurent Gomila** · 27/02/2007, 00h09

std::make_pair(key, T) va construire un std::pair puis le renvoyer par valeur, ce qui fait déjà une ou deux copies (selon les optimisations du compilo).

Avec std::map<int, STest>::value_type(key, T) tu construis l'élément à insérer directement et évites donc ces copies.

**JolyLoic** · 27/02/2007, 00h12

Normalement, map est implémenté à l'aide d'un red/black tree. Par contre le rééquilibrage devrait concerner des pointeurs, et ne pas déclencher de copies. Pour ce qui est de la mesure du nombre de copies, a-t-elle été bien faite avec toutes les optimisations à fond, y compris inlining et RVO ?

**olive_le_malin** · 27/02/2007, 09h58

Envoyé par Laurent

std::make_pair(key, T) va construire un std::pair puis le renvoyer par valeur, ce qui fait déjà une ou deux copies (selon les optimisations du compilo).

Oui, pour moi 2.

Envoyé par JolyLoic

Normalement, map est implémenté à l'aide d'un red/black tree.

Oui c'est ce que j'ai vu en traffiquant un peu dans les sources.

Envoyé par JolyLoic

Par contre le rééquilibrage devrait concerner des pointeurs, et ne pas déclencher de copies. Pour ce qui est de la mesure du nombre de copies, a-t-elle été bien faite avec toutes les optimisations à fond, y compris inlining et RVO ?

Je n'ai pas modifié les optimisations par défaut.

Probleme avec std::map

SL & STL C++

Discussions similaires

Partager

Partager