如何按其他std :: vector的值对std :: vector进行排序?

c++ stl boost vector sorting

31165 观看

13回复

41757 作者的声誉

我有几个std::vector,长度都一样。我想对这些向量之一进行排序,并将相同的变换应用于所有其他向量。有一个整齐的方法吗?(最好使用STL或Boost)?一些载体的持有intS和他们中的一些std::string秒。

伪代码:

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" };
作者: John Carter 的来源 发布者: 2008 年 10 月 25 日

回应 13


4

5483 作者的声誉

我想到的只有一个简单的解决方案:创建一个向量,该向量是所有其他向量的总和(结构的向量,例如{3,Third,...},{1,First,...}),然后进行排序向量由第一个字段组成,然后再次拆分结构。

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

作者: Gabriele D'Antona 发布者: 2008 年 10 月 25 日

31

420924 作者的声誉

决定

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

现在,您可以使用自定义排序器对该数组进行排序:

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());

现在,您已经捕获了内部的重新排列顺序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;
}
作者: Konrad Rudolph 发布者: 2008 年 10 月 25 日

3

32701 作者的声誉

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

与其重新安排我的原始收藏,不如从数据库设计中借用一个概念:保留一个按特定标准排序的索引。该索引是一个额外的间接寻址,提供了极大的灵活性。

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

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

}
作者: xtofl 发布者: 2008 年 10 月 26 日

8

10587 作者的声誉

将值放入Boost Multi-Index容器中,然后进行迭代以按所需顺序读取值。如果需要,您甚至可以将它们复制到另一个向量。

作者: Dave Hillier 发布者: 2008 年 10 月 26 日

9

453 作者的声誉

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}

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

作者: lalitm 发布者: 2008 年 12 月 5 日

3

14190 作者的声誉

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

作者: ltjax 发布者: 2010 年 11 月 24 日

1

31 作者的声誉

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

无论您提供什么迭代器,它都将打包成一个元组。

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

这种方法的一个不错的功能是,它允许您保持每个单独矢量的内存连续(如果您正在使用矢量,那就是您想要的)。您也不需要存储单独的int索引向量。

作者: aph 发布者: 2011 年 12 月 21 日

1

2565 作者的声誉

如果您只是想基于一个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;
}
作者: Tim MB 发布者: 2014 年 10 月 23 日

1

16 作者的声誉

这将是Konrad答案的附录,因为它是将排序顺序应用于向量的就地变体的一种方法。无论如何,由于编辑无法进行,因此将其放在此处

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

这是一个具有较高时间复杂度的就地变体,这是由于检查布尔值的原始操作所致。额外的空间复杂度是矢量的,它可以是节省空间的编译器相关实现。如果可以修改给定顺序本身,则可以消除向量的复杂性。这是该算法正在执行的示例。如果顺序为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;
}
}
};
作者: user1596722 发布者: 2014 年 12 月 11 日

0

5185 作者的声誉

这是一个相对简单的实现,它使用有序和无序之间的索引映射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); 
}

为了完整起见,以下是函数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";
        }
    }
}

和:

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

最后,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...
作者: Ziezi 发布者: 2016 年 3 月 9 日

0

56 作者的声誉

**// C++ program to demonstrate sorting in vector
// of pair according to 2nd element of pair
#include <iostream>
#include<string>
#include<vector>
#include <algorithm>

using namespace std;

// Driver function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<char,char> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}

int main()
{
    // declaring vector of pairs
    vector< pair <char, int> > vect;

    // Initialising 1st and 2nd element of pairs
    // with array values
    //int arr[] = {10, 20, 5, 40 };
    //int arr1[] = {30, 60, 20, 50};
    char arr[] = { ' a', 'b', 'c' };
    int arr1[] = { 4, 7, 1 };

    int n = sizeof(arr)/sizeof(arr[0]);

    // Entering values in vector of pairs
    for (int i=0; i<n; i++)
        vect.push_back( make_pair(arr[i],arr1[i]) );

    // Printing the original vector(before sort())
    cout << "The vector before sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;

    }

    // Using sort() function to sort by 2nd element
    // of pair
    sort(vect.begin(), vect.end(), sortbysec);

    // Printing the sorted vector(after using sort())
    cout << "The vector after sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;
    }
    getchar();
    return 0;`enter code here`
}**
作者: umair butt 发布者: 2017 年 7 月 8 日

-2

72 作者的声誉

如此多的人问了这个问题,没有人给出满意的答案。这是一个std :: sort辅助函数,它可以同时考虑两个向量的值,而只考虑一个向量的值。此解决方案基于自定义的RadomIt(随机迭代器),可直接对原始矢量数据进行操作,而无需临时副本,结构重排或其他索引:

C ++,基于另一个对一个向量进行排序

作者: cDc 发布者: 2017 年 9 月 22 日

0

72 作者的声誉

基于Konrad Rudolph和Gabriele D'Antona的答案的C ++ 11 lambda和STL算法:

template< typename T, typename U >
std::vector<T> sortVecAByVecB( std::vector<T> & a, std::vector<U> & b ){

    // zip the two vectors (A,B)
    std::vector<std::pair<T,U>> zipped(a.size());
    for( size_t i = 0; i < a.size(); i++ ) zipped[i] = std::make_pair( a[i], b[i] );

    // sort according to B
    std::sort(zipped.begin(), zipped.end(), []( auto & lop, auto & rop ) { return lop.second < rop.second; }); 

    // extract sorted A
    std::vector<T> sorted;
    std::transform(zipped.begin(), zipped.end(), std::back_inserter(sorted), []( auto & pair ){ return pair.first; }); 

    return sorted;
}
作者: kingusiu 发布者: 2019 年 5 月 8 日
32x32