c++ - 如何使用 STL 对包含相关条目的两个 vector 进行排序？

Question

我的函数有两个 vector 引用作为输入。他们的条目是相关的。 为了清楚起见，我们假设它们是:

vector<string> firstname = { "Bjarne",     "Alexander",  "Dennis",   "James",   "James"   };
vector<string> lastname  = { "Stroustrup", "Stepanov",   "Ritchie",  "Coplien", "Gosling" };

我想使用 STL 对它们进行排序，找到唯一的条目，然后删除其余的条目。

我知道我可以将它们复制到成对的中间 vector ，v，然后完成工作

void my_func (vector<string> *firstname, vector<string> *lastname)
{
   vector<pair<string,string>> v;
   for ( all i in firstname )
      v.push_back( (*firstname)[i], (*lastname)[i] ); // copy all entries

   sort(v.begin(), v.end());                          // clear duplicates
   v.erase(unique(v.begin(), v.end()), v.end());

   for ( all i in v ) {
       // copy back to firstname and lastname
   }
}

但我想知道是否可以使用 STL 来执行此操作，而无需创建整个临时 vector v 或没有其他类似大小的中间 vector ，因为我的输入数据有大量条目。

看起来我可以将临时比较器对象传递给 std::sort

struct ComparePersons
{
   vector<string> *first_names;
   vector<string> *last_names;

   bool operator() (const string &a, const string &b) 
   {
       // get indexes of names
       int index_a = std::distance( first_names.begin(), &a );
       int index_b = std::distance( first_names.begin(), &b );

       // create temporary persons   
       pair<string, string> person_a ( 
                                  (*first_names)[index_a], 
                                  (*last_names)[index_a] );

       pair<string, string> person_b ( 
                                  (*first_names)[index_b], 
                                  (*last_names)[index_b] );

       // compare persons
       return person_a < person_b;
   }
};

sort( first_names.begin(), first_names.end(), 
      ComparePersons(&first_names, &last_names) );

但我想不出如何进行排序来交换两个 vector 中的条目。

关于如何使用 STL 处理这些情况有什么想法吗？

Answer 1

STL 方法是使用 map ，但为了拼图的目的，我们尝试不使用拷贝。

您所需要的只是以某种方式“连接”两个 vector

一个好的方法是根据“主” vector 对索引 vector 进行排序，然后根据这些索引重新排列 vector 。

#include <iostream>
#include <vector>
#include <iterator>
#include <string>
#include <algorithm>
#include <numeric>

using namespace std;

// ------------------------------------------------------
template<typename It>
void replace(
    It beg, 
    It end, 
    typename iterator_traits<It>::value_type const& oldval, 
    typename iterator_traits<It>::value_type const& newval)
{
    while ((beg = find(beg, end, oldval)) != end)
    {
        *beg = newval;
        ++beg;
    }
}
// ------------------------------------------------------

// ------------------------------------------------------    
template<typename T>
void rearrange_vector(vector<int> nInd, vector<T> &v)
{
    size_t indx; 
    for (size_t ie(v.size()), i(0); i < ie; ++i)
    {
        auto it = find(nInd.begin(), nInd.end(), i);
        if (nInd.end() != it)
        {
            indx = distance(nInd.begin(), it);
            swap(v.at(i), v.at(indx));
            replace(nInd.begin(), nInd.end(), indx, i);
        }
    }
}
// ------------------------------------------------------


int main() 
{
    // 1. Problem space
    vector<string> firstnames = { 
        "Bjarne",     "Alexander",  "Dennis",   "James",   "James"   };
    vector<string> lastnames  = { 
        "Stroustrup", "Stepanov",   "Ritchie",  "Coplien", "Gosling" };

    // 2. vector of indices - sorted according to the order of firstnames
    vector<int> indices(firstnames.size());
    iota(indices.begin(), indices.end(), 0);

    sort(indices.begin(), indices.end(), [&](int i1, int i2){
        return firstnames[i1] < firstnames[i2]; 
    });

    // 3. rearrangement according to the sorted indices
    rearrange_vector(indices, firstnames);
    rearrange_vector(indices, lastnames);

    // 4. print results
    for (size_t i(0), ie(firstnames.size()); i < ie; ++i)
        cout << firstnames[i] << " " << lastnames[i] << endl;

    return 0;
}

Demo

当然，这样的唯一优点是，对于巨大的 vector ，您可以并行执行步骤(3)。此外，该解决方案还可以扩展到任意数量的“相关” vector 排序。

您只需支付索引排序的费用，后续的重新排序只需要线性时间。