Quel container STL utiliser pour un ensemble d'éléments dont l'ordre est arbitraire ?

Version imprimable

19/12/2018, 14h44
Daikyo

Quel container STL utiliser pour un ensemble d'éléments dont l'ordre est arbitraire ?

Bonjour,

Je dois manipuler un ensemble d'éléments dont l'utilisateur peut modifier l'ordre.
Je cherche donc à savoir quel container STL utiliser sachant que l'ordre des éléments doit pouvoir changer à la guise de l'utilisateur et comment effectuer de telles opérations.
Chaque nouvel élément peut être ajouté au début ou à la fin du container, peut importe, il ne sera jamais inséré au milieu en tout cas. L'utilisateur pourra cependant ensuite le replacer.

Ex: A B C D E
A C B D E
A C D E B
etc...

Je vous remercie.
Cordialement,
19/12/2018, 15h10
foetus

std::deque :koi: :koi:

Bonjour,

A priorio deque semble pas mal : https://fr.cppreference.com/w/cpp/container/deque

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::deque<int> d;
 
d.push_back(50);
d.push_back(60);
d.push_back(70);
 
d.push_front(30);
d.push_front(10); // not inserted at the correct position
d.push_front(20);
 
std::cout << "Initial" << std::endl;
for (const auto& e :d) {
	std::cout << e << std::endl;
}
 
std::swap(d[0], d[1]); // swap inverted elements
 
std::cout << "Final" << std::endl;
for (const auto& e :d) {
	std::cout << e << std::endl;
}

19/12/2018, 16h16
Daikyo

Bonjour et merci de votre réponse.

Je ne désire pas faire de swap entre deux éléments mais bien déplacer un seul élément afin de "l'insérer" ailleurs dans le conteneur.
19/12/2018, 16h25
koala01

Salut,

Par défaut, à partir du moment où tu n'as pas besoin d'un container associatif, tu vas systématiquement utiliser std::vector ou std::deque, en donnant une préférence au deuxième si tu dois régulièrement insérer un nouvel élément entre deux éléments existants.

Si tu ne dois insérer un nouvel élément entre deux éléments existants, ou que tu peux te "contenter" d'ajouter les nouveaux éléments à la fin de la collection, std::vector fera le taf sans grosses difficultés, surtout si tu a pris soin de définir une capacité "suffisante" que pour qu'il n'ait pas besoin de l'augmenter "sans arrêt" ;)
19/12/2018, 17h17
Bktero

Citation:

Envoyé par Daikyo

Je ne désire pas faire de swap entre deux éléments mais bien déplacer un seul élément afin de "l'insérer" ailleurs dans le conteneur.

Donc ça veut dire suppression puis ajout au milieu... Ce qu'on n'avait normalement pas à faire :aie:

Bon ça tombe bien deque a insert() : https://fr.cppreference.com/w/cpp/co...r/deque/insert
19/12/2018, 17h42
Daikyo

D'accord donc il n'existe rien dans la STL qui fait directement ce genre de chose, tel un std::move ou autre...
Je dois donc le faire à la mano (suppression puis insertion), c'était ce que je voulais savoir.
Je vous remercie!
19/12/2018, 20h20
koala01
Citation:

Envoyé par Daikyo

D'accord donc il n'existe rien dans la STL qui fait directement ce genre de chose, tel un std::move ou autre...
Je dois donc le faire à la mano (suppression puis insertion), c'était ce que je voulais savoir.
Je vous remercie!

Attention!!!

Ta question portait à la base sur le type de conteneur / collection que tu pouvais utiliser. Il se fait que les différents conteneurs fournissent une implémentation de notions telles que
- tableau d'élément contigus
- pile
- file
- liste
- arbre binaire
qui présentent tous des avantages et des inconvénients en termes de complexité algorithmique des "opérations de base" (ajout, suppression, insertion, accès, recherche) :
Tn tableau par exemple sera très efficace pour permettre l'accès à un élément donné de manière aléatoire : cela te prendra exactement le même temps de passer du troisième élément au quatrième que de passer du troisième élément au 10 000 eme (en évitant les neuf milles neuf cents et quelques qu'il y a entre les deux)

L'ajout (après le dernier élément existant) et la suppression du dernier élément se fera également relativement vite, du moins, tant que le tableau ne devra pas augmenter sa capacité. Mais la suppression et -- surtout --l'ajout d'un élément "au beau milieu" demandera un temps proportionnels au nombre d'éléments qui devront être décalés pour "faire de la place" à l'élément qui doit être rajouté.

La pile et la file présente les restrictions classiques des systèmes LIFO et FIFO

La liste sera beaucoup plus efficace pour l'ajout ou la suppression d'un élément quel que soit l'endroit où elle survient (pour autant que cet endroit ait été atteint avant de la tenter), mais sera particulièrement inefficace en cas d'accès à un élément choisi de manière aléatoire, car il sera proportionnel au nombre d'élément à "traverser"

Les arbres binaires sont particulièrement efficaces lors de la recherche, mais les autres opérations prennent énormément de temps

std::move n'a absolument rien à voir avec ce genre de problématique, mais plutôt avec celui de (ne pas) copier un objet dont la copie prendrait "trop de temps" (ou ne serait carrément pas possible) en décidant de "vampiriser" les ressources qui le composent pour le donner à un autre élément.

Citation:

Envoyé par Daikyo

Bonjour et merci de votre réponse.

Je ne désire pas faire de swap entre deux éléments mais bien déplacer un seul élément afin de "l'insérer" ailleurs dans le conteneur.

tu t'exprimes mal sur ce coup, car, ce que tu veux réellement faire, ce n'est pas "déplacer" mais ... "supprimer" un élément afin de pouvoir le réinsérer ailleurs.

Sauf si tu veux effectivement permuter deux éléments (auquel cas, il s'agit bel et bien d'un swap)

En théorie, la notion qui présente la meilleure complexité pour les actions que tu veux entreprendre serait sans doute la liste (et son implémentation [c]std::list[/]) car insertion et suppression se font avec une complexité en temps constant (O(1) ) avec les listes.

Le problème, c'est que, en te focalisant sur cette pair d'actions particulière, tu laisses peut-être l'arbre te cacher la forêt, et que le gain que tu obtiens pour cet action n'est pas gratuit : les autres actions seront plus lentes. je ne sais pas quelle est ta situation, mais il me semble important que tu te poses la question de savoir si le gain que tu espère vaut réellement le prix que cela va te coûter:

Si c'est pour déplacer un élément toutes les cinq minutes, alors que tu dois accéder à un élément quelconque (qui n'est peut être pas celui qui est juste à coté de celui sur lequel tu te trouves) toutes les demis-secondes, tu perdras au change, parce que tu gagnera -- certes -- "un peu de temps" lors du déplacement de l'élément, mais tu en perdra "un max" sur le parcours "classique" des éléments de ta collection.

La première question que tu devrais donc te poser ici -- et à laquelle seul un profilage de ton application pourra répondre -- est donc : est-ce que je passe "suffisamment de temps" à déplacer les éléments de ma collection pour que cela vaille effectivement la peine d'essayer de rendre ce processus plus rapide :question:

Autant dire que la réponse ne pourras -- de toutes évidences -- être "oui" que si tu passes réellement le plus clair de ton temps à exécuter de tels déplacements.

Si ce n'est pas le cas, tu as sans doute bien plus intérêt à choisir le type de conteneur le plus adapté à l'action que tu exécute "le plus souvent" sur le conteneur ;)