Discussion :

[ternel]

Du coup, si tu veux effectivement maintenir deux ordres sur une collection.

Il n'y a pas de solutions miracles:
tu ranges selon un ordre, et tu conserves l'autre ordre "dans un coin".
C'est à dire deux collections empaquetées dans une seule interface.

Tes choix à prendre sont la nature des deux collections, et si la deuxième collection stoque l'objet, un pointeur ou un index.
Reste à fournir deux classes d'itérateurs (par typedef ou non), une pour chaque ordre.

[Alexoy82]

@ stendhal666 - Yep c'est bien du Machine Learning
Promis, quand j'aurais fini de coder cette approche je ferais un poste pour expliquer tout ça

Merci encore à tous pour vos conseils ! Il y a beaucoup de bonnes idées dans ce que vous avez proposé
Finalement, je pars sur une refonte de mon code qui m'évitera ce genre de problème ...

[bacelar]

Vue la taille des données, c'est peut-être le moment de faire péter un SGBD avec des index, non ?

http://www.sqlserverdatamining.com/s...5/Default.aspx

Voir les environnements dédiés au ML :
http://blog.cellenza.com/data/sql-se...prise-en-main/

[Invité]

Pourtant au niveau des collections de la STL, on est bien servi!

std::vector : la plus simple, c'est une simple liste dynamique d'éléments et on peut accéder à chaque élément via son index comme avec un tableau statique, on peut ajouter un élément en fin de liste avec la méthode push_back, mais on peut aussi en insérer à n'importe quel endroit et en supprimer grâce aux itérateurs.
Moi ce que je fais en général pour conserver un accès o(n) c'est que je créer une variable entière dans la classe de l'élément qui est la position de l'élément dans le vecteur et ensuite je crée une std::map qui me permet de retrouver son rang.

std::map : chaque élément est associé à une clé, on pourrait par exemple associer à chaque élément une position de l'élément dans un std::vector et dans ton cas c'est ce que je ferais, chaque clé doit être unique et les éléments sont trié par ordre croissant des clés, par contre, une même valeur peut avoir deux clé différentes.

std::multimap : même chose que pour std::map mais plusieurs éléments peuvent être associé à une même clé. (Les clés peuvent donc ne pas être unique)

std::unordered_map : même chose que pour std::map mais les éléments ne sont pas triés.

Au sujet des sets, ils sont similaires aux std::map, à la différence que, dans un set les éléments doivent être unique donc un même élément ne peut pas être ajouté deux fois.

Donc le choix est facile à faire :

-Liste dynamique => std::vector.
-Tableau associatif avec clé unique et avec tri des éléments => std::map.
-Tableau associatif avec clé multiple => std::multimap.
-Tableau associatif avec éléments non triés => std::unordered_map.
-Tableau associatif avec élément unique => std::set ou bien std::unordered_set ou bien std::multiset suivant le cas dans lequel on se retrouve ci-dessus.

Dans des cas plus complexe comme le tiens il est nécessaire d'utiliser plusieurs types de contenaires.

Voilà j'espère que ça pourra t'aider.

[Laugilus]

Bonjour,

Je ne sais pas pourquoi personne ne propose ça, mais si aucun container de la STL ne convient, rien ne nous empêche de faire notre propre container.

D'après le cahier des charges, on doit:
- Pouvoir insérer des éléments
- Les supprimer
- Les avoir triés ou avoir un accès rapide
- Pouvoir retrouver leur rang/index.

