STLまたはBoostはマップを値でソートするのに役立ちますか？

Question

タイトルの「ソート」という単語が誤解を招く可能性があります。私はこの動作を探しています：

{ 1: 100,    { 1: 1, 
    3: 10,  =>  3: 10, 
    5: 1000,    5: 100, 
    9: 1 }     9: 1000 } 

つまり、値を既存のキーに昇順に再割り当てします。

これは一時的に行うのは難しいことではないでしょう。

using K = int; 
using V = int; 
std::map<K, V> myMap{ {1, 100}, {3, 10}, {5, 1000}, {9, 1} }; 
std::vector<V> tempVec; // insert map values into vector 
std::transform(myMap.begin(), myMap.end(), std::back_inserter(tempVec), 
       [](auto const& mapPair) { return mapPair.second; }); 
std::sort(tempVec.begin(), tempVec.end()); 
size_t i = 0; 
for (auto& mapPair : myMap) { 
    mapPair.second = tempVec[i++]; 
} 

この簡素化することができるか、さらに良い、場所で行われますか？

Answer 1

マップを値でソートすることはできません。

std::mapは（O(log n)のルックアップと挿入のように）仕事をするためにキーでエントリを編成するため、この動作を変更する方法はありません。あなたは何ができるか

は、しかし、（以下に示すように同様std::pairまたはカスタムタイプ）YourTypeがタプルであるstd::set<YourType>を使用している、あなたはセットが値によって組織されるように、カスタム比較演算子を提供しています。

struct YourType { 
    int key; 
    int value; 
    bool operator<(const YourType& other) const { 
    return std::tie(value, key) < std::tie(other.value, other.key); 
    } 
}; 

Answer 2

効率的なアルゴリズムが必要ない場合は、単に選択ソートを実装できます。

技術的

for (auto mi = myMap.begin(); mi != myMap.end(); ++mi) { 
    auto const& mini = min_element(mi, myMap.end(), [](auto const& pa, auto const& pb) { return pa.second < pb.second; }); 
    swap(mi->second, mini->second); 
}