Trier des conteneurs zippés (verrouillés) en C++ en utilisant boost ou la STL

Question

Ce que je veux faire : Je veux trier 2, ou 3, ou N vecteurs, verrouillés ensemble, sans les copier en un tuple. C'est-à-dire, en laissant de côté la verbosité, quelque chose comme :

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;

Cela devrait donner un résultat :

5 55 555
4 44 444
...
1 11 111

Comment je le fais en ce moment : J'ai implémenté mon propre quicksort, où le premier tableau que je passe est utilisé pour la comparaison, et les permutations sont appliquées à tous les autres tableaux. Je n'ai pas réussi à trouver comment réutiliser std::sort pour mon problème (par exemple, extraire les permutations).

Ce que j'ai essayé : boost::zip_iterator y boost::zip_range (avec boost::combine range), mais std::sort et boost::range::algorithme::sort se plaindre que les itérateurs/plages sont en lecture seule et non en accès aléatoire...

Question : Comment trier N vecteurs en lock step (zippé) ? Le problème semble assez générique et commun, donc je suppose qu'il doit y avoir une solution facile à travers une bibliothèque probablement très complexe, mais je ne la trouve pas...

Remarques : oui, il y a des questions similaires sur stackoverflow, cette question est souvent posée sous différentes formes. Cependant, elles se terminent toujours par l'une des réponses suivantes :

• Copiez vos vecteurs dans une paire/tuple et triez ce tuple...
• Copiez vos vecteurs dans un struct avec un membre par vecteur et triez un vecteur de structs...
• Implémentez votre propre fonction de tri pour votre problème particulier...
• Utiliser un tableau auxiliaire d'indices...
• Utilisez boost::zip_iterator sans exemple ou avec un exemple qui donne de mauvais résultats.

Des conseils :

• J'ai trouvé ce fil de discussion dans le liste d'adresses de relance qui pointe vers ce papier d'Anthony Williams. Bien que cela semble ne fonctionner que pour les paires, ils discutent également un TupleIteratorType mais je n'ai pas été capable de le trouver.
• utilisateur673679 trouvé este post contenant une belle solution pour le cas des deux conteneurs. Il définit également le problème (c'est moi qui souligne) :

[...] le problème fondamental est que les "paires" de références de tableaux ne se comportent pas comme elles le devraient [...] J'ai simplement décidé d'abuser de la notation d'un itérateur et d'écrire quelque chose qui fonctionne. Cela a impliqué l'écriture, en fait, d'un itérateur non-conforme où la référence du type de valeur n'est pas la même que celle du type de référence.

Réponse : voir le commentaire d'interjay ci-dessous (ceci répond aussi partiellement à la question 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;
}

Question à venir : la réponse précédente fonctionne pour les conteneurs de séquence. Pourrions-nous la faire fonctionner également sur triable des conteneurs (par exemple, des séquences et des listes) ? Cela nécessiterait un accès aléatoire et des TupleIterators bidirectionnels ainsi qu'un algorithme de tri qui fonctionne sur les itérateurs bidirectionnels.

Mise à jour : cela fonctionne pour les combinaisons de conteneurs de type séquence. Cependant, pour mélanger une liste, il faudrait que std::sort supporte les BidirectionalIterators (ce qui n'est pas le cas).

Answer 1

Voici un exemple de travail basé sur le gamme-v3 Bibliothèque qui a été proposée pour la normalisation

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

Exemple en direct (nécessite un compilateur récent avec un bon support du C++14, pas VS 2015).

Answer 2

Pour le cas des deux conteneurs, voici une version qui compile sur gcc 4.4.6, basée sur le document mentionné ci-dessus. Dans les versions ultérieures de gcc, vous pouvez remplacer boost::tuple par 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);
}

Answer 3

Créez un tableau auxiliaire qui contient les indices 0..N-1. Triez ce tableau avec un comparateur personnalisé qui renvoie les résultats de la comparaison des éléments de l'un de vos tableaux primaires. Utilisez ensuite le tableau auxiliaire trié pour imprimer vos tableaux primaires dans le bon ordre.

Answer 4

Ravi de rencontrer un collègue archéologue sur Internet !

Comment trier N vecteurs en lock step (zippé) ? Le problème semble assez générique et commun donc je suppose qu'il doit y avoir une solution facile à travers une bibliothèque probablement très complexe mais je ne la trouve pas.

Il y a quelques temps, j'ai participé à la même chasse au trésor avec des hypothèses similaires...
Je n'ai jamais trouvé le trésor :(

J'ai suivi les mêmes traces que vous :

• Je passe en revue les suspects habituels boost.iterator/boost.range/boost.fusion/boost.oven et après pas mal d'expérimentation et de recherche, je réalise qu'ils ne peuvent pas résoudre ce problème particulier.
• J'ai parcouru de nombreuses questions sur SO, pour me rendre compte que chacune d'entre elles a été fermée soit avec une réponse incorrecte (par exemple recommander boost::zip_iterator qui ne fonctionne pas dans ce cas comme vous l'avez souligné), soit avec une solution de contournement qui évite le cœur du problème.
• Vous avez parcouru de nombreux articles de blog, de listes de diffusion, pour vous rendre compte que personne n'a vraiment résolu le problème sauf.....
• Après de nombreuses recherches, nous avons finalement retrouvé le vieux codex d'Antonius Wilhelm, qui prétend avoir conçu une solution générale "TupleIterator" et l'avoir enfermée dans une archive "tupleit.zip". Les sources historiques sont si rares à ce sujet que je ne sais toujours pas si cette archive est un mythe, une légende ou si elle est toujours enfouie quelque part dans une couche perdue de l'internet :)

Ok, plus sérieusement, l'article d'Anthony Williams suggère que le problème est en fait très difficile, il n'est donc pas si surprenant de constater qu'aucune bibliothèque existante comme boost ne l'a résolu.

Answer 5

J'ai le plaisir de dire que j'ai trouvé une solution, après une chasse au trésor similaire. range-v3 est une excellente idée si vous pouvez l'utiliser, mais si vous avez vraiment besoin d'une itérateur le projet HPX a créé un et cela fonctionne parfaitement avec le tri.

En raison d'un oubli, qui sera, je l'espère, réparé, il est toujours nécessaire d'établir un lien avec la bibliothèque HPX, mais cela ne me dérange pas, car le but est d'utiliser les algorithmes parallèles C++17, dont HPX fournit une implémentation.

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