C++ 如何按不同 std::vector 的值对 std::vector 进行排序？

How do I sort a std::vector by the values of a different std::vector?

提问by John Carter

I have several std::vector, all of the same length. I want to sort one of these vectors, and apply the same transformation to all of the other vectors. Is there a neat way of doing this? (preferably using the STL or Boost)? Some of the vectors hold ints and some of them std::strings.

我有几个std::vector，长度都一样。我想对这些向量之一进行排序，并对所有其他向量应用相同的转换。有没有一种巧妙的方法来做到这一点？（最好使用 STL 或 Boost）？一些向量包含ints，其中一些向量包含std::strings。

Pseudo code:

伪代码：

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };

Transformation = sort(Index);
Index is now { 1, 2, 3};

... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };

采纳答案by Konrad Rudolph

friol's approach is good when coupled with yours. First, build a vector consisting of the numbers 1…n, along with the elements from the vector dictating the sorting order:

friol 的方法与您的方法结合使用时很好。首先，构建一个由数字 1... n组成的向量，以及向量中指示排序顺序的元素：

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > order(Index.size());

size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
    order[n] = make_pair(n, it);

Now you can sort this array using a custom sorter:

现在您可以使用自定义排序器对这个数组进行排序：

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return *(a.second) < *(b.second);
    }
};

sort(order.begin(), order.end(), ordering());

Now you've captured the order of rearrangement inside order(more precisely, in the first component of the items). You can now use this ordering to sort your other vectors. There's probably a very clever in-place variant running in the same time, but until someone else comes up with it, here's one variant that isn't in-place. It uses orderas a look-up table for the new index of each element.

现在您已经捕获了内部的重新排列顺序order（更准确地说，在项目的第一个组件中）。您现在可以使用此顺序对其他向量进行排序。可能有一个非常聪明的就地变体同时运行，但在其他人提出它之前，这里有一个不是就地变体。它order用作每个元素的新索引的查找表。

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> ret(in.size());

    size_t const size = in.size();
    for (size_t i = 0; i < size; ++i)
        ret[i] = in[reference[i].first];

    return ret;
}

回答by lalitm

typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> index_vec_t;

class SequenceGen {
  public:
    SequenceGen (int start = 0) : current(start) { }
    int operator() () { return current++; }
  private:
    int current;
};

class Comp{
    int_vec_t& _v;
  public:
    Comp(int_vec_t& v) : _v(v) {}
    bool operator()(size_t i, size_t j){
         return _v[i] < _v[j];
   }
};

index_vec_t indices(3);
std::generate(indices.begin(), indices.end(), SequenceGen(0));
//indices are {0, 1, 2}

int_vec_t Index = { 3, 1, 2 };
str_vec_t Values = { "Third", "First", "Second" };

std::sort(indices.begin(), indices.end(), Comp(Index));
//now indices are {1,2,0}

Now you can use the "indices" vector to index into "Values" vector.

现在您可以使用“索引”向量来索引“值”向量。

回答by Dave Hillier

Put your values in a Boost Multi-Index containerthen iterate over to read the values in the order you want. You can even copy them to another vector if you want to.

将您的值放入Boost Multi-Index 容器中，然后迭代以按您想要的顺序读取值。如果您愿意，您甚至可以将它们复制到另一个向量。

回答by Gabriele D'Antona

Only one rough solution comes to my mind: create a vector that is the sum of all other vectors (a vector of structures, like {3,Third,...},{1,First,...}) then sort this vector by the first field, and then split the structures again.

Probably there is a better solution inside Boost or using the standard library.

我想到的只有一个粗略的解决方案：创建一个向量，它是所有其他向量的总和（一个结构向量，如 {3,Third,...},{1,First,...}），然后对其进行排序向量，然后再次拆分结构。

Boost 或使用标准库可能有更好的解决方案。

回答by xtofl

I think what you reallyneed (but correct me if I'm wrong) is a way to access elements of a container in some order.

我认为您真正需要的是（如果我错了，请纠正我）是一种以某种顺序访问容器元素的方法。

Rather than rearranging my original collection, I would borrow a concept from Database design: keep an index, ordered by a certain criterion. This index is an extra indirection that offers great flexibility.

我不会重新排列我的原始集合，而是从数据库设计中借用一个概念：保留一个索引，按特定标准排序。这个索引是一个额外的间接索引，提供了很大的灵活性。

This way it is possible to generate multiple indices according to different members of a class.

这样就可以根据类的不同成员生成多个索引。

using namespace std;

template< typename Iterator, typename Comparator >
struct Index {
    vector<Iterator> v;

    Index( Iterator from, Iterator end, Comparator& c ){
        v.reserve( std::distance(from,end) );
        for( ; from != end; ++from ){
            v.push_back(from); // no deref!
        }
        sort( v.begin(), v.end(), c );
    }

};

template< typename Iterator, typename Comparator >
Index<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
    return Index<Iterator,Comparator>(from,end,c);
}

