我怎样才能以相同的方式sorting两个向量，只使用其中一个向量？
我怎样才能以相同的方式sorting两个向量，只使用其中一个向量？
例如，假设我有两个相同大小的向量：
vector<MyObject> vectorA; vector<int> vectorB; 然后我使用一些比较函数对vectorA进行sorting。 该sorting重新sortingvectorA 。 我怎样才能有相同的重新sorting适用于vectorB ？
一个选项是创build一个结构体：
struct ExampleStruct { MyObject mo; int i; };
然后对包含vectorA和vectorB内容的vector进行sorting，将vectorB压缩成单个vector：
// vectorC[i] is vectorA[i] and vectorB[i] combined vector<ExampleStruct> vectorC;
这似乎不是一个理想的解决scheme。 还有其他的select，特别是在C + + 11？
寻找一个排列组合
给定一个std::vector<T>和一个std::vector<T>的比较，我们希望能够find你将使用的排列，如果你要使用这个比较sorting向量。
template <typename T, typename Compare> std::vector<std::size_t> sort_permutation( const std::vector<T>& vec, Compare& compare) { std::vector<std::size_t> p(vec.size()); std::iota(p.begin(), p.end(), 0); std::sort(p.begin(), p.end(), [&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); }); return p; }
应用sorting排列
给定一个std::vector<T>和一个排列，我们希望能够build立一个新的std::vector<T> ，它是根据排列重新sorting的。
template <typename T> std::vector<T> apply_permutation( const std::vector<T>& vec, const std::vector<std::size_t>& p) { std::vector<T> sorted_vec(vec.size()); std::transform(p.begin(), p.end(), sorted_vec.begin(), [&](std::size_t i){ return vec[i]; }); return sorted_vec; }
你当然可以修改apply_permutation来改变你给它的向量，而不是返回一个新的sorting副本。 这种方法仍然是线性的时间复杂度，并使用向量中的每个项目一位。 从理论上讲，它仍然是线性的空间复杂性。 但实际上，当sizeof(T)很大时，内存使用量的减less可能会很大。 （ 见详情 ）
template <typename T> void apply_permutation_in_place( std::vector<T>& vec, const std::vector<std::size_t>& p) { std::vector<bool> done(vec.size()); for (std::size_t i = 0; i < vec.size(); ++i) { if (done[i]) { continue; } done[i] = true; std::size_t prev_j = i; std::size_t j = p[i]; while (i != j) { std::swap(vec[prev_j], vec[j]); done[j] = true; prev_j = j; j = p[j]; } } }
例
vector<MyObject> vectorA; vector<int> vectorB; auto p = sort_permutation(vectorA, [](T const& a, T const& b){ /*some comparison*/ }); vectorA = apply_permutation(vectorA, p); vectorB = apply_permutation(vectorB, p);
资源
-
std::vector -
std::iota -
std::sort -
std::swap -
std::transform
就地sorting使用排列
我会使用像Timothy这样的排列，但是如果你的数据太大，你不想为sorting的向量分配更多的内存，你应该在原地进行 。 这是一个O（n）（线性复杂度） 就地sorting使用排列的例子：
诀窍是获得置换和相反排列，以知道将最后一个sorting步骤覆盖的数据放在哪里。
template <class K, class T> void sortByKey(K * keys, T * data, size_t size){ std::vector<size_t> p(size,0); std::vector<size_t> rp(size); std::vector<bool> sorted(size, false); size_t i = 0; // Sort std::iota(p.begin(), p.end(), 0); std::sort(p.begin(), p.end(), [&](size_t i, size_t j){ return keys[i] < keys[j]; }); // ----------- Apply permutation in-place ---------- // // Get reverse permutation item>position for (i = 0; i < size; ++i){ rp[p[i]] = i; } i = 0; K savedKey; T savedData; while ( i < size){ size_t pos = i; // Save This element; if ( ! sorted[pos] ){ savedKey = keys[p[pos]]; savedData = data[p[pos]]; } while ( ! sorted[pos] ){ // Hold item to be replaced K heldKey = keys[pos]; T heldData = data[pos]; // Save where it should go size_t heldPos = rp[pos]; // Replace keys[pos] = savedKey; data[pos] = savedData; // Get last item to be the pivot savedKey = heldKey; savedData = heldData; // Mark this item as sorted sorted[pos] = true; // Go to the held item proper location pos = heldPos; } ++i; } }
-
从您的个别向量中创build一个对的向量。
初始化对的向量
添加到一个对的向量 -
制作自定义sorting比较器：
sorting自定义对象的vector
http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B -
sorting您的对的向量。
-
分开你的载体对单个载体。
-
把所有这些放到一个函数中。
码：
std::vector<MyObject> vectorA; std::vector<int> vectorB; struct less_than_int { inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b) { return (a.second < b.second); } }; sortVecPair(vectorA, vectorB, less_than_int()); // make sure vectorA and vectorB are of the same size, before calling function template <typename T, typename R, typename Compare> sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp) { std::vector<pair<T,R>> vecC; vecC.reserve(vecA.size()); for(int i=0; i<vecA.size(); i++) { vecC.push_back(std::make_pair(vecA[i],vecB[i]); } std::sort(vecC.begin(), vecC.end(), cmp); vecA.clear(); vecB.clear(); vecA.reserve(vecC.size()); vecB.reserve(vecC.size()); for(int i=0; i<vecC.size(); i++) { vecA.push_back(vecC[i].first); vecB.push_back(vecC[i].second); } }
我假设vectorA和vectorB具有相同的长度。 你可以创build另一个vector，我们称之为pos，其中：
pos[i] = the position of vectorA[i] after sorting phase
然后，可以使用pos对vectorB进行sorting，即创buildvectorBsorted，其中：
vectorBsorted[pos[i]] = vectorB[i]
然后vectorBsorted按照与vectorA相同的索引排列进行sorting。
我不知道这是否有效，但我会使用这样的东西。 例如，要sorting两个向量，我会使用降序气泡sorting方法和向量对。
对于降序冒泡sorting，我会创build一个function，需要一个向量对。
void bubbleSort(vector< pair<MyObject,int> >& a) { bool swapp = true; while (swapp) { int key; MyObject temp_obj; swapp = false; for (size_t i = 0; i < a.size() - 1; i++) { if (a[i].first < a[i + 1].first) { temp_obj = a[i].first; key = a[i].second; a[i].first = a[i + 1].first; a[i + 1].first = temp_obj; a[i].second = a[i + 1].second; a[i + 1].second = key; swapp = true; } } } }
之后，我会把你的2vector值成一个向量对。 如果你可以同时使用这个值来添加数值，而不是调用冒泡sortingfunction。
vector< pair<MyObject,int> > my_vector; my_vector.push_back( pair<MyObject,int> (object_value,int_value)); bubbleSort(my_vector);
如果你想添加到你的2个向量后使用的值，你可以使用这个，而不是调用冒泡sortingfunction。
vector< pair<MyObject,int> > temp_vector; for (size_t i = 0; i < vectorA.size(); i++) { temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i])); } bubbleSort(temp_vector);
我希望这有帮助。 问候，凯恩
我想用我提出的一个扩展做出贡献。 目标是能够使用简单的语法同时对多个向量进行sorting。
sortVectorsAscending(criteriaVec, vec1, vec2, ...)
该algorithm与Timothy提出的algorithm相同，但是使用可变模板 ，所以我们可以同时对任意types的多个向量进行sorting。
以下是代码片段：
template <typename T, typename Compare> void getSortPermutation( std::vector<unsigned>& out, const std::vector<T>& v, Compare compare = std::less<T>()) { out.resize(v.size()); std::iota(out.begin(), out.end(), 0); std::sort(out.begin(), out.end(), [&](unsigned i, unsigned j){ return compare(v[i], v[j]); }); } template <typename T> void applyPermutation( const std::vector<unsigned>& order, std::vector<T>& t) { assert(order.size() == t.size()); std::vector<T> st(t.size()); for(unsigned i=0; i<t.size(); i++) { st[i] = t[order[i]]; } t = st; } template <typename T, typename... S> void applyPermutation( const std::vector<unsigned>& order, std::vector<T>& t, std::vector<S>&... s) { applyPermutation(order, t); applyPermutation(order, s...); } template<typename T, typename Compare, typename... SS> void sortVectors( const std::vector<T>& t, Compare comp, std::vector<SS>&... ss) { std::vector<unsigned> order; getSortPermutation(order, t, comp); applyPermutation(order, ss...); } // make less verbose for the usual ascending order template<typename T, typename... SS> void sortVectorsAscending( const std::vector<T>& t, std::vector<SS>&... ss) { sortVectors(t, std::less<T>(), ss...); }
在Ideonetesting。
我在这篇博客文章中解释了这一点。
实现operator< ExampleStruct
bool operator<(ExampleStruct const& es1, ExampleStruct const& es2) { return es1.i < es2.i; }
然后，对vectorC使用std::sort 。
std::sort(vectorC.begin(), vectorC.end());
