Discussion :

[DEVfan]

Bonjour,
ce que je cherche n'est pas dans le dernier tuto sur la stl avec les algorithmes, la fonction de recherche dans le forum C++ pour assign et insert donne ... 0 reponses . Je poste donc

LA question est fort simple :
J'ai 3 vector et je veux les mettre "bout a bout"... quelle est la methode la plus adaptee (rapide)?

La solution generale qui fait ecrire 6 lignes de codes (donc simple mais 3 ce serait plus sympa et lisible) est de faire un push_back de chaque element de chaque vector dans le bon sens...
...en commencant par un petit reserve ca me parait encore mieux.

Sinon pour faire moins de ligne et mieux, j4ai pense : faire un assign pour le premier vecto à recopie puis refaire comme si apres...

Sinon faire un 3 insert... mais aucune idee de la vitesse par rapport a la solution de base.

Merci de vos avis d'experts.

[JolyLoic]

A priori, je partirais sur les insert, après tout c'est fait pour ça. Avec un reserve avant, tant qu'à faire.

Autrement, si tu as souvent ce genre de merge de conteneurs à faire, une std::list peut être plus adaptée, puisqu'elle est capable de le faire en O(1), grâce à splice.

[yan]

tu parle de celui la?
http://r0d.developpez.com/articles/algos-stl/

un truc comme cela devrai être trés rapide

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
std::vector< int> vect1;
std::vector< int> vect2;
std::vector< int> vect3;
.
.
.
vector<int> vectres;
//tu réserve la mémoire. vectres à toujours 0 élément
vectres.reserve(vect1.size()+vect2.size()+vect3.size());
 
//tu merge les deux premier vector
std::merge((vect1.begin(),vect1.end(),vect2.begin(),vect2.end(),std::back_inserter(vectres));
//tu ajoute le dernier a la fin
std::copy(vect3.begin(),vect3.end(),std::back_inserter(vectres));

[DEVfan]

Pour les insert et reserve...ok si c4est fait pour

Pour merge, ca trie et j'en ai pas franchement besoin mais je ne l'avais pas vu celui-la. Merci pour ma suite

Pour la liste, oui effectivement mais j'ai pas l'interet dans ce projet.

Par contre, je veux bien un peu de detail sur le copy(...back_inserter). Je pensais que ca, ca inserer a l'envers mais a priori non.

Encore une question, j'ai un moment a faire une sorte fusion de deux vector en un... c'est a dire que je fais une lecture 1 a 1 et comparaison puis push_back...
Existe-t-il une methode qui peut le faire avec un predicat?
Vector1
-------
-------->Vector (combinaison des elements de 1 et 2 suivant une regle de selection)
-------
Vector2

Le push_back avec reserve est_il aussi efficace que le insert?
Le assign remet-il en question le reserve?

[yan]

Pour merge, ca trie et j'en ai pas franchement besoin mais je ne l'avais pas vu celui-la. Merci pour ma suite

??????
merge ne trie pas ????

Par contre, je veux bien un peu de detail sur le copy(...back_inserter). Je pensais que ca, ca inserer a l'envers mais a priori non.

copy va parcourir un ensemble et les copier.
back_inserter permet de créer un iterator qui va faire des push_back lors de la copie.Pour faire a l'enver tu peut utiliser le front_inserter
Le reserve permet que la memoire soit alloué avant le traitement et non par le push_back

Encore une question, j'ai un moment a faire une sorte fusion de deux vector en un... c'est a dire que je fais une lecture 1 a 1 et comparaison puis push_back...

std::copy_if

[yan]

http://r0d.developpez.com/articles/algos-stl/
est une bonne introduction au algo.

[DEVfan]

merci pour le lien et je l'ai deja lu il y a qq jours (enfin semaine en fait)

pour le merge... je sais dans cette doc mais sur d'autres sources, moi je vois

Merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies elements from [first1, last1) and [first2, last2) into [result, result + (last1 - first1) + (last2 - first2)) such that the resulting range is in ascending order. Merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent [1] elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 - first1) + (last2 - first2).

The two versions of merge differ in how elements are compared. The first version uses operator<. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, *j < *i is false. The second version uses the function object comp. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, comp(*j, *i) is false.

tire de http://www.sgi.com/tech/stl/merge.html
Et l'utilisation de operator<... ca m'inspire un tri et l'exemple a la fin... m'en convint.


Pour le copy... ca devrait etre par defaut le back_inserter mais j'ai relu et effectivement ca peut etre pratique (surtout en front...)
Sinon ya copy_backward.

pour le copy_if en fait, non, il me faudrait un truc genre "copy(dans vect3, vect1[i] si condition et sinon, vect2[i], du debut a la fin...)" Bon perso, je pense pas que ca existe et je m'en suis fais un maison. Mais merci pour l'aide.
[special pour Mongaulois... les segments et lignages sont faits, reste le compact ]

[yan]

merci pour le lien et je l'ai deja lu il y a qq jours (enfin semaine en fait)

pour le merge... je sais dans cette doc mais sur d'autres sources, moi je vois

tire de http://www.sgi.com/tech/stl/merge.html
Et l'utilisation de operator<... ca m'inspire un tri et l'exemple a la fin... m'en convint.

Ah ouai. t'as raison....
[EDIT]
puis le copy_if n'existe pas

[yan]

pour le copy_if en fait, non, il me faudrait un truc genre "copy(dans vect3, vect1[i] si condition et sinon, vect2[i], du debut a la fin...)" Bon perso, je pense pas que ca existe et je m'en suis fais un maison. Mais merci pour l'aide.
[special pour Mongaulois... les segments et lignages sont faits, reste le compact ]

Peut etre cela

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
int &  Choix(const int &a , const int &b)
{
if (/*test*/)
return a;
else
return b;
}
 
 
transform(vect1.begin(), vect1.end(),
               vect2.begin(), std::back_inserter(vectres),
                         &Choix);

[DEVfan]

J'ai regarde mais c'est un peu complexe a comprendre... je vais relire ca soigneusement un peu plus tard mais ca a lair de colle. En attendant, je garde mon truc moche for(){if...return else push_back}