struct mytype {
    string name;
    double number;
};

template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
};

template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; }
};

void indices() {

    mytype v[] =    { { "me"    ,  0.0 }
                    , { "you"   ,  1.0 }
                    , { "them"  , -1.0 }
                    };
    mytype* vend = v + _countof(v);

    Index<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
    Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );

    assert( byname.v[0] == v+0 );
    assert( byname.v[1] == v+2 );
    assert( byname.v[2] == v+1 );

    assert( bynum.v[0] == v+2 );
    assert( bynum.v[1] == v+0 );
    assert( bynum.v[2] == v+1 );

}

回答by ltjax

You can probably define a custom "facade" iterator that does what you need here. It would store iterators to all your vectors or alternatively derive the iterators for all but the first vector from the offset of the first. The tricky part is what that iterator dereferences to: think of something like boost::tuple and make clever use of boost::tie. (If you wanna extend on this idea, you can build these iterator types recursively using templates but you probably never want to write down the type of that - so you either need c++0x auto or a wrapper function for sort that takes ranges)

您可能可以定义一个自定义的“外观”迭代器来满足您的需求。它会将迭代器存储到所有向量，或​​者从第一个向量的偏移量中导出除第一个向量之外的所有向量的迭代器。棘手的部分是迭代器取消引用的内容：想像 boost::tuple 之类的东西并巧妙地使用 boost::tie。（如果你想扩展这个想法，你可以使用模板递归地构建这些迭代器类型，但你可能永远不想写下它的类型 - 所以你要么需要 c++0x auto 或一个包装函数来进行范围排序）

回答by aph

ltjax's answer is a great approach - which is actually implemented in boost's zip_iterator http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

ltjax 的答案是一个很好的方法 - 实际上是在 boost 的 zip_iterator http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html 中实现的

It packages together into a tuple whatever iterators you provide it.

无论你提供什么迭代器，它都会打包成一个元组。

You can then create your own comparison function for a sort based on any combination of iterator values in your tuple. For this question, it would just be the first iterator in your tuple.

然后，您可以根据元组中迭代器值的任意组合为排序创建自己的比较函数。对于这个问题，它只是元组中的第一个迭代器。

A nice feature of this approach is that it allows you to keep the memory of each individual vector contiguous (if you're using vectors and that's what you want). You also don't need to store a separate index vector of ints.

这种方法的一个很好的特点是它允许您保持每个单独向量的内存连续（如果您正在使用向量并且这就是您想要的）。您也不需要存储单独的整数索引向量。

回答by Tim MB

A slightly more compact variant of xtofl's answer for if you are just looking to iterate through all your vectors based on the of a single keysvector. Create a permutation vector and use this to index into your other vectors.

如果您只是想根据单个keys向量的来遍历所有向量，那么 xtofl 答案的稍微紧凑一点的变体。创建一个置换向量并使用它来索引其他向量。

#include <boost/iterator/counting_iterator.hpp>
#include <vector>
#include <algorithm>

std::vector<double> keys = ...
std::vector<double> values = ...

std::vector<size_t> indices(boost::counting_iterator<size_t>(0u), boost::counting_iterator<size_t>(keys.size()));
std::sort(begin(indices), end(indices), [&](size_t lhs, size_t rhs) {
    return keys[lhs] < keys[rhs];
});

// Now to iterate through the values array.
for (size_t i: indices)
{
    std::cout << values[i] << std::endl;
}

回答by user1596722

This would have been an addendum to Konrad's answer as it an approach for a in-place variant of applying the sort order to a vector. Anyhow since the edit won't go through I will put it here

这将是 Konrad 答案的附录，因为它是一种将排序顺序应用于向量的就地变体的方法。无论如何，因为编辑不会通过，我会把它放在这里

Here is a in-place variant with a slightly higher time complexity that is due to a primitive operation of checking a boolean. The additional space complexity is of a vector which can be a space efficient compiler dependent implementation. The complexity of a vector can be eliminated if the given order itself can be modified.

