我有几个std::vector，它们的长度都相同。 我想对其中一个向量进行排序，并将相同的转换应用于所有其他向量。 有没有一种巧妙的方法可以做到这一点？（最好使用STL或Boost）？ 其中一些向量包含int，而另一些向量则包含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" };
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;
}
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}
现在您可以使用“indices”向量索引“Values”向量。
我脑海中只有一个粗略的解决方案：创建一个向量，它是所有其他向量的总和（结构体向量，如{3,Third,...},{1,First,...}），然后按第一个字段对该向量进行排序，最后再将结构体拆分。
可能在Boost或使用标准库中有更好的解决方案。
我认为你真正需要的是以某种顺序访问容器中的元素，如果我说错了请纠正我。
与其重新排列原始集合，不如借鉴数据库设计的概念：保持一个由特定标准排序的索引。这个索引是一种额外的间接性，提供了极大的灵活性。
这样就可以根据类的不同成员生成多个索引。
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 );
}
binary_function<T, T, bool>的目的是什么？是否可以在不继承自binary_function的情况下使用NameLess？ - Karikeys 向量的值迭代遍历所有向量，则可以使用 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;
}
ltjax的回答是一个很好的方法 - 实际上在boost的zip_iterator中已经被实现http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html
它会将您提供的任何迭代器打包到一个元组中。
然后，您可以为基于元组中任何组合的迭代器值的排序创建自己的比较函数。对于这个问题，它只是您元组中的第一个迭代器。
这种方法的一个好处是，它允许您保持每个单独向量的内存连续（如果您使用向量并且这就是您想要的）。您也不需要存储单独的整数索引向量。
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;
}
}
};
下面是一个相对简单的实现，使用有序和无序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...
custom_sort函数，该函数返回一个索引的std::vector<std::size_t>，类似于MATLAB。 - vsoftco