How Can I Sort Multiple Vectors in C Without Copying Data?

Sorting Zipped Containers in C Without Copying

Sorting multiple vectors concurrently without creating copies presents a unique challenge. Existing solutions often require duplication of data into tuples or structs, which is inefficient. This question explores an elegant solution that leverages the power of C libraries to achieve sorting without copying.

The Problem:

The goal is to sort multiple vectors in lock step, ensuring that corresponding elements remain paired. Copying the vectors would be redundant and undesirable.

Failed Attempts:

While boost::zip_iterator and boost::range::algorithm::sort appear promising, they reject read-only and non-random access iterators.

The Answer:

As suggested by interjay, using the custom TupleIteratorType from the "tupleit.hh" header enables us to bypass the limitations of built-in iterators. This allows us to define a custom sort function that works directly on the zipped vectors.

Here's a demonstration:

#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&amp;... 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&amp;,double&amp;,long&amp;> 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>() << &quot; &quot; << t.get<1>() << &quot; &quot; << 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;
}

This code sorts the vectors in place without copying them. The use of custom iterators and the "sort" function handles all necessary permutations.

Future Extension:

The current solution works well for sequence containers. To extend it to sortable containers such as lists, RandomAccess and Bidirectional TupleIterators would be required, along with a sorting algorithm that supports bidirectional iterators.

The above is the detailed content of How Can I Sort Multiple Vectors in C Without Copying Data?. For more information, please follow other related articles on the PHP Chinese website!