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..

[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"

[_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 !

[ternel]

Au besoion, il y a moyen de tripatouiller.
Par exemple, dans la lib standard de Java, ils se sont "amusés" à créer une LinkedHashMap.
la hashmap est notre unordered_map.
C'est un conteneur associatif trié par un calcul de hash, et rangé dans un tableau. L'astuce étant d'avoir le hash qui remplisse le tableau comme il faut.

Sauf que comme c'est trié "sous le capot", ils ont rajouté une liste dans la classe, pour pouvoir itérer dans l'ordre d'insertion

Tu peux éventuellement faire pareil: avoir un conteneur dédié au stockage, et un à la recherche.

[koala01]

Merci beaucoup pour tes précisions sur les différents types de conteneur cela est très instructif !

C'était le but

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 ...

En effet... Sans oublier std::array (C++11)... Mais commme c'est un tableau de taille fixe (connue à la compilation), il ne semble définitivement pas adapté à ton problème

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!

C'est pour cela que tu dois essayer de déterminer ce que tu fera le plus souvent avec tes données :
Vas-tu utiliser essentiellement l'accès aléatoire? ==> std::vector
Veux tu que tes données soient triées, pouvoir les retrouver facilement ? ==> std:unordered_)map et autres std:unordered_)set
Beaucoup d'insertions, de suppressions, accès essentiellement itératif, peu de recherche, tri non obligatoire? std::list

Notes que, pour la plupart des conteneurs, la fonction distance a beau être d'une complexité en O(n),elle ne fait que tester l'égalité entre deux itérateurs, ce qui fait qu'elle reste relativement rapide (comparé à d'autres comparaisons qui pourraient être possibles

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.

Ouaip... Mais bon, avec les progrès de la génétique moderne, tout devient possible .

Par exemple, tu peux envisager de le créer (attention, cela se fera au dépend de la vitesse d'ajout, car il faudra remettre les liens à jour à chaque ajout ou suppression d'un élément!!!)
Un code proche de

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MySixLegsSheep{
public:
/* C++11 */
    using Key = int;
    using Value = std::string;
    using const_iterator = typename std::map<Key, Value>::const_iterator;
    Value & operator[] (size_t index){
        assert(index< constantAcess_.size());
        return *(constantAccess_[index]);
    }
    Value const & operator[] (size_t index) const{
        assert(index< constantAcess_.size());
        return  *(constantAccess_[index]);
    }
    const_iterator find(Key const & k)const{
        return sorted_.find(k);
    }
    size_t indexOf(Key const & k) const{
        const_iterator found=find(k);
        if(found == end())
            return std::numeric_limits<size_t>::max();
        return std::distance(sorted_.begin(), found);
    }
    const_iterator begin() const{return sorted_.begin();
    }
    const_iterator end() const{return sorted_.end();}
    void add(Key const & k, Value const & value){
        sorted_.insert(std::make_pair(k, value));
        if(sorted_.size() < constantAccess_.size()){
            constantAccess_.clear();
            constantAccess_.reserve(sorted_.size());
            for (auto & it : sorted_){
                constantAccess_.push_back(&(it.second));
            }
        }
    }
    /* d'autres fonctions sont envisageables (erase(Key const &) ?) */
private:
    std::map<Key,Value> sorted_; // Collection utilisée pour la recherche
    std::vector< Value *> constantAccess_; // les accès constants
};

(modifie l'alias Key et Value en fonction de tes besoins, penses aux pointeurs intelligent si la valeur a sémantique d'entité )
qui pourrait être utilisé sous une forme proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
   MySixLegsSheep collection;
   collection.add(1,"salut");
   collection.add(5,"hello");
   collection.add(10,"monde");
   collection.add(-10,"monde");
   for(auto const & it:collection ){
        std:: cout<<it.first<<" "<<it.second<<"\n";
   }
   std::cout<<collection.indexOf(-10)<<"\n";
   std::cout<<collection.indexOf(-5)<<"\n"; //un indice invalide ;)
   std::cout<<collection.indexOf(5)<<"\n";
}

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.

C'est normal : la il n'y a -- une fois encore -- que les tableaux (de taille fixe ou non) qui proposent l'accès aléatoire aux différents éléments. Du coup, il n'y a que pour les tableau que l'on peut simplifier le calcul en se disant que la distance qui sépare deux éléments du tableau correspond à la différence entre l'adresse mémoire du deuxième élément fourni et celle du premier.
Pour tous les autre, la fonction distance est malheureusement obligée de compter le nombre d'éléments par lesquels on doit passer pour rejoindre le deuxième élément

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

