Discussion :

[johan_b]

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 :

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

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

[MatRem]

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

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

[johan_b]

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

[johan_b]

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?

[Laurent Gomila]

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.

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.

[Luc Hermitte]

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

[johan_b]

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 :

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

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 :

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

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.

[Sylvain Togni]

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

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

Code :

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

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.

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

Code :

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

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 :

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

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

[johan_b]

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

Code :

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

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 :

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

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

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

[Laurent Gomila]

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

Code :

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

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

Code :

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

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 :

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

monset.erase(monObjet);

[johan_b]

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

Code :

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

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

assign fonctionne pour les vecteur mais pas pour les sets visiblement

[Sylvain Togni]

Alors soit

Code :

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

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

soit (plus rapide)

Code :

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

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