C++Talk.NET

Amerio · Guest

Amerio wrote:

Franck Branjonneau · Guest

"Amerio" <amerio (AT) hotmail (DOT) com> écrivait:

Hylvenir · Guest

Bonjour,
Je vais me mouiller un peu...
La solution avec le multimap ne devrait pas fonctionner
pour une hériarchie un peu complexe.

Voici une ébauche de solution, qui n'améliore
pas vraiment les performances mais permettent
de rendre plus lisible l'extraction d'un sous-arbre
de ton arbre d'héritage.
Ex:

A ---- AA ---- AAA
--- AAB

-- AB ---- ABA

Je vais donc garder le vector comme conteneur.
Je vais ajouter une méthode dans chacune des classes
afin déterminer la place de la classe dans la hiérarchie
classRank() qui donnera les résultats suivants:

A ---- AA ---- AAA "111"
--- AAB "112"

-- AB ---- ABA "121"

On tri le vector par un object fonction utilisant la chaine complète
représentant le rang.
Ensuite pour accèder à une sous-branche de la hiérarchie, il suffit
de récupérer par exemple tous les rangs commençant pas "11" pour
les classes issues de AA ( AA, AAA, AAB )

Voici l'idée, maintenant le brouillon de code :

// -------------------------------------
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

class A { public: virtual string classRank() const { return "1"; } };
class AA : public A
{
public:
virtual string classRank() const { return A::classRank() + "1"; }
virtual string print() const { return "AA::print()"; }
};

class AAA : public AA
{
public:
virtual string classRank() const{ return AA::classRank() + "1"; }
virtual string print() const { return "AAA::print()"; }
};
class AAB : public AA
{
public:
virtual string classRank() const { return AA::classRank() + "2"; }
virtual string print() const { return "AAB::print()"; }
};

class AB : public A
{
public:
virtual string classRank() const { return A::classRank() + "2"; }
virtual string print() const { return "AB::print()"; }
};
class ABA : public AB
{
public:
virtual string classRank() const { return AB::classRank() + "1"; }
virtual string print() const { return "ABA::print()"; }
};

// le functor de comparaison
struct compareA {
compareA( int l = 0 ) : l_( l ) {}
bool operator() ( const A* lhs, const A* rhs ) const {
if ( !l_ ) return lhs->classRank() < rhs->classRank();
return lhs->classRank().substr( 0, l_ )
< rhs->classRank().substr( 0, l_ );
}
int l_;
};

// l'insertion dans le vector trié
void inserer( vector<A*>& v, A* a )
{
v.insert( upper_bound( v.begin(), v.end(), a, compareA() ), a );
}

// la recherche avec cast, très expérimental peut être amélioré,
// mais j'ai pas trop le temps
template< typename T >
struct Recherche {
Recherche( vector<A*>& v, const A& a )
: lower_( lower_bound( v.begin(), v.end(), &a, compareA(
: a.classRank().length() ) ) ),
upper_( upper_bound( v.begin(), v.end(), &a, compareA(
a.classRank().length() ) ) )
{}

T& operator* () const { return *dynamic_cast<T*>( *lower_ ); } T*
operator-> () const { return dynamic_cast<T*>(*lower_) ; }
vector<A*>::iterator lower_, upper_;
};

int main()
{
vector< A* > vA;
vA.reserve( 120000 );

while( vA.size() < 100000 ) {
int r = rand() % 6;
switch(r){
case 0: inserer( vA, new A() ); break; case 1: inserer( vA,
new AA() ); break; case 2: inserer( vA, new AAA() ); break;
case 3: inserer( vA, new AB() ); break; case 4: inserer( vA,
new ABA() ); break; case 5: inserer( vA, new AAB() ); break;
}
}
}
// Recherche de la branche AA
Recherche< AA > v( vA, AA() );
while( v.lower_ != v.upper_ )
{
cout << '[' << (*v).classRank() << ']'
<< '[' << (*v).print() << ']';

cout << '[' << v->classRank() << ']'
<< '[' << v->print() << ']'
<< endl;
++v.lower_;
}
}

// Voilà, faut bien se mouiller en peu un jour ;-)

Amerio · Guest

Franck Branjonneau wrote:

Amerio · Guest

Amerio a écrit :

Amerio · Guest

Bon, j'ai finalement trouvé une solution à mon problème
(merci Franck pour avoir relever des problemes, et Hylvenir pour les
(bonnes) idées)

Voici les modifs faites par rapport au code precedent :

class Base
{
public:
Base(std::string const& n):name(n) {make_hier();}
virtual ~Base() {}
inline std::vector<std::string> const& hier() {return m_hier;}

public:
std::string name;
protected:
std::vector<std::string> m_hier;
inline void make_hier() { m_hier.push_back(typeid(*this).name()); }
};

class Derived : public Base
{
public:
Derived(std::string const& n):Base(n) {make_hier();}
};

class DerivedMore : public Derived
{
public:
DerivedMore(std::string const& n):Derived(n) {make_hier();}
};

class Another : public Base
{
public:
Another(std::string const& n):Base(n) {make_hier();}
};

class AnotherMore : public Another
{
public:
AnotherMore(std::string const& n):Another(n) {make_hier();}
};

et pour le world :

les iterator::operator*() et const_iterator::operator*() renvoie une
references et une ref constante.

template<class T>
inline world::iterator<T> world::begin()
{
return iterator<T>( m_mmap_idbase.lower_bound( typeid(T).name() ) );
}
template<class T>
inline world::const_iterator<T> world::begin() const
{
return const_iterator<T>( m_mmap_idbase.lower_bound(
typeid(T).name() ) );
}
template<class T>
inline world::iterator<T> world::end()
{
return iterator<T>( m_mmap_idbase.upper_bound( typeid(T).name() ) );
}
template<class T>
inline world::const_iterator<T> world::end() const
{
return iterator<T>( m_mmap_idbase.upper_bound( typeid(T).name() ) );
}
inline void world::insert(Base* b)
{
std::cout << "INSERT -> "
<< b->name << " : "
<< typeid(*b).name()
<< std::endl;
// Insertion de l'objet b, selon la hierarchie d'héritage de la classe
for (std::vector i = b->hier().begin();
i!= b->hier().end();
++i)
{
std::cout << "HIER -> "
<< (*i)
<< std::endl;
m_mmap_idbase.insert( std::make_pair( (*i), b) );
}
}

Et là, ca marche ! Youpi !
Reste plus qu'a optimiser en 'cachant' le resultat des end() pour optimiser
les boucles.

Franck Branjonneau · Guest

"Amerio" <amerio (AT) hotmail (DOT) com> écrivait:

Franck Branjonneau · Guest

"Amerio" <amerio (AT) hotmail (DOT) com> écrivait:

Amerio · Guest

Franck Branjonneau wrote:

Amerio · Guest

Franck Branjonneau wrote: