ajouter un élément dans une liste avec un tri d'insertion: possible dans la STL?

Bonjour à tous,
je voulais juste savoir si la STL permettait d'insérer un élément dans une liste (ou vecteur) déjà triée en l'insérant à la bonne place?

par exemple, si j'ai:

Code:

---

1 2 3 4 5

std::vector<MonObjet> monvecteur; //remplissage //...   std::sort(monvecteur.begin(), monvecteur.end()); //tri

---

avec MonObjet qui surchage la fonction opérateur <
Existe-t-il une méthode pour ajouter l'élément à la bonen place ou je dois le faire manuellement (les algo de la stl étant généralement mieux optimisés que les miens XD)

merci pour vs réponses

Il suffit de regarder sur cette page pour connaitre les conteneurs triés de la STL (avec clef unique):
http://www.sgi.com/tech/stl/UniqueSo...Container.html

Aprés tu as aussi des algorithmes de tri dans la STL:
http://www.sgi.com/tech/stl/sort.html

Tu peux utiliser std::equal_range pour directement déterminer la position où l'élément devrait être inséré.

Si tu en as la possibilité, remplis d'abord ton vecteur et trie le ensuite. Je soupçonne que cela sera plus efficace.

Citation:

---

Envoyé par Luc Hermitte

Tu peux utiliser std::equal_range pour directement déterminer la position où l'élément devrait être inséré.

Si tu en as la possibilité, remplis d'abord ton vecteur et trie le ensuite. Je soupçonne que cela sera plus efficace.

---

En fait je rempli à la base mon vecteur que je trie ensuite. Puis lors d'un traitement, j'ai besoin de prendre un élément dans la liste (le retirer), puis le rajouter ensuite. Le reste de la liste est déjà trié à ce moment, donc un ajout+tri sera peut etre moins efficace qu'un ajout directement à la bonen position.

Merci pour les liens MatRem je regarde ça de suite

Bon j'ai regardé un peu tes liens, et ça me semble pas si evident.
Déjà pour utiliser une Unique Sorted Associative Container, je n'arrive pas a chopper la bonne syntaxe pour le déclarer (ya un include special a mettre?).
je crois que je vais garder la soluce du tri après avoir inséré l'élément dans mon vecteur

sinon il ya visiblement deux types de tri:
sort et stable_sort.

Visiblement il est conseillé d'utiliser le deuxieme dans le cas ou on a des enregistrements à champ multiple.
Mais dans mon cas, sachant que mes objets stockés ont la méthode '<' surchargée, doi-je vraiment utiliser stable_sort ou je peux laisser le sort normal?

Citation:

---

Déjà pour utiliser une Unique Sorted Associative Container, je n'arrive pas a chopper la bonne syntaxe pour le déclarer (ya un include special a mettre?).

---

C'est juste un concept, ça ne correspond concrétement à aucune classe.
Ce qu'il fallait comprendre de cette réponse c'était d'utiliser std::set.

Citation:

---

sinon il ya visiblement deux types de tri:
sort et stable_sort.

Visiblement il est conseillé d'utiliser le deuxieme dans le cas ou on a des enregistrements à champ multiple.
Mais dans mon cas, sachant que mes objets stockés ont la méthode '<' surchargée, doi-je vraiment utiliser stable_sort ou je peux laisser le sort normal?

---

stable_sort sert juste à garder les éléments équivalents dans le même ordre qu'avant le tri.

?? Détermine les positions des élements à retirer et à ajouter avec equal_range, et appelle les fonctions idiones des vecteurs.
Si tu connais les positions avant et après, il doit même y avoir moyen de tout déplacer avant d'inscrire le nouvel élément.

Citation:

---

Envoyé par Laurent Gomila

C'est juste un concept, ça ne correspond concrétement à aucune classe.
Ce qu'il fallait comprendre de cette réponse c'était d'utiliser std::set.

---

J'aivais trouvé les set , mais je n'ai pas tout compris du fonctionnement.

A première vu, ça ressemblait fortement aux sets utilisés pour les SGBD orientés objets (OQL par ex). Donc j'en ai déduit que le set est plus ou moins un vecteur dans lequel les éléments sont indexés par une clé (genre tableau associatif/map). Mais en regardant un peu plus, j'ai compris que j'avais fais erreur.


