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

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 v1 = { 1, 2, 3, 4, 5}; vector v2 = { 11, 22, 33, 44, 55}; vector v3 = {111, 222, 333, 444, 555}; typedef tuple tup_t; sort(zip(v1,v2,v3),[](tup_t t1, tup_t t2){ return t1.get() > t2.get(); }); for(auto& t : zip(v1,v2,v3)) cout << t.get() << " " << t.get() << " " << t.get() << 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 se quejan de que los iteradores / rangos son de solo lectura y no acceso aleatorio …

Pregunta: ¿Cómo ordeno N vectores en el paso de locking (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 artículo de Anthony Williams. Aunque parece que esto solo funciona para los pares, también discuten un TupleIteratorType pero no he podido encontrarlo.
  • user673679 encontró esta 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  #include  #include  #include  #include  template  auto zip(T&... containers) -> boost::iterator_range { return boost::make_iterator_range(iterators::makeTupleIterator(std::begin(containers)...), iterators::makeTupleIterator(std::end(containers)...)); } int main() { typedef boost::tuple tup_t; std::vector a = { 1, 2, 3, 4 }; std::vector b = { 11, 22, 33, 44 }; std::vector c = { 111, 222, 333, 444 }; auto print = [](tup_t t){ std::cout << t.get() << " " << t.get() << " " << t.get() << 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() > j.get(); }); 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).

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

 #include  #include  using namespace ranges; int main() { std::vector a1{15, 7, 3, 5}; std::vector a2{ 1, 2, 6, 21}; sort(view::zip(a1, a2), std::less<>{}, &std::pair::first); std::cout << view::all(a1) << '\n'; std::cout << view::all(a2) << '\n'; } 

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

Para los dos contenedores, aquí hay una versión que comstack en gcc 4.4.6, basado en el documento mencionado anteriormente. En versiones posteriores de gcc, puede cambiar boost :: tuple por std :: tuple

 #include  #include  #include  #include  # include  # include  using namespace std; template  struct helper_type { typedef boost::tuple::value_type, typename iterator_traits::value_type> value_type; typedef boost::tuple::value_type&, typename iterator_traits::value_type&> ref_type; }; template  class dual_iterator : public boost::iterator_facade, typename helper_type::value_type, boost::random_access_traversal_tag, typename helper_type::ref_type> { public: explicit dual_iterator(T1 iter1, T2 iter2) : mIter1(iter1), mIter2(iter2) {} typedef typename iterator_traits::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::ref_type dereference() const { return (typename helper_type::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  dual_iterator make_iter(T1 t1, T2 t2) { return dual_iterator(t1, t2); } template  struct iter_comp { typedef typename helper_type::value_type T; bool operator()(const T& t1, const T& t2) { return get<0>(t1) < get<0>(t2); } }; template  iter_comp make_comp(T1 t1, T2 t2) { return iter_comp(); } template void print(T& items) { copy(items.begin(), items.end(), ostream_iterator(cout, " ")); cout << endl; } int main() { vector nums1 = {3, 2, 1, 0}; vector 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); } 

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.

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

¿Cómo clasifico N vectores en el paso de locking (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 fonts 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ó.

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 objective era utilizar algoritmos paralelos C ++ 17, que HPX proporciona una implementación de.

 #include  using zip_it = hpx::util::zip_iterator::iterator, std::vector::iterator, std::vector::iterator>; int main() { std::vector rows{3, 2, 1}; std::vector cols{1, 2, 3}; std::vector 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"; } }