Discussion :

[salseropom]

Bonjour, j'ai une std::map<int,int> m;

Je fais quelque chose du genre

Code :

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

1
2
3
 
for(int i = 0 ; i < N ; i++)
  m.insert(std::make_pair(i,2 * i));

(l'exemple est bête, mais là n'est pas ma question). En gros, je fais toujours une insertion dans ma map au dernier élément. J'ai vu que je pouvais indiquer via un iterator, un "indice" à partir du quel insérer mon nouvel objet. L'exemple précédent deviendrait alors

Code :

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

1
2
3
 
for(int i = 0 ; i < N ; i++)
  m.insert(m.end(),std::make_pair(i,2 * i));

L'idée étant de gagner du temps de calcul.

Maintenant, voici un exemple (avec ma question dedans) :

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
 
#include <map>
#include <iostream>
using namespace std;
 
void printMap(const map<int,int> & m)
{
	//for(size_t i = 0 ; i < m.size() ; i++)
	map<int,int>::const_iterator it;
	for(it = m.begin() ; it != m.end() ; it++)
		cout << it->first << " : " << it->second << endl;
	cout << endl;
}
 
int main()
{
	map<int,int> m;
 
	m.insert(make_pair(0,0));
	m.insert(make_pair(3,3));
	m.insert(make_pair(2,2));
	m.insert(m.end(),make_pair(4,4));
	m.insert(m.begin(),make_pair(5,5));
	m.insert(m.end(),make_pair(1,1)); // pourquoi cet élément est-il inséré ?
	m.insert(make_pair(2,0));
 
	printMap(m);
 
	return 0;
}

J'avoue ne pas comprendre pourquoi l'élément (1,1) est inséré car je lui ai dis d'insérer à partir du dernier élément...

Merci d'avance de vos réponses.

[vikki]

Hello,

Spécifier un iterateur de position ne veut pas dire que ton élément va être inséré exactement à cette position. La map étant un conteneur trié, l'élément à insérer se retrouvera toujours à sa bonne position, dépendant uniquement de l'opérateur de comparaison fourni en paramètre template de la map (si je dis pas de bêtises). Le paramètre de position veut dire, en gros, que la recherche de la vrai position d'insertion commencera à la position donnée (ce qui peut faire gagner pas mal de temps).

[koala01]

Salut,

Tu sembles oublier que la std::map agit comme un arbre binaire équilibré, afin d'assurer sa capacité à assurer une recherche en O(log n).

Chaque insertion sera donc obligatoirement suivie par un rééquilibrage de l'arbre, et tu ne gagnes absolument rien à demander à ce que l'insertion se fasse à la fin de la collection.

Au contraire, j'aurais tendance à estimer que tu force le déséquilibre de l'arbre, et donc que tu perds plus de temps que tu ne pourrais en gagner en laissant la std::map sélectionner d'elle-même le meilleur endroit pour insérer le nouvel élément

[koala01]

Hello,

Spécifier un iterateur de position ne veut pas dire que ton élément va être inséré exactement à cette position. La map étant un conteneur trié, l'élément à insérer se retrouvera toujours à sa bonne position, dépendant uniquement de l'opérateur de comparaison fourni en paramètre template de la map (si je dis pas de bêtises).

C'est effectivement en fonction de l'opérateur de comparaison "plus petit que"

Le paramètre de position veut dire, en gros, que la recherche de la vrai position d'insertion commencera à la position donnée (ce qui peut faire gagner pas mal de temps).

Cela peut faire gagner du temps si tu a déjà pu déterminer un sous ensemble de ta collection dans lequel tu es sur que ton nouvel élément prendra place.

Or, la fin de la std::map n'est que rarement un tel sous ensemble

[vikki]

On est d'accord, ça n'arrive pas souvent (en fait jamais pour moi). Par contre il suffit que la position spécifiée soit inférieure à l'élément à insérer (au sens du std::less ou autre foncteur) pour gagner (un peu, ca dépend du nombre d'éléments dans la map précédant la positions spécifiée) de temps. Si l'élément situé directement après cette position est supérieur à l'insertion, la map effectuera sa tambouille interne classique pour déterminer la position adéquate (donc en partant du plus petit élément je crois, pas sûr). Tout ça pour dire que ça sert pas à grand chose

[koala01]

En fait, le tri se fait par équilibrage de l'arbre sous-jasent, avec tout ce que cela implique de permutations d'élément pour arriver à équilibrer l'arbre "global".

Je suspecte en fait que la possibilité de préciser une position d'insertion est essentiellement due au souhait de fournir une interface similaire pour l'ensemble des collections supportant l'insertion, car tu ne peux même pas avoir la certitude que si tu fournis une position dont la comparaison "less than" est vérifiée rendra l'équilibrage plus rapide