Discussion :

[r0d]

Bonjour,

voilà, j'ai une map, dont les clés sont des string et les éléments sont des petites structures. A un moment donné dans mon programme, je dois désallouer cette map. Or, à ce moment, elle a une taille de l'ordre de 500Mo. Donc la libération prends un certain temps. Du coup, j'aimerais faire un système de progress bar, pour que l'utilisateur ne pense pas que l'appli est plantée.

Alors j'avais pensé faire une boucle qui détruit élément par élément, avec un compteur. Quelque chose comme ça:

Code :

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

1
2
3
4
5
6
int count = 0;
for ( MaMap::iterator it = ma_map.begin(); it != ma_map.end(); ++it )
{
	ma_map.erase( it );
	Step( count ++ ); // gère la barre de progression
}

Mais ça ne marche pas, le erase rends it inutilisable et du coup le ++it suivant envoie mon iterateur dans la stratosphère.

Auriez-vous quelques idées?

[Nogane]

Bonjours,
Je suppose qu'il s'agit d'une std::map?

Est-ce la map qui est grosse ou plutôt les objets contenue?
Les objet sont-ils des pointeurs intelligents?
Dans ce cas il serai possible de faire un parcourt normal avec reset et Step, puis un clear de la map.

Autre solution, en restant sur ton idée de départ:

Code :

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

1
2
3
4
5
6
7
8
 
int count = 0;
MaMap::iterator it = ma_map.begin();
while (  it != ma_map.end())
{
	ma_map.erase( it++ ); //l'opérateur ++ renvoie une copie non incrémenté de it, donc it reste valide
	Step( count ++ ); // gère la barre de progression
}

[Invité]

Salut r0d,

C'est prévu! La fonction erase() renvoie un itérateur sur l'élément qui suit celui que tu supprimes, il faut donc écrire

Code :

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

while(it!=conteneur.end()) it=conteneur.erase(it);

Ce comportement est commun à tous les conteneurs de la STL... tu peux donc conserver ton code, même si tu abandonnes la map (ouais, parce qu'une map indexée par des string, en terme de performance...)

Francois

[Nogane]

j'ai une map, dont les clés sont des string et les éléments sont des petites structures.

Woups, j'avais pas vu ca, du coup j'ai posé des questions pour rien...

C'est prévu! La fonction erase() renvoie un itérateur sur l'élément qui suit celui que tu supprimes, il faut donc écrire

C'est ce que je me suis dit au début, mais apparemment pas la std::map.(en tout cas pas avec la std de minGW, ni dans la doc de cplusplus.com)

Question a part:
Pourquoi une map indexée par des strings est-ce si terrible? L'opérateur < sur des string est rapide, et une map ne fait pas de copie en interne(comme un vector ferait). Alors pourquoi?
Et quel autre alternative pour faire un tableau associatif chaine de caractère -> quelque chose ? unordered_map? le faire soit même?

[Invité]

C'est ce que je me suis dit au début, mais apparemment pas la std::map.(en tout cas pas avec la std de minGW, ni dans la doc de cplusplus.com)

Tu as raison. Je l'ai sur la STL que j'utilise (dinkumware) mais après vérification, je ne le vois pas dans STLport. C'est probablement une extension non standard (c'est un peu bête, soit dit en passant). Pour être portable, il faut donc faire comme tu dis, incrémenter l'itérateur avant, et détruire après (personnellement je préfère faire une copie plutôt qu'une postincrémentation, mais c'est une affaire de goût).

Pourquoi une map indexée par des strings est-ce si terrible? L'opérateur < sur des string est rapide, et une map ne fait pas de copie en interne(comme un vector ferait). Alors pourquoi?
Et quel autre alternative pour faire un tableau associatif chaine de caractère -> quelque chose ? unordered_map? le faire soit même?

Il y a deux aspects :

