Ordenar por proxy (o: ordenar un contenedor por el contenido de otro) en C++

Question

Tengo un conjunto de datos que se divide en dos matrices (llamémoslos data y keys). Es decir, para cualquier artículo dado con un índice i, puedo acceder a los datos para ese artículo con data[i] y la clave para ese artículo con keys[i]. No puedo cambiar esta estructura (por ejemplo, para intercalar claves y datos en una sola matriz), porque necesito pasar la matriz data a una función de biblioteca que espera una cierta disposición de datos.

¿Cómo puedo ordenar ambas matrices (preferiblemente utilizando funciones de la biblioteca estándar) de acuerdo con el contenido de la matriz de keys?

Answer 1

Resulta que Boost contiene un iterador que no hace más o menos lo que el paired_iteratormy other answer desde hace:

Boost.Iterator Zip Iterator

Esta parece ser la mejor opción.

Answer 2

Se puede usar un mapa:

int main() { 
    vector<int> keys; 
    vector<string> data; 
    keys.push_back(5); data.push_back("joe"); 
    keys.push_back(2); data.push_back("yaochun"); 
    keys.push_back(1); data.push_back("holio"); 

    // load the keys and data to the map (they will automatically be inserted in sorted order by key) 
    map<int, string> sortedVals; 
    for(int i = 0; i < (int)keys.size(); ++i) { 
    sortedVals[keys[i]] = data[i]; 
    } 

    // copy the map values back to vectors 
    int ndx=0; 
    for(map<int, string>::iterator it = sortedVals.begin(); it != sortedVals.end(); ++it) { 
    keys[ndx] = it->first; 
    data[ndx] = it->second; 
    ++ndx; 
    } 

    // verify 
    for(int i = 0; i < (int)keys.size(); ++i) { 
    cout<<keys[i]<<" "<<data[i]<<endl; 
    } 

    return 0; 
} 

Aquí está la salida:

---------- Capture Output ---------- 
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe 
1 holio 
2 yaochun 
5 joe 

> Terminated with exit code 0. 

Answer 3

crear un vector de objetos que contienen los índices a las dos matrices. Defina operator< para ese objeto para hacer la comparación basada en keys[index]. Ordenar ese vector. Cuando haya terminado, caminar a través de ese vector y poner los objetos originales en el orden definido por los objetos proxy:

// warning: untested code. 
struct sort_proxy { 
    size_t i; 

    bool operator<(sort_proxy const &other) const { 
     return keys[i] < keys[other.i]; 
    } 
}; 

// ... key_size = number of keys/data items. 
std::vector<sort_proxy> proxies(key_size); 

for (i=0; i<keys_size; i++) 
    proxies[i].i = i; 

std::sort(proxies.begin(), proxies.end()); 

// in-place reordering left as an exercise for the reader. :-) 
for (int i=0; i<proxies[i].size(); i++) { 
    result_keys[i] = keys[proxies[i].i]; 
    result_data[i] = data[proxies[i].i]; 
} 

Answer 4

Usted puede utilizar funtores a realizar la ordenación, por ejemplo:

template <class T> 
struct IndexFunctor { 
    IndexFunctor(const std::vector<T>& v_) : v(v_) {} 
    bool operator()(int a, int b) const { 
    return v[a] < v[b]; 
    } 
    const std::vector<T>& v; 
}; 

template <class K, class D> 
void SortByKeys(std::vector<K>& keys, std::vector<D>& data) { 
    // Calculate the valid order inside a permutation array p. 
    const int n = static_cast<int>(keys.size()); 
    std::vector<int> p(n); 
    for (int i = 0; i < n; ++i) p[i] = i; 
    std::sort(p.begin(), p.end(), IndexFunctor(keys)); 

    // Reorder the keys and data in temporary arrays, it cannot be done in place. 
    std::vector<K> aux_keys(n); 
    std::vector<D> aux_data(n); 
    for (int i = 0; i < n; ++i) { 
    aux_keys[i] = keys[p[i]]; 
    aux_data[i] = data[p[i]]; 
    } 

    // Assign the ordered vectors by swapping, it should be faster. 
    keys.swap(aux_keys); 
    data.swap(aux_data); 
} 

Answer 5

Este problema realmente me hizo pensar. Se me ocurrió una solución que hace uso de algunas características de C++ 0x para obtener un algoritmo muy similar a STL parallel_sort. Para realizar el tipo "in situ", tuve que escribir un back_remove_iterator como la contraparte de back_insert_iterator para permitir que el algoritmo lea y escriba en el mismo contenedor. Puede omitir esas partes e ir directamente a las cosas interesantes.