Donc en gros je peux créer un set vide et ajouter les éléments un par un:

Code:

---

1 2 3 4 5 6

std::set<monObjet> monset; //ajout d'une valeur: monset.insert(monObjet); //insertion directement triée ou non (parce que plus de méthode sort dispo)? Sinon comment utiliser equal_range? //retrait d'une valeur: monset.erase(monset.find(monObjet)); //peut être une vérification sur l'iterateur retourné par find() pour éviter les erreurs?

---

Une question aussi:
si j veux créer le set à partir d'un vecteur par exemple, le code ci-desous est-til correct:

Code:

---

1 2 3 4 5 6 7

std::vector<monObjet> monvecteur; std::set<monObjet> monset; //remplissage du vecteur //... //on copy les valeur du vecteur (de debut a fin) vers monset std::copy(monvecteur.begin(), monvecteur.end(),monset.begin());

---

En tout cas le set convient surement très bien à l'utilisation que je veux en faire, car on peut aussi faire des unions et intersection. Or je dois faire un traitement sur des ensembles (résolution de CSP) et donc faire des union/intersection... pour affiner le domaine de définition de mes variables.

Un std::set est un container dans lequel les éléments sont triés. L'accès, la suppression et l'insertion s'effectuent en O(log n).

Citation:

---

Envoyé par johan_b

Donc en gros je peux créer un set vide et ajouter les éléments un par un:

Code:

---

1 2 3 4 5 6

std::set<monObjet> monset; //ajout d'une valeur: monset.insert(monObjet); //insertion directement triée ou non (parce que plus de méthode sort dispo)? Sinon comment utiliser equal_range? //retrait d'une valeur: monset.erase(monset.find(monObjet)); //peut être une vérification sur l'iterateur retourné par find() pour éviter les erreurs?

---

---

Oui, c'est bien ça. Les éléments sont automatiquement triés.

Citation:

---

Envoyé par johan_b

Une question aussi:
si j veux créer le set à partir d'un vecteur par exemple, le code ci-desous est-til correct:

Code:

---

1 2 3 4 5 6 7

std::vector<monObjet> monvecteur; std::set<monObjet> monset; //remplissage du vecteur //... //on copy les valeur du vecteur (de debut a fin) vers monset std::copy(monvecteur.begin(), monvecteur.end(),monset.begin());

---

---

Non, la fonction std::copy copie, elle n'insère pas.
Pour construire un std::set depuis un autre container :

Code:

---

1 2	std::vector<monObjet> monvecteur; std::set<monObjet> monset(monvecteur.begin(), monvecteur.end());

---

Citation:

---

Envoyé par Sylvain Togni

Non, la fonction std::copy copie, elle n'insère pas.
Pour construire un std::set depuis un autre container :

Code:

---

1 2	std::vector<monObjet> monvecteur; std::set<monObjet> monset(monvecteur.begin(), monvecteur.end());

---

---

Merci pour la précision.

Donc dans le cas ou j'ai un vecteur déjà existant et mon set déjà déclaré je devrais faire:

Code:

---

monset=std::set<monObjet>(monvecteur.begin(), monvecteur.end());

---

bon ben je crois que j'ai résolu mon probleme, merci à vous pour tout :D :bravo:

Si ton std::set est déjà construit utilise plutôt sa fonction assign, ça t'évitera des copies inutiles.

Code:

---

monset.assign(monvecteur.begin(), monvecteur.end());

---

Citation:

---

Code:

---

monset.erase(monset.find(monObjet)); //peut être une vérification sur l'iterateur retourné par find() pour éviter les erreurs?

---

---

Autant utiliser la version de erase qui prend directement l'objet en paramètre.

Code:

---

monset.erase(monObjet);

---

Citation:

---

Envoyé par Laurent Gomila

Si ton std::set est déjà construit utilise plutôt sa fonction assign, ça t'évitera des copies inutiles.

Code:

---

monset.assign(monvecteur.begin(), monvecteur.end());

---

---

assign fonctionne pour les vecteur mais pas pour les sets visiblement

Alors soit

Code:

---

monset = std::set<monObjet>(monvecteur.begin(), monvecteur.end());

---

soit (plus rapide)

Code:

---

std::set<monObjet>(monvecteur.begin(), monvecteur.end()).swap(monset);

---