boost::multi_index devrait pouvoir t'aider un peu, car elle permet de trier des données selon différents critères (attention, il y a toujours un critère "principal" )

[stendhal666]

Le cahier des charges n'est pas tout à fait clair: si je comprends bien l'essentiel est de pouvoir connaître le rang d'insertion dans le temps le plus court possible? La seule possibilité pour l'avoir en temps constant est la table de hachage (unordered map) où la clé est l'élement et le rang d'insertion la valeur.

Néanmoins, si on supprime des éléments, il faut mettre à jour les liens à chaque fois. Plutôt que de combiner deux conteneurs (emprunte mémoire doublée, maintenance difficile), j'envelopperais unordered_map dans une classe qui tiendrait l'historique des suppressions et modifierait le rang retourné en conséquence. En choisissant la façon la plus simple de tenir l'historique (un vecteur non trié), la vitesse d'accès passe à O (1+M) où M est le nombre de modifications faites. C'est un bon compromis si le nombre de valeurs dépasse très largement le nombre de suppressions.

Le vecteur contiendrait le rang des éléments supprimés de façon à diminuer les rangs supérieurs. Par exemple, si l'historique des suppressions est { 9, 5, 12 } et qu'on cherche le rang d'insertion de 75 qui, d'après la table est 13, on le réduit de 3.

Une optimisation simple serait de stocker l'historique dans un ordered_set pour ne pas itérer sur les valeurs supérieures au rang d'insertion retourné par la table. La complexité est alors O(1+m) où m est le nombre de suppressions d'éléments dont le rang est inférieur au rang de l'objet recherché.

Pour changer un élément, bien que la hashmap ne soit pas faite pour, ce n'est pas difficile:

Code :

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

1
2
3
4
void changeValue(int oldKey, int newKey) {
  hashMap[newKey] = hashMap[oldKey] // on conserve le rang d'insertion
  hashMap.erase(oldKey); // c'est bien erase? je ne me souviens plus
}

[koala01]

Le cahier des charges n'est pas tout à fait clair: si je comprends bien l'essentiel est de pouvoir connaître le rang d'insertion dans le temps le plus court possible? La seule possibilité pour l'avoir en temps constant est la table de hachage (unordered map) où la clé est l'élement et le rang d'insertion la valeur.

Néanmoins, si on supprime des éléments, il faut mettre à jour les liens à chaque fois. Plutôt que de combiner deux conteneurs (emprunte mémoire doublée, maintenance difficile), j'envelopperais unordered_map dans une classe qui tiendrait l'historique des suppressions et modifierait le rang retourné en conséquence. En choisissant la façon la plus simple de tenir l'historique (un vecteur non trié), la vitesse d'accès passe à O (1+M) où M est le nombre de modifications faites. C'est un bon compromis si le nombre de valeurs dépasse très largement le nombre de suppressions.

En plus, il reste un autre problème: le risque d'ajout d'un élément après en avoir supprimé un ou plusieurs.

Tu ne peux en effet pas ignorer le risque que l'utilisateur décide de rajouter deux éléments, d'en supprimer trois, avant d'en rajouter cinq nouveaux... Comment vas tu déterminer "le rang d'insertion" des cinq derniers éléments ajoutés

• En fonction de la taille de la map mais, alors, tu (risques) d'avoir plusieurs clé associées à une seule et même valeur Comment faire la différence, dans ce cas
• En maintenant le nombre total des élément ajouté à ton unordered_map Ce serait dommage car cela fait sans doute double usage.

Sans oublier qu'il faut alors que chaque élément soit en mesure de "maintenir l'historique" qui s'applique réellement pour lui afin d'appliquer la modification exacte qui permettra de retrouver son indice réel .

Cela signifie sans doute de parcourir tous les éléments présents dans la collection afin de "mettre à jour" leur historique, ce qui n'est pas forcément mieux que de re-remplir un tableau de pointeurs, d'autant plus qu'un tableau de pointeur a malgré tout une emprunte mémoire relativement faible vu qu'elle n'est que de (nombre d'éléments * sizeof(ptr_t) ) (aux quelques valeurs supplémentaires requises pour la gestion dynamique de la mémoire)

