使用 boost 或 STL 在 C++ 中对压缩(锁定)容器进行排序 [英] Sorting zipped (locked) containers in C++ using boost or the STL
问题描述
我想要做什么:我想对 2、3 或 N 个向量进行排序，锁定在一起，不将它们复制到一个元组中.也就是说，把冗长放在一边，比如:
What I want to do: I want to sort 2, or 3, or N vectors, locked together, without copying them into a tuple. That is, leaving verbosity aside, something like:
vector<int> v1 = { 1, 2, 3, 4, 5};
vector<double> v2 = { 11, 22, 33, 44, 55};
vector<long> v3 = {111, 222, 333, 444, 555};
typedef tuple<int&,double&,long&> tup_t;
sort(zip(v1,v2,v3),[](tup_t t1, tup_t t2){ return t1.get<0>() > t2.get<0>(); });
for(auto& t : zip(v1,v2,v3))
cout << t.get<0>() << " " << t.get<1>() << " " << t.get<2>() << endl;
这应该输出:
5 55 555
4 44 444
...
1 11 111
我现在的做法:我已经实现了我自己的快速排序，其中我传递的第一个数组用于比较，并且排列应用于所有其他数组.我只是不知道如何重用 std::sort 来解决我的问题(例如提取排列).
How I am doing it right now: I have implemented my own quicksort, where the first array I pass is used for the comparison, and the permutations are applied to all other arrays. I just couldn't figure out how to reuse std::sort for my problem (e.g. extract permutations).
我尝试过的: boost::zip_iterator 和 boost::zip_range(带有 boost::combine 范围)，但 std::sort 和 boost::range::algorithm::sort 抱怨迭代器/范围是只读的，而不是随机访问......
What I've tryed: boost::zip_iterator and boost::zip_range (with boost::combine range), but both std::sort and boost::range::algorithm::sort complain that the iterators/ranges are read only and not random access...
问题: 如何在锁步(压缩)中对 N 个向量进行排序?这个问题看起来非常普遍和常见，所以我想通过一个可能非常复杂的库必须有一个简单的解决方案，但我找不到它......
Question: How do I sort N vectors in lock step (zipped)? The problem looks pretty generic and common so I guess there must be an easy solution through a probably very complex library but I just can't find it...
备注: 是的，stackoverflow 中也有类似的问题，这个问题以不同的形式被问到很多.但是，它们总是以以下答案之一关闭:
Remarks: yes, there are similar questions in stackoverflow, this question gets asked a lot in different forms. However they are always closed with one of the following answers:
- 将您的向量复制到一对/元组中并对该元组进行排序...
- 将您的向量复制到一个结构中，每个向量有一个成员，并对结构向量进行排序...
- 针对您的特定问题实现您自己的排序功能...
- 使用辅助索引数组...
- 使用 boost::zip_iterator 不带示例或带有产生不良结果的示例.
提示:
- 我在 boost 邮件列表 指向 Anthony Williams 的这篇论文.虽然这似乎只适用于成对，但他们也讨论了 TupleIteratorType，但我找不到它.
- user673679 找到了 这篇 帖子包含一个很好的解决方案，适用于两个容器的情况.它还确定了问题(重点是我的):
- I've found this thread in the boost mailing list which points to this paper from Anthony Williams. Although this seems to only work for pairs, they also discus a TupleIteratorType but I haven't been able to find it.
- user673679 found this post containing a nice solution for the two container case. It also nails down the problem (the emphasis is mine):
[...] 根本问题是对"数组引用的行为不像它们应该的那样 [...] 我只是决定滥用迭代器的符号并编写一些有效的东西.这实际上涉及编写一个不符合规范的迭代器，其中值类型的引用与引用类型不同.
[...] the fundamental problem is that "pairs" of array references do not behave like they should [...] I simply decided to abuse the notation of an iterator and write something that works. This involved writing, effectively, a non-conforming iterator where the reference of the value type is not the same as the reference type.
答案:见下面 interjay 的评论(这也部分回答了未来的问题):
#include "tupleit.hh"
#include <vector>
#include <iostream>
#include <boost/range.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/algorithm/for_each.hpp>
template <typename... T>
auto zip(T&... containers)
-> boost::iterator_range<decltype(iterators::makeTupleIterator(std::begin(containers)...))> {
return boost::make_iterator_range(iterators::makeTupleIterator(std::begin(containers)...),
iterators::makeTupleIterator(std::end(containers)...));
}
int main() {
typedef boost::tuple<int&,double&,long&> tup_t;
std::vector<int> a = { 1, 2, 3, 4 };
std::vector<double> b = { 11, 22, 33, 44 };
std::vector<long> c = { 111, 222, 333, 444 };
auto print = [](tup_t t){ std::cout << t.get<0>() << " " << t.get<1>() << " " << t.get<2>() << std::endl; };
boost::for_each( zip(a, b, c), print);
boost::sort( zip(a, b, c), [](tup_t i, tup_t j){ return i.get<0>() > j.get<0>(); });
for ( auto tup : zip(a, b, c) ) print(tup);
return 0;
}
未来问题:上一个答案适用于序列容器.我们能否让它也适用于 sortable 容器(例如序列和列表)?这将需要 random_access 和双向 TupleIterator 以及适用于双向迭代器的排序算法.
Future question: the previous answer works for sequence containers. Could we get it also to work on sortable containers (e.g. sequences and lists)? This would require random_access and bidirectional TupleIterators as well as a sort algorithm that works on bidirectional iterators.
更新:这适用于类似序列的容器的组合.但是，混合列表需要 std::sort 支持双向迭代器(不支持).
Update: this works for combinations of sequence-like containers. However mixing a list would require that std::sort supported BidirectionalIterators (which does not).
推荐答案
这是一个基于 range-v3 的工作示例 已建议标准化的库
Here's a working example based on the range-v3 Library that has been proposed for Standardization
#include <range/v3/all.hpp>
#include <iostream>
using namespace ranges;
int main()
{
std::vector<int> a1{15, 7, 3, 5};
std::vector<int> a2{ 1, 2, 6, 21};
sort(view::zip(a1, a2), std::less<>{}, &std::pair<int, int>::first);
std::cout << view::all(a1) << '
';
std::cout << view::all(a2) << '
';
}
实时示例(需要具有良好 C++14 支持的最新编译器，不是 VS 2015).
Live Example (requires recent compiler with good C++14 support, not VS 2015).
这篇关于使用 boost 或 STL 在 C++ 中对压缩(锁定)容器进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