La solution que je propose est de maintenir deux arbres binaires. L'un serait un arbre binaire de recherche où tu enregistres tes éléments. (par exemple un std::set ferait très bien l'affaire (ou std::unordered_set si tu ne tiens pas à ce qu'ils soient triés)).

Le second (à coder à la main) serait un arbre binaire parfaitement équilibré où tous tes éléments sont sur les feuilles de l'arbre (tout en bas de l'arbre). Dans chaque noeud de l'arbre, tu stockes un pointeur vers le fils gauche, le fils droit, le parent (important) et un compteur qui indique le nombre de feuilles que contient le noeud. (Ainsi le compteur d'une feuille est à 1, le compteur de la racine est à N, le compteur d'un noeud est égal à la somme des compteurs de ses fils). C'est cet arbre qui te permettra de retrouver l'information de l'index.
En partant d'un élément de l'arbre, tu peux facilement retrouver son index en remontant dans l'arbre et en regardant le compteur de chaque noeud que tu rencontres. Ceci prend O(log N).
De même, insérer un élément dans cet arbre et en supprimer un prend un temps O(log N) (en plus d'insérer/supprimer un élément de l'arbre, tu dois maintenir les compteurs des noeuds supérieurs (ce qui prend O(log N) aussi, vu qu'il y a O(log N) noeuds supérieurs)).

Ensuite il faut faire le lien entre les deux arbres. Ceci se fait simplement en modifiant le type enregistré dans le premier arbre (std::set). Plutôt que de stocker directement tes données, tu peux stocker un std::pair<TonType, Leaf*>. Le premier élément de la pair est la donnée que tu veux enregistrer. Le second est un pointeur qui pointe vers la feuille correspondante à ton élément dans le second arbre. Ainsi pour insérer un élément dans ta structure de données, il faut d'abord que tu rajoutes une feuille au bon endroit dans le second arbre (le plus à droite possible, et bien penser à mettre à jour les O(log N) compteurs des noeuds supérieurs de la feuille), récupérer l'adresse de la feuille et la stocker avec ta donnée dans ton std::set. (A noter que tu n'as pas besoin de stocker ta donnée dans la feuille elle même, vu que tu peux y accéder via le set).

Ainsi, pour résumer:
- Insérer un élément prend O(log N)
- Supprimer aussi
- Trouver un élément prend O(log N) (ou O(1) amorti si tu utilises std::unordered_set à la place).
- Trouver le rang d'un élément prend O(log N) (il faut d'abord trouver l'élément dans le premier arbre (std::set/unordered_set), et ensuite remonter le deuxième arbre en partant de la feuille associée à l'élément (se qui permet de calculer le rang, grâce aux compteurs de chaque node)).
- Mémoire utilisée: N (premier arbre) + Nlog(N) (deuxième) = O(Nlog(N))

Le seul point noir que j'ai omis est comment maintenir le second arbre parfaitement équilibré. Le fait de pouvoir supprimer les éléments rend la chose plus complexe, mais avec un peu de réflexion ça doit être faisable.

En conclusion, je ne pense pas qu'on puisse faire mieux en terme de complexité asymptotique. Il y a peut-être une solution plus simple mais celle-là à l'air de marcher

Si tu as des questions, n'hésites pas !

[ternel]

Mais dis moi, construire une classe de constructeur, c'est bien ma proposition.
Sauf que j'ai plutot proposé un vector et un deque, le premier utilisé comme séquence gardant l'ordre d'insertion, le second pour pouvoir insérer "au bon endroit" et ainsi maintenir l'ordre mathématique souhaité.

La solution est assez simple à écrire.

Une fois faite, il faut en améliorer les performances.
Il convient alors de remplacer le deque par un multiset (qui est un arbre)

[Laugilus]

Désolé si j'ai offensé quelqu'un ce n'était nullement mon intention. Je cherchais juste à montrer une solution, qui est il faut l'admettre assez complexe à implémenter.

En revanche elle a l'avantage d'avoir une bonne complexité asymptotique (en comparaison avec un vecteur et un deque où les opérations d'insertion au milieu et de suppression sont en O(n)).

Après il ne faut pas forcément se fier à la complexité asymptotique, mais voir en pratique les temps d'exécution, et chercher quel et le meilleur compromis entre facilité d'implémentation/maintenance et performance.

Encore une fois désolé si j'ai offensé quelqu'un, je voulais seulement montrer une bonne solution d'un point de vue théorique.

[ternel]

Mais il n'y a pas d'offense, rassure-toi
J'ai peut-être été un poil sec, désolé.

Un deque pour l'ordre d'insertion permet d'insérer au bout en temps constant, et un parcours assez léger à coup d'itérateur.

La seconde collection est dépendant de la nature du besoin.

[Invité]

Implémenter son propre container est plus compliqué moi je partirais plutôt sur une std::map avec l'index de l'élément et l'élément.

[ternel]

Si tu les regroupe dans une classe, et propose quelques méthodes bien choisies, tel que begin et end en délégation au deque et at en délégation à la map, tu as déjà fais les trois quarts du conteneur.
Reste à coder add(), et éventuellement remove(), si le besoin s'en fait sentir.
Plus size() en demandant à l'une ou l'autre des collections (vérifier les performances).

Si cela te parait compliqué, alors fais-le. Ça ne dois pas être si difficile.
Je vais d'ailleurs m'empresser d'en coder une version de mon côté, histoire de vérifier que je ne dis pas n'importe quoi.