这是一个时间复杂度稍高的就地变体，这是由于检查布尔值的原始操作。额外的空间复杂度是一个向量，它可以是一个空间高效的编译器相关实现。如果可以修改给定的顺序本身，则可以消除向量的复杂性。

Here is a in-place variant with a slightly higher time complexity that is due to a primitive operation of checking a boolean. The additional space complexity is of a vector which can be a space efficient compiler dependent implementation. The complexity of a vector can be eliminated if the given order itself can be modified. This is a example of what the algorithm is doing. If the order is 3 0 4 1 2, the movement of the elements as indicated by the position indices would be 3--->0; 0--->1; 1--->3; 2--->4; 4--->2.

这是一个时间复杂度稍高的就地变体，这是由于检查布尔值的原始操作。额外的空间复杂度是一个向量，它可以是一个空间高效的编译器相关实现。如果可以修改给定的顺序本身，则可以消除向量的复杂性。这是算法正在做什么的一个例子。如果顺序是 3 0 4 1 2，则由位置索引指示的元素的移动将是 3--->0；0--->1; 1--->3; 2--->4; 4--->2。

template<typename T>
struct applyOrderinPlace
{
void operator()(const vector<size_t>& order, vector<T>& vectoOrder)
{
vector<bool> indicator(order.size(),0);
size_t start = 0, cur = 0, next = order[cur];
size_t indx = 0;
T tmp; 

while(indx < order.size())
{
//find unprocessed index
if(indicator[indx])
{   
++indx;
continue;
}

start = indx;
cur = start;
next = order[cur];
tmp = vectoOrder[start];

while(next != start)
{
vectoOrder[cur] = vectoOrder[next];
indicator[cur] = true; 
cur = next;
next = order[next];
}
vectoOrder[cur] = tmp;
indicator[cur] = true;
}
}
};

回答by Ziezi

Here is a relatively simple implementation using index mappingbetween the ordered and unordered namesthat will be used to match the agesto the ordered names:

这是一个使用有序和无序之间的索引映射的相对简单的实现names，用于将 与ages有序匹配names：

void ordered_pairs()
{
    std::vector<std::string> names;
    std::vector<int> ages;

    // read input and populate the vectors
    populate(names, ages);

    // print input
    print(names, ages);

    // sort pairs
    std::vector<std::string> sortedNames(names);
    std::sort(sortedNames.begin(), sortedNames.end());

    std::vector<int> indexMap;
    for(unsigned int i = 0; i < sortedNames.size(); ++i)
    {
        for (unsigned int j = 0; j < names.size(); ++j)
        {
            if (sortedNames[i] == names[j]) 
            {
                indexMap.push_back(j);
                break;
            }
        }
    }
    // use the index mapping to match the ages to the names
    std::vector<int> sortedAges;
    for(size_t i = 0; i < indexMap.size(); ++i)
    {
        sortedAges.push_back(ages[indexMap[i]]);
    }

    std::cout << "Ordered pairs:\n";
    print(sortedNames, sortedAges); 
}

For the sake of completeness, here are the functions populate()and print():

为了完整起见，这里是函数populate()和print()：

void populate(std::vector<std::string>& n, std::vector<int>& a)
{
    std::string prompt("Type name and age, separated by white space; 'q' to exit.\n>>");
    std::string sentinel = "q";

    while (true)
    {
        // read input
        std::cout << prompt;
        std::string input;
        getline(std::cin, input);

        // exit input loop
        if (input == sentinel)
        {
            break;
        }

        std::stringstream ss(input);

        // extract input
        std::string name;
        int age;
        if (ss >> name >> age)
        {
            n.push_back(name);
            a.push_back(age);
        }
        else
        {
            std::cout <<"Wrong input format!\n";
        }
    }
}

and:

和：

void print(const std::vector<std::string>& n, const std::vector<int>& a)
{
    if (n.size() != a.size())
    {
        std::cerr <<"Different number of names and ages!\n";
        return;
    }

    for (unsigned int i = 0; i < n.size(); ++i)
    {
         std::cout <<'(' << n[i] << ", " << a[i] << ')' << "\n";
    }
}

And finally, main()becomes:

最后，main()变成：

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

void ordered_pairs();
void populate(std::vector<std::string>&, std::vector<int>&);
void print(const std::vector<std::string>&, const std::vector<int>&);

//=======================================================================
int main()
{
    std::cout << "\t\tSimple name - age sorting.\n";
    ordered_pairs();
}
//=======================================================================
// Function Definitions...