使用两个向量进行排序

Question

使用两个向量进行排序

c++sorting

3

我想知道是否有可能对于一个包含相应成对元素的vector<string>和vector<double>，按照字母顺序排序vector<string>，同时保持这些成对元素的匹配关系。

我知道可以通过创建一个类来保存这两个值，并对其进行排序来实现此目的，但我更愿意保留两个单独的向量。

有什么好的想法吗？

最终代码：

#include "std_lib_facilities.h"

struct Name_pairs
{
       vector<string>names;
       vector<double>ages;
       void quicksort(vector<string>& num, vector<double>& num2, int top, int bottom);
       int divide(vector<string>& array, vector<double>& array2, int top, int bottom);
       bool test();
       string read_names();
       double read_ages();
       void print();
};

string Name_pairs::read_names()
{
       string name;
     cout << "Enter name: ";
     cin >> name;
     names.push_back(name);
     return name;
}

double Name_pairs::read_ages()
{
     double age;
     cout << "Enter corresponding age: ";
     cin >> age;
     ages.push_back(age);
     cout << endl;
     return age;
}

int Name_pairs::divide(vector<string>& array, vector<double>& array2, int top, int bottom)
{
    string x = array[top];
    int i = top-1;
    int j = bottom+1;
    string temp;
    double temp2;
    do{
        do
        {
             j--;
             }while(x<array[j]);

        do
        {
             i++;
             }while(x>array[i]);

        if(i<j)
        {
               temp = array[i];
               temp2 = array2[i];
               array[i] = array[j];
               array2[i] = array2[j];
               array[j] = temp;
               array2[j] = temp2;
               }
               }while(i<j);
        return j;
}


void Name_pairs::quicksort(vector<string>& num, vector<double>& num2, int top, int bottom) // top is subscript of beginning of vector
{
     int middle;
     if(top < bottom)
     {
            middle = divide(num, num2, top, bottom);
            quicksort(num, num2, top, middle);
            quicksort(num, num2, middle+1, bottom);
            }
     return;
}

void Name_pairs::print()
{
     for(int i = 0; i < (names.size()-1) && i < (ages.size()-1); ++i)
             cout << names[i] << " , " << ages[i] << endl;
}

int main(){
    Name_pairs np;
    cout << "Enter names and ages. Use 0 to cancel.\n";
    bool finished = false;
    while(!finished){
    finished = "0" == np.read_names();
    finished = 0 == np.read_ages();}
    np.quicksort(np.names, np.ages, 0, (np.names.size()-2));
    np.print();
    keep_window_open();}

- trikker

你使用两个向量而不是更复杂的数据结构有什么特别的原因吗？ - beggs

从书上学习，这是练习的意图。甚至还没有学习关于映射或数组的知识。 - trikker

4个回答

4

虽然指数的概念是相同的，但实际上您可以定义一个随机访问迭代器类型，它知道这两个向量，并将它们（通过赋值）同步移动。该迭代器的value_type将是pair。在函数式编程中，您会称其为“zip”（但不是拉链）。

除非您非常紧缩空间，否则绝对不值得麻烦。如果有足够的空间，将两个向量压缩成一对向量或使用索引方法都更容易。

如果您第一次就能做对，复制/粘贴具有明显修改的10行快速排序将是最快捷的方式。

编辑注：已经有一个Zip Iterator可用于Boost中，正如在同一问题的这个新答案中指出的那样："Locking" two vectors and sorting them

- Jonathan Graehl

这正是我想建议的迭代器，只不过我可能会忘记提到zip，并且我还要补充一句：“我真的懒得费心为你提供一个经过测试的实现示例”;-) - Steve Jessop

3

您可以创建一个辅助向量：

vector<unsigned int> indices;

将其初始化为0,1,2,...n-1，其中n是您的向量大小，并使用查看vector<string>的函数对象对其进行排序，即当要求比较index1和index2时，函数对象将查找相应的字符串并进行比较。一旦您已经将indices排序，您可以轻松地在线性时间内将两个数组排序以符合它。 编辑：我没有看到Jim Buck的第二个建议。我的答案只是那个建议的扩展版本。

- Ari

2

如果您想使用 std::sort，您需要使用像 pair 这样的数据结构。当然，您也可以手动排序向量，并重新实现 std::sort。但这要看很多其他问题，例如：“向量中有多少项？性能有多重要？您真的想要实现自己的排序算法吗？”实现快速排序应该相对简单，并且可以避免移动数据。

- Dave Gamble

嗯，那怎么样将这些向量同步，让一个的索引发生的任何事情都同样发生在另一个的索引上呢？ - trikker

问题在于同步。std::sort 不允许同步，因此您必须实现自己的排序算法。 - Dave Gamble

哼……我看了一下<algorithm>中的sort成员，似乎没有什么可以借鉴的。有什么主意吗？ - trikker

如果你真的想这么做，实现一个快速排序，或者如果性能不是问题，使用冒泡排序，保持两个向量同步。 - Dave Gamble

如果你正在学习编程语言，实现一个排序算法是非常好的练习，可以让你更加熟悉它。 - Dave Gamble

1

好的，谢谢。听起来像是一个有趣的小型项目（希望如此！）。 - trikker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Buck · Accepted Answer

如果您手动排序，只需交换双数组中相应的项目以及通常会执行的字符串数组中的项目即可。或者，您可以有第三个数组：

vector<unsigned int> indices;

这只是在字符串/双精度数组中进行索引，并对该数组进行排序（基于字符串数组中的值进行交换）。