Discussion :

[Alexoy82]

Bonjour à vous !

Je cherche désespérément un conteneur dont la taille est dynamique (comme un std::vector par exemple) avec la possibilité d'ajouter des éléments, de changer leur valeur, de les effacer ... etc.
La difficulté : j'ai besoin d'une fonction d'accès "inversée" qui retourne le rang d'un élément (en prenant en argument l'élément lui même).
Évidement les éléments stockés sont tous uniques .

Je ne connais pas très bien la librairie standard, j'ai fait plusieurs essais infructueux en utilisant un std::unordered_set.
Mon gros problème est que le nombre d'éléments à stocker est potentiellement très important.
Je souhaite accéder aux rangs des éléments avec une complexité constante, ou éventuellement en O(log(N)).

Voici un code fictif pour mieux expliquer ce que j'ai en tête :

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
Conteuneur_a_definir<int> toto; 
 
toto.insert(28);  // insertion des éléments dans l'ordre initiale 
toto.insert(10);
toto.insert(43);
toto.insert(79);
toto.insert(267);
toto.insert(2);
toto.insert(8);
 
cout << toto.getRank(79) << endl; // affiche "3"
 
toto.erase(79);
toto.changeValue(267,100);
 
cout << toto.getRank(100) << endl; // affiche "3"

J'espère que ma question n'est pas trop idiote et qu'elle n'a pas déjà été traitée 156 fois sur ce forum.

Merci beaucoup pour votre aide !

[renoo]

Si tu veux pouvoir les supprimer en temps qui ne soit pas linéaire alors cela ne peut être un vector. Je ne comprend pas pourquoi dans ton exemple toto.getRank(79) retourne "3" ; qu'est ce que tu appelles le rang ? Pour moi, il y a 2, 8, 10, 28, 43 avant 79 donc 79 est le 6eme ?

[bacelar]

http://stackoverflow.com/questions/4...-stl-container

[Bousk]

En dehors du fait que tu sembles vouloir un mouton noir à 6 pattes, ce qui n'existe pas. Il faut juste penser un peu "out of the box". Et surtout avoir une idée claire de ce qu'on souhaite.
Il faut toujours commencer par utiliser un std::vector, ça corrspondra à un bon 90% des cas d'utilisation.

Ensuite, on parle des cas particuliers..

La difficulté : j'ai besoin d'une fonction d'accès "inversée" qui retourne le rang d'un élément (en prenant en argument l'élément lui même).

Je souhaite accéder aux rangs des éléments avec une complexité constante, ou éventuellement en O(log(N)).

L'idéal est encore d'ajouter cet info à ton élément... on n'y pense pas assez souvent.
Si tu peux vraiment absolument pas modifier ton élément, réessaye de le modifier. Si seulement après ça sa modification est impossible, tu peux envisager une méta-class qui englobe l'élément et l'identifiant.
Si les objets sont créés dans la heap, une map<*, int> peut être utilisé.
Chacune de ces méthodes nécessite un update des identifiants en cas de modification du vector. Une classe perso utilisant vector en interne est tout indiquée.

Si tu veux pas avoir à gérer ça, reste la moins bonne solution amha, mais la plus simple et évidente tu parcours ton vector .

Évidement les éléments stockés sont tous uniques

Et tu es certain de la méthode qui assurerait l'unicité ?
Parce que vu que tu parles de set, ça semble pas trop le cas..

Mon gros problème est que le nombre d'éléments à stocker est potentiellement très important.

Rajoutons une patte au mouton.
Pourquoi ce nombre serait important ? Y'a-t-il une réelle utilité à tous les stocker en même temps ?
Parce que si c'est pour stocker 100K éléments mais n'en utiliser que 1K à la fois..

[_zzyx_]

Il faut toujours commencer par utiliser un std::vector, ça corrspondra à un bon 90% des cas d'utilisation.

J'ajouterais que les 10% de cas qu'il reste c'est souvent std::map

Les autres conteneurs je les utilise de façon très très anecdotiques. (C'est surement un tord, il doit y avoir des cas où ils m'auraient servit)

Si je comprend bien tu veux un conteneur complètement Bijectif, où on peut trouver un élément par clé et par valeur.
{0,1},{1,2},{2,4},{3,8}
Tu aurais Objet[1] = 2
et GetRank(2) =1
Ce n'est bien sur possible que si tu n'as pas de doublon.

Une solution qui vaut ce qu'elle vaut c'est d'utiliser notre amis std::find http://en.cppreference.com/w/cpp/algorithm/find

[Alexoy82]

Merci pour vos réponses nombreuses et très enrichissantes ce forum est génial !
Je vais essayer de reprendre vos propositions dans l'ordre

@ renoo -

J'ai oublié de préciser que "getRank" doit renvoyer le rang d'insertion (comme l'indice d'un vecteur) et non pas le rang de la valeur selon un trie.
Effectivement, sans cette précision .. ma question n'avait pas beaucoup de sens

@ bousk -

Je ne souhaite pas inclure l'information de rang dans mes éléments (ex : int id = mon rang) car, comme tu le dis, cela obligerait à mettre à jour les id en cas de suppression ou d'insertion d'un nouvel élément. Le parcours du vecteur pour retrouver l'élément qui m'intéresse n'est pas envisageable car elle serait trop lente : en O(N)

@ koala -

Merci beaucoup pour tes précisions sur les différents types de conteneur cela est très instructif !
Ton idée d'utiliser la fonction std::distance est très séduisante car elle a une complexité constance
Pour cela, la condition est d'utiliser un conteneur qui fonctionne avec des "RandomAccessIterator".
Si je ne me trompe pas cela limite le choix entre un std::vector et un std::deque ? du moins, dans la librairie standard ...

Il me reste cependant un dernier problème à résoudre :
Ni les std::vector, ni les std::deque ne proposent de fonction "find" permettant de retrouver un élément à partir de son contenu.
La fonction std::find est apparemment utilisable dans ce cas, mais cette fonction a une complexité en O(N) .... Arf!

Finalement, je cherche bien un mouton noir à 6 pattes
C'est à dire un conteneur :

1) disposant d'une fonction "find" efficace, comme par exemple les std::unordered_set qui retrouvent un élément en O(log(N))
2) permettant d'utiliser la fonction std::distance avec une complexité raisonnable.

