Ordina per proxy (o: ordina un contenitore per il contenuto di un altro) in C++

Question

Ho un set di dati che è diviso in due array (chiamiamoli data e keys). Cioè, per ogni articolo con un indice i, posso accedere ai dati per quell'articolo con data[i] e la chiave per quell'articolo con keys[i]. Non riesco a modificare questa struttura (ad esempio, per intercalare chiavi e dati in un unico array), perché ho bisogno di passare l'array data a una funzione di libreria che si aspetta un determinato layout di dati.

Come è possibile ordinare entrambi gli array (preferibilmente utilizzando le funzioni di libreria standard) in base al contenuto dell'array keys?

Answer 1

Si scopre che Boost contiene un iteratore che fa più o meno quello del paired_iterator da my other answer fa:

Boost.Iterator Zip Iterator

Questo mi sembra l'opzione migliore.

Answer 2

è possibile utilizzare una mappa:

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

ecco l'output:

---------- 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

Creare un vettore di oggetti che contengono gli indici ai due array. Definire operator< per quell'oggetto per fare il confronto basato su keys[index]. Ordina quel vettore. Quando hai finito, a piedi attraverso quel vettore e mettere le oggetti originali nell'ordine definito da quegli oggetti 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

È possibile utilizzare funtori per fare l'ordinamento, ad esempio:

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

Questo problema mi ha fatto davvero riflettere. Ho trovato una soluzione che utilizza alcune funzionalità di C++ 0x per ottenere un algoritmo parallel_sort molto simile a STL. Per eseguire l'ordinamento "sul posto", ho dovuto scrivere uno back_remove_iterator come la controparte di back_insert_iterator per consentire all'algoritmo di leggere e scrivere nello stesso contenitore. Puoi saltare quelle parti e andare direttamente alle cose interessanti.

Non ho eseguito alcun test approfondito, ma sembra ragionevolmente efficiente sia nel tempo che nello spazio, principalmente a causa dell'uso di std::move() per impedire la copia non necessaria.

#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() 

Spero che questo si riveli utile, o almeno divertente.

Answer 6

Ecco un'implementazione di esempio che definisce un nuovo tipo di iteratore per fornire una vista accoppiata su due sequenze. Ho cercato di renderlo conforme agli standard e corretto, ma poiché lo standard C++ è orribilmente complesso nei suoi dettagli, sono quasi sicuro di aver fallito. Dirò che questo codice sembra funzionare quando è stato creato con clang++ o g++.

Questo codice è non consigliato per uso generale, poiché è più lungo e meno comprensibile rispetto alle altre risposte e probabilmente invoca il temuto 'comportamento non definito'.

Tuttavia,, presenta il vantaggio di un sovraccarico di tempo e spazio costante poiché fornisce una vista sui dati esistenti anziché creare effettivamente una rappresentazione alternativa temporanea o un vettore di permutazione. Il problema di prestazioni più ovvio (per me) con questo codice è che i singoli elementi dei due contenitori dovranno essere copiati durante l'operazione di swap.Nonostante diversi tentativi, non ho trovato un modo per specializzarmi con successo nello std::swap in modo che std::sort o std::random_shuffle evitino di utilizzare l'implementazione di swap basata su copia temporanea predefinita. È possibile che l'uso del sistema di riferimento del valore di C++ 0x (vedere std::move e la risposta di Jon Purdy) possa risolvere questo problema.

#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

Non so se il seguente utilizzo dei dati di implementazione di std::swap è UB o no. Penso che nessuno".

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