No lo sometí a ninguna prueba estricta, pero parece razonablemente eficiente en tiempo y espacio, principalmente debido al uso de std::move() para evitar copias innecesarias.

#include <algorithm> 
#include <iostream> 
#include <string> 
#include <vector> 


// 
// An input iterator that removes elements from the back of a container. 
// Provided only because the standard library neglects one. 
// 
template<class Container> 
class back_remove_iterator : 
    public std::iterator<std::input_iterator_tag, void, void, void, void> { 
public: 


    back_remove_iterator() : container(0) {} 
    explicit back_remove_iterator(Container& c) : container(&c) {} 

    back_remove_iterator& operator= 
     (typename Container::const_reference value) { return *this; } 

    typename Container::value_type operator*() { 

     typename Container::value_type value(container->back()); 
     container->pop_back(); 
     return value; 

    } // operator*() 

    back_remove_iterator& operator++() { return *this; } 
    back_remove_iterator operator++(int) { return *this; } 


    Container* container; 


}; // class back_remove_iterator 


// 
// Equivalence operator for back_remove_iterator. An iterator compares equal 
// to the end iterator either if it is default-constructed or if its 
// container is empty. 
// 
template<class Container> 
bool operator==(const back_remove_iterator<Container>& a, 
    const back_remove_iterator<Container>& b) { 

    return !a.container ? !b.container || b.container->empty() : 
     !b.container ? !a.container || a.container->empty() : 
     a.container == b.container; 

} // operator==() 


// 
// Inequivalence operator for back_remove_iterator. 
// 
template<class Container> 
bool operator!=(const back_remove_iterator<Container>& a, 
    const back_remove_iterator<Container>& b) { 

    return !(a == b); 

} // operator!=() 


// 
// A handy way to default-construct a back_remove_iterator. 
// 
template<class Container> 
back_remove_iterator<Container> back_remover() { 

    return back_remove_iterator<Container>(); 

} // back_remover() 


// 
// A handy way to construct a back_remove_iterator. 
// 
template<class Container> 
back_remove_iterator<Container> back_remover(Container& c) { 

    return back_remove_iterator<Container>(c); 

} // back_remover() 


// 
// A comparison functor that sorts std::pairs by their first element. 
// 
template<class A, class B> 
struct sort_pair_by_first { 

    bool operator()(const std::pair<A, B>& a, const std::pair<A, B>& b) { 

     return a.first < b.first; 

    } // operator()() 

}; // struct sort_pair_by_first 


// 
// Performs a parallel sort of the ranges [keys_first, keys_last) and 
// [values_first, values_last), preserving the ordering relation between 
// values and keys. Sends key and value output to keys_out and values_out. 
// 
// This works by building a vector of std::pairs, sorting them by the key 
// element, then returning the sorted pairs as two separate sequences. Note 
// the use of std::move() for a vast performance improvement. 
// 
template<class A, class B, class I, class J, class K, class L> 
void parallel_sort(I keys_first, I keys_last, J values_first, J values_last, 
        K keys_out, L values_out) { 

    typedef std::vector< std::pair<A, B> > Pairs; 
    Pairs sorted; 

    while (keys_first != keys_last) 
     sorted.push_back({std::move(*keys_first++), std::move(*values_first++)}); 

    std::sort(sorted.begin(), sorted.end(), sort_pair_by_first<A, B>()); 

    for (auto i = sorted.begin(); i != sorted.end(); ++i) 
     *keys_out++ = std::move(i->first), 
     *values_out++ = std::move(i->second); 

} // parallel_sort() 


int main(int argc, char** argv) { 

    // 
    // There is an ordering relation between keys and values, 
    // but the sets still need to be sorted. Sounds like a job for... 
    // 
    std::vector<int> keys{0, 3, 1, 2}; 
    std::vector<std::string> values{"zero", "three", "one", "two"}; 

    // 
    // parallel_sort! Unfortunately, the key and value types do need to 
    // be specified explicitly. This could be helped with a utility 
    // function that accepts back_remove_iterators. 
    // 
    parallel_sort<int, std::string> 
     (back_remover(keys), back_remover<std::vector<int>>(), 
     back_remover(values), back_remover<std::vector<std::string>>(), 
     std::back_inserter(keys), std::back_inserter(values)); 

    // 
    // Just to prove that the mapping is preserved. 
    // 
    for (unsigned int i = 0; i < keys.size(); ++i) 
     std::cout << keys[i] << ": " << values[i] << '\n'; 

    return 0; 

} // main() 

