Sortierung einer Std :: Map nach Wert vor Ausgabe & Destroy

Question

Ich bin mir bewusst, dass Map nicht vorbereitet ist, sortiert zu werden, stark für den schnellen und zufälligen Schlüsselzugriff optimiert., Und unterstützt tatsächlich nicht std :: sort.

Mein aktuelles Problem ist, dass ich ein volles

map<std::string,int> 

, die ich nicht mehr verwenden würde, ich brauche nur 10 Paare in Wert (int), um zu extrahieren und sie zerstören.

Das Beste wäre, wenn es möglich wäre, es an Ort und Stelle zu sortieren und dann 10 Mal iterieren, aber das ist anscheinend keine Lösung.

Ich versuche verschiedene Lösungen wie durch eine Multimap (um doppelte Schlüssel zu ermöglichen), aber ich würde gerne wissen, ob es eine elegantere Lösung gibt, mit stl-Algorithmen so viel wie möglich.

EDIT:

ich eine Karte bin mit, weil für das 99% der Zeit, die ich als eine Karte benötigen, schnell Schlüssel-Lookups Werte zu erhöhen. Brauche einfach einen guten Weg, um später in Wertordnung zu extrahieren, wenn ich die Map nicht mehr benötige.

Aktueller Ansatz whould sein:

• std :: kopieren Sie die Karte (std :: string, int) auf einen Vektor (Paar (std :: string, int))
• Art der Vektor
• erhalten die ersten 10 Werte
• Vektor zerstören und

Answer 1

Karten werden als Baum in der Reihenfolge der Reihenfolge sortiert gespeichert. Sie möchten die 10 kleinsten (oder größten) Ganzzahlwerte und ihre Schlüssel, richtig?

In diesem Fall, iterieren Sie die Karte und legen Sie alle Schlüssel-Wert-Paare in einem Vektor von Paaren (std::vector<std::pair<std::string, int> >)). Ich denke, Sie können einfach die zwei-Iterator-Arg-Konstruktor von std :: Vektor dafür verwenden std::partial_sort im Vektor Geben Sie einen Komparator für partial_sort an, der Paare vergleicht, indem Sie nur den Wert int vergleichen und die Schlüsselzeichenfolge ignorieren Dann haben Sie die 10 Paare am Anfang des Vektors und der Rest des Vektors enthält die restlichen Paare in einer nicht angegebenen Reihenfolge.

-Code (ungetestet):

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

Beachten Sie, dass, wenn es mehrere Strings mit dem gleichen Wert, auf beiden Seiten der Grenze von 10, dann ist es nicht angegeben, welche Sie bekommen. Sie können dies steuern, indem Sie den Komparator auch auf die Zeichenkette schauen lassen, wenn die ganzen Zahlen gleich sind.

Answer 2

Karte Wenn Sie die Karte Iterator iTERATE verwenden, erhalten Sie die Einzelteile auf Schlüssel sortiert, wie es intern ausgeglichen bina verwendet ry tree, um die Werte zu speichern. Sie könnten also die 10 Werte aus den Iteratoren extrahieren. Willst du das oder willst du etwas anderes machen? Bitte klären Sie.

BEARBEITEN: Anstatt den Vektor und die Sortierung zu verwenden, können Sie direkt set verwenden und die Vergleichsfunktion übergeben. Dann können Sie die Top 10 Elemente extrahieren. Das ist mein Testcode:

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

Für wert Iterieren Sie boost::multi_index nutzen könnten. Es wird sieht wie folgt aus:

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

Sie alle Index für Iteration verwenden könnte (val_str oder val_int).

Answer 4

Kann die eleganteste Art und Weise nicht, aber Sie können sie per Wert in einem Satz als sortieren:

 
#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

Eine andere Möglichkeit ist ein Reverse-Karte zu bauen. Für Sie wäre das std::map<int, std::string>. Einträge in der umgekehrten Karte sind nach ihrem Wert sortiert.

Nachstehend ist das, was ich in meinem Werkzeugkasten für solche Gelegenheiten haben:

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

Dieser Code geht davon aus, dass die Werte eindeutig sind, auch (und eine Behauptung wirft, wenn dies nicht der Fall ist). Wenn dies nicht auf Ihr Problem zutrifft, können Sie den Code problemlos ändern, um eine Mehrfachkarte zu verwenden.