5
\$\begingroup\$

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;   

}
\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to wait a bit until you accept an answer. There are quite a lot of people on this site that want to comment \$\endgroup\$ – miscco Nov 26 '18 at 20:47
  • \$\begingroup\$ Ok, I am a newbee, kind of excited to participate :) \$\endgroup\$ – Ring Zero. Nov 26 '18 at 22:15
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx. \$\endgroup\$ – Ring Zero. Nov 26 '18 at 20:49
  • \$\begingroup\$ I could implement all the items, except for auto template arg deduction. Item 2. when I use auto items = std::vector(freq.begin(), freq.end()); clang++-6.0 complains about not being able to deduce vector type. perhaps I am doing something wrong ? \$\endgroup\$ – Ring Zero. Nov 26 '18 at 21:09
  • 1
    \$\begingroup\$ It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there. \$\endgroup\$ – miscco Nov 27 '18 at 6:41
  • 2
    \$\begingroup\$ Clang is still adding support for Class Template Argument Deduction as much of the standard library had to be rewritten to accommodate the feature. Clang 7.0 was the first version to introduce CTAD for library types. \$\endgroup\$ – Snowhawk Nov 27 '18 at 6:49
  • \$\begingroup\$ Passing small trivially-copyable types by value is The Right Thing. Not that it matters if the callee is such a simple function-object and the call thus gets inlined. Regarding the best container to use for calculating frequencies, it is hard to beat a plain native array. \$\endgroup\$ – Deduplicator Nov 27 '18 at 23:00
7
\$\begingroup\$

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.1]

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 128th element) of the array.
\$\endgroup\$
  • 1
    \$\begingroup\$ The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there. \$\endgroup\$ – Toby Speight Nov 27 '18 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.