Espero que esto sea útil, o al menos entretenido.

Answer 6

Aquí es una implementación de ejemplo que define un nuevo tipo de iterador para proporcionar una vista emparejado más de dos secuencias. He intentado que sea compatible con los estándares y correcta, pero dado que el estándar C++ es horriblemente complejo en sus detalles, estoy casi seguro de que he fallado. Diré que este código parece funcionar cuando se construye con clang++ o g++.

Este código es no recomendado para uso general, ya que es más largo y menos comprensible que las otras respuestas, y posiblemente invoca el temido 'comportamiento indefinido'.

Sin embargo, tiene la ventaja de una sobrecarga de tiempo y espacio constantes, ya que proporciona una vista de los datos existentes en lugar de construir una representación alternativa temporal o un vector de permutación. El problema de rendimiento más obvio (para mí) con este código es que los elementos individuales de los dos contenedores tendrán que copiarse durante la operación de intercambio.A pesar de varios intentos, no he encontrado una manera de especializar con éxito std::swap de modo que std::sort o std::random_shuffle evite utilizar la implementación de intercambio basada en copia temporal predeterminada. Es posible que el uso del sistema de referencia C++ 0x rvalue (vea std::move y la respuesta de Jon Purdy) pueda resolver esto.

#ifndef HDR_PAIRED_ITERATOR 
#define HDR_PAIRED_ITERATOR 

#include <iterator> 

/// pair_view mostly looks like a std::pair, 
/// and can decay to a std::pair, but is really a pair of references 
template <typename ItA, typename ItB> 
struct pair_view { 
    typedef typename ItA::value_type first_type; 
    typedef typename ItB::value_type second_type; 

    typedef std::pair<first_type, second_type> pair_type; 

    pair_view() {} 
    pair_view(const ItA &a, const ItB &b): 
     first(*a), second(*b) {} 

    pair_view &operator=(const pair_view &x) 
     { first = x.first; second = x.second; return *this; } 
    pair_view &operator=(const pair_type &x) 
     { first = x.first; second = x.second; return *this; } 

    typename ItA::reference first; 
    typename ItB::reference second; 
    operator pair_type() const 
     { return std::make_pair(first, second); } 

    friend bool operator==(const pair_view &a, const pair_view &b) 
     { return (a.first == b.first) && (a.second == b.second); } 
    friend bool operator<(const pair_view &a, const pair_view &b) 
     { return (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)); } 
    friend bool operator!=(const pair_view &a, const pair_view &b) 
     { return !(a == b); } 
    friend bool operator>(const pair_view &a, const pair_view &b) 
     { return (b < a); } 
    friend bool operator<=(const pair_view &a, const pair_view &b) 
     { return !(b < a); } 
    friend bool operator>=(const pair_view &a, const pair_view &b) 
     { return !(a < b); } 

    friend bool operator==(const pair_view &a, const pair_type &b) 
     { return (a.first == b.first) && (a.second == b.second); } 
    friend bool operator<(const pair_view &a, const pair_type &b) 
     { return (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)); } 
    friend bool operator!=(const pair_view &a, const pair_type &b) 
     { return !(a == b); } 
    friend bool operator>(const pair_view &a, const pair_type &b) 
     { return (b < a); } 
    friend bool operator<=(const pair_view &a, const pair_type &b) 
     { return !(b < a); } 
    friend bool operator>=(const pair_view &a, const pair_type &b) 
     { return !(a < b); } 

    friend bool operator==(const pair_type &a, const pair_type &b) 
     { return (a.first == b.first) && (a.second == b.second); } 
    friend bool operator<(const pair_type &a, const pair_type &b) 
     { return (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)); } 
    friend bool operator!=(const pair_type &a, const pair_type &b) 
     { return !(a == b); } 
    friend bool operator>(const pair_type &a, const pair_type &b) 
     { return (b < a); } 
    friend bool operator<=(const pair_type &a, const pair_type &b) 
     { return !(b < a); } 
    friend bool operator>=(const pair_type &a, const pair_type &b) 
     { return !(a < b); } 
}; 

template <typename ItA, typename ItB> 
struct paired_iterator { 
    // --- standard iterator traits 
    typedef typename pair_view<ItA, ItB>::pair_type value_type; 
    typedef pair_view<ItA, ItB> reference; 
    typedef paired_iterator<ItA,ItB> pointer; 

    typedef typename std::iterator_traits<ItA>::difference_type difference_type; 
    typedef std::random_access_iterator_tag iterator_category; 

    // --- methods not required by the Random Access Iterator concept 
    paired_iterator(const ItA &a, const ItB &b): 
     a(a), b(b) {} 

    // --- iterator requirements 

    // default construction 
    paired_iterator() {} 

    // copy construction and assignment 
    paired_iterator(const paired_iterator &x): 
     a(x.a), b(x.b) {} 
    paired_iterator &operator=(const paired_iterator &x) 
     { a = x.a; b = x.b; return *this; } 

    // pre- and post-increment 
    paired_iterator &operator++() 
     { ++a; ++b; return *this; } 
    paired_iterator operator++(int) 
     { paired_iterator tmp(*this); ++(*this); return tmp; } 

    // pre- and post-decrement 
    paired_iterator &operator--() 
     { --a; --b; return *this; } 
    paired_iterator operator--(int) 
     { paired_iterator tmp(*this); --(*this); return tmp; } 

    // arithmetic 
    paired_iterator &operator+=(const difference_type &n) 
     { a += n; b += n; return *this; } 
    friend paired_iterator operator+(const paired_iterator &x, const difference_type &n) 
     { return paired_iterator(x.a+n, x.b+n); } 
    friend paired_iterator operator+(const difference_type &n, const paired_iterator &x) 
     { return paired_iterator(x.a+n, x.b+n); } 
    paired_iterator &operator-=(const difference_type &n) 
     { a -= n; b -= n; return *this; } 
    friend paired_iterator operator-(const paired_iterator &x, const difference_type &n) 
     { return paired_iterator(x.a-n, x.b-n); } 
    friend difference_type operator-(const paired_iterator &x, const paired_iterator &y) 
     { return (x.a - y.a); } 

    // (in-)equality and ordering 
    friend bool operator==(const paired_iterator &x, const paired_iterator &y) 
     { return (x.a == y.a) && (x.b == y.b); } 
    friend bool operator<(const paired_iterator &x, const paired_iterator &y) 
     { return (x.a < y.a); } 

    // derived (in-)equality and ordering operators 
    friend bool operator!=(const paired_iterator &x, const paired_iterator &y) 
     { return !(x == y); } 
    friend bool operator>(const paired_iterator &x, const paired_iterator &y) 
     { return (y < x); } 
    friend bool operator<=(const paired_iterator &x, const paired_iterator &y) 
     { return !(y < x); } 
    friend bool operator>=(const paired_iterator &x, const paired_iterator &y) 
     { return !(x < y); } 

    // dereferencing and random access 
    reference operator*() const 
     { return reference(a,b); } 
    reference operator[](const difference_type &n) const 
     { return reference(a+n, b+n); } 
private: 
    ItA a; 
    ItB b; 
}; 

template <typename ItA, typename ItB> 
paired_iterator<ItA, ItB> make_paired_iterator(const ItA &a, const ItB &b) 
{ return paired_iterator<ItA, ItB>(a, b); } 

#endif 


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

template <typename ItA, typename ItB> 
void print_kvs(const ItA &k0, const ItB &v0, const ItA &kn, const ItB &vn) { 
    ItA k(k0); 
    ItB v(v0); 
    while (k != kn || v != vn) { 
     if (k != kn && v != vn) 
      std::cout << "[" << *k << "] = " << *v << "\n"; 
     else if (k != kn) 
      std::cout << "[" << *k << "]\n"; 
     else if (v != vn) 
      std::cout << "[?] = " << *v << "\n"; 

     if (k != kn) ++k; 
     if (v != vn) ++v; 
    } 
    std::cout << std::endl; 
} 

int main() { 
    std::vector<int> keys; 
    std::vector<std::string> data; 

    keys.push_back(0); data.push_back("zero"); 
    keys.push_back(1); data.push_back("one"); 
    keys.push_back(2); data.push_back("two"); 
    keys.push_back(3); data.push_back("three"); 
    keys.push_back(4); data.push_back("four"); 
    keys.push_back(5); data.push_back("five"); 
    keys.push_back(6); data.push_back("six"); 
    keys.push_back(7); data.push_back("seven"); 
    keys.push_back(8); data.push_back("eight"); 
    keys.push_back(9); data.push_back("nine"); 

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end()); 

    std::cout << "Shuffling\n"; 
    std::random_shuffle(
     make_paired_iterator(keys.begin(), data.begin()), 
     make_paired_iterator(keys.end(), data.end()) 
    ); 

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end()); 

    std::cout << "Sorting\n"; 
    std::sort(
     make_paired_iterator(keys.begin(), data.begin()), 
     make_paired_iterator(keys.end(), data.end()) 
    ); 

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end()); 

    std::cout << "Sort descending\n"; 
    std::sort(
     make_paired_iterator(keys.begin(), data.begin()), 
     make_paired_iterator(keys.end(), data.end()), 
     std::greater< std::pair<int,std::string> >() 
    ); 

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end()); 

    return 0; 
} 

Answer 7

No sé si la siguiente explotación de conocimiento de std::swap detalles de implementación es UB o no. Creo que no".

#include <iostream> 
#include <iomanip> 

#include <type_traits> 
#include <utility> 
#include <iterator> 
#include <algorithm> 
#include <numeric> 
#include <deque> 
#include <forward_list> 
#include <vector> 

#include <cstdlib> 
#include <cassert> 

template< typename pattern_iterator, typename target_iterator > 
void 
pattern_sort(pattern_iterator pbeg, pattern_iterator pend, target_iterator tbeg, target_iterator tend) 
{ 
    //assert(std::distance(pbeg, pend) == std::distance(tbeg, tend)); 
    using pattern_traits = std::iterator_traits<pattern_iterator>; 
    using target_traits = std::iterator_traits<target_iterator>; 
    static_assert(std::is_base_of< std::forward_iterator_tag, typename pattern_traits::iterator_category >{}); 
    static_assert(std::is_base_of< std::forward_iterator_tag, typename target_traits::iterator_category >{}); 
    struct iterator_adaptor 
    { 

     iterator_adaptor(typename pattern_traits::reference pattern, 
         typename target_traits::reference target) 
      : p(&pattern) 
      , t(&target) 
     { ; } 

     iterator_adaptor(iterator_adaptor &&) 
      : p(nullptr) 
      , t(nullptr) 
     { ; } 

     void 
     operator = (iterator_adaptor && rhs) & 
     { 
      if (!!rhs.p) { 
       assert(!!rhs.t); 
       std::swap(p, rhs.p); 
       std::iter_swap(t, rhs.t); 
      } 
     } 

     bool 
     operator < (iterator_adaptor const & rhs) const 
     { 
      return (*p < *rhs.p); 
     } 

    private : 

     typename pattern_traits::pointer p; 
     typename target_traits::pointer t; 

    }; 
    std::deque<iterator_adaptor> proxy_; // std::vector can be used instead 
    //proxy_.reserve(static_cast<std::size_t>(std::distance(pbeg, pend))); // it's (maybe) worth it if proxy_ is std::vector and if walking through whole [tbeg, tend) range is not too expensive operation (in case if target_iterator is worse then RandomAccessIterator) 
    auto t = tbeg; 
    auto p = pbeg; 
    while (p != pend) { 
     assert(t != tend); 
     proxy_.emplace_back(*p, *t); 
     ++p; 
     ++t; 
    } 
    std::sort(std::begin(proxy_), std::end(proxy_)); 
} 

int 
main() 
{ 
    std::forward_list<int> keys{5, 4, 3, 2, 1}; 
    std::vector<std::size_t> indices(static_cast<std::size_t>(std::distance(std::cbegin(keys), std::cend(keys)))); 
    std::iota(std::begin(indices), std::end(indices), std::size_t{0}); // indices now: 0, 1, 2, 3, 4  
    std::copy(std::cbegin(keys), std::cend(keys), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; 
    std::copy(std::cbegin(indices), std::cend(indices), std::ostream_iterator<std::size_t>(std::cout, " ")); std::cout << std::endl; 
    pattern_sort(std::cbegin(keys), std::cend(keys), std::begin(indices), std::end(indices)); std::cout << std::endl; 
    std::copy(std::cbegin(keys), std::cend(keys), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; 
    std::copy(std::cbegin(indices), std::cend(indices), std::ostream_iterator<std::size_t>(std::cout, " ")); std::cout << std::endl; 
    // now one can use indices to access keys and data to as ordered containers 
    return EXIT_SUCCESS; 
}