Как я могу одинаково отсортировать два вектора, используя критерий, который использует только один из векторов?
Например, предположим, что у меня есть два вектора одинакового размера:
vector<MyObject> vectorA;
vector<int> vectorB;
Затем я сортирую, vectorA
используя некоторую функцию сравнения. Порядок сортировки изменился vectorA
. Как я могу применить такое же изменение порядка vectorB
?
Один из вариантов - создать структуру:
struct ExampleStruct {
MyObject mo;
int i;
};
а затем отсортируйте вектор, содержащий содержимое vectorA
и vectorB
заархивированный в один вектор:
// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;
Это не похоже на идеальное решение. Есть ли другие варианты, особенно в C ++ 11?
vectorA
и то иvectorB
другое по содержимомуvectorB
.vector<pair<MyObject, int>>
. Тогда вам не придется беспокоиться о рассинхронизации двух списков; одна сортировка переупорядочивает оба набора данных одновременно. И нет никакой дополнительной структуры для написания.Ответы:
Поиск перестановки сортировки
Учитывая a
std::vector<T>
и сравнение дляT
's, мы хотим иметь возможность найти перестановку, которую вы использовали бы, если бы вы отсортировали вектор, используя это сравнение.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; }
Применение перестановки сортировки
Учитывая a
std::vector<T>
и перестановку, мы хотим иметь возможность построить новый,std::vector<T>
который переупорядочивается в соответствии с перестановкой.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
вектор, который вы ему передаете, вместо того, чтобы возвращать новую отсортированную копию. Этот подход по-прежнему имеет линейную временную сложность и использует один бит на элемент в вашем векторе. Теоретически это все еще линейная пространственная сложность; но на практике, когдаsizeof(T)
оно велико, сокращение использования памяти может быть значительным. ( Подробнее )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
источник
apply_permutation
чтобы изменить вектор, который вы ему даете, вместо того, чтобы возвращать новую отсортированную копию. » Я бы нашел конкретизацию этого, по крайней мере концептуально, полезным дополнением к ответу. Вы бы реализовали это так же, как и онapply_permutation
сам?Compare& compare
должно быть константным . В противном случае вы не сможете использовать std :: less <T> или подобное.С range-v3 просто отсортируйте zip-представление:
std::vector<MyObject> vectorA = /*..*/; std::vector<int> vectorB = /*..*/; ranges::v3::sort(ranges::view::zip(vectorA, vectorB));
или явно использовать проекцию:
ranges::v3::sort(ranges::view::zip(vectorA, vectorB), std::less<>{}, [](const auto& t) -> decltype(auto) { return std::get<0>(t); });
Демо
источник
Я хотел бы внести свой вклад в расширение, которое я придумал. Цель состоит в том, чтобы иметь возможность сортировать несколько векторов одновременно, используя простой синтаксис.
Алгоритм тот же, что предложил Тимоти, но с использованием вариативных шаблонов. , поэтому мы можем сортировать несколько векторов произвольных типов одновременно.
Вот фрагмент кода:
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...); }
Протестируйте в Ideone .
Я объясню это немного лучше в этом сообщении в блоге .
источник
Сортировка на месте с использованием перестановки
Я бы использовал перестановку, такую как Тимоти, хотя, если ваши данные слишком велики и вы не хотите выделять больше памяти для отсортированного вектора, вы должны сделать это на месте . Вот пример сортировки на месте O (n) (линейная сложность) с использованием перестановки :
Хитрость заключается в том, чтобы получить перестановку и обратную перестановку, чтобы знать, куда поместить данные, перезаписанные на последнем этапе сортировки.
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; } }
источник
Составьте вектор из ваших индивидуальных векторов.
инициализировать вектор пар
Добавление к вектору пары
Создайте собственный компаратор
сортировки : Сортировка вектора настраиваемых объектов
http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B
Отсортируйте свой вектор пар.
Разделите свой вектор пар на отдельные векторы.
Поместите все это в функцию.
Код:
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 имеют одинаковую длину. Вы можете создать другой вектор, назовем его pos, где:
pos[i] = the position of vectorA[i] after sorting phase
а затем вы можете отсортировать vectorB с помощью pos, т.е. создать vectorBsorted, где:
а затем vectorBsorted сортируется по той же перестановке индексов, что и vectorA.
источник
Я не уверен, работает ли это, но я бы использовал что-то вроде этого. Например, для сортировки двух векторов я бы использовал метод сортировки по убыванию пузырьков и пары векторов.
Для сортировки по убыванию пузырьков я бы создал функцию, которая требует векторной пары.
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; } } } }
После этого я бы поместил ваши 2 векторных значения в одну векторную пару. Если вы можете добавлять значения одновременно, используйте это, а затем вызовите функцию пузырьковой сортировки.
vector< pair<MyObject,int> > my_vector; my_vector.push_back( pair<MyObject,int> (object_value,int_value)); bubbleSort(my_vector);
Если вы хотите использовать значения после добавления к вашим 2 векторам, вы можете использовать это, а затем вызвать функцию пузырьковой сортировки.
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);
Надеюсь, это поможет. С уважением, Канер
источник
Недавно я написал правильный итератор zip, который работает с алгоритмами stl. Это позволяет вам создавать такой код:
std::vector<int> a{3,1,4,2}; std::vector<std::string> b{"Alice","Bob","Charles","David"}; auto zip = Zip(a,b); std::sort(zip.begin(), zip.end()); for (const auto & z: zip) std::cout << z << std::endl;
Он содержится в одном заголовке, и единственное требование - C ++ 17. Проверьте это на GitHub .
Также есть сообщение о codereview, которое содержит весь исходный код.
источник
На основе ответа Тимоти Шилдса.
С помощью небольшой настройки
apply_permutaion
вы можете применить перестановку к нескольким векторам разных типов одновременно с использованием выражения свертки.template <typename T, typename... Ts> void apply_permutation(const std::vector<size_t>& perm, std::vector<T>& v, std::vector<Ts>&... vs) { std::vector<bool> done(v.size()); for(size_t i = 0; i < v.size(); ++i) { if(done[i]) continue; done[i] = true; size_t prev = i; size_t curr = perm[i]; while(i != curr) { std::swap(v[prev], v[curr]); (std::swap(vs[prev], vs[curr]), ...); done[curr] = true; prev = curr; curr = perm[curr]; } } }
источник