Sort int array by frequency then value












7














Problem



Take an array of ints as input and run a special sorting algorithm on it. This algorithm must first sort by int frequency, less frequent first, then sort by value.



For example [4,5,6,5,4,3] is sorted to [3,6,4,4,5,5].



I'm looking for feedback on my use of data structures to implement this sort, memory management, any redundancies, and other general optimizations I can make. No need to give feedback on how I capture input in main since that is not my priority here.



Code



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int * customSort(int * arr, int n) {
unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}

map<int, set<int>> orderedfrequencyMap;
for (auto &p : frequencyMap) {
auto mapIt = orderedfrequencyMap.find(p.second);
if (mapIt == orderedfrequencyMap.end()) {
set<int> s = {p.first};
orderedfrequencyMap.insert(make_pair(p.second, s));
} else {
(*mapIt).second.insert(p.first);
}
}

int arrI = 0;
int solution[n];
for (auto &p : orderedfrequencyMap) {
for (auto element : p.second) {
for (int i = 0; i < p.first; i++) {
arr[arrI] = element;
cout << element << endl;
arrI++;
}
}
}

return solution;
}

int main() {
int n;
cin >> n;

int arr[n];

int element;
for (int i = 0; i < n; i++) {
cin >> element;
arr[i] = element;
}

customSort(arr, n);

return 0;
}









share|improve this question




















  • 8




    Please don't remove your header includes - not only does it slow down those of us who want to compile your code ourselves, but we frequently find improvements to make in that respect (missing includes, unnecessary includes, C includes, for example). Same goes for namespace std: we want to see your actual code, not some mangled version of it. Thanks!
    – Toby Speight
    Dec 6 at 17:42








  • 5




    Don't remove your includes. As part of the code review I want to copy and paste it into a file and compile it. Having to add the includes back adds to my work load. Also if you leave the includes I can spot where you have bad includes.
    – Martin York
    Dec 6 at 17:47






  • 1




    Use your real code.
    – Nic Hartley
    Dec 6 at 20:20












  • Thanks for the feedback everyone, I will remember this in the future. Added my includes and removed the namesapce comment, as my real code did originally use the bad practice global using statement so myself some time in implementing this prototype.
    – greg
    Dec 6 at 20:55
















7














Problem



Take an array of ints as input and run a special sorting algorithm on it. This algorithm must first sort by int frequency, less frequent first, then sort by value.



For example [4,5,6,5,4,3] is sorted to [3,6,4,4,5,5].



I'm looking for feedback on my use of data structures to implement this sort, memory management, any redundancies, and other general optimizations I can make. No need to give feedback on how I capture input in main since that is not my priority here.



Code



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int * customSort(int * arr, int n) {
unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}

map<int, set<int>> orderedfrequencyMap;
for (auto &p : frequencyMap) {
auto mapIt = orderedfrequencyMap.find(p.second);
if (mapIt == orderedfrequencyMap.end()) {
set<int> s = {p.first};
orderedfrequencyMap.insert(make_pair(p.second, s));
} else {
(*mapIt).second.insert(p.first);
}
}

int arrI = 0;
int solution[n];
for (auto &p : orderedfrequencyMap) {
for (auto element : p.second) {
for (int i = 0; i < p.first; i++) {
arr[arrI] = element;
cout << element << endl;
arrI++;
}
}
}

return solution;
}

int main() {
int n;
cin >> n;

int arr[n];

int element;
for (int i = 0; i < n; i++) {
cin >> element;
arr[i] = element;
}

customSort(arr, n);

return 0;
}









share|improve this question




















  • 8




    Please don't remove your header includes - not only does it slow down those of us who want to compile your code ourselves, but we frequently find improvements to make in that respect (missing includes, unnecessary includes, C includes, for example). Same goes for namespace std: we want to see your actual code, not some mangled version of it. Thanks!
    – Toby Speight
    Dec 6 at 17:42








  • 5




    Don't remove your includes. As part of the code review I want to copy and paste it into a file and compile it. Having to add the includes back adds to my work load. Also if you leave the includes I can spot where you have bad includes.
    – Martin York
    Dec 6 at 17:47






  • 1




    Use your real code.
    – Nic Hartley
    Dec 6 at 20:20












  • Thanks for the feedback everyone, I will remember this in the future. Added my includes and removed the namesapce comment, as my real code did originally use the bad practice global using statement so myself some time in implementing this prototype.
    – greg
    Dec 6 at 20:55














7












7








7







Problem