1- la map n'est pas une bonne implémentation d'un tableau associatif, si celui ci est lu, utilisé puis détruit (ou change très peu dans le temps). Un vecteur trié, avec une recherche binaire (lower_bound, des trucs comme ca) sera toujours plus efficace, en terme de mémoire et de vitesse. La map est utile quand on fait beaucoup d'ajouts et de suppressions, et des recherches entre, ou quand on a de petites structures (ou que la vitesse n'est pas un problème). Son principal avantage, dans ces situations, c'est qu'elle est très facile à mettre en oeuvre.

Si on fait essentiellement un chargement, des tas de recherches, et une destruction (avec un ou deux petits ajouts/destruction au milieu), le vector gagne toujours...

Dans des cas intermédiaires, et pour de gros volumes (surtout si les index ne sont pas des entiers), les tables de hachage fonctionneront mieux (par rapport au vector, elles prennent plus d'espace et vont plus vite, par rapport à la map, elles prennent généralement autant d'espace, et vont nettement plus vite...)

2- l'indexation par des string, c'est lent, parce que toutes les méthodes de recherche/tri rapide reposent sur des comparaisons, et que les comparaisons de string sont lentes (par rapport aux comparaisons d'entier). Par ailleurs, les string ca mange de la mémoire (et du temps lors de l'allocation)...

Sur de petites tables, la question ne se pose pas, mais dès qu'on va sur quelque chose de gros, on a intérêt à réindexer. Souvent on peut s'arranger pour le faire, soit dans les entrées (si on travaille sur des données "mortes", soit au chargement : on indexe les string qu'on va utiliser et on utilise cet index entier). Si c'est impossible, c'est là que le hachage devient très puissant.

Une fois de plus, le problème ne se pose que quand on travaille avec de grosses structures (plusieurs milliers d'enregistrements, je dirais, en fait dès que les approches reposant sur des conteneurs triés commencent à faire la différence). Et la STL fournit les outils qui permettent de traiter cela (les vecteurs triés et les outils de recherche qui vont avec, et le hachage, même s'il n'est pas tout à fait standardisé d'une implémentation à l'autre).

Sur un gros programme qui fait de la "gestion", retravailler les map, les indexations par des string, et les entrées sortie, c'est presque toujours faire un gros gain de vitesse...

Francois

[Nogane]

Merci beaucoup pour ces explications!
Je n'ai jamais utiliser des tableaux associatifs avec de fortes contraintes de mémoire/vitesse, mais au moins quand ca arrivera j'aurais une idée plus précises des différentes possibilités.
C'est vrais qu'au premier abord, je n'aurais pas pensé au vector trié, ou a la "réindexation".

[r0d]

Je suppose qu'il s'agit d'une std::map?

oui oui, comme on est sur le sous-forum sl/stl, je n'avais pas pensé utile de le préciser.

Est-ce la map qui est grosse ou plutôt les objets contenue?

Ce sont des petits éléments, mais il y en a vraiment beaucoup.

Les objet sont-ils des pointeurs intelligents?

Non. Ce ne sont pas des pointeurs. Si tu veux, ça ressemble à ça:

Code :

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

1
2
3
4
5
6
struct Dum
{
   int x1, x2, x3;
};
 
std::map<std::string, Dum> ma_map;

Autre solution [..]

Merci
Pour l'instant je pars là-dessus, ça à l'air de fonctionner. Merci.

une map indexée par des string, en terme de performance...

Ben là, ce n'est pas si évident que ça. Ce week-end j'ai fait toute une batterie de tests pour comparer les performances de maps indexées par des string par rapport à d'autres types de clés (entiers, enums, etc.), et je n'ai pas obtenu de différences significatives. Bon, je n'ai pas effectués ces tests dans des vrais conditions de tests, ni sur plusieurs machines, ni avec différentes compilos, mais disons que ce point n'est pas si évident que ça. Je n'ai malheureusement trouvé aucune littérature sur le sujet