Map stl et arbres rouges et noirs

Soyez le premier à donner votre avis sur cette source.

Snippet vu 4 839 fois - Téléchargée 18 fois

Contenu du snippet

Ce bout de code est fait dans le but de faire découvrir les propriétés d'indexation des MAPs de la STL.
Une map est en fait un arbre rouge et noir dont le principal but est d'optimiser les recherches d'éléments ( c'est un peu le même concept qu'un index en terme de base de données).

On observera donc ici qu'une map ne peut pas être mélangée dans un ordre aléatoire, qu'une map ne peut pas être triée dans un ordre différent de celui établi à son initialisation.

Ce code permet d'afficher la structure sous forme de _RB_Tree_node. Il requiert pour visualiser le résultat l'utilitaire libre graphviz.

Source / Exemple :


#include <map>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;
#define _mCAST static_cast<NODE>

typedef map<int,string> mapTree ;
typedef pair<int,string> PAIR ;
typedef _Rb_tree_node<PAIR>::_Link_type NODE ;

/**
*

  • Qq fonctions auxilliaires
*
  • /
string i2str( long int i ) { ostringstream oss ; oss<<i; return oss.str() ; } long int str2i( string ent ) { return atoi( ent.c_str() ); } NODE left(NODE node) { return ( _mCAST( node->_M_left ) ) ; } NODE parent(NODE node) { return ( _mCAST( node->_M_parent ) ) ; } NODE right(NODE node) { return ( _mCAST( node->_M_right ) ); } NODE getNode( mapTree::iterator it ) { return _mCAST( it._M_node ) ; } bool isLeaf(NODE node) { return ( !left( node ) && !right( node ) ) ; } string getColor( NODE node ) { return ( ( node->_M_color )? "black" : "red" ); } void infoDot( mapTree::iterator it, ofstream& f ) { NODE node = getNode( it ) ; ostringstream ossaddr ; string tmp = "", tmpL = "", tmpR="" ; string position = "" ; if ( f.is_open() ) { if ( node ) { ossaddr << "\"" << (node) << "\"" ; tmp = ossaddr.str() ; if ( !isLeaf( node ) ) { f << tmp << "[shape=\"triangle\"];" << endl ; } if ( left( node ) ) { ossaddr.str( "" ) ; ossaddr << "\"" << left( node ) << "\"" ; tmpL = ossaddr.str() ; f << tmp << "->" << tmpL << ";" << endl ; } if ( right( node ) ) { ossaddr.str( "" ) ; ossaddr << "\"" << right( node ) << "\"" ; tmpR = ossaddr.str() ; f << tmp << "->" << tmpR << ";" << endl ; } f << tmp << "[label=\"" << node->_M_value_field.first << "\\n" ; f << node->_M_value_field.second << "\"];" << endl ; f << tmp << "[color=\"" << getColor( node )<< "\"];" << endl ; ossaddr.str( "" ) ; } } } void mapToDot( mapTree mp, string filename ) { mapTree::iterator it = mp.begin() ; ofstream ofile( filename.c_str() ); if (ofile.is_open()) { ofile << "digraph DG {" << endl ; ofile << "size=\"10,10\";" << endl ; while( it != mp.end() ) { infoDot( it, ofile ) ; ++it ; } ofile<<"}"<<endl; } ofile.close(); } int main() { mapTree myMap ; mapTree::iterator it=myMap.begin(); int entier=0; for ( entier=1;entier<30;entier++) it = myMap.insert( it, make_pair( entier, "entier"+i2str(entier)) ); mapToDot( myMap, "mymap.dot" ) ; // Si graphviz installé system ("dotty mymap.dot"); }

Conclusion :


J'ai fait ce code pour étudier un peu plus les maps car je l'ai utilisées sans vraiment les connaître.
Jusqu'au jour où j'ai voulu en trier une dans un ordre différent: sans résultats.
J'ai donc cherché le pourquoi dans l'entête stl_tree.h et ça m'a amené vers les arbres rouges et noirs que je ne connaissais pas.
Donc voilà si ça peut aider certains débutants comme moi.

A voir également

Ajouter un commentaire

Commentaires

cs_tibur
Messages postés
101
Date d'inscription
samedi 9 février 2002
Statut
Membre
Dernière intervention
5 mai 2009
-
Excellent !
Je te remercie bien, ça m'évitera des explications à un stagiaire qui était persuadé qu'une map était en accès direct. Sympa la sortie en graphviz.
Personne n'avait commenté cette source. Me voilà, et mon dix sur dix.
guill76
Messages postés
193
Date d'inscription
mercredi 24 août 2005
Statut
Membre
Dernière intervention
3 juin 2016
-
Bonjour,
Merci et content que ça puisse être utile à quelqu'un :)

Je voulais aussi ajouter un truc que j'avais oublié mais j'arrive pas à modifier le code : pas de bouton terminer pour valider(visible sous IE 6), je pense que c'est un petit bug de CS.

Je voulais en fait montrer les particularité du "sommet de la map" [ici l'lement de clé 8 dans l'exemple de la capture] qui en fait est lié par son parent au noeud pointé par l'iterateur end()(donc le vrai sommet)
le noeud du end lui pointe à gauche sur le begin() (le minimum de la map) et à droite sur le maximum.
je compléterai la source dès que je pourrais à nouveau valider la modification.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.