Ordinamento di std :: mappa per valore prima dell'output e destroy

Question

Sono consapevole che la mappa non è pronta per essere ordinata, è fortemente ottimizzata per l'accesso rapido e casuale alla chiave., E in realtà non supporta std :: sort.

mio problema attuale è che ho un full

map<std::string,int> 

che io non ho intenzione di usare più, ho solo bisogno di estrarre 10 coppie di valore (int) ordine e distruggerla.

La cosa migliore, se fosse possibile, sarebbe quella di ordinarlo e poi ripeterlo per 10 volte, ma a quanto pare non è una soluzione.

Sto provando diverse soluzioni passando da una multimappa (per consentire chiavi duplicate), ma mi piacerebbe sapere se c'è una soluzione più elegante, utilizzando gli algoritmi di stl il più possibile.

EDIT:

Sto utilizzando una mappa perché per il 99% del tempo ho bisogno di una mappa, le ricerche fondamentali veloci per aumentare i valori. Ho solo bisogno di un buon metodo per estrarre in un secondo momento l'ordine dei valori quando non ho più bisogno della mappa.

approccio attuale whould essere:

• std :: copiare la mappa (std :: string, int) per un vettore (coppia (std :: string, int))
• sorta vettore
• ottenere i primi 10 valori
• distruggono vettoriale e mappa

Answer 1

Le mappe vengono memorizzate come un albero ordinato in ordine di chiave. Vuoi i 10 valori interi più piccoli (o più grandi) e le loro chiavi, giusto?

In tal caso, iterare la mappa e inserire tutte le coppie chiave-valore in un vettore di coppie (std::vector<std::pair<std::string, int> >). Penso che si possa semplicemente utilizzare il costruttore di due iteratori-arg di std :: vector per questo. std::partial_sort sul vettore Specificare un comparatore a partial_sort, che confronta le coppie confrontando semplicemente il valore int, ignorando la stringa di chiavi, quindi si hanno le 10 coppie che si desidera all'inizio del vettore e il resto del vettore contiene il resto coppia in un ordine non specificato.

Codice (non testata):

typedef std::pair<std::string, int> mypair; 

struct IntCmp { 
    bool operator()(const mypair &lhs, const mypair &rhs) { 
     return lhs.second < rhs.second; 
    } 
}; 


void print10(const std::map<std::string,int> &mymap) { 
    std::vector<mypair> myvec(mymap.begin(), mymap.end()); 
    assert(myvec.size() >= 10); 
    std::partial_sort(myvec.begin(), myvec.begin() + 10, myvec.end(), IntCmp()); 

    for (int i = 0; i < 10; ++i) { 
     std::cout << i << ": " << myvec[i].first 
      << "-> " << myvec[i].second << "\n"; 
    } 
} 

Nota che se ci sono diverse stringhe con lo stesso valore, entrambi i lati del limite del 10, allora non è specificato che quelli che si ottiene. Puoi controllarlo facendo in modo che anche il tuo comparatore guardi la stringa, nel caso in cui gli interi siano uguali.

Answer 2

Se si iterare utilizzando la mappa iteratore, si ottengono le voci ordinate sulla chiave come si usa internamente bina equilibrata ry tree per memorizzare i valori. Quindi puoi semplicemente estrarre i 10 valori da esso usando gli iteratori. È questo che vuoi o vuoi fare qualcos'altro? Si prega di precisare.

MODIFICA: Invece di utilizzare il vettore e l'ordinamento, è possibile utilizzare direttamente set e passare la funzione di confronto. Quindi puoi estrarre i 10 elementi principali. Questo è il mio codice di prova:

typedef std::pair<std::string, int> MyPair; 


struct MyTestCompare 
{ 

    bool operator()(const MyPair& firstPair, const MyPair& secondPair) const 
    { 
     return firstPair.second < secondPair.second; 
    } 
}; 

int main() 
{ 
    std::map<std::string, int> m; 
    m[std::string("1")] = 10; 
m[std::string("2")] = 40; 
m[std::string("3")] = 30; 
m[std::string("4")] = 20; 



    std::set<MyPair,MyTestCompare> s; 
    std::map<std::string, int>::iterator iter = m.begin(); 
    std::map<std::string, int>::iterator endIter = m.end(); 
    for(; iter != endIter; ++iter) 
    { 
     s.insert(*iter); 
    } 

} 