L'emprunte mémoire nécessaire au maintient de l'historique de chaque élément -- quelle que soit la manière envisagée pour y arriver -- sera à mon sens bien plus importante

[stendhal666]

En plus, il reste un autre problème: le risque d'ajout d'un élément après en avoir supprimé un ou plusieurs.

Je ne pense pas que cela pose problème.
Le rang d'insertion conservé dans la table est déterminé par un compteur incrémenté à chaque insertion; il est totalement indépendant des suppressions.
Par exemple, si on entre 5 éléments, qu'on en supprime 3, puis qu'on en ajoute 3 nouveaux, il seront numérotés 6, 7, et 8. Lorsqu'on soustrait l'historique des modifications, on retrouve 3, 4 et 5.

Sans oublier qu'il faut alors que chaque élément soit en mesure de "maintenir l'historique" qui s'applique réellement pour lui afin d'appliquer la modification exacte qui permettra de retrouver son indice réel .

Non, c'est le conteneur qui tient l'historique.

Un prototype de classe serait peut être plus clair:

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
18
19
20
21
22
23
24
25
26
27
28
29
class Ranker // cool, comme nom?
{
  int counter;
  std::unordered_map<int, int> hash;
  std::vector<int> historique;
 
  int offset(int rank) {
    return std::count_if(historique.begin(), historique.end(), [](int modif) { return modif < rank } );
  }
 
  public:
 
  Ranker() : counter(0) {}
 
  int getRank(int elem) {
     int rank = hash[elem];
     return rank - offset(rank);
  }
 
  void addElem(int elem) {
    hash[elem] = ++counter;  // first rank is 1
  }
 
  void deleteElem(int elem) {
    historique.push_back(hash[elem]);
    hash.erase(elem);
  }
 
};

[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]

Je ne pense pas que cela pose problème.
Le rang d'insertion conservé dans la table est déterminé par un compteur incrémenté à chaque insertion; il est totalement indépendant des suppressions.
Par exemple, si on entre 5 éléments, qu'on en supprime 3, puis qu'on en ajoute 3 nouveaux, il seront numérotés 6, 7, et 8. Lorsqu'on soustrait l'historique des modifications, on retrouve 3, 4 et 5.



Non, c'est le conteneur qui tient l'historique.

Ah??? et comment vas tu déterminer à quel élément s'applique quelle partie de l'historique ???

Si tu applique l'historique "sans distinction" à tous les élément, tu vas avoir bobo car on ne peut pas préjuger de quels éléments seront supprimés .

Si tu supprimes trois éléments, ce sont peut être ceux pour lesquels les indices d'origine étaient 0,1 et 2... tout comme cela peut être ceux dont les indice d'origine étaient 1, 3 et 4 ou ... n'importe quelle autre combinaison

