Discussion :

[SteelBox]

Bonjour, j'ai besoin d'un conseil :

J'ai une structure suivante (bateau, c'est un point...)

Code :

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

1
2
3
4
5
6
 
struct elt{
int x;
int y;
};
list<elt> l; //deque<elt> d;

J'ai besoin de trier par x puis par y.

Méthode envisagée :

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
16
17
 
void MaClasse::Insertion(elt e)
{
   list<elt>::iterator i=l.begin();
   for(;i!=l.end();i++)
   {
      if( (l->x) == e.x)
         // cherche le y
         while((i!=l.end()) && ((l->y) > e.y))
            i++;
      else
          if( (l->x) > e.x)
            break; // tu es supérieur, tu arrêtes...
   }
   // arrivée ici, i pointe sur l'élément AVANT lequel tu dois insérer (il pointe sur l.end() si tu dois insérer à la fin)
   // cf l.insert() ...
}

Ma question est simple :
Y'a t'il d'autres structures plus performantes pour faire ce que je veux faire ?
Dans le cas de la multimap, x serait ta clé, et il y aurait une fonction de hashage sur le x (en gros, ca peut être une bonne solution si tu fais presque toutes tes recherches sur un élt : en l'occurence x). Je pense pas que ce soit une meilleure solution...

QU'en pensez vous ?
Merci

[Laurent Gomila]

Pourquoi pas ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct SortMyElts
{
    bool operator ()(const elt& e1, const elt& e2) const
    {
        return e1.x == e2.x ? e1.y < e2.y : e1.x < e2.x;
    }
};
 
std::set<elt, SortMyElts> s;
 
s.insert(e); // Insère au bon endroit, en temps logarithmique

Après il faut voir ce que tu auras à faire comme autres opérations sur ton ensemble.

[Luc Hermitte]

Il doit être possible de générer (au besoin) des ensembles/structures triées d'indirections vers les éléments originaux de ton premier tableau.
Si j'ai bien suivi, c'est ce qu'enveloppe pour nous boost.multi_index (je peux me tromper, n'ayant jamais utilisé la bibliothèque en question)

[SteelBox]

L'exemple de Loulou24 me convient bien? Je savais bien qu'il y a avait moyen de le faire en exploitant encore plus la STL...
Merci