Std::map sorteren op waarde

Ik moet een std::mapsorteren op waarde in plaats van op sleutel. Is er een gemakkelijke manier om dit te doen?

Ik heb een oplossing uit de volgende thread:
std::map sorteren op gegevens?
Is er een betere oplossing?

map<long, double> testMap;
// some code to generate the values in the map.
sort(testMap.begin(), testMap.end());  // is there any function like this to sort the map?

Antwoord 1, autoriteit 100%

Hoewel de juiste antwoorden al zijn gepost, dacht ik dat ik een demo zou toevoegen van hoe je dit netjes kunt doen:

template<typename A, typename B>
std::pair<B,A> flip_pair(const std::pair<A,B> &p)
{
    return std::pair<B,A>(p.second, p.first);
}
template<typename A, typename B>
std::multimap<B,A> flip_map(const std::map<A,B> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()), 
                   flip_pair<A,B>);
    return dst;
}
int main(void)
{
    std::map<int, double> src;
    ...    
    std::multimap<double, int> dst = flip_map(src);
    // dst is now sorted by what used to be the value in src!
}

Algemene associatieve bron (vereist C++11)

Als je een alternatief voor std::mapgebruikt voor de associatieve broncontainer (zoals std::unordered_map), kun je een aparte overload coderen, maar uiteindelijk is de actie nog steeds hetzelfde, dus een gegeneraliseerde associatieve container met behulp van variadische sjablonen kan worden gebruikt voor ofweltoewijzingsconstructies:

// flips an associative container of A,B pairs to B,A pairs
template<typename A, typename B, template<class,class,class...> class M, class... Args>
std::multimap<B,A> flip_map(const M<A,B,Args...> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(),
                   std::inserter(dst, dst.begin()),
                   flip_pair<A,B>);
    return dst;
}

Dit werkt voor zowel std::mapals std::unordered_mapals de bron van de omslag.

Antwoord 2, autoriteit 68%

Ik had iets soortgelijks nodig, maar de omgedraaide kaart werkte niet voor mij. Ik heb zojuist mijn kaart (frequentie hieronder) gekopieerd naar een vector van paren en heb de paren vervolgens gesorteerd zoals ik wilde.

std::vector<std::pair<int, int>> pairs;
for (auto itr = freq.begin(); itr != freq.end(); ++itr)
    pairs.push_back(*itr);
sort(pairs.begin(), pairs.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b)
{
    return a.second < b.second;
}
);

Antwoord 3, autoriteit 22%

Als u de waarden op een kaart in gesorteerde volgorde wilt presenteren, kopieert u de waarden van de kaart naar vector en sorteert u de vector.

Antwoord 4, autoriteit 12%

Ik vind het antwoord van Oli leuk (een kaart omdraaien), maar het lijkt erop dat het een probleem heeft: de containerkaart staat geen twee elementen met dezelfde sleutel toe.

Een oplossing is om dst het type multimap te maken. Een andere is om src in een vector te dumpen en de vector te sorteren. De eerste vereist kleine aanpassingen aan Oli’s antwoord, en de laatste kan beknopt worden geïmplementeerd met behulp van STL-kopie

#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
  map<int, int> m;
  m[11] = 1;
  m[22] = 2;
  m[33] = 3;
  vector<pair<int, int> > v;
  copy(m.begin(),
       m.end(),
       back_inserter<vector<pair<int, int> > >(v));
  for (size_t i = 0; i < v.size(); ++i) {
    cout << v[i].first << " , " << v[i].second << "\n";
  }
  return 0;
};

Antwoord 5, autoriteit 7%

Om voort te bouwen op Oli’s oplossing (https://stackoverflow.com/a/5056797/2472351) met behulp van multimaps, je kunt de twee sjabloonfuncties die hij gebruikte vervangen door de volgende:

template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {
    multimap<B,A> dst;
    for(map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));
    return dst;
}

Hier is een voorbeeldprogramma dat laat zien dat alle sleutel-waardeparen behouden blijven na het uitvoeren van de omslag.

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {
    multimap<B,A> dst;
    for(typename map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));
    return dst;
}
int main() {
    map<string, int> test;
    test["word"] = 1;
    test["spark"] = 15;
    test["the"] = 2;
    test["mail"] = 3;
    test["info"] = 3;
    test["sandwich"] = 15;
    cout << "Contents of original map:\n" << endl;
    for(map<string, int>::const_iterator it = test.begin(); it != test.end(); ++it)
        cout << it -> first << " " << it -> second << endl; 
    multimap<int, string> reverseTest = flip_map(test);
    cout << "\nContents of flipped map in descending order:\n" << endl;
    for(multimap<int, string>::const_reverse_iterator it = reverseTest.rbegin(); it != reverseTest.rend(); ++it)
        cout << it -> first << " " << it -> second << endl; 
    cout << endl;
}

Resultaat:

Antwoord 6, autoriteit 6%