Take an array of ints as input and run a special sorting algorithm on it. This algorithm must first sort by int frequency, less frequent first, then sort by value.



For example [4,5,6,5,4,3] is sorted to [3,6,4,4,5,5].



I'm looking for feedback on my use of data structures to implement this sort, memory management, any redundancies, and other general optimizations I can make. No need to give feedback on how I capture input in main since that is not my priority here.



Code



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int * customSort(int * arr, int n) {
unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}

map<int, set<int>> orderedfrequencyMap;
for (auto &p : frequencyMap) {
auto mapIt = orderedfrequencyMap.find(p.second);
if (mapIt == orderedfrequencyMap.end()) {
set<int> s = {p.first};
orderedfrequencyMap.insert(make_pair(p.second, s));
} else {
(*mapIt).second.insert(p.first);
}
}

int arrI = 0;
int solution[n];
for (auto &p : orderedfrequencyMap) {
for (auto element : p.second) {
for (int i = 0; i < p.first; i++) {
arr[arrI] = element;
cout << element << endl;
arrI++;
}
}
}

return solution;
}

int main() {
int n;
cin >> n;

int arr[n];

int element;
for (int i = 0; i < n; i++) {
cin >> element;
arr[i] = element;
}

customSort(arr, n);

return 0;
}









share|improve this question















Problem



Take an array of ints as input and run a special sorting algorithm on it. This algorithm must first sort by int frequency, less frequent first, then sort by value.



For example [4,5,6,5,4,3] is sorted to [3,6,4,4,5,5].



I'm looking for feedback on my use of data structures to implement this sort, memory management, any redundancies, and other general optimizations I can make. No need to give feedback on how I capture input in main since that is not my priority here.



Code



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int * customSort(int * arr, int n) {
unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}

map<int, set<int>> orderedfrequencyMap;
for (auto &p : frequencyMap) {
auto mapIt = orderedfrequencyMap.find(p.second);
if (mapIt == orderedfrequencyMap.end()) {
set<int> s = {p.first};
orderedfrequencyMap.insert(make_pair(p.second, s));
} else {
(*mapIt).second.insert(p.first);
}
}

int arrI = 0;
int solution[n];
for (auto &p : orderedfrequencyMap) {
for (auto element : p.second) {
for (int i = 0; i < p.first; i++) {
arr[arrI] = element;
cout << element << endl;
arrI++;
}
}
}

return solution;
}

int main() {
int n;
cin >> n;

int arr[n];

int element;
for (int i = 0; i < n; i++) {
cin >> element;
arr[i] = element;
}

customSort(arr, n);

return 0;
}






c++ sorting hash-map set






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 6 at 20:53

























asked Dec 6 at 17:16









greg

29017




29017








  • 8




    Please don't remove your header includes - not only does it slow down those of us who want to compile your code ourselves, but we frequently find improvements to make in that respect (missing includes, unnecessary includes, C includes, for example). Same goes for namespace std: we want to see your actual code, not some mangled version of it. Thanks!
    – Toby Speight
    Dec 6 at 17:42








  • 5




    Don't remove your includes. As part of the code review I want to copy and paste it into a file and compile it. Having to add the includes back adds to my work load. Also if you leave the includes I can spot where you have bad includes.
    – Martin York
    Dec 6 at 17:47






  • 1




    Use your real code.
    – Nic Hartley
    Dec 6 at 20:20












  • Thanks for the feedback everyone, I will remember this in the future. Added my includes and removed the namesapce comment, as my real code did originally use the bad practice global using statement so myself some time in implementing this prototype.
    – greg
    Dec 6 at 20:55














  • 8




    Please don't remove your header includes - not only does it slow down those of us who want to compile your code ourselves, but we frequently find improvements to make in that respect (missing includes, unnecessary includes, C includes, for example). Same goes for namespace std: we want to see your actual code, not some mangled version of it. Thanks!
    – Toby Speight
    Dec 6 at 17:42








  • 5




    Don't remove your includes. As part of the code review I want to copy and paste it into a file and compile it. Having to add the includes back adds to my work load. Also if you leave the includes I can spot where you have bad includes.
    – Martin York
    Dec 6 at 17:47






  • 1




    Use your real code.
    – Nic Hartley
    Dec 6 at 20:20












  • Thanks for the feedback everyone, I will remember this in the future. Added my includes and removed the namesapce comment, as my real code did originally use the bad practice global using statement so myself some time in implementing this prototype.
    – greg
    Dec 6 at 20:55








8




8




