A random access iterator over two random access iterators

Question

Suppose I have a random access iterator (see also relevant type traits) representing keys, and a random access iterator representing values (not necessarily a single value, mind you!). Is it possible to combine them into a new random access iterator to perform, say, simultaneous sort with std::sort (by keys, but permute both keys and values at the same time)? std::sort only accepts one iterator. And how do I do it using only core C++?

I tried to specify a new iterator over a tuple of references, but the problem is how do I make swap work with rvalues (with some proxies?)?

Moreover, these two sequences are of huge size, so I cannot copy their values to create pairs, or even allocate a data structure of references. In fact, you can try and see that you cannot sort a vector of reference pairs (think about the behavior of operator= in this context). So, this code will fail (unless std::sort decides to use swap only):

  int arr1[] = {3, 2, -100, 5, 6, -200, 4, 0, -1, 2, 11, 12, -3, -4, -15};
  int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};

  std::vector<std::tuple<int&, int&>> pairs;
  for (int i = 0; i < len; ++i) {
    pairs.push_back(std::tie(arr1[i], arr2[i]));
  }
  std::sort(pairs.begin(), pairs.end(), [](auto lhs, auto rhs) {return std::get<0>(lhs) < std::get<1>(rhs);});

arrays print outs:
-15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15 -15
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14

So far I found this: https://web.archive.org/web/20120422174751/http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html. This solution uses boost, however, and is not swap compatible.

Update: I was able to resolve the swap problem by creating a wrapper over a tuple of references. But now I have a move problem. std::sort extracts and assigns values. But how do I do that for references? (see the broken code above).

Answer 1

Inspired by this thread it seems I was able to resolve the issue by writing a custom wrapper over tuple like this:

template <typename ...Ts>
struct references_holder {
  using tuple_references = std::tuple<Ts&...>;
  using tuple_values = std::tuple<Ts...>;

  references_holder(tuple_references data)
    : data{data}
  {}

  operator tuple_references() {
    return data;
  }

  tuple_references& as_tuple() {
    return data;
  }

  operator tuple_values() {
    return data;
  }

  references_holder& operator=(tuple_values val) {
    data = val;
    return *this;
  }

  tuple_references data;
};

template <typename ...Ts>
void swap(references_holder<Ts...> th1, references_holder<Ts...> th2) {
  return std::swap(th1.data, th2.data);
}

template<int N, typename ...Ts>
auto get(references_holder<Ts...>& th) -> decltype(std::get<N>(th.data)){
  return std::get<N>(th.data);
}

And in my composite iterator:

template <typename KeyIterator, typename ValueIterator>
class CompositeIterator {
public:  
  using key_iterator_value_type =
    typename std::iterator_traits<KeyIterator>::value_type;
  using value_iterator_value_type =
    typename std::iterator_traits<ValueIterator>::value_type;

  using value_type = std::tuple<
    key_iterator_value_type,
    value_iterator_value_type>;
  using reference = references_holder<
    key_iterator_value_type,
    value_iterator_value_type>;
...

It definitely assumes that the template-dependent types have reference = value_type&. The rest is implemented based on value_type and reference.