如何通过不同的std :: vector的值对std :: vector进行sorting？
我有几个std::vector ，都是相同的长度。 我想对这些向量之一进行sorting，并将相同的转换应用于所有其他向量。 有没有一个干净的方式做到这一点？ （最好使用STL或Boost）？ 一些向量保存int s，其中一些std::strings 。
伪代码：
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的方法是很好的，加上你的。 首先，构build一个由数字1 … n组成的向量，以及来自向量的指定sorting顺序的元素：
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);
现在，您可以使用自定义分拣机对此数组进行sorting：
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 。 您现在可以使用此sorting来sorting其他向量。 在同一时间可能有一个非常聪明的就地变体，但直到有人提出它，这是一个不在位的变体。 它使用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; }
把你的值放在一个Boost Multi-Index容器中，然后遍历你想要的顺序来读取值。 你甚至可以将它们复制到另一个vector，如果你想。
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}
现在您可以使用“索引”向量来索引“值”向量。
我的脑海里只有一个粗略的解决scheme：创build一个向量，它是所有其他向量（一个结构向量，如{3，Third，…}，{1，First，…}）的总和，然后对其进行sorting向量由第一个字段，然后再拆分结构。
Boost或使用标准库可能有更好的解决scheme。
你可以定义一个自定义的“外观”迭代器，它可以在这里做你所需要的。 它会将迭代器存储到所有的向量中，或者从第一个向量的偏移量中导出除了第一个向量之外的所有迭代器。 棘手的部分是迭代器解引用的东西：想到像boost :: tuple这样的东西，并巧妙地使用boost :: tie。 （如果你想扩展这个想法，你可以使用模板recursion地构build这些迭代器types，但是你可能永远都不想写下它的types – 所以你需要c ++ 0x auto或者需要范围的包装函数来sorting）
我认为你真正需要的是什么（但如果我错了，纠正我）是以某种顺序访问容器元素的一种方式。
我不会重新排列我的原始集合，而是从数据库devise中借用一个概念：保留一个按某个标准sorting的索引。 这个索引是一个额外的间接提供了很大的灵活性。
这样就可以根据一个类的不同成员生成多个索引。
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 ); }
ltjax的答案是一个很好的方法 – 这实际上是在boost的zip_iterator中实现http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html
无论您提供什么迭代器，它都可以打包成一个元组。
然后，您可以根据元组中的迭代器值的任意组合创build自己的比较函数。 对于这个问题，它只是你的元组中的第一个迭代器。
这种方法的一个很好的function是它可以让你保持每个单独的向量连续的记忆（如果你正在使用向量，那就是你想要的）。 您也不需要存储单独的索引向量。
xtofl的一个稍微更紧凑的变体的答案，如果你只是想通过一个单一的向量遍历所有的向量。 创build一个置换vector，并用它来索引你的其他vector。
#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; }
这将是Konrad答案的附录，因为它是一种将sorting顺序应用于向量的就地变体方法。 无论如何，因为编辑将不会通过我会把它放在这里
这是一个就地变体，其时间复杂度稍高，这是由于检查一个布尔值的原始操作。 额外的空间复杂度是一个向量，可以是一个空间高效的编译器依赖的实现。 如果给定的订单本身可以被修改，则vector的复杂性可以被消除。
这是一个就地变体，其时间复杂度稍高，这是由于检查一个布尔值的原始操作。 额外的空间复杂度是一个向量，可以是一个空间高效的编译器依赖的实现。 如果给定的订单本身可以被修改，则vector的复杂性可以被消除。 这是algorithm正在做的一个例子。 如果顺序是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; } } };
这是一个相对简单的实现，它使用有序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); }
为了完整起见，下面是函数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...
**// 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` }**
很多人问这个问题，没有人提出一个满意的答案。 这是一个std :: sort帮助器，它可以同时对两个向量进行sorting，同时考虑到只有一个向量的值。 这个解决scheme基于一个自定义的RadomIt（随机迭代器），并且直接在原始vector数据上运行，没有临时副本，结构重排或附加索引：
基于另一个向量sorting一个向量
