Sortowanie std :: map według wartości przed wyjściem i zniszczeniem

Question

Jestem świadomy, że mapa nie jest przygotowana do sortowania, jest mocno zoptymalizowana pod kątem szybkiego i losowego dostępu do klucza., A tak naprawdę nie obsługuje std :: sort.

Mój obecny problem jest, że mam pełną

map<std::string,int> 

których nie będę już używać, po prostu trzeba wyodrębnić 10 par wartości (int) zamówienia i zniszczyć go.

Najlepszą rzeczą, gdyby to było możliwe, byłoby posortowanie go na miejscu, a następnie powtórzenie go 10 razy, ale to najwyraźniej nie jest rozwiązaniem.

Próbuję różnych rozwiązań jako przechodzenie przez multimap (aby umożliwić zduplikowanie kluczy), ale chciałbym wiedzieć, czy istnieje bardziej eleganckie rozwiązanie, używając algorytmów stl w takim stopniu, jak to możliwe.

EDIT:

używam mapę bo dla 99% czasu muszę go jako mapa, fast kluczowych wyszukiwań w celu zwiększenia wartości. Potrzebuję tylko dobrego sposobu późniejszego wyodrębniania w porządku wartości, kiedy nie potrzebuję już mapy.

Aktualne podejście whould być:

• std :: kopiować mapy (std :: string, int) do wektora (para (std :: string, int))
• rodzaj wektor
• dostać pierwsze 10 wartości
• niszczą wektor i mapa

Answer 1

Mapy są zapisywane jako drzewa posortowane w kolejności alfabetycznej. Chcesz 10 najmniejszych (lub największych) wartości całkowitych i ich kluczy, prawda?

W takim przypadku wykonaj iterację mapy i umieść wszystkie pary klucz-wartość w wektorze par (std::vector<std::pair<std::string, int> >). Myślę, że możesz po prostu użyć do tego konstruktora dwustapika-arg std :: vector. std::partial_sort na wektorze Określ porównawcę do partial_sort, który porównuje pary przez porównanie wartości int, zignorowanie ciągu klucza, a następnie masz 10 par, które chcesz na początku wektora, a reszta wektora zawiera pozostałe pary w nieokreślonej kolejności.

Code (niesprawdzone):

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

Zauważ, że jeśli istnieje kilka ciągów o tej samej wartości, po obu stronach granicy 10, to nie jest określone, które z nich można dostać. Możesz to kontrolować, porównując swój ciąg znaków również z ciągiem znaków w przypadkach, gdy liczby całkowite są równe.

Answer 2

Jeśli iteracyjne pomocą map iterator, dostaniesz elementy posortowane na klucz, ponieważ używa wewnętrznie zrównoważony Bina ry drzewo do przechowywania wartości. Możesz więc wyodrębnić z niej 10 wartości za pomocą iteratorów. Czy tego chcesz, czy chcesz zrobić coś innego? Proszę o wyjaśnienie.

EDYTOWANIE: Zamiast używać wektora i sortowania, można bezpośrednio użyć zestawu i przejść funkcję porównania. Następnie możesz wyodrębnić 10 najlepszych elementów. To jest mój kodu testu:

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

Dla iteracji przez wartości można użyć boost::multi_index. Będzie wygląda następująco:

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

Można użyć dowolnego indeksu dla iteracji (val_str lub val_int).

Answer 4

nie może być najbardziej elegancki sposób, ale można sortować je przez wartość w zbiorze jako:

 
#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

Inną możliwością jest zbudowanie odwrotnej mapę. Dla Ciebie będzie to std::map<int, std::string>. Wpisy na odwróconej mapie są sortowane według ich wartości.

Oto co mam w skrzynce narzędziowej dla takich okazjach:

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

Kod ten zakłada, że ​​wartości są unikatowe, zbyt (i rzuca twierdzenie, jeśli nie jest to przypadek). Jeśli to nie dotyczy Twojego problemu, możesz łatwo zmienić kod, aby korzystać z wielu map.