C++根據雙向量向量<T>排序向量

Question

我想根據雙向向量對T的向量進行排序。也就是說，如果我有

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

如果a是{t1, t2, t3, t4}和b是{3, 1, 5, 2}，我想獲得{t2, t4, t1, t3}。

我不知道如何聲明模板。我正在嘗試類似

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

而且我也不知道如何編寫函數體。

謝謝。

編輯：這是我的算法的用法。我不明白。

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; 
}; 

我想使用相同的模板「點」的向量的「點」的載體和載體：

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

錯誤是

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

你應該做的是什麼創建一個struct或class像這樣：

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; 

} 

然後，創建這些dataPair類型

{ 
    // 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) 

}

編輯的矢量：有一些錯別字

EDIT2：您還可以用仿函數的更高的效率做到這一點，但是這是基本的想法。

EDIT3：Using functors with sort is described very nicely here. See where they use the functor myclass in which they overload operator(). This allows compile-time optimizations to be made (because from std::sort's perspective the sorting criterion is a template type)

Answer 2

我能想到的最簡單的方法，就是如果你只是包含的T類聲明內雙，並用它作爲你的排序參數。對不起，如果我的模板語法不是很好，它已經有一段時間，因爲我使用它們：

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

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

Answer 3

我只是在做這樣的事情，而且這是我的想法。把兩個矢量，並將它們組合成一個multimap。只需將它們插入到地圖中即可自動完成排序，然後將它們從地圖中提取回載體中。我想出了這個工作的2個功能模板，它們是：

// 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); 
} 

這實際上是將兩個矢量同時排序。首先是正常排序，二是根據第一的順序進行排序：

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

Answer 4

如果你需要對這個問題通用的解決方案，然後採取拉鍊模板來看看這裏的答案之一： number of matches in two sequences with STL

你將需要一些接近拉鍊的東西 - 一些將兩個序列拉成一個的實體。

Answer 5

這是一個通用的解決方案 - 一個函數，它將索引的向量返回到數組中。您可以在您的a或b中的任一個上使用這些索引，以按排序順序獲取它們。

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.我已經測試了這個代碼，並且它可以工作。

Answer 6

如果你想同時排序兩個向量，你應該創建一個std :: vector（比如c）std :: pair。 第一個組件必須是要正常排序的組件，第二個組件必須是相應排序的組件。

std::vector<std::pair<double, T>> c; 
std::sort(c.begin(), c.end()); 

希望這會有所幫助。