Sorting zipped (locked) containers in C++ using boost or the STL

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;

This should output:

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).

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...

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:

Copy your vectors into a pair/tuple and sort that tuple...
Copy your vectors into a struct with one member per vector and sort a vector of structs...
Implement your own sorting function for your particular problem...
Use an auxiliary array of indices...
Use boost::zip_iterator without an example or with an example that produces bad results.

Hints:

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.

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;
}

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.

Update: this works for combinations of sequence-like containers. However mixing a list would require that std::sort supported BidirectionalIterators (which does not).

Solution

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';
}

Live Example (requires recent compiler with good C++14 support, not VS 2015).