Clasificación de contenedores comprimidos(bloqueados) en C++ con boost o STL

algorithm c++11

Question

Lo que quiero hacer: quiero ordenar 2, o 3, o N vectores, bloqueados, sin copiarlos en una tupla. Es decir, dejando de lado la verbosidad, algo así como:

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;

Esto debería dar como resultado:

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

Cómo lo estoy haciendo ahora mismo: he implementado mi propio quicksort, donde la primera matriz que paso se usa para la comparación, y las permutaciones se aplican a todas las demás matrices. Simplemente no pude entender cómo reutilizar std :: sort para mi problema (por ejemplo, extraer permutaciones).

Lo que he probado: boost::zip_iterator y boost::zip_range (con boost :: combine range), pero tanto std :: sort como boost::range::algorithm::sort quejan de que los iteradores / rangos son de solo lectura y no acceso aleatorio ...

Pregunta: ¿Cómo ordeno N vectores en el paso de bloqueo (comprimido)? El problema parece bastante genérico y común, así que supongo que debe haber una solución fácil a través de una biblioteca probablemente muy compleja, pero no puedo encontrarla ...

Observaciones: sí, hay preguntas similares en stackoverflow, esta pregunta se hace mucho en diferentes formas. Sin embargo, siempre están cerrados con una de las siguientes respuestas:

• Copie sus vectores en un par / tupla y clasifique esa tupla ...
• Copie sus vectores en una estructura con un miembro por vector y clasifique un vector de estructuras ...
• Implemente su propia función de clasificación para su problema particular ...
• Use una matriz auxiliar de índices ...
• Utilice boost :: zip_iterator sin un ejemplo o con un ejemplo que produzca malos resultados.

Sugerencias:

• He encontrado este hilo en la lista de correo de impulso que apunta a este paper de Anthony Williams. Aunque parece que esto solo funciona para los pares, también discuten un TupleIteratorType pero no he podido encontrarlo.
• user673679 encontró this publicación que contiene una buena solución para el caso de dos contenedores. También aclara el problema (el énfasis es mío):

[...] el problema fundamental es que los "pares" de referencias de matriz no se comportan como debieran [...] Simplemente decidí abusar de la notación de un iterador y escribir algo que funciona. Esto implicó escribir, efectivamente, un iterador no conforme donde la referencia del tipo de valor no es la misma que el tipo de referencia.

Respuesta: vea el comentario por interjay a continuación (esto también responde parcialmente a la pregunta futura ):

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

Pregunta futura: la respuesta anterior funciona para contenedores de secuencia. ¿Podríamos conseguir que también trabaje en contenedores ordenables (por ejemplo, secuencias y listas)? Esto requeriría random_access y bidirectional TupleIterators así como también un algoritmo de clasificación que funciona en iteradores bidireccionales.

Actualización: esto funciona para combinaciones de contenedores similares a secuencias. Sin embargo, mezclar una lista requeriría que std :: sort sea compatible con BidirectionalIterators (que no lo hace).

Answer 1

Aquí hay un ejemplo de trabajo basado en la biblioteca range-v3 que se ha propuesto para la estandarización

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

Ejemplo en vivo (requiere compilador reciente con buen soporte para C ++ 14, no VS 2015).

Answer 2

Cree una matriz auxiliar que contenga los índices 0..N-1. Clasifique esa matriz con un comparador personalizado que realmente arroje resultados al comparar elementos de una de sus matrices principales. Luego use la matriz auxiliar ordenada para imprimir sus matrices primarias en el orden correcto.

Answer 3

Encantado de conocer a un compañero arqueólogo de Internet!

¿Cómo clasifico N vectores en el paso de bloqueo (comprimido)? El problema parece bastante genérico y común, así que supongo que debe haber una solución fácil a través de una biblioteca probablemente muy compleja, pero no puedo encontrarla.

A veces, fui en la misma búsqueda del tesoro con suposiciones similares ...
Nunca encontré el tesoro :(

Seguí las mismas pistas que tú:

• Revisa los sospechosos habituales boost.iterator / boost.range / boost.fusion / boost.oven y después de una gran cantidad de experimentación e investigación, date cuenta de que no pueden resolver este problema en particular.
• Repase muchas preguntas sobre SO, solo para darse cuenta de que cada una de ellas ha sido cerrada con una respuesta incorrecta (por ejemplo, recomendando boost :: zip_iterator que no funciona en este caso como usted señala), o con alguna solución alternativa que evite la lo importante del asunto.
• Revisa muchas publicaciones de blogs, listas de correo, solo para darte cuenta de que nadie realmente resolvió el problema, excepto ...
• Después de mucha investigación finalmente desenterrar el antiguo códice por Antonius Wilhelm, que afirman haber diseñado una solución general "TupleIterator" y la bloquearon dentro de un archivo "tupleit.zip". Las fuentes históricas son tan escasas en este caso, que todavía no estoy seguro de si este archivo es un mito, una leyenda, o si todavía está enterrado en alguna parte de una capa perdida de Internet :)

De acuerdo, más en serio, el artículo de Anthony Williams sugiere que el problema en realidad es muy difícil, por lo que no es sorprendente descubrir que ninguna biblioteca existente como la mejora lo resolvió.

Answer 4

Me complace decir que he encontrado una solución, después de una búsqueda del tesoro similar. range-v3 es una gran idea si puede usarlo, pero si realmente necesita un iterador , el proyecto HPX ha creado uno y funciona perfectamente con sort.

Debido a un descuido, que con suerte será reparado, aún requiere que establezca un enlace con la biblioteca HPX, pero eso está bien para mí, porque el objetivo era utilizar algoritmos paralelos C ++ 17, que HPX proporciona una implementación de.

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

Answer 5

Para los dos contenedores, aquí hay una versión que compila en gcc 4.4.6, basado en el documento mencionado anteriormente. En versiones posteriores de gcc, puede cambiar boost :: tuple por 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);
}