Please don't remove your header includes - not only does it slow down those of us who want to compile your code ourselves, but we frequently find improvements to make in that respect (missing includes, unnecessary includes, C includes, for example). Same goes for namespace std: we want to see your actual code, not some mangled version of it. Thanks!
– Toby Speight
Dec 6 at 17:42






Please don't remove your header includes - not only does it slow down those of us who want to compile your code ourselves, but we frequently find improvements to make in that respect (missing includes, unnecessary includes, C includes, for example). Same goes for namespace std: we want to see your actual code, not some mangled version of it. Thanks!
– Toby Speight
Dec 6 at 17:42






5




5




Don't remove your includes. As part of the code review I want to copy and paste it into a file and compile it. Having to add the includes back adds to my work load. Also if you leave the includes I can spot where you have bad includes.
– Martin York
Dec 6 at 17:47




Don't remove your includes. As part of the code review I want to copy and paste it into a file and compile it. Having to add the includes back adds to my work load. Also if you leave the includes I can spot where you have bad includes.
– Martin York
Dec 6 at 17:47




1




1




Use your real code.
– Nic Hartley
Dec 6 at 20:20






Use your real code.
– Nic Hartley
Dec 6 at 20:20














Thanks for the feedback everyone, I will remember this in the future. Added my includes and removed the namesapce comment, as my real code did originally use the bad practice global using statement so myself some time in implementing this prototype.
– greg
Dec 6 at 20:55




Thanks for the feedback everyone, I will remember this in the future. Added my includes and removed the namesapce comment, as my real code did originally use the bad practice global using statement so myself some time in implementing this prototype.
– greg
Dec 6 at 20:55










1 Answer
1






active

oldest

votes


















15














Headers



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>


Some issues here. You definitely don't need all those headers. Proon out the ones you don't need. The problem with putting them all in is that this can hide missing dependencies (if this was a header file and included by other header files).



Normally I don't care much about the order of headers (usually there is some logic there and everybody has their own). But sorting by filename length of include seems a bit odd. I have seen people sort by alphabetical order (not my favorite but it has options and I see the merit). Personally I put things into logical (to me) groups; I put container stuff together, stream stuff together, algorithm stuff together and meta programming stuff together. I put all my C++ headers before my C header.



Maps



If you access an element in a map and it does not exist then it is automatically created and "zero-initialized". This means you don't need to search and conditialy update.



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}


Can be simplified too:



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
++frequencyMap[arr[i]];
}


VLA



Variable length arrays are an extension of C (part of C99). They were never part of the C++ standard. So this is not legal C++.



cin >> n;
int arr[n];


Your compiler supports it as an extension to the language but its not a good idea to use it. We use std::vector as a better alternative:



cin >> n;
std::vector<int> arr(n);


This also allows you to use range based for loops:



  unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}


Order by frequency.



I like your idea of ordering by frequency using a std::map but it becomes clunky when you also have to order by value (and thus have a map of std::set). I would simply copy the frequency info into a vector and use a sort.



using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs)
{
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});


Standard Issues from Beginners



Don't use



using namespace std;


This is a crutch that will break for you. Don't get into the habit of using it when it breaks it is not obvious and can lead to hours of debugging. The reason the standard namespace is called std and not standard is so prefixing object in the standard namespace is not that burdensome.



std::vector<int>  val;  // not that hard to add std::


Don't return an array from a function



 return solution;


You are returning the address of a local variable. Once this goes out of scope that variable no longer exists. So you have an invalid pointer returned. This is also another good reason to use std::vector as the copy/move semantics will correctly move it from the current scope to the calling scope.



PS. Your compiler should warn you about this.



No need to use return in main



return 0;


The compiler plants a return 0 at the end of main.



By not planting a return in main() it is an indication that your application does not have a failing state (usual for simple code). If it does have a user inserted return 0 I always start looking for other places it could return an error code. By not putting a return 0 you indicate to me that there is no error situation and I don't have to look for it.



Prefer pre increment to post increment



for (int i = 0; i < p.first; i++)

for (int i = 0; i < p.first; ++i)


In this case there is basically no difference. But there are situations where the post increment is slightly more complex.



What happen if we change i from an int into an iterator. Then it is a class the executes a function. Most iteratros behave like POD types with pre/post increment but to do that the post increment is slightly more complex. So why not use the one that will always give you optimal code (even if you change the type). So prefer pre-increment.



Prefer 'n' over std::endl



The difference is that std::endl will force a flush. In simple things like this it makes no difference. But if you are outputting a large amount of information then the extra flush can cause significant performance degradation.



