C++ 如何以相同的方式对两个向量进行排序，而标准仅使用其中一个向量？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17074324/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I sort two vectors in the same way, with criteria that uses only one of the vectors?
提问by user2381422
How can I sort two vectors in the same way, with criteria that uses only one of the vectors?
如何以相同的方式对两个向量进行排序，而标准仅使用其中一个向量？
For example, suppose I have two vectors of the same size:
例如，假设我有两个大小相同的向量：
vector<MyObject> vectorA;
vector<int> vectorB;
I then sort vectorAusing some comparison function. That sorting reordered vectorA. How can I have the same reordering applied to vectorB?
然后我vectorA使用一些比较函数进行排序。该排序重新排序vectorA。如何将相同的重新排序应用于vectorB？
One option is to create a struct:
一种选择是创建一个结构：
struct ExampleStruct {
MyObject mo;
int i;
};
and then sort a vector that contains the contents of vectorAand vectorBzipped up into a single vector:
然后对包含以下内容的向量进行排序，vectorA并将其vectorB压缩为单个向量：
// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;
This doesn't seem like an ideal solution. Are there other options, especially in C++11?
这似乎不是一个理想的解决方案。还有其他选择吗，尤其是在 C++11 中？
回答by Timothy Shields
Finding a sort permutation
查找排序排列
Given a std::vector<T>and a comparison for T's, we want to be able to find the permutation you would use if you were to sort the vector using this comparison.
给定 astd::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;
}
Applying a sort permutation
应用排序排列
Given a std::vector<T>and a permutation, we want to be able to build a new std::vector<T>that is reordered according to the permutation.
给定 astd::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;
}
You could of course modify apply_permutationto mutate the vector you give it rather than returning a new sorted copy. This approach is still linear time complexity and uses one bit per item in your vector. Theoretically, it's still linear space complexity; but, in practice, when sizeof(T)is large the reduction in memory usage can be dramatic. (See details)
您当然可以修改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];
}
}
}
Example
例子
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);
Resources
资源
回答by Jarod42
With range-v3, it is simple, sort a zip view:
使用range-v3，很简单，对 zip 视图进行排序：
std::vector<MyObject> vectorA = /*..*/;
std::vector<int> vectorB = /*..*/;
ranges::v3::sort(ranges::view::zip(vectorA, vectorB));
or explicitly use projection:
或明确使用投影：
ranges::v3::sort(ranges::view::zip(vectorA, vectorB),
std::less<>{},
[](const auto& t) -> decltype(auto) { return std::get<0>(t); });
回答by tuket
I would like to contribute with a extension I came up with. The goal is to be able to sort multiple vectors at the same time using a simple syntax.
我想贡献一个我想出的扩展。目标是能够使用简单的语法同时对多个向量进行排序。
sortVectorsAscending(criteriaVec, vec1, vec2, ...)
The algorithm is the same as the one Timothy proposed but using variadic templates, so we can sort multiple vectors of arbitrary types at the same time.
该算法与 Timothy 提出的算法相同，但使用可变参数模板，因此我们可以同时对多个任意类型的向量进行排序。
Here's the code snippet:
这是代码片段：
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...);
}
Test it in Ideone.
在Ideone 中进行测试。
I explain this a little bit better in this blog post.
我在这篇博文中更好地解释了这一点。
回答by MtCS
In-place sorting using permutation
使用置换就地排序
I would use a permutation like Timothy, although if your data is too large and you don't want to allocate more memory for the sorted vector you should do it in-place. Here is a example of a O(n) (linear complexity) in-place sorting using permutation:
我会使用像 Timothy 这样的排列，但如果您的数据太大并且您不想为排序向量分配更多内存，您应该就地进行。以下是使用置换的 O(n)（线性复杂度）就地排序的示例 ：
The trick is to get the permutation and the reverse permutation to know where to put the data overwritten by the last sorting step.
诀窍是获得排列和反向排列，以知道将最后一个排序步骤覆盖的数据放在哪里。
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;
}
}
回答by ruben2020
Make a vector of pairs out of your individual vectors.
initialize vector of pairs
Adding to a vector of pairMake a custom sort comparator:
Sorting a vector of custom objects
http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2BSort your vector of pairs.
Separate your vector of pairs into individual vectors.
Put all of these into a function.
制作自定义排序比较器：
排序自定义对象的向量
http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B对你的向量进行排序。
将成对的向量分成单独的向量。
将所有这些放入一个函数中。
Code:
代码：
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);
}
}
回答by DarioP
I have recently wrote a proper zip iterator which works with the stl algorithms. It allows you to produce code like this:
我最近编写了一个适用于 stl 算法的适当的 zip 迭代器。它允许您生成这样的代码：
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;
It is contained in a single header and the only requirement is C++17. Check it out on GitHub.
它包含在单个头文件中，唯一的要求是 C++17。在GitHub 上查看。
There is also a post on codereviewwhich contains all the source code.
还有一篇关于codereview的帖子，其中包含所有源代码。
回答by Caner SAYGIN
I am not sure if this works but i would use something like this. For example to sort two vectors i would use descending bubble sort method and vector pairs.
我不确定这是否有效，但我会使用这样的东西。例如，要对两个向量进行排序，我将使用降序冒泡排序方法和向量对。
For descending bubble sort, i would create a function that requires a vector pair.
对于降序冒泡排序，我会创建一个需要向量对的函数。
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;
}
}
}
}
After that i would put your 2 vector values into one vector pair. If you are able to add values at the same time use this one and than call the bubble sort function.
之后，我会将您的 2 个向量值放入一个向量对中。如果您能够同时添加值，请使用此方法，而不是调用冒泡排序函数。
vector< pair<MyObject,int> > my_vector;
my_vector.push_back( pair<MyObject,int> (object_value,int_value));
bubbleSort(my_vector);
If you want to use values after adding to your 2 vectors, you can use this one and than call the bubble sort function.
如果您想在添加到 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);
I hope this helps. Regards, Caner
我希望这有帮助。问候， 卡纳
回答by pkacprzak
I'm assuming that vectorA and vectorB have equal lengths. You could create another vector, let's call it pos, where:
我假设 vectorA 和 vectorB 的长度相等。您可以创建另一个向量，我们称之为 pos，其中：
pos[i] = the position of vectorA[i] after sorting phase
pos[i] = the position of vectorA[i] after sorting phase
and then, you can sort vectorB using pos, i.e create vectorBsorted where:
然后，您可以使用 pos 对 vectorB 进行排序，即在其中创建 vectorBsorted：
vectorBsorted[pos[i]] = vectorB[i]
and then vectorBsorted is sorted by the same permutation of indexes as vectorA is.
然后 vectorBsorted 按与 vectorA 相同的索引排列排序。
