Сортировка сжатых (заблокированных) контейнеров в С++ с использованием boost или STL

Ответ 1

Здесь приведен рабочий пример, основанный на библиотеке range-v3, которая была предложена для стандартизации

#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 (требуется недавний компилятор с хорошей поддержкой С++ 14, а не VS 2015).

Ответ 2

Для двух контейнеров, здесь версия, которая компилируется на gcc 4.4.6, основывается на документе, упомянутом выше. В более поздних версиях gcc вы можете поменять boost:: tuple для std:: tuple

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

# include <boost/iterator/iterator_facade.hpp>
# include <boost/tuple/tuple.hpp> 

using namespace std;

template <class T, class T2>
struct helper_type {
  typedef boost::tuple<typename iterator_traits<T>::value_type, typename iterator_traits<T2>::value_type> value_type;
  typedef boost::tuple<typename iterator_traits<T>::value_type&, typename iterator_traits<T2>::value_type&> ref_type;
};

template <typename T1, typename T2>
class dual_iterator : public boost::iterator_facade<dual_iterator<T1, T2>,
                                                    typename helper_type<T1, T2>::value_type,
                                                    boost::random_access_traversal_tag,
                                                    typename helper_type<T1, T2>::ref_type> {
public:
   explicit dual_iterator(T1 iter1, T2 iter2) : mIter1(iter1), mIter2(iter2) {}
   typedef typename iterator_traits<T1>::difference_type difference_type;
private:
   void increment() { ++mIter1; ++mIter2; }
   void decrement() { --mIter1; --mIter2; }
   bool equal(dual_iterator const& other) const { return mIter1 == other.mIter1; }
   typename helper_type<T1, T2>::ref_type dereference() const { return (typename helper_type<T1, T2>::ref_type(*mIter1, *mIter2)); }
   difference_type distance_to(dual_iterator const& other) const { return other.mIter1 - mIter1; }
   void advance(difference_type n) { mIter1 += n; mIter2 += n; }

   T1 mIter1;
   T2 mIter2;
   friend class boost::iterator_core_access;
};

template <typename T1, typename T2>
dual_iterator<T1, T2> make_iter(T1 t1, T2 t2) { return dual_iterator<T1, T2>(t1, t2); }

template <class T1, class T2> struct iter_comp {
  typedef typename helper_type<T1, T2>::value_type T;
  bool operator()(const T& t1, const T& t2) { return get<0>(t1) < get<0>(t2); }
};

template <class T1, class T2> iter_comp<T1, T2> make_comp(T1 t1, T2 t2) { return iter_comp<T1, T2>(); }

template<class T> void print(T& items) {
  copy(items.begin(), items.end(), ostream_iterator<typename T::value_type>(cout, " ")); cout << endl;
}

int main() {
  vector<double> nums1 = {3, 2, 1, 0};
  vector<char> nums2 = {'D','C', 'B', 'A'};
  sort(make_iter(nums1.begin(), nums2.begin()), 
       make_iter(nums1.end(), nums2.end()), 
       make_comp(nums1.begin(), nums2.begin()));
  print(nums1);
  print(nums2);
}

Ответ 3

Создайте вспомогательный массив, содержащий индексы 0..N-1. Сортируйте этот массив с помощью специализированного компаратора, который фактически возвращает результаты сравнения элементов одного из ваших основных массивов. Затем используйте отсортированный вспомогательный массив для распечатки первичных массивов в правильном порядке.

Ответ 4

Приятно познакомиться с другим интернет-археологом!

Как сортировать N векторов в шаге блокировки (zipped)? Проблема выглядит довольно общий и общий, поэтому я предполагаю, что должно быть простое решение через, вероятно, очень сложную библиотеку, но я просто не могу ее найти.

Иногда назад я продолжал ту же охоту за сокровищами с аналогичными предположениями...
Никогда не находил сокровище: (

Я следил за теми же дорожками, что и вы:

• Пройдите через обычные подозреваемые boost.iterator/boost.range/boost.fusion/boost.oven, и после довольно много экспериментов и исследований поймите, что они не могут решить эту конкретную проблему.
• Пройдите много вопросов на SO, только чтобы понять, что каждый из них был закрыт либо с неправильным ответом (например, рекомендуя boost:: zip_iterator, который не работает в этом случае, когда вы указываете), либо с некоторым обходным решением которые избегают сути дела.
• Пройдите много сообщений в блоге, список рассылки, только чтобы понять, что никто на самом деле не решил проблему, кроме....
• После долгих исследований окончательно откопайте старый код от Антониуса Вильгельма, который утверждает, что разработал общее решение "TupleIterator" и заблокировал его в каком-то архиве "tupleit.zip". Исторические источники настолько ограничены в этом, что я до сих пор не уверен, что этот архив - это миф, легенда или если он все еще похоронен где-то в потерянном слое Интернета:)

Хорошо, более серьезно, статья Энтони Уильямса предполагает, что проблема на самом деле действительно сложная, поэтому не удивительно, что никакая существующая библиотека, подобная boost, не решила ее.

Ответ 5

Я рад сказать, что нашел решение после похожей охоты за сокровищами. range-v3 - отличная идея, если вы можете его использовать, но если вам действительно нужен итератор, проект HPX создал один, и он работает отлично с сортировкой.

Из-за недосмотра, который, как мы надеемся, будет исправлен, он по-прежнему требует, чтобы вы связывались с библиотекой HPX, но это ОК для меня, потому что все дело в том, чтобы использовать параллельные алгоритмы С++ 17, которые HPX обеспечивает реализацию.

#include <hpx/util/zip_iterator.hpp>

using zip_it = 
    hpx::util::zip_iterator<std::vector<std::size_t>::iterator,
                            std::vector<std::size_t>::iterator,
                            std::vector<double>::iterator>;

int main() {
    std::vector<std::size_t> rows{3, 2, 1};
    std::vector<std::size_t> cols{1, 2, 3};
    std::vector<double> values{4.0, 5.0, 6.0};

    auto start = hpx::util::make_zip_iterator(rows.begin(), cols.begin(), values.begin());
    auto stop  = hpx::util::make_zip_iterator(rows.end(), cols.end(), values.end());

    std::sort(start, stop);

    for ( int i = 0; i < 3; ++i ) {
        std::cerr << rows[i] << ", " << cols[i] << ", " << values[i] << "\n";
    }
}