Discussion :

[Eames38]

Bonjour,

Je cherche une liste /unique/non-ordonnée/ de int. C'est à dire qu'elle conserve l'ordre d'entrée des éléments.

A la base j'utilise std::set, mais cette dernière ordonne la liste (ordre croissant). J'ai donc essayé unordered_set de <tr1/unordered_set>, sauf qu'elle ne réagit pas comme je le souhaitais. En effet, la liste range aussi dans l'ordre croissant.

Ensuite j'ai voulu voir si il y avait une différence avec unordered_set de Boost, mais je n'arrive pas à l'implémenter dans mon compilateur.

Connaissez vous une liste répondant à ce besoin? ou de Quel manière doit-je utiliser unordered_set?

Merci pour vos réponses^^

[Arzar]

Bonjour,
Je pense que ça dépend de la taille finale de la liste. Si la liste n'est pas trop grande, il vaut probablement mieux ne pas chercher les complications et utiliser un simple vecteur + une vérification à chaque nouvelle insertion que le valeur n'est pas déjà présente dans le vecteur :

Code :

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

1
2
3
4
5
6
7
8
9
bool push_back_unique(std::vector<int>& myVec, int value)
{
    if(std::find(myVec.begin(), myVec.end() == myVec.end())
   {
       myVec.push_back(value);
       return true;
   }
    return false;
}

C'est du O(n²) vu qu'il faut retraverser entièrement le vecteur à chaque nouvelle insertion pour la recherche... donc à surveiller quand même, il faudra surement être plus malin si par exemple le but final est de balancer une entière base de données dans la liste de plusieurs dizaines millions d’éléments.

[JolyLoic]

Le nom de unordered_set est assez mal choisi. Ça aurait dû s'appeler hash_set, si le nom n'avait pas posé des problèmes de compatibilité. Les données sont certes non triées, mais par contre, l'ordre d'insertion n'est quand même pas respecté.

Maintenant, pour ton problème, si j'ai en entrée :

Code :

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

1 4 1 2 1

Qu’appelles tu respecter l'ordre d'entrée ?

Code :

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

1
2
3
1 4 2
4 1 2
4 2 1

[JolyLoic]

il faudra surement être plus malin si par exemple le but final est de balancer une entière base de données dans la liste de plusieurs dizaines millions d’éléments.

Une solution un peu plus fine serait de dupliquer le stockage dans un vector (pour respecter l'ordre) et dans un set (pour faire des tests de doublon plus rapidement).

[Eames38]

En fait, Quand je fais :

Code :

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

1
2
3
4
5
6
7
maliste.insert(1);
maliste.insert(3);
maliste.insert(2);
maliste.insert(4);
maliste.insert(6);
maliste.insert(5);
maliste.insert(3);

Quand je parcours ma liste du début à la fin : 1,3,2,4,6,5,.

Pour ton exemple, ça serait 1,4,2.


Mais l'idée d'avoir un vector pour l'ordre et un set pour tester les doublons n'est vraiment pas mauvaise. Je vais la retenir^^. Mais il faut savoir que ma liste peut être composé de beaucoup d'élément...

Par contre, je voulai savoir comment on comparait deux éléments de deux listes différentes (vector et map). Sans trop détailler, mon programme renvoyai des resultats différents de ce que j'attendais. (peut être que je devrai ouvrir une autre discussion?)

Edit : la méthode qui consiste à avoir une liste set et une autre vector est vraiment pratique