The streams will auto flush themselves and having a human forcing a flush is always non optimal. So prefer to get the same resutls but at optimal speed with 'n'.



Pointer short hand



You should note that we have a shortcut pointer notation.



(*mapIt).second

// Shorthand as:
mapIt->second


Avoid short variable names



for (int i = 0; i < n; i++) {


This is great if your for loop is two lines long. But if the loop grows and becomes more complex then searching for all instances of i becomes a pain because of all the false positives.



Believe me just because your loop only covers two lines today, in ten years after thousands of bug fixes it will not look as neat. So give me something that is easy to search for in the code base.



I know a lot of people like using i as a loop variable. But this is a hold over from Foortran. Please use longer identifiers it will not cost you that much and the maintainer will not hunt you down with an axe.



Looks Like this:



#include <unordered_map>
#include <vector>
#include <iostream>
#include <iterator>

std::vector<int> customSort(std::vector<int> const& arr)
{
std::unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}

using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs) {
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});

std::vector<int> result;
result.reserve(arr.size());
for(auto const& val: values) {
for(int loop = 0;loop < val.second; ++loop) {
result.push_back(val.first);
}
}
return result;
}

int main()
{
std::vector<int> arr;

int n;
std::cin >> n;
std::copy_n(std::istream_iterator<int>(std::cin), n,
std::back_inserter(arr));

std::vector<int> sorted = customSort(arr);
std::copy(std::begin(sorted), std::end(sorted),
std::ostream_iterator<int>(std::cout, "n"));
}





share|improve this answer























  • Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types?
    – greg
    Dec 6 at 18:32






  • 1




    Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef.
    – Martin York
    Dec 6 at 19:13






  • 1




    POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression.
    – Martin York
    Dec 6 at 19:14










  • IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?).
    – wondra
    Dec 7 at 7:33












  • @wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move.
    – Martin York
    Dec 7 at 17:52











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',
autoActivateHeartbeat: false,
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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209168%2fsort-int-array-by-frequency-then-value%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









15














Headers



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>


Some issues here. You definitely don't need all those headers. Proon out the ones you don't need. The problem with putting them all in is that this can hide missing dependencies (if this was a header file and included by other header files).



Normally I don't care much about the order of headers (usually there is some logic there and everybody has their own). But sorting by filename length of include seems a bit odd. I have seen people sort by alphabetical order (not my favorite but it has options and I see the merit). Personally I put things into logical (to me) groups; I put container stuff together, stream stuff together, algorithm stuff together and meta programming stuff together. I put all my C++ headers before my C header.



Maps



If you access an element in a map and it does not exist then it is automatically created and "zero-initialized". This means you don't need to search and conditialy update.



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}


Can be simplified too:



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
++frequencyMap[arr[i]];
}


VLA



Variable length arrays are an extension of C (part of C99). They were never part of the C++ standard. So this is not legal C++.



cin >> n;
int arr[n];


Your compiler supports it as an extension to the language but its not a good idea to use it. We use std::vector as a better alternative:



cin >> n;
std::vector<int> arr(n);


This also allows you to use range based for loops:



  unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}


Order by frequency.



I like your idea of ordering by frequency using a std::map but it becomes clunky when you also have to order by value (and thus have a map of std::set). I would simply copy the frequency info into a vector and use a sort.



using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs)
{
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});


Standard Issues from Beginners



Don't use



using namespace std;


This is a crutch that will break for you. Don't get into the habit of using it when it breaks it is not obvious and can lead to hours of debugging. The reason the standard namespace is called std and not standard is so prefixing object in the standard namespace is not that burdensome.



std::vector<int>  val;  // not that hard to add std::


Don't return an array from a function



 return solution;


You are returning the address of a local variable. Once this goes out of scope that variable no longer exists. So you have an invalid pointer returned. This is also another good reason to use std::vector as the copy/move semantics will correctly move it from the current scope to the calling scope.



PS. Your compiler should warn you about this.



No need to use return in main



return 0;


The compiler plants a return 0 at the end of main.



By not planting a return in main() it is an indication that your application does not have a failing state (usual for simple code). If it does have a user inserted return 0 I always start looking for other places it could return an error code. By not putting a return 0 you indicate to me that there is no error situation and I don't have to look for it.



Prefer pre increment to post increment



for (int i = 0; i < p.first; i++)

for (int i = 0; i < p.first; ++i)


In this case there is basically no difference. But there are situations where the post increment is slightly more complex.