D'après ce que je comprend, la fonction std::distance a une complexité en O(N) si elle n'est pas utilisée sur un std::vector ou sur un std::deque.

Connaissez-vous les conteneur de la librairie Boost ? peut-être que je pourrais y trouver mon bonheur ?

Merci vous !

[renoo]

J
Si je comprend bien tu veux un conteneur complètement Bijectif, où on peut trouver un élément par clé et par valeur.
{0,1},{1,2},{2,4},{3,8}
Tu aurais Objet[1] = 2
et GetRank(2) =1
Ce n'est bien sur possible que si tu n'as pas de doublon.

Vu sous cet angle, on a l'impression qu'une double map dans un sens et dans l'autre irait bien.

[koala01]

Salut,

De manière générale, la notion d'indice (de position) d'un élément donné dans une collection n'a réellement de sens que dans le cadre d'un tableau.

En effet, si l'on écarte de la discussion les files (principe FIFO) et les piles (principe LIFO), on se rend compte que toutes les collections permettent d'itérer sur l'ensemble de leurs éléments au travers des itérateurs obtenus par les fonction begin() et end().

Cependant, on peut classer les collections en trois grandes catégories :

• Celles qui privilégient l'accès aléatoire (en temps constant) au dépend de la vitesse d'exécution des commandes d'ajout, d'insertion et de suppression ainsi qu'au dépend des possibilités de tri (et donc de recherche d'un élément donné). Ce sont les classes std::vector (et std::array en C++11)
• Celles qui privilégient la rapidité des commandes d'ajout, de suppression et d'insertion, au dépend de l'accès en temps constant qui est rendu impossible et au dépend des possibilités de tri (et donc de recherche d'un élément donné) (std::list, pour l'essentiel)
• Celles qui privilégient le tri (et donc la recherche d'un élément donné) au dépend de l'accès en temps constant (rendu impossible) et du temps nécessaire à l'ajout ou à la suppression d'un élément car il est nécessaire de veiller à garder un arbre binaire "le plus équilibré possible" (std::map et std::set, pour l'essentiel).

Après, bien sur, il y a les collections qui tendent d'adoucir un peu les angles en déplaçant le curseur entre la rapidité d'insertion / suppression des élément et la recherche d'un élément donné (les unordred_XXX). Mais il ne s'agit au final que de classes qui essayent de tirer le meilleur parti des deux dernières catégories

Par contre, ce qu'il y a de bien, avec les itérateurs, c'est que l'on peut utiliser une fonction sympa nommée std::distance, qui nous permet de déterminer le nombre d'éléments entre lesquels il faut passer pour relier un itérateur représentant la première borne de l'intervalle à parcourir à un deuxième itérateur représentant la deuxième borne de cet intervalle.

Cette fonction est particulièrement intéressante car, si le premier itérateur fourni comme argument est celui qui correspond à la fonction begin, elle permet de connaitre le "numéro d'ordre" de l'élément représenté par le deuxième itérateur dans la collection ou, si tu travailles avec un tableau (std::array ou std::vector), de connaitre l'indice de l'élément représenté par le deuxième itérateur dans ce tableau. (notes d'ailleurs que cette fonction sera beaucoup plus rapide à l'exécution si les itérateurs sont issus d'un tableau que s'ils sont issus de n'importe quel autre type de collections )

Et comme le seul type de collection qui te permettra l'accès en temps constant aux éléments qu'elle contient, il y a peut être "quelque chose à faire", car, autrement, tu seras de toutes façons obligé de créer une boucle comptant le nombre d'éléments par lesquels tu dois passer avant d'atteindre celui que tu recherches...

Dans une std::list (ou toute autre collection appartenant à la deuxième catégorie que je viens de citer), l'utilisation d'une boucle basée sur un compteur sera peut-être plus intéressante que la comparaison des différents éléments (en fonction du temps nécessaire à la comparaison), mais, dans une std::map ou un std::set (ou, de manière générale, toute collection appartenant à la troisième catégorie que j'ai citée), tu remplacera une recherche en O(log(n)) par un accès itératif en O(n)... A moins que la comparaison de la clé (ou de ce qui sert de clé) ne prenne énormément de temps, l'accès itératif sera très vraisemblablement (toutes choses étant par ailleurs égales) sub-optimal en termes de performances

Dés lors, la question qui tue est "pourquoi voudrais tu récupérer l'indice à laquelle se trouve une donnée particulière, sachant qu'il risque d'être invalidé par l'insertion ou par la suppression d'un élément dans la collection"