Dés lors, si tu applique "simplement" l'historique à tous tes éléments, ton calcul d'indice sera faussé pour tous les éléments qui "précèdent" (dans l'ordre d'itération) l'élément qui a été supprimé. Ainsi, le premier élément que tu as mis à l'origine dans ta collection a -- s'il n'a pas été retiré -- l'indice d'origine 0, auquel tu vas vouloir retirer 3 (le nombre d'éléments que tu as retiré depuis le début), ce qui devrait te donner un indice négatif. Mais comme l'indice est une valeur non signée, tu obtiens un indice équivalent à std::numeric_limits<size_t>::max() -3. Et cette valeur est très largement supérieure à la taille de ta collection

Donc, dans le meilleur des cas, il faut que chaque élément de ta (unordreded_)map sache exactement quelles sont les modifications de la collection qui ont eu un impact sur son indice d'origine. L'avantage, c'est que l'historique peut en réalité se limiter à une simple valeur numérique signée, pour autant que l'on veille à l'incrémenter de 1 si l'insertion a pour effet de "repousser" un élément donné d'une place et à la décrémenter de 1 si la suppression d'un élément a pour effet de le "rapprocher du début" d'une place.
Nous pourrions donc envisager une classe proche de

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
class MySixLegsSheep{
    struct Data{
        size_t originalIndex;
        int moves;
        size_t calculatedIndex() const{
            return originalIndex + moves;
        }
    };
public:
    using const_iterator = typename std::map<std::string, Data>::const_iterator;
    void add(std::string const & toadd){
        if(items_.find(toadd) ==items_.end()){
            items_.insert(std::make_pair(toadd, Data()));
            auto it = items_.find(toadd);
            it->second.originalIndex = std::distance(items_.begin(),it);
            ++ it;
            while(it != items_.end()){
                ++(it->second.moves);
                ++ it;
            }
        }
    }
    void erase(std::string const & torem){
        auto found = items_.find(torem);
        if(found!= items_.end()){
            auto it = items_.erase(found);
            while(it!= items_.end()){
                --(it->second.moves);
                ++it;
            }
        }
    }
    size_t indexOf(std::string const & tofind) const{
        auto it = items_.find(tofind);
        if(it == items_.end())
            return std::numeric_limits<size_t>::max();
        return it->second.calculatedIndex();
    }
    std::string const & operator[](size_t index) const{
        assert(index < items_.size());
        auto it = items_.begin();
        for(int i = 0;i<index; ++i)
            ++it;
        return it->first;
    }
    const_iterator begin() const{
        return items_.begin();
    }
    const_iterator end() const{
        return items_.end();
    }
private:
    /* Note :j'ai choisi map, par facilité, on peut choisir n'importe quel autre conteneur associatif clé / valeur
     * et j'ai choisi de maintenir des std::string, mais on peut choisir n'importe quoi comme clé du moment
     * qu'il est possible d'appliquer l'opérateur <
     */
    std::map<std::string, Data> items_;
};

qui pourrait être utilisée sous une forme proche de

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
int main(){
   MySixLegsSheep collection;
   collection.add("salut");
   collection.add("hello");
   collection.add("monde");
   collection.add("world");
   for(auto const & it:collection ){
        std:: cout<<it.first<<" "<<"\n";
   }
   std::cout<<collection.indexOf("salut")<<"\n";
   std::cout<<collection.indexOf("world")<<"\n";
   std::cout<<collection.indexOf("monde")<<"\n";
   std::cout<< collection[0]<<"\n";
   std::cout<< collection[1]<<"\n";
   std::cout<< collection[2]<<"\n";
   return 0;
}

MAIS!!!!!
Il faut savoir que, à partir du moment où l'on ne place pas les différents éléments dans un tableau (quel qu'il soit), la messe est dite.... On ne pourra pas avoir un accès en temps constant à un élément de la collection. L'opérateur [], quelle que soit la forme qu'il prendra, sera au mieux un sucre syntaxique cachant une recherche en O(log(n) ) (si l'argument est du type de la clé utilisée), au pire des cas un sucre syntaxique cachant une boucle de parcours itérative de complexité en O(n) ou n est l'indice utilisé (si on n'a pas la chance de pouvoir profiter de la recherche en O(log(n) ) ).

Alors, bien sur, les tables de hashages pourront sans doute améliorer un peu les choses, mais il n'empêche que l'on restera très loin de l'accès en temps constant (parce que, quoi qu'il arrive, les tables de hashage sont spécialisées pour faciliter la recherche et non pour permettre l'accès en temps constant).

C'est, d'une certaine manière, la raison pour laquelle je suis farouchement opposé à l'utilisation de l'opérateur [] d'une std::map, car il ne s'agit que d'un sucre syntaxique mis à la place de la fonction find et qui, de plus, provoque la création d'une paire clé / valeur (dont la valeur est construite par défaut !!) si la clé est inexistante

[Alexoy82]

Vous m’impressionnez par la qualité de vos réponses Merci beaucoup pour votre aide !

Voici quelques précisions sur le code que je suis en train d’écrire (modulo quelques simplifications).

J’ai besoin de gérer une collection d’éléments en maintenant :
A) l’ordre d’insertion des éléments (au sens d’une liste chainée)
B) l’ordre des valeurs des éléments (un trie)

Voici la première classe qui décrit le contenu d’un élément :

Code :

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

1
2
3
4
5
6
7
class element
{
public:
	double value;									// valeur stockee
	element * prevInterval;							// pointeur vers l'intervalle précédent
	element * nextInterval;							// pointeur vers l'intervalle suivant
};

Ayant besoin de trier des éléments selon leur valeur, j’ai implémenté la structure suivante :

Code :

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

1
2
3
4
struct Ptr_Comp
{
	bool operator()(const element * lower, const element * bigger) const {return lower->value < bigger->value;}
};

Et enfin, voici la classe qui gère la collection d’éléments avec les complexité de chaque fonction membre :

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
18
19
20
21
22
class LinkedSortedList {
 
private:
 