What happen if we change i from an int into an iterator. Then it is a class the executes a function. Most iteratros behave like POD types with pre/post increment but to do that the post increment is slightly more complex. So why not use the one that will always give you optimal code (even if you change the type). So prefer pre-increment.



Prefer 'n' over std::endl



The difference is that std::endl will force a flush. In simple things like this it makes no difference. But if you are outputting a large amount of information then the extra flush can cause significant performance degradation.



The streams will auto flush themselves and having a human forcing a flush is always non optimal. So prefer to get the same resutls but at optimal speed with 'n'.



Pointer short hand



You should note that we have a shortcut pointer notation.



(*mapIt).second

// Shorthand as:
mapIt->second


Avoid short variable names



for (int i = 0; i < n; i++) {


This is great if your for loop is two lines long. But if the loop grows and becomes more complex then searching for all instances of i becomes a pain because of all the false positives.



Believe me just because your loop only covers two lines today, in ten years after thousands of bug fixes it will not look as neat. So give me something that is easy to search for in the code base.



I know a lot of people like using i as a loop variable. But this is a hold over from Foortran. Please use longer identifiers it will not cost you that much and the maintainer will not hunt you down with an axe.



Looks Like this:



#include <unordered_map>
#include <vector>
#include <iostream>
#include <iterator>

std::vector<int> customSort(std::vector<int> const& arr)
{
std::unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}

using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs) {
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});

std::vector<int> result;
result.reserve(arr.size());
for(auto const& val: values) {
for(int loop = 0;loop < val.second; ++loop) {
result.push_back(val.first);
}
}
return result;
}

int main()
{
std::vector<int> arr;

int n;
std::cin >> n;
std::copy_n(std::istream_iterator<int>(std::cin), n,
std::back_inserter(arr));

std::vector<int> sorted = customSort(arr);
std::copy(std::begin(sorted), std::end(sorted),
std::ostream_iterator<int>(std::cout, "n"));
}





share|improve this answer























  • Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types?
    – greg
    Dec 6 at 18:32






  • 1




    Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef.
    – Martin York
    Dec 6 at 19:13






  • 1




    POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression.
    – Martin York
    Dec 6 at 19:14










  • IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?).
    – wondra
    Dec 7 at 7:33












  • @wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move.
    – Martin York
    Dec 7 at 17:52
















15














Headers



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>


Some issues here. You definitely don't need all those headers. Proon out the ones you don't need. The problem with putting them all in is that this can hide missing dependencies (if this was a header file and included by other header files).



Normally I don't care much about the order of headers (usually there is some logic there and everybody has their own). But sorting by filename length of include seems a bit odd. I have seen people sort by alphabetical order (not my favorite but it has options and I see the merit). Personally I put things into logical (to me) groups; I put container stuff together, stream stuff together, algorithm stuff together and meta programming stuff together. I put all my C++ headers before my C header.



Maps



If you access an element in a map and it does not exist then it is automatically created and "zero-initialized". This means you don't need to search and conditialy update.



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}


Can be simplified too:



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
++frequencyMap[arr[i]];
}


VLA



Variable length arrays are an extension of C (part of C99). They were never part of the C++ standard. So this is not legal C++.



cin >> n;
int arr[n];


Your compiler supports it as an extension to the language but its not a good idea to use it. We use std::vector as a better alternative:



cin >> n;
std::vector<int> arr(n);


This also allows you to use range based for loops:



  unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}


Order by frequency.



I like your idea of ordering by frequency using a std::map but it becomes clunky when you also have to order by value (and thus have a map of std::set). I would simply copy the frequency info into a vector and use a sort.



using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs)
{
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});


Standard Issues from Beginners



Don't use



using namespace std;


This is a crutch that will break for you. Don't get into the habit of using it when it breaks it is not obvious and can lead to hours of debugging. The reason the standard namespace is called std and not standard is so prefixing object in the standard namespace is not that burdensome.



std::vector<int>  val;  // not that hard to add std::


Don't return an array from a function



 return solution;


You are returning the address of a local variable. Once this goes out of scope that variable no longer exists. So you have an invalid pointer returned. This is also another good reason to use std::vector as the copy/move semantics will correctly move it from the current scope to the calling scope.



PS. Your compiler should warn you about this.



No need to use return in main



return 0;


The compiler plants a return 0 at the end of main.



By not planting a return in main() it is an indication that your application does not have a failing state (usual for simple code). If it does have a user inserted return 0 I always start looking for other places it could return an error code. By not putting a return 0 you indicate to me that there is no error situation and I don't have to look for it.



