sorting a map by converting it to vector











up vote
5
down vote

favorite
1












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;

}









share|improve this question







New contributor




Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1




    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
    – miscco
    Nov 26 at 20:47










  • Ok, I am a newbee, kind of excited to participate :)
    – Ring Zero.
    Nov 26 at 22:15















up vote
5
down vote

favorite
1












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;

}









share|improve this question







New contributor




Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1




    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
    – miscco
    Nov 26 at 20:47










  • Ok, I am a newbee, kind of excited to participate :)
    – Ring Zero.
    Nov 26 at 22:15













up vote
5
down vote

favorite
1









up vote
5
down vote

favorite
1






1





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;

}









share|improve this question







New contributor




Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











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;

}






c++ sorting hash-map






share|improve this question







New contributor




Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question







New contributor




Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question






New contributor




Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked Nov 26 at 20:22









Ring Zero.

325




325




New contributor




Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Ring Zero. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 1




    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
    – miscco
    Nov 26 at 20:47










  • Ok, I am a newbee, kind of excited to participate :)
    – Ring Zero.
    Nov 26 at 22:15














  • 1




    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
    – miscco
    Nov 26 at 20:47










  • Ok, I am a newbee, kind of excited to participate :)
    – Ring Zero.
    Nov 26 at 22:15








1




1




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
– miscco
Nov 26 at 20:47




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
– miscco
Nov 26 at 20:47












Ok, I am a newbee, kind of excited to participate :)
– Ring Zero.
Nov 26 at 22:15




Ok, I am a newbee, kind of excited to participate :)
– Ring Zero.
Nov 26 at 22:15










2 Answers
2






active

oldest

votes

















up vote
8
down vote



accepted










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.







share|improve this answer























  • I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx.
    – Ring Zero.
    Nov 26 at 20:49












  • 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 ?
    – Ring Zero.
    Nov 26 at 21:09








  • 1




    It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there.
    – miscco
    Nov 27 at 6:41






  • 2




    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.
    – Snowhawk
    Nov 27 at 6:49










  • 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.
    – Deduplicator
    Nov 27 at 23:00


















up vote
7
down vote













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.






share|improve this answer



















  • 1




    The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there.
    – Toby Speight
    Nov 27 at 11:24











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});






Ring Zero. is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f208474%2fsorting-a-map-by-converting-it-to-vector%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
8
down vote



accepted










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.







share|improve this answer























  • I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx.
    – Ring Zero.
    Nov 26 at 20:49












  • 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 ?
    – Ring Zero.
    Nov 26 at 21:09








  • 1




    It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there.
    – miscco
    Nov 27 at 6:41






  • 2




    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.
    – Snowhawk
    Nov 27 at 6:49










  • 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.
    – Deduplicator
    Nov 27 at 23:00















up vote
8
down vote



accepted










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.







share|improve this answer























  • I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx.
    – Ring Zero.
    Nov 26 at 20:49












  • 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 ?
    – Ring Zero.
    Nov 26 at 21:09








  • 1




    It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there.
    – miscco
    Nov 27 at 6:41






  • 2




    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.
    – Snowhawk
    Nov 27 at 6:49










  • 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.
    – Deduplicator
    Nov 27 at 23:00













up vote
8
down vote



accepted







up vote
8
down vote



accepted






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.







share|improve this answer














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.








share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 26 at 21:24









Null

1,1372921




1,1372921










answered Nov 26 at 20:44









miscco

3,367517




3,367517












  • I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx.
    – Ring Zero.
    Nov 26 at 20:49












  • 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 ?
    – Ring Zero.
    Nov 26 at 21:09








  • 1




    It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there.
    – miscco
    Nov 27 at 6:41






  • 2




    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.
    – Snowhawk
    Nov 27 at 6:49










  • 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.
    – Deduplicator
    Nov 27 at 23:00


















  • I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx.
    – Ring Zero.
    Nov 26 at 20:49












  • 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 ?
    – Ring Zero.
    Nov 26 at 21:09








  • 1




    It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there.
    – miscco
    Nov 27 at 6:41






  • 2




    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.
    – Snowhawk
    Nov 27 at 6:49










  • 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.
    – Deduplicator
    Nov 27 at 23:00
















I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx.
– Ring Zero.
Nov 26 at 20:49






I know we should not say thanks and become sentimental, but this was a very thorough and nice review of my code. Tnx.
– Ring Zero.
Nov 26 at 20:49














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 ?
– Ring Zero.
Nov 26 at 21:09






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 ?
– Ring Zero.
Nov 26 at 21:09






1




1




It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there.
– miscco
Nov 27 at 6:41




It seems that the compiler cannot deduce from the iterator constructor, so you will have to add the template argument there.
– miscco
Nov 27 at 6:41




2




2




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.
– Snowhawk
Nov 27 at 6:49




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.
– Snowhawk
Nov 27 at 6:49












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.
– Deduplicator
Nov 27 at 23:00




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.
– Deduplicator
Nov 27 at 23:00












up vote
7
down vote













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.






share|improve this answer



















  • 1




    The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there.
    – Toby Speight
    Nov 27 at 11:24















up vote
7
down vote













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.






share|improve this answer



















  • 1




    The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there.
    – Toby Speight
    Nov 27 at 11:24













up vote
7
down vote










up vote
7
down vote









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.






share|improve this answer














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.







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 27 at 21:56

























answered Nov 27 at 8:09









Jerry Coffin

27.8k460125




27.8k460125








  • 1




    The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there.
    – Toby Speight
    Nov 27 at 11:24














  • 1




    The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there.
    – Toby Speight
    Nov 27 at 11:24








1




1




The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there.
– Toby Speight
Nov 27 at 11:24




The std::array might be problematic with plain char as index - it would be safer to convert input to unsigned char there.
– Toby Speight
Nov 27 at 11:24










Ring Zero. is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















Ring Zero. is a new contributor. Be nice, and check out our Code of Conduct.













Ring Zero. is a new contributor. Be nice, and check out our Code of Conduct.












Ring Zero. is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to Code Review Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f208474%2fsorting-a-map-by-converting-it-to-vector%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

AnyDesk - Fatal Program Failure

How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

QoS: MAC-Priority for clients behind a repeater