Tri d'un fichier std :: map avant valeur et destruction

Question

Je suis conscient que la carte n'est pas prête à être triée, qu'elle est fortement optimisée pour l'accès rapide et aléatoire aux clés, et qu'elle ne prend pas en charge std :: sort.

Mon problème actuel est que j'ai un plein

map<std::string,int> 

que je ne vais plus utiliser, je juste besoin d'extraire 10 paires en valeur (int) l'ordre et le détruire. La meilleure chose, si c'était possible, serait de le trier et de l'itérer 10 fois, mais ce n'est apparemment pas une solution. J'essaie différentes solutions en passant par un multimap (pour permettre les clés en double) mais j'aimerais savoir s'il existe une solution plus élégante, en utilisant autant que possible les algorithmes stl.

EDIT:

J'utilise une carte parce que pour 99% du temps, je besoin comme une carte, recherche de clé rapide pour augmenter les valeurs. Juste besoin d'un bon moyen d'extraire plus tard dans l'ordre des valeurs quand je n'ai plus besoin de la carte.

approche actuelle whould être:

• std :: copier la carte (std :: string, int) à un vecteur (paire (std :: string, int))
• sorte le vecteur
• obtenir les 10 premières valeurs
• vecteur et carte détruisent

Answer 1

Les cartes sont stockées en tant qu'arbre trié dans l'ordre des clés. Vous voulez les 10 valeurs entières les plus petites (ou les plus grandes) et leurs clés, n'est-ce pas?

Dans ce cas, parcourez la carte et placez toutes les paires clé-valeur dans un vecteur de paires (std::vector<std::pair<std::string, int> >)) Je pense que vous pouvez simplement utiliser le constructeur two-iterator-arg de std :: vector pour cela. std::partial_sort sur le vecteur Spécifiez un comparateur à partial_sort, qui compare les paires en comparant simplement la valeur int, en ignorant la chaîne de caractères, puis vous avez les 10 paires souhaitées au début du vecteur, et le reste du vecteur contient le reste. paires dans un ordre non spécifié.

code (non testé):

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

Notez que s'il y a plusieurs chaînes avec la même valeur, de chaque côté de la limite de 10, alors il est impossible de savoir lequel ceux que vous obtenez. Vous pouvez contrôler cela en demandant à votre comparateur de regarder la chaîne aussi, dans les cas où les entiers sont égaux.

Answer 2

Si vous itérer en utilisant la carte iterator, vous obtenez les articles triés sur la touche car il utilise en interne Bina équilibrée ry tree pour stocker les valeurs. Vous pouvez donc en extraire les 10 valeurs en utilisant les itérateurs. Est-ce ce que vous voulez ou voulez-vous faire d'autre? Précisez s'il vous plaît.

EDIT: Au lieu d'utiliser le vecteur et le tri, vous pouvez directement utiliser set et passer la fonction de comparaison. Ensuite, vous pouvez extraire les 10 meilleurs éléments. Ceci est mon code de test:

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

Pour itérer par valeur, vous pouvez utiliser boost::multi_index. Il va se présente comme suit:

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

Vous pouvez utiliser un indice pour l'itération (val_str ou val_int).

Answer 4

ne peut pas être la manière la plus élégante, mais vous pouvez les trier par valeur dans un ensemble comme:

 
#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

Une autre possibilité est de construire une carte inverse. Pour vous, ce serait std::map<int, std::string>. Les entrées dans la carte inverse sont triées par leur valeur.

Ce qui suit est ce que j'ai dans ma boîte à outils pour de telles occasions:

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

Ce code suppose que les valeurs sont uniques, aussi (et jette une affirmation, si ce n'est pas le cas). Si cela ne s'applique pas à votre problème, vous pouvez facilement modifier le code pour utiliser une carte multiple.