	multiset<element*,Ptr_Comp> sortedList; 	// les éléments triés par valeur
	element * firstElement; // début liste chainée
	element * lastElement;	// fin liste chainée
	unsigned int size;		// taille de la collection 
 
public:
 
	LinkedSortedList();
	virtual ~LinkedSortedList();
	void pushBack(double value); // ajout d'un élément en fin de chaine			=> O(log(N))
	double getMinValue(); // retourne le plus petite valeur 						=> O(1)
	unsigned int  getMinId(); // retoune l'id de l'intervalle comportant la plus petite valeur 	=> O(N) Arf!!. 
	element * getAddressLowerElement(); // retourne l'adresse de l’élément le plus petit 		=> O(1)
	element * getAddressElementById(unsigned int id); // retourne l'adresse du ième intervalle	=> O(N)
	void erase(element * element); // supprime un élément 								=> O(1)
	element * setValue(element * element, double value); // change la valeur d'un élément 		=> O(log(N))
	void insertAfter(element * element, double value); // O(log(N))
};

Comme vous pouvez le constatez, il me reste deux fonctions en O(N) :

La fonction «getAddressElementById» est très facile à passer en O(1) en utilisant un std::vector<element*>

En revanche, la fonction «getMinId» est beaucoup plus pénibles à optimiser !
Le multiset «sortedList» possède l’intérateur .begin() qui correspond au plus petit l’élément.
Je transforme cet intérateur en pointeur «element*» de la façon suivante : prt = (*sortedList.begin())
En suite, je parcours la liste chainée à la recherche de ce pointeur pour en déduire l’id du plus petit élément.

Bof ! cette recherche est en O(N) et cette fonction est très fréquemment utilisée dans mon code (je suis triste !)

Je ne sais pas comment fonctionnent les hashmap ?
Peut être que ce type de conteneur pourrait m’aider à faire le lien entre un pointeur «element*» et un id ?
Le fait que de les éléments puissent être insérés, supprimés, modifiés ne semble pas faciliter la tâche

@ koala - Ta classe «MySixLegsSheep» me paraît sympa, mais j’avoue que je ne comprend pas bien ton code
ça dépasse mon niveau en C++
pourrais tu en expliquer les grandes lignes ?

Encore merci à vous tous !

[stendhal666]

@koala: l'historique contient le rang d'insertion des éléments supprimés; on applique donc la "réduction de rang" aux éléments qui sont postérieurs aux éléments supprimés:

Si tu supprimes trois éléments, ce sont peut être ceux pour lesquels les indices d'origine étaient 0,1 et 2... tout comme cela peut être ceux dont les indice d'origine étaient 1, 3 et 4 ou ... n'importe quelle autre combinaison

mettons que ce soit les élements de rang 1, 3 et 4 qui aient été supprimés et qu'on interroge la hashmap pour l'élément inséré en premier (rang 0): l'historique ne contient que des éléments postérieurs, donc aucune réduction ne sera appliquée. Si ce sont les éléments de rang 0, 1 et 2 qui ont été supprimés et que l'on demande l'élément inséré en 4ème, alors, au contraire, tous les éléments supprimés sont antérieurs et la réduction est de 3. Ce n'est pas plus compliqué que cela...

N'hésite pas à regarder mon code d'un peu plus près avant d'être si catégorique!

@Alexoy:
- le principe des hashmap est le suivant: ce sont de grands tableaux où chaque valeur est stockée à un indice calculé par une fonction de hachage qui prend comme input la clé associée.
Ex: une table de hachage avec comme clé un nom, comme valeur un numéro de téléphone.
Durand -> fonction de hachage -> 26: le numéro de Durand sera stocké à l'indice 26 du tableau sous-jacent.
Du coup la recherche se fait en O(1)
-

J’ai besoin de gérer une collection d’éléments en maintenant :
A) l’ordre d’insertion des éléments (au sens d’une liste chainée)
B) l’ordre des valeurs des éléments (un trie)

Alors je modifie un peu mon conseil: tu devrais passer par une "ordered map" (std::map). Elle est implémentée en arbre binaire, donc les clés restent toujours triées.
La recherche est en O(log N) et avec mon système d'historique, retrouver le rang d'insertion est en O(log N + M) où M est le nombre de modifications.

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
 
class Ranker {
 
	int counter;
	std::map<int, int> omap;
	std::vector<int> historique;
 
	int offset(int rank) {
		return std::count_if(historique.begin(), historique.end(), [rank](int modif) { return modif < rank; });
	}
 
public:
 
