在輸出和銷燬之前按值排序std :: map

Question

我知道map並沒有準備好排序，它對於快速和隨機的密鑰訪問進行了大量優化，並且實際上不支持std :: sort。

我現在的問題是，我有充分的

map<std::string,int> 

這我不打算再使用，我只需要在值（INT），以提取物10對，並摧毀它。

如果可能的話，最好的辦法是對它進行排序，然後迭代10次，但這顯然不是解決方案。我想嘗試不同的解決方案，通過一個multimap（以允許重複鍵），但我想知道是否有一個更優雅的解決方案，儘可能多地使用stl算法。

編輯：

我使用的地圖，因爲我需要它作爲一個地圖時的99％，快速鍵查找，增加值。當我不再需要地圖時，只需要一個以後按價值順序提取的好方法。

當前方法是對子級：

• 的std ::地圖（標準::字符串，整數）複製到一個向量（對（標準::字符串，整數））
• 排序矢量
• 拿到第10個值
• 破壞載體和地圖

Answer 1

地圖以按鍵順序排序的樹存儲。你想要10個最小（或最大）的整數值和它們的鍵，對嗎？

在這種情況下，迭代的地圖，並把所有的鍵值對成對的向量（std::vector<std::pair<std::string, int> >)，我想你可以只使用std兩個迭代器參數的構造函數::矢量這一點。然後使用std::partial_sort在vector上指定一個比較器到partial_sort，它通過比較int值忽略關鍵字串來比較對，然後在矢量的起始位置有10對，剩餘的矢量包含剩餘的以未指定的順序配對。

代碼（未經測試）：

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

注意，如果有幾個字符串具有相同值，10個極限的兩側，那麼它沒有規定你哪些。在整數相等的情況下，您可以通過讓比較器查看字符串來控制這一點。

Answer 2

如果您使用迭代地圖迭代器，你會得到整理重點項目，因爲它內部使用的平衡比娜ry樹來存儲值。所以你可以使用迭代器從中提取10個值。這是你想要的還是你想要做的其他事情？請澄清。

編輯： 而不是使用向量和排序，你可以直接使用設置和通過比較功能。然後你可以提取前10個元素。這是我的測試代碼：

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

對於通過值迭代，您可以使用boost::multi_index。它會看起來如下：

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

你可以使用任何指數迭代（val_str或val_int）。

Answer 4

未必是最優雅的方式，但你可以通過值在一組作爲對它們進行排序：

 
#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

另一種可能性是建立一個反向映射。對你而言，這將是std::map<int, std::string>。反向映射中的條目按其值排序。

以下是我在我的工具箱爲這樣的場合：

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

此代碼假定值是唯一的，太（並拋出一個斷言，如果不是這種情況）。如果這不適用於您的問題，您可以輕鬆更改代碼以使用多地圖。