Discussion :

[oodini]

Bonjour,

J'ai 3 vecteurs. Un élément d'indice i d'un vecteur est lié aux éléments d'indice i des autres vecteurs. Ce qui veut dire que si je trie un vecteur, je dois trier les autres en effectuant les même permutations.

Y a-t-il moyen d'effectuer un tri sur un vecteur, de sauvegarder la séquence de permutation, et de l'utiliser sur les autres vecteurs ?

Vous allez me dire : "Il faut faire un vecteur de structures avec 3 éléments, correspondant aux 3 vecteurs, et effectuer le tri selon une des composantes de la structure."

Oui, mais au final, je dois fournir les données sous forme de 3 vecteurs indépendants.

Que feriez-vous ?

Merci.

[cyberpi]

Visiblement tu ne fais pas le tri toi-même, sinon ce ne serait pas compliqué d'appliquer en parallèle les mêmes permutations aux autres vecteurs.

Dans ton cas, avant le tri je récupérerais dans un tableau les adresses de tous les éléments de ton vecteur v1. Puis le tri. Puis avec deux boucles for je construirais un tableau pour dire où était placé dans le tableau original l'élément d'indice i (newValues[j] = i). Et enfin appliquer les mêmes changements aux vecteurs v2 et v3.

[loufoque]

Que feriez-vous ?

Je ferais un adapteur autour du vecteur qui détecterait les permutations et les répercuterait sur les autres vecteurs.

[cyberpi]

Je ferais un adapteur autour du vecteur qui détecterait les permutations et les répercuterait sur les autres vecteurs.

Comment tu coderais-tu ton adapteur sur un container de la stl?

Remarque: tu vas faire nlogn permutations aussi sur les autres vecteurs, au lieu de juste n.

[koala01]

Salut,

Peut-être pourrais tu envisager un quatrième tableau, qui contiendrait un tuple manipulant... trois pointeurs (un par tableau à trier)...

Plutôt que de trier les trois tableaux, tu te "contenterait" de trier le tableau de tuple selon tes besoins, et tu choisirais tes objet au départ de cela.

Cela te donnerait un code sans doute proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <tr1/tuple>
class T1
{
    /* le type manipulé par le premier tableau  */
};
class T2
{
    /* le type manipulé par le deuxième tableau */
};
class T3
{
   /* le type manipulé par le troisième tableau */
};
 
/* pour s'éviter des écritures à rallonges et à charnières */
 
typedef std::tr1::tuple<T1*,T2*,T3> MyTuple;
 
/* foncteur utile pour le tri au départ de T1 */
struct lessByT1
{
    bool operator <(MyTyple const & t1, MyTuple const & t2)  const
    {
        return std::tr1::get<0>(t1)->laFonctionQuiVaBien()< 
               std::tr1::get<0>(t2)->laFonctionQuiVaBien()
    }
};
/* foncteur utile pour le tri au départ de T2 */
struct lessByT2
{
    bool operator <(MyTyple const & t1, MyTuple const & t2)  const
    {
        return std::tr1::get<1>(t1)->laFonctionQuiVaBien()< 
               std::tr1::get<1>(t2)->laFonctionQuiVaBien()
    }
};
 
/* foncteur utile pour le tri au départ de T3 */
struct lessByT3
{
    bool operator <(MyTyple const & t1, MyTuple const & t2)  const
    {
        return std::tr1::get<2>(t1)->laFonctionQuiVaBien()< 
               std::tr1::get<2>(t2)->laFonctionQuiVaBien()
    }
};
std::vector<T1> tab1;
std::vector<T2> tab2;
std::vector<T3> tab3;
std::vector<MyTuple> reftab;
/* remplissage des tableaux */
for(size_t i=0;i<TOTAL_ITEM; ++i)
{
    tab1.push_back(T1(/*...*/);
    tab2.push_back(T2(/*...*/);
    tab3.push_back(T3(/*...*/);
    reftab.push_back(std::tr1::make_tuple(&tab1[i],&tab2[i],&tab3[i]);
}
/* trions les éléments en fonction  de T1 */
std::sort(reftab.begin(),reftab.end(),lessByT1);
/* accédons au troisième élément d'après le tri */
std::tr1::get<0>(tabref[2])->laFonctionDeT1Requise();
std::tr1::get<1>(tabref[2])->laFonctionDeT2Requise();
std::tr1::get<2>(tabref[2])->laFonctionDeT1Requise();

Le code n'est absolument pas testé (mais, à moins d'une erreur d'attention, il devrait être juste) et présente, il est vrai, une indirection supplémentaire, mais il t'évite les problèmes liés au fait de devoir respecter les ordres de tri pour trois tableaux en simultané

[loufoque]

Le code n'est absolument pas testé (mais, à moins d'une erreur d'attention, il devrait être juste)

Il est faux, push_back invalide les pointeurs vers les éléments.

Comment tu coderais-tu ton adapteur sur un container de la stl?

Ce serait relativement chiant à faire.
Des choses similaires existent déjà, comme zip_iterator dans boost, mais je ne pense pas que cela fonctionne avec un tri. (en effet, ça ne fonctionne pas, mais il y a un patch : https://svn.boost.org/trac/boost/ticket/1860)

[Arzar]

Je ferais un adapteur autour du vecteur qui détecterait les permutations et les répercuterait sur les autres vecteurs.

Tu aurais un exemple ou un lien vers de la doc démontrant ce genre de technique ?

[loufoque]

Comme je l'ai dit, tu prends le code de zip_iterator dans boost, t'appliques le patch pour corriger le bug (je vais essayer de faire pression que pour la résolution soit integrée dans le tronc prochainement) et voilà, tu as la solution.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <boost/iterator/zip_iterator.hpp>
#include <boost/range/as_array.hpp>
#include <algorithm>
#include <iostream>
 
struct first_element_compare
{
    bool operator()(const boost::tuple<int, int>& lft, const boost::tuple<int, int>& rgt) const
    {
         return boost::get<0>(lft) < boost::get<0>(rgt);
    }
};
 
int main()
{
    int foo[] = {9, 5, 6, 1};
    int bar[] = {1, 2, 3, 4};
 
    std::sort(
       boost::make_zip_iterator(
           boost::make_tuple(
               &foo[0],
               &bar[0]
           )
       ),
       boost::make_zip_iterator(
           boost::make_tuple(
               foo + 4,
               bar + 4
           )
       ),
       first_element_compare()
    );
 
    std::cout << boost::as_array(foo) << std::endl;
    std::cout << boost::as_array(bar) << std::endl;
}

affiche, avec le patch

Code :

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

1
2
1569
4231

[Arzar]

Ah oui ! Désolé, j'avais lu trop vite, c'est effectivement une jolie solution le boost::iterator.

Dommage qu'on ait pas encore boost.Range_ex, ça simplifierait énormement la syntaxe. (Elle se fait désirer cette bibliothèque, ça fait déjà plusieurs mois qu'elle a été revue et acceptée dans Boost mais elle n'est toujours pas livrée dans la dernière version !)

Le code deviendrait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
struct first_element_compare
{
    bool operator()(const boost::tuple<int, int>& lft, const boost::tuple<int, int>& rgt) const
    {
         return boost::get<0>(lft) < boost::get<0>(rgt);
    }
};
 
int main()
{
    int foo[] = {9, 5, 6, 1};
    int bar[] = {1, 2, 3, 4};
 
   // combine sera disponible dans Boost.Range_ex 
    std::sort(boost::combine(foo, bar), first_element_compare);
}