Krdytkyu

I have a map that I want to print out sorted by value, I convert it to vector and sort the vector. Is this code correct?

#include <map>

#include <iostream>

#include <vector>

#include <algorithm>

#include <utility>

int main()

{

    std::map<char, int> freq;

    std::string text;

    std::getline(std::cin, text);

    std::vector<std::pair<char, int>> items;

    for(auto & ch: text)

            freq[ch]++;



    for(auto [key, value]: freq)

        items.push_back(std::make_pair(key, value));



    std::sort(items.begin(), items.end(),



              (auto a, auto b)

                { return a.second > b.second;});     



    for(auto [key, value]: items)

       std::cout << key << " " << value << std::endl;

    return 0;   



}

The code is correct. However, I still have some recommendations:

1. 
   

   Sort the includes, so you can easily spot recurring/missed ones

   
   
   

   #include <algorithm>
   
   #include <iostream>
   
   #include <map>
   
   #include <utility>
   
   #include <vector>
   
   

   
   


2. 
   

   You do not need to run the loop, you can simply pass the map to the std::vector constructor. As you use structured bindings and therewith at least C++17, I suggest Template Argument Deduction to omit the type of the vector

   
   
   

   std::vector items(freq.begin(), freq.end());
   
   

   
   


3. 
   

   The comparison function takes the arguments by copy, which is not optimal. Rather use const auto&:

   
   
   

    (const auto& a, const auto& b) { return a.second > b.second;})
   
   

   
   



4. Note that std::sort may change the ordering of elements with equal value. If you want those elements with equal frequency to appear in the same order than in the map you would need std::stable_sort. However, keep in mind that this requires additional resources in memory and compute time.




5. You are using a std::map, which is an ordered container. If you are only interested in the frequencies then a std::unordered_map will generally offer better performance. Although for a simple alphabet this will most likely be negligible.

Just a few comments to add.

Data Structure

In this case, I'd tend to avoid std::map for counting frequencies. I probably wouldn't use std::unordered_map either though. Instead, I'd create a simple array:

std::array<int, std::numeric_limits<unsigned char>::max()> freq;

[Note: when using this, you want to convert the input characters to unsiged char before using them as indices.¹]

Both map and unordered_map do quite a bit of work to create something that acts like an array, but indexed using types (like strings) for which it's impractical to use the values of that type as an index directly because it would typically require far too much memory. In your case, however, you're using a char as an index, so creating an array that just allows all possible values of char as its index is utterly trivial. The amount of memory used is small enough that it's feasible even on thoroughly ancient computers (e.g., a Commodore 64 or Apple II). In this case, the array is so small (1 or 2 kilobytes) that it'll normally save space.

In addition, the array will almost certainly be quite a bit faster than either a map or unordered_map.

One time you'd want to think about using the map or unordered_map would be if you were going to support a character set like Unicode where using characters directly as array indices would lead to an inconveniently large array. In this case, you might (easily) want to us a map rather than an unordered_map. This would make it easy (for one example) to show frequencies for things like letters and digits, while ignoring things like punctuation and diacritics.

Formatting

I prefer to leave at least one blank line between the last header inclusion line, and whatever comes after it (in this case, the beginning of main).

Return value from main

There's no need to return 0; from main--the compiler will do that automatically if you just let control flow off the end of main.

using of std::endl

I advise against using std::endl in general. In addition to writing a new-line to the stream (which is all you probably want) it flushes the stream (which you almost never want). Especially if you're producing a lot of output, these unnecessary flushes can (and often do) slow programs substantially (a 10:1 margin is fairly common).

On the relatively rare occasion that you want to writ a new line and flush the stream, I'd do that explicitly: std::cout << 'n' << std:flush;

1. If you prefer, you can use a char that's signed (either by default or explicitly) and use it to index off of a pointer that points to the middle (usually the 128^th element) of the array.