Ordenando std :: map por valor antes de la salida & destroy

Question

Soy consciente de que el mapa no está preparado para ser ordenado, está muy optimizado para acceso rápido y aleatorio a las claves, y en realidad no es compatible con std :: sort.

Mi problema actual es que tengo una completa

map<std::string,int> 

que yo no voy a usar nunca más, sólo hay que extraer 10 pares de valor (int) orden y destruirlo.

Lo mejor si fuera posible sería ordenarlo en su lugar y luego repetirlo 10 veces, pero aparentemente no es una solución.

Estoy probando diferentes soluciones como ir a través de un multimap (para permitir duplicar las claves) pero me gustaría saber si hay una solución más elegante, utilizando algoritmos STL tanto como sea posible.

EDIT:

estoy usando un mapa porque para el 99% de las veces que lo necesite como un mapa, las búsquedas rápidas clave para aumentar los valores. Solo necesito una buena forma de extraer más tarde en orden de valores cuando ya no necesite el mapa.

enfoque actual whould ser:

• std :: copiar el mapa (std :: string, int) a un vector (par (std :: string, int))
• especie del vector
• obtener los primeros 10 valores
• destruyen vector y correspondencia

Answer 1

Los mapas se almacenan como un árbol ordenados por orden de clave. Quieres los 10 valores enteros más pequeños (o más grandes) y sus claves, ¿verdad?

En ese caso, itere el mapa y ponga todos los pares clave-valor en un vector de pares (std::vector<std::pair<std::string, int> >). Creo que puede usar el constructor two-iterator-arg de std :: vector para esto. std::partial_sort en el vector. Especifique un comparador para partial_sort, que compara pares simplemente comparando el valor int, ignorando la cadena de clave. Luego tiene los 10 pares que desea al comienzo del vector, y el resto del vector contiene el resto pares en un orden no especificado.

de código (no probado):

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

Tenga en cuenta que si hay varias cadenas con el mismo valor, a ambos lados del límite del 10, entonces no se especifica cuáles se obtiene. Puede controlar esto haciendo que su comparador observe la cadena también, en los casos donde los enteros son iguales.

Answer 2

Si iterar usando el mapa iterador, obtendrá los artículos ordenados en clave, ya que utiliza internamente bina equilibrada ry tree para almacenar los valores. Entonces podrías extraer los 10 valores de él usando los iteradores. ¿Es eso lo que quieres o quieres hacer otra cosa? Por favor aclara

EDITAR: En lugar de utilizar el vector y la clasificación, puede usar directamente establecer y pasar la función de comparación. Luego puedes extraer los 10 elementos principales. Este es mi código de prueba:

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

para iterar por el valor que podría utilizar boost::multi_index. Será ve de la siguiente manera:

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

usted podría utilizar cualquier índice de iteración (val_str o val_int).

Answer 4

no puede ser la forma más elegante, pero se puede ordenar a través de valor en un conjunto como:

 
#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

Otra posibilidad es construir un mapa inversa. Para usted eso sería std::map<int, std::string>. Las entradas en el mapa inverso están ordenadas por su valor.

Lo siguiente es lo que tengo en mi caja de herramientas para estas ocasiones:

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

Este código se supone que los valores son únicos, también (y lanza una afirmación, si este no es el caso). Si esto no se aplica a su problema, podría cambiar fácilmente el código para usar un mapa múltiple.