1

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

Nik Ved
  • 168
  • 2
  • 8
  • "*I have a random access iterator representing keys*" Iterators represent a position in a sequence. So you have a position of a key in some sequence of keys; that alone isn't really useful. That's why most algorithms take pairs of iterators, one representing the start, and one representing past-the-end. – Nicol Bolas Jun 03 '20 at 04:19
  • Random access iterator by definition supports all the operations like a basic pointer. So, I have a range that I want to sort (say, from it to it + len). The issue is that I want to sort two "arrays" simultaneously without any overhead of extra memory copy.. – Nik Ved Jun 03 '20 at 04:27
  • "*from it to it + len*" Then you don't just have an iterator; you have an iterator *and a size*. – Nicol Bolas Jun 03 '20 at 04:28
  • Only if I want to sort it, but what if I want to view two arrays as one array? – Nik Ved Jun 03 '20 at 04:29
  • Make a new class/object/struct which holds your values. Most maps in languages use something like `Entry` or `Pair` – Rogue Jun 03 '20 at 04:36
  • Storing pairs of values is a double copy. Suppose I have two huge arrays, and only pointers to them. Now I want to see them as one to, potentially, perform partial sorts and what not... – Nik Ved Jun 03 '20 at 04:40
  • @NikVed what you mean by sort by 2 iterator. because either you sort by first **or** sort by second. can you give examples? – apple apple Jun 03 '20 at 06:57
  • You are correct, I had to be more specific. I want to sort by keys, but any operations on the key iterator have to be performed on the value iterator (swaps, derefs, operator[]). – Nik Ved Jun 03 '20 at 07:04
  • I was able to resolve the swap problem by creating a wrapper of 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? – Nik Ved Jun 05 '20 at 13:00
  • @NikVed If you have two separate arrays whose values correspond 1:1 to each other, then why not just use a single array of pairs instead? – Remy Lebeau Jun 05 '20 at 20:48
  • @RemyLebeau, "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". And I am not in control of their creation... – Nik Ved Jun 05 '20 at 20:50
  • The easiest thing is [`boost::zip_iterator`](https://www.boost.org/doc/libs/1_41_0/libs/iterator/doc/zip_iterator.html), which is literally designed to do exactly this. – Mooing Duck Jun 05 '20 at 21:09
  • @MooingDuck As mentioned in the description, no boost, only core C++. But you are right it is a great inspiration. – Nik Ved Jun 05 '20 at 21:10

1 Answers1

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.

Nik Ved
  • 168
  • 2
  • 8