Answer 3

Per l'iterazione per valore si potrebbe usare boost::multi_index. Sarà appare come segue:

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/member.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
using namespace boost::multi_index; 

struct X { 
    X(std::string val_str, int val_int) : val_str(val_str), val_int(val_int) {}; 
    std::string val_str; 
    int   val_int; 
}; 

typedef multi_index_container< 
    X, 
    indexed_by< 
     hashed_unique< member<X, std::string, &X::val_str> >, 
     ordered_non_unique< member<X, int, &X::val_int> > 
    > 
> X_map; 

void func() 
{ 
    X_map data; 
    data.insert(X("test", 1)); 
    // ... 

    // search by val_str 
    // complexity is equal to O(1) for hashed index (worst cast O(n)), 
    // and O(log n) for ordered index 
    X_map::const_iterator it = data.find("test"); 
    // ... 

    // iterate in order of val_int 
    size_t N = 0; 
    for (X_map::nth_index<1>::type::const_iterator it = data.get<1>().begin(); N < 10 && it != data.get<1>().end(); ++it, ++N) { 
    // copy elements somewhere 
    } 
} 

è possibile utilizzare qualsiasi indice per l'iterazione (val_str o val_int).

Answer 4

non può essere il modo più elegante, ma è possibile ordinare tramite il valore in un set come:

 
#include <map> 
#include <set> 
#include <iostream> 
#include <string> 

using namespace std; 

struct sortPairSecond 
{ 
    bool operator()(const pair<string, int> &lhs, const pair<string, int> &rhs) 
    { 
     return lhs.second < rhs.second; 
    } 
}; 


int main (int argc, char *argv[]) 
{ 
    cout << "Started...\n"; 
    map<string, int> myMap; 
    myMap["One"] = 1; 
    myMap["Ten"] = 10; 
    myMap["Five"] = 5; 
    myMap["Zero"] = 0; 
    myMap["Eight"] = 8; 


    cout << "Map Order:\n---------------\n"; 
    set<pair<string,int>, sortPairSecond > mySet; 
    for(map<string, int>::const_iterator it = myMap.begin(); it != myMap.end(); ++it) 
    { 
     cout << it->first << " = " << it->second << "\n"; 
     mySet.insert(*it); 
    } 

    cout << "\nSet Order:\n--------------\n"; 
    for(set<pair<string, int> >::const_iterator it = mySet.begin(); it != mySet.end(); ++it) 
    { 
     cout << it->first << " = " << it->second << "\n"; 
    } 

    return 1; 
} 

Answer 5

Un'altra possibilità è quella di costruire una mappa inversa. Per te quello sarebbe std::map<int, std::string>. Le voci nella mappa inversa sono ordinate in base al loro valore.

Quanto segue è quello che ho nella mia cassetta degli attrezzi per queste occasioni:

template< typename TK, typename TV, class TP, class TA, typename T1, typename T2 > 
inline void asserted_insert(std::map<TK,TV,TP,TA>& m, const T1& k, const T2& v) 
{ 
    typedef std::map<TK,TV,TP,TA>     map_type; 
    typedef typename map_type::value_type   value_type; 
    assert(m.insert(value_type(k,v)).second); 
} 

template< class TMap > struct reverse_map; 
template< typename T1, typename T2 > struct reverse_map< std::map<T1,T2> > { 
    typedef std::map<T2,T1>       result_t; 
}; 

template< typename T1, typename T2, class TP1, class TA1, class TP2, class TA2 > 
inline void build_reverse_map(const std::map<T1,T2,TP1,TA1>& map, std::map<T2,T1,TP2,TA2>& reverse_map) 
{ 
    typedef std::map<T1,T2,TP1,TA1>     map_type; 

    for(typename map_type::const_iterator it=map.begin(), 
             end=map.end(); it!=end; ++it) { 
    asserted_insert(reverse_map, it->second, it->first); 
    } 
} 

Questo codice si presuppone che i valori sono unici, anche (e lancia un'affermazione, se non è questo il caso). Se questo non si applica al tuo problema, puoi facilmente cambiare il codice per usare una multi mappa.