Discussion :

[Olistan]

Bonjour,
Je souhaiterais avoir votre avis sur le meilleur choix du container et de l'algorithme du bout de code suivant.

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
 
typedef std::vector< size_t >  col;
typedef std::vector< col >  table;
 
void f( size_t i, size_t j )
{
  col& c1 = table[ i ];
  col& c2 = table[ j ];
  if( find( c1.begin(), c1.end(), j ) == c1.end() )
  {
      // Sorted insertion.
      c1.insert( lower_bound( c1.begin(), c1.end(), j ), j );
      c2.insert( lower_bound( c2.begin(), c2.end(), i ), i );
  }
}

Vu que les éléments des colonnes sont triés dans le container, utiliser un vecteur n'est certainement pas l'idéal. De plus, faire un find puis un lower bound peut certainement être réduit en une seule opération. Le coût le plus important est lors de la construction de la table.

Un tout grand merci pour vos conseils !

[Olistan]

J'ai utilisé un unordered_set à la place. Je pense que c'est déjà bien mieux (recherche avec table de haschage ?). De plus, j'évite le recours à un algorithme

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
 
typedef boost::unordered_set< size_t > col;
typedef std::vector< connection >           table;
 
  void f( size_t i, size_t j )
  {
    col& c1 = table[ i ];
    col& c2 = table[ j ];
 
    if( c1.find( j ) == c1.end() )
    {
      c1.insert( j );
      c2.insert( i );
    }
  }

Qu'en pensez-vous ?

[yan]

Salut,
faudrais plus de détail sur ce que tu fais aprés avec tes contenaire
pour te repondre.

[reptils]

http://cpp.developpez.com/faq/cpp/?p...hoix_conteneur

[Olistan]

Merci reptil pour le lien (que je connaissais déjà et je l'ai même collé sur mon bureau). Par contre il ne reprend pas les containers de boost / TR1. Après examen du diagramme ci-dessus, je partais donc vers un 'set' standard avant de découvrir la 'boost::unordered_set' qui apparement convient mieux pour les find mais j'ai pas vraiment compris les différences (dichotromie pour le set et table de hachage par défaut dans l'autre) ?

@Mongaulois: C'est vrai que j'ai été assez vague. En fait, par la suite, je ne fais que parcourir les colonnes du graphe. C'est pourquoi je pense que la construction est la partie la plus coûteuse.

[yan]

@Mongaulois: C'est vrai que j'ai été assez vague. En fait, par la suite, je ne fais que parcourir les colonnes du graphe. C'est pourquoi je pense que la construction est la partie la plus coûteuse.

Si aprés construction le contenue ne change pas(voir peu) alors utilise un vector. C'est le plus adapté.
Si il y as des ajout/retraire regulier et de manière trié, utilise un set.

Pour ta partie construction, tu peut utiliser le set, puis convertir en vector par la suite