我想做什么:我要排序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 ::排序我的问题(如提取排列)。
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).
我已经tryed: boost::zip_iterator和提高:: zip_range (带升压::合并范围),但两者的std ::排序和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个向量(压缩)?这个问题看起来pretty的通用和通用,所以我想必须有通过可能非常复杂的库一个简单的解决方案,但我不能找到它......
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...
注:是,也有计算器类似的问题,这个问题被问了很多不同的形式。但是他们总是封闭的下列答案之一:
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邮件列表指向这个纸安东尼·威廉斯。尽管这似乎只对对,他们也铁饼TupleIteratorType,但我一直没能找到它。 user673679 发现this发布包含两个容器的情况下一个很好的解决方案。它还指甲下来的问题(重点是我的): 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评论(这也部分地回答了的的未来的问题的):
Answer: see comment by interjay below (this also partially answers the future question):
#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;
}
未来的问题:的previous答案适用于序列容器。我们能得到它也上班的排序的容器(如序列和列表)?这就需要random_access和双向TupleIterators以及排序算法的双向迭代器的工作原理。
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 ::排序支持BidirectionalIterators(不)。
Update: this works for combinations of sequence-like containers. However mixing a list would require that std::sort supported BidirectionalIterators (which does not).
下面的基础上, 范围-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) << '\n';
std::cout << view::all(a2) << '\n';
}
活生生的例子 (需要近期的编译器具有良好的C ++ 14的支持,没有VS 2015)。
Live Example (requires recent compiler with good C++14 support, not VS 2015).
上一篇:子集和算法子集、算法