C++ Trier un vecteur de <T> selon un vecteur de doubles

Question

Je veux trier un vecteur de T en fonction d'un vecteur de double. C'est-à-dire que si j'ai

vector<T> a;
vector<double>b;

Si a es {t1, t2, t3, t4} y b es {3, 1, 5, 2} Je veux obtenir {t2, t4, t1, t3} .

Je ne sais pas comment déclarer le modèle. J'essaie quelque chose comme

template<vector<class T>> vector<T> sortByArray(vector<T> a, vector<double>b)

Et je n'ai aucune idée de la façon d'écrire le corps de la fonction non plus.

Merci.

EDIT : C'est l'utilisation de mon algorithme. Je n'y arrive pas.

template <typename T> struct dataPair
{
    dataPair(double s, T o) 
    : m_sortData(s)
    , m_otherData(o)
    {

    }

    bool operator< (const dataPair &rhs) { return (m_sortData < rhs.m_sortData); }

    double m_sortData;
    T m_otherData;

}

  template <class T> vector<T> sortByArrayStuff(vector<T> objects, vector<double> sortNumber) {
    vector<dataPair<T>> v;
    for (unsigned int i = 0; i < objects.size(); i++) {
        v.push_back(dataPair<T>(objects[i], sortNumber[i]));
    }
    sort(v.begin(), v.end());
    vector<T> retVal;

    for (unsigned int i = 0; i < objects.size(); i++) {
        retVal.push_back(dataPair<T>(objects[i], sortNumber[i]));
    }
    return retVal;
};

Je veux utiliser le même modèle pour les vecteurs de "Points" et les vecteurs de vecteurs de "Points" :

vector<double> sortedAreas;
vector<Point> sortedPoints = sortByArray<vector<Point>>(points, sortedAreas);
vector<vector<Point>> sortedContours = sortByArray<vector<vector<Point>>>(contours, sortedAreas);

L'erreur est

cannot convert parameter 1 from 'dataPair<T>' to 'cv::Point &&'
          with
          [
              _Ty=cv::Point
          ]
          and
          [
              T=cv::Point
          ]
          Reason: cannot convert from 'dataPair<T>' to 'cv::Point'
          with
          [
              T=cv::Point
          ]

Answer 1

Ce que vous devez faire, c'est créer un struct o class comme ça :

template <typename T> struct dataPair
{
    dataPair(double s, T o) 
    : m_sortData(s)
    , m_otherData(o)
    {

    }

    bool operator< (const dataPair &rhs) { return (m_sortData < rhs.m_sortData); }

    double m_sortData;
    T m_otherData;

}

Ensuite, vous créez un vecteur de ces dataPair types

{
    // your code ...
    // that assumes b is is a std::vector<YourType>

    // create vector and populate it
    std::vector<dataPair<YourType>> v;
    v.push_back(dataPair<YourType>(a[0],b[0]));
    v.push_back(dataPair<YourType>(a[1],b[1]));
    v.push_back(dataPair<YourType>(a[2],b[2]));
    v.push_back(dataPair<YourType>(a[3],b[3]));

    std::sort(v.begin(),v.end());

    // your code (now they will be sorted how you like in v)

}

EDIT : quelques fautes de frappe

EDIT2 : Vous pouvez également faire cela avec des foncteurs pour plus d'efficacité, mais c'est l'idée de base.

EDIT3 : L'utilisation des foncteurs avec le tri est très bien décrite ici. Voyez où ils utilisent le foncteur myclass dans laquelle ils surchargent operator(). Cela permet d'effectuer des optimisations au moment de la compilation (car de std::sort le critère de tri est un type de modèle)

Answer 2

Le moyen le plus simple auquel je pense est d'inclure le double dans la déclaration de la classe T et de l'utiliser comme paramètre de tri. Désolé si la syntaxe de mes modèles n'est pas très bonne, cela fait un moment que je ne les ai pas utilisés :

class YourClass
{
  //Some stuff...
  double sortVal;
};

bool std::less<YourClass>(YourClass left, YourClass  right)
{
   return left.sortVal < right.sortval;
}

Answer 3

Je faisais justement quelque chose comme ça l'autre jour, et voici mon idée. Prenez les deux vecteurs, et combinez-les dans une multimap. Le tri sera fait automatiquement juste en les insérant dans la carte, puis vous les extrayez de la carte pour les remettre dans les vecteurs. J'ai créé 2 modèles de fonctions pour ce travail, les voici :

// This function basically does the reverse of a transform.  Whereas transform takes
// two inputs and by some method merges them into one, this function takes one input
// and by some method splits it in two.
template<typename InIt, typename Out1It, typename Out2It, typename Fn>
void fork_transform(InIt ibegin, InIt iend, Out1It o1begin, Out2It o2begin, Fn fork)
{
    while(ibegin != iend)
    {
        fork(*ibegin, *o1begin, *o2begin);
        ++o1begin;
        ++o2begin;
        ++ibegin;
    }
}

template<typename ItPrimary, typename ItSecondary>
void simul_sort(ItPrimary begin1, ItPrimary end1, ItSecondary begin2)
{
    typedef std::iterator_traits<ItPrimary>::value_type T1;
    typedef std::iterator_traits<ItSecondary>::value_type T2;

    typedef std::multimap<T1,T2> Map_t;
    typedef Map_t::value_type Pair_t;

    Map_t m;

    // this was necessary for me because of a bug in VC10, see my most recent question
    auto MakePair = [](const T1 & first, const T2 & second) { return std::make_pair(first,second); };
    std::transform(begin1, end1, begin2, std::inserter(m,m.begin()), MakePair);

    auto Fork = [](const Pair_t & p, T1 & first, T2 & second) { first = p.first; second = p.second; };
    fork_transform(m.begin(), m.end(), begin1, begin2, Fork);
}

Cela permet en fait de trier les deux vecteurs simultanément. Le premier est trié normalement, le second est trié selon l'ordre du premier :

simul_sort(b.begin(), b.end(), a.begin());

Answer 4

Si vous avez besoin d'une solution générique pour ce problème, consultez le modèle de fermeture éclair dans l'une des réponses ici : nombre de correspondances dans deux séquences avec STL

Vous aurez besoin de quelque chose de proche de cette fermeture à glissière - une entité qui ferme deux séquences en une seule.

Answer 5

Voici une solution générique - une fonction qui renvoie un vecteur des index dans un tableau. Vous pouvez utiliser ces index sur l'un ou l'autre des éléments suivants a o b pour les obtenir dans un ordre trié.

template<class RandomAccessIterator>
struct IndirectCompare : public std::binary_function<size_t, size_t, bool>
{
    IndirectCompare(RandomAccessIterator first) : m_first(first)
    {
    }
    bool operator()(const size_t &left, const size_t &right)
    {
        return *(m_first + left) < *(m_first + right);
    }
    RandomAccessIterator m_first;
};

template<class RandomAccessIterator>
std::vector<size_t> ordered_index(RandomAccessIterator first, RandomAccessIterator last)
{
    size_t n = last - first;
    std::vector<size_t> result;
    result.reserve(n);
    for (size_t i = 0;  i < n;  ++i)
        result.push_back(i);
    IndirectCompare<RandomAccessIterator> comp(first);
    std::sort(result.begin(), result.end(), comp);
    return result;
}

P.S. J'ai testé ce code maintenant, et il fonctionne.