Een std::mapgesorteerd op waarde is in wezen een std::set. Verreweg de gemakkelijkste manier is om alle items op de kaart naar een set te kopiëren (overgenomen en aangepast van hier)

template <typename M, typename S> 
void MapToSet( const  M & m, S & s )
{
    typename M::const_iterator end = m.end();
    for( typename M::const_iterator it = m.begin(); it != end ; ++it )
    {
        s.insert( it->second );
    }
}

Eén waarschuwing: als de kaart verschillende sleutels met dezelfde waarde bevat, worden deze niet in de set ingevoegd en gaan ze verloren.

Antwoord 7, autoriteit 6%

Je kunt een std::mapniet op deze manier sorteren, omdat a de items op de kaart op de sleutel worden gesorteerd. Als u op waarde wilt sorteren, moet u een nieuwe std::mapmaken met verwisselde sleutel en waarde.

map<long, double> testMap;
map<double, long> testMap2;
// Insert values from testMap to testMap2
// The values in testMap2 are sorted by the double value

Denk eraan dat de dubbele sleutels uniek moeten zijn in testMap2of gebruik std::multimap.

Antwoord 8, autoriteit 4%

Een andere oplossing zou het gebruik van std::make_move_iterator zijn om een nieuwe vector te bouwen (C++11 )

   int main(){
      std::map<std::string, int> map;
       //Populate map
      std::vector<std::pair<std::string, int>> v {std::make_move_iterator(begin(map)),
                                      std::make_move_iterator(end(map))};
       // Create a vector with the map parameters
       sort(begin(v), end(v),
             [](auto p1, auto p2){return p1.second > p2.second;});
       // Using sort + lambda function to return an ordered vector 
       // in respect to the int value that is now the 2nd parameter 
       // of our newly created vector v
  }

Antwoord 9, autoriteit 3%

Gespiegelde structuur is misschien niet langer een kaart maar eerder een multimap, dus in het bovenstaande flip_map-voorbeeld zullen niet alle elementen van B noodzakelijkerwijs in de resulterende gegevensstructuur verschijnen.

Antwoord 10

U kunt overwegen om boost::bimap te gebruiken, waardoor u het gevoel krijgt dat de kaart tegelijkertijd op sleutel en op waarden wordt gesorteerd (dit is echter niet wat er echt gebeurt)

Antwoord 11

In de volgende voorbeeldcode heb ik een eenvoudige manier geschreven om topwoorden uit te voeren in een word_map-kaart, waarbij de sleutel string (woord) is en de waarde unsigned int (wordt voorkomen).

Het idee is simpel: zoek het huidige bovenste woord en verwijder het van de kaart. Het is niet geoptimaliseerd, maar het werkt goed als de kaart niet groot is en we alleen de bovenste N woorden hoeven uit te voeren, in plaats van de hele kaart te sorteren.

const int NUMBER_OF_TOP_WORDS = 300;
for (int i = 1; i <= NUMBER_OF_TOP_WORDS; i++) {
  if (word_map.empty())
    break;
  // Go through the map and find the max item.
  int max_value = 0;
  string max_word = "";
  for (const auto& kv : word_map) {
    if (kv.second > max_value) {
      max_value = kv.second;
      max_word = kv.first;
    }
  }
  // Erase this entry and print.
  word_map.erase(max_word);
  cout << "Top:" << i << " Count:" << max_value << " Word:<" << max_word << ">" <<     endl;
}

Antwoord 12

Een alternatieve manier om een std::mapte sorteren zonder extra kopiëren of transformatie is om de std::mapopnieuw te definiëren met verschillende Comparetyp:

namespace nonstd {
template <class Key,
          class T,
          class Compare = std::greater<T>,
          class Allocator = std::allocator<std::pair<Key const, T>>
          >
using map = std::map<Key, T, Compare, Allocator>;
}
int main() {
  nonstd::map<char, std::size_t> const values = {
    {'A', 3}, {'B', 2}, {'C', 5}
  };
  for (auto const& value : values) {
    std::clog << value.first << " : " << value.second << std::endl;
  }
}

Antwoord 13

In deze context moeten we kaart naar multimap converteren. Ik denk dat Converteerkaart om instellen niet goed is omdat we veel informatie zullen verliezen in het geval dat er veel duplicaatwaarden op de oorspronkelijke kaart zijn. Hier is mijn oplossing, ik heb de minder dan vergelijker gedefinieerd die op waarde (CMP-functie) sorteren. We kunnen de CMP-functie aanpassen als onze vraag.

std::map<int, double> testMap = { {1,9.1}, {2, 8.0}, {3, 7.0}, {4,10.5} };
auto cmp = [](const double &lhs,
              const double &rhs)->bool
{
    return lhs < rhs;
};
std::multimap<double, int, decltype(cmp)> mmap(cmp);
for (auto item : testMap)
    mmap.insert(make_pair(item.second, item.first));