	Ranker() : counter(0) {}
 
	void insert(int elem) {   // O(log N)
		omap[elem] = counter++;
	}
 
	int getRank(int elem) {  // O(log N + length(historique)) 
		int rank = omap[elem];
		return rank - offset(rank);
	}
 
	void erase(int elem) {  // O(log N)
		historique.push_back(omap[elem]);
		omap.erase(elem);
	}
 
	void changeValue(int old, int nov) { // O(log N) 
		omap[nov] = omap[old];
		omap.erase(old);
	}
 
	std::map<int, int>::iterator begin() { return omap.begin(); }
	std::map<int, int>::iterator end() { return omap.end(); }
};
 
int main(int argc, char* argv[])
{
	Ranker 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);
 
	std::cout << toto.getRank(79) << std::endl; // affiche "3"
 
	toto.erase(79);
	toto.changeValue(267, 100);
 
	std::cout << toto.getRank(100) << std::endl; // affiche "3"
 
        for (auto elem : toto) std::cout << elem.first << ' '; // affiche 2 8 10 28 43 100
	std::cout << std::endl;  
 
	char c;
	std::cin >> c;
	return 0;
}

testé et approuvé

[Alexoy82]

@ stendhal666 -

Le système d'historique que tu proposes est intéressant mais dans mon cas je dois faire les opérations suivantes :

N fois : insertion d'un élément,
N fois : accès d'un id à partir d'un pointeur "element*"
N fois : suppression d'un élément
n fois (avec n << N) : accès d'un pointeur "element*" à partir d'un id

La valeur de N peut être très grande !
Mon but est d'écrire un code optimisé, c'est pour cela que j'ai choisi d'écrire mon projet en C++

Malheureusement la solution que tu proposes est en O(N) puisque : puisque M = N dans ce cas ...

Finalement, je pense qu'il faut absolument éviter d'écrire les rangs (ou les modifications de rang) c'est trop couteux !

Peut-être qu'il n'y a pas de solution à mon problème
Snif !

[stendhal666]

Peut-être qu'il n'y a pas de solution à mon problème

On doit bien pouvoir trouver qqc...

N fois : insertion d'un élément,
N fois : accès d'un id à partir d'un pointeur "element*"
N fois : suppression d'un élément
n fois (avec n << N) : accès d'un pointeur "element*" à partir d'un id

Est-ce que tu pourrais expliquer ton but? je veux dire, l'objet du programme? Cela permettrait peut-être de trouver une solution appropriée. A mon avis, si tu supprimes les N éléments que tu insères, c'est du côté de l'algorithme, pas de la structure de donnée, qu'il faut chercher...

[Alexoy82]

@ stendhal666 - ça va être (très) compliqué à expliquer sur un forum, je suis en train d'implémenter une méthode statistique.
Sans entrer dans le détail, le but est d'apprendre un modèle à partir d'un échantillon de données.
Dans mon cas, le N correspond à la taille du jeu de données qui peut atteindre des millions d'observations ...
C'est pour cette raison que je dois faire très attention aux complexités de mes fonctions.

Pour faire simples j'ai deux structures :

A) le modèle statistique
B) les éléments nécessaire à l'optimisation du modèle (utilisés par un algorithme d'optimisation)

J'ai besoin de faire "communiquer" ces deux structures, d'où mon besoin de récupérer un "id" à partir d'un pointeur ...

La solution ultime consisterait à faire une seule structure qui englobe A et B ... Dans ce cas, je devrait tout réécrire ce qui représente plusieurs mois de travaille !
De plus le code serait beaucoup moins lisible ...

Je me sens bête de ne pas avoir anticipé ce problème

[stendhal666]

Sans entrer dans le détail, le but est d'apprendre un modèle à partir d'un échantillon de données.

Du machine learning? very interesting!

ça va être (très) compliqué à expliquer sur un forum

Dommage, ça avait l'air très intéressant!

Je me sens bête de ne pas avoir anticipé ce problème

Eh bien c'est en forgeant qu'on devient forgeron!

J'ai besoin de faire "communiquer" ces deux structures, d'où mon besoin de récupérer un "id" à partir d'un pointeur ...

Présenté comme ça, c'est un peu trop abstrait... Pourrais-tu décrire en pseudo-code les parties les plus importantes de ton programme? Disons au moins celles qui concernent l'insertion / la recherche / la suppression des données?