Prefer pre increment to post increment



for (int i = 0; i < p.first; i++)

for (int i = 0; i < p.first; ++i)


In this case there is basically no difference. But there are situations where the post increment is slightly more complex.



What happen if we change i from an int into an iterator. Then it is a class the executes a function. Most iteratros behave like POD types with pre/post increment but to do that the post increment is slightly more complex. So why not use the one that will always give you optimal code (even if you change the type). So prefer pre-increment.



Prefer 'n' over std::endl



The difference is that std::endl will force a flush. In simple things like this it makes no difference. But if you are outputting a large amount of information then the extra flush can cause significant performance degradation.



The streams will auto flush themselves and having a human forcing a flush is always non optimal. So prefer to get the same resutls but at optimal speed with 'n'.



Pointer short hand



You should note that we have a shortcut pointer notation.



(*mapIt).second

// Shorthand as:
mapIt->second


Avoid short variable names



for (int i = 0; i < n; i++) {


This is great if your for loop is two lines long. But if the loop grows and becomes more complex then searching for all instances of i becomes a pain because of all the false positives.



Believe me just because your loop only covers two lines today, in ten years after thousands of bug fixes it will not look as neat. So give me something that is easy to search for in the code base.



I know a lot of people like using i as a loop variable. But this is a hold over from Foortran. Please use longer identifiers it will not cost you that much and the maintainer will not hunt you down with an axe.



Looks Like this:



#include <unordered_map>
#include <vector>
#include <iostream>
#include <iterator>

std::vector<int> customSort(std::vector<int> const& arr)
{
std::unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}

using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs) {
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});

std::vector<int> result;
result.reserve(arr.size());
for(auto const& val: values) {
for(int loop = 0;loop < val.second; ++loop) {
result.push_back(val.first);
}
}
return result;
}

int main()
{
std::vector<int> arr;

int n;
std::cin >> n;
std::copy_n(std::istream_iterator<int>(std::cin), n,
std::back_inserter(arr));

std::vector<int> sorted = customSort(arr);
std::copy(std::begin(sorted), std::end(sorted),
std::ostream_iterator<int>(std::cout, "n"));
}





share|improve this answer























  • Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types?
    – greg
    Dec 6 at 18:32






  • 1




    Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef.
    – Martin York
    Dec 6 at 19:13






  • 1




    POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression.
    – Martin York
    Dec 6 at 19:14










  • IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?).
    – wondra
    Dec 7 at 7:33












  • @wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move.
    – Martin York
    Dec 7 at 17:52














15












15








15






Headers



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>


Some issues here. You definitely don't need all those headers. Proon out the ones you don't need. The problem with putting them all in is that this can hide missing dependencies (if this was a header file and included by other header files).



Normally I don't care much about the order of headers (usually there is some logic there and everybody has their own). But sorting by filename length of include seems a bit odd. I have seen people sort by alphabetical order (not my favorite but it has options and I see the merit). Personally I put things into logical (to me) groups; I put container stuff together, stream stuff together, algorithm stuff together and meta programming stuff together. I put all my C++ headers before my C header.



Maps



If you access an element in a map and it does not exist then it is automatically created and "zero-initialized". This means you don't need to search and conditialy update.



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}


Can be simplified too:



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
++frequencyMap[arr[i]];
}


VLA



Variable length arrays are an extension of C (part of C99). They were never part of the C++ standard. So this is not legal C++.



cin >> n;
int arr[n];


Your compiler supports it as an extension to the language but its not a good idea to use it. We use std::vector as a better alternative:



cin >> n;
std::vector<int> arr(n);


This also allows you to use range based for loops:



  unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}


Order by frequency.



I like your idea of ordering by frequency using a std::map but it becomes clunky when you also have to order by value (and thus have a map of std::set). I would simply copy the frequency info into a vector and use a sort.



using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs)
{
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});


Standard Issues from Beginners



Don't use



using namespace std;


This is a crutch that will break for you. Don't get into the habit of using it when it breaks it is not obvious and can lead to hours of debugging. The reason the standard namespace is called std and not standard is so prefixing object in the standard namespace is not that burdensome.



std::vector<int>  val;  // not that hard to add std::


Don't return an array from a function



 return solution;


You are returning the address of a local variable. Once this goes out of scope that variable no longer exists. So you have an invalid pointer returned. This is also another good reason to use std::vector as the copy/move semantics will correctly move it from the current scope to the calling scope.



PS. Your compiler should warn you about this.



No need to use return in main



return 0;


The compiler plants a return 0 at the end of main.



By not planting a return in main() it is an indication that your application does not have a failing state (usual for simple code). If it does have a user inserted return 0 I always start looking for other places it could return an error code. By not putting a return 0 you indicate to me that there is no error situation and I don't have to look for it.



Prefer pre increment to post increment



for (int i = 0; i < p.first; i++)

for (int i = 0; i < p.first; ++i)


In this case there is basically no difference. But there are situations where the post increment is slightly more complex.



What happen if we change i from an int into an iterator. Then it is a class the executes a function. Most iteratros behave like POD types with pre/post increment but to do that the post increment is slightly more complex. So why not use the one that will always give you optimal code (even if you change the type). So prefer pre-increment.



Prefer 'n' over std::endl



The difference is that std::endl will force a flush. In simple things like this it makes no difference. But if you are outputting a large amount of information then the extra flush can cause significant performance degradation.



The streams will auto flush themselves and having a human forcing a flush is always non optimal. So prefer to get the same resutls but at optimal speed with 'n'.



Pointer short hand



You should note that we have a shortcut pointer notation.



(*mapIt).second

// Shorthand as:
mapIt->second


Avoid short variable names



for (int i = 0; i < n; i++) {


This is great if your for loop is two lines long. But if the loop grows and becomes more complex then searching for all instances of i becomes a pain because of all the false positives.



Believe me just because your loop only covers two lines today, in ten years after thousands of bug fixes it will not look as neat. So give me something that is easy to search for in the code base.



I know a lot of people like using i as a loop variable. But this is a hold over from Foortran. Please use longer identifiers it will not cost you that much and the maintainer will not hunt you down with an axe.



Looks Like this:



#include <unordered_map>
#include <vector>
#include <iostream>
#include <iterator>

std::vector<int> customSort(std::vector<int> const& arr)
{
std::unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}

using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs) {
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});

std::vector<int> result;
result.reserve(arr.size());
for(auto const& val: values) {
for(int loop = 0;loop < val.second; ++loop) {
result.push_back(val.first);
}
}
return result;
}

int main()
{
std::vector<int> arr;

int n;
std::cin >> n;
std::copy_n(std::istream_iterator<int>(std::cin), n,
std::back_inserter(arr));

std::vector<int> sorted = customSort(arr);
std::copy(std::begin(sorted), std::end(sorted),
std::ostream_iterator<int>(std::cout, "n"));
}





share|improve this answer














Headers



#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>


Some issues here. You definitely don't need all those headers. Proon out the ones you don't need. The problem with putting them all in is that this can hide missing dependencies (if this was a header file and included by other header files).



Normally I don't care much about the order of headers (usually there is some logic there and everybody has their own). But sorting by filename length of include seems a bit odd. I have seen people sort by alphabetical order (not my favorite but it has options and I see the merit). Personally I put things into logical (to me) groups; I put container stuff together, stream stuff together, algorithm stuff together and meta programming stuff together. I put all my C++ headers before my C header.



Maps



If you access an element in a map and it does not exist then it is automatically created and "zero-initialized". This means you don't need to search and conditialy update.



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
auto mapIt = frequencyMap.find(arr[i]);
if (mapIt == frequencyMap.end()) {
frequencyMap.insert(make_pair(arr[i], 1));
} else {
frequencyMap[arr[i]]++;
}
}


Can be simplified too:



  unordered_map<int, int> frequencyMap;
for (int i = 0; i < n; i++) {
++frequencyMap[arr[i]];
}


VLA



Variable length arrays are an extension of C (part of C99). They were never part of the C++ standard. So this is not legal C++.



cin >> n;
int arr[n];


Your compiler supports it as an extension to the language but its not a good idea to use it. We use std::vector as a better alternative:



cin >> n;
std::vector<int> arr(n);


This also allows you to use range based for loops:



  unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}


Order by frequency.



I like your idea of ordering by frequency using a std::map but it becomes clunky when you also have to order by value (and thus have a map of std::set). I would simply copy the frequency info into a vector and use a sort.



using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs)
{
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});


Standard Issues from Beginners



Don't use



using namespace std;


This is a crutch that will break for you. Don't get into the habit of using it when it breaks it is not obvious and can lead to hours of debugging. The reason the standard namespace is called std and not standard is so prefixing object in the standard namespace is not that burdensome.



std::vector<int>  val;  // not that hard to add std::


Don't return an array from a function



 return solution;


You are returning the address of a local variable. Once this goes out of scope that variable no longer exists. So you have an invalid pointer returned. This is also another good reason to use std::vector as the copy/move semantics will correctly move it from the current scope to the calling scope.



PS. Your compiler should warn you about this.



No need to use return in main



return 0;


The compiler plants a return 0 at the end of main.



By not planting a return in main() it is an indication that your application does not have a failing state (usual for simple code). If it does have a user inserted return 0 I always start looking for other places it could return an error code. By not putting a return 0 you indicate to me that there is no error situation and I don't have to look for it.



Prefer pre increment to post increment



for (int i = 0; i < p.first; i++)

for (int i = 0; i < p.first; ++i)


In this case there is basically no difference. But there are situations where the post increment is slightly more complex.



What happen if we change i from an int into an iterator. Then it is a class the executes a function. Most iteratros behave like POD types with pre/post increment but to do that the post increment is slightly more complex. So why not use the one that will always give you optimal code (even if you change the type). So prefer pre-increment.



Prefer 'n' over std::endl



The difference is that std::endl will force a flush. In simple things like this it makes no difference. But if you are outputting a large amount of information then the extra flush can cause significant performance degradation.



The streams will auto flush themselves and having a human forcing a flush is always non optimal. So prefer to get the same resutls but at optimal speed with 'n'.



Pointer short hand



You should note that we have a shortcut pointer notation.



(*mapIt).second

// Shorthand as:
mapIt->second


Avoid short variable names



for (int i = 0; i < n; i++) {


This is great if your for loop is two lines long. But if the loop grows and becomes more complex then searching for all instances of i becomes a pain because of all the false positives.



Believe me just because your loop only covers two lines today, in ten years after thousands of bug fixes it will not look as neat. So give me something that is easy to search for in the code base.



I know a lot of people like using i as a loop variable. But this is a hold over from Foortran. Please use longer identifiers it will not cost you that much and the maintainer will not hunt you down with an axe.



Looks Like this:



#include <unordered_map>
#include <vector>
#include <iostream>
#include <iterator>

std::vector<int> customSort(std::vector<int> const& arr)
{
std::unordered_map<int, int> frequencyMap;
for (int val: arr) {
++frequencyMap[val];
}

using Val = std::pair<int, int>;
std::vector<Val> values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), (Val const& lhs, Val const& rhs) {
return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
});

std::vector<int> result;
result.reserve(arr.size());
for(auto const& val: values) {
for(int loop = 0;loop < val.second; ++loop) {
result.push_back(val.first);
}
}
return result;
}

int main()
{
std::vector<int> arr;

int n;
std::cin >> n;
std::copy_n(std::istream_iterator<int>(std::cin), n,
std::back_inserter(arr));

std::vector<int> sorted = customSort(arr);
std::copy(std::begin(sorted), std::end(sorted),
std::ostream_iterator<int>(std::cout, "n"));
}






share|improve this answer














share|improve this answer



share|improve this answer








edited Dec 7 at 17:55

























answered Dec 6 at 17:44









Martin York

72.4k483259




72.4k483259












  • Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types?
    – greg
    Dec 6 at 18:32






  • 1




    Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef.
    – Martin York
    Dec 6 at 19:13






  • 1




    POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression.
    – Martin York
    Dec 6 at 19:14










  • IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?).
    – wondra
    Dec 7 at 7:33












  • @wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move.
    – Martin York
    Dec 7 at 17:52


















  • Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types?
    – greg
    Dec 6 at 18:32






  • 1




    Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef.
    – Martin York
    Dec 6 at 19:13






  • 1




    POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression.
    – Martin York
    Dec 6 at 19:14










  • IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?).
    – wondra
    Dec 7 at 7:33












  • @wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move.
    – Martin York
    Dec 7 at 17:52
















Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types?
– greg
Dec 6 at 18:32




Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types?
– greg
Dec 6 at 18:32




1




1




Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef.
– Martin York
Dec 6 at 19:13




Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef.
– Martin York
Dec 6 at 19:13




1




1




POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression.
– Martin York
Dec 6 at 19:14




POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression.
– Martin York
Dec 6 at 19:14












IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?).
– wondra
Dec 7 at 7:33






IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?).
– wondra
Dec 7 at 7:33














@wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move.
– Martin York
Dec 7 at 17:52




@wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move.
– Martin York
Dec 7 at 17:52


















draft saved

draft discarded




















































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%2f209168%2fsort-int-array-by-frequency-then-value%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

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei