Map stl et arbres rouges et noirs

Commenter

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

S'inscrire maintenant

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.

Du même auteur (guill76)