# Find the most frequent integer in an array

I have been a Python developer for a few years and I'm going through some simple exercises to learn C++.

Please consider the following Python snippet

# Find the most frequent integer in an array
lst = [1,2,4,3,1,3,1,4,5,15,5,2,3,5,4]
mydict   = {}
cnt, itm = 0, ''

for item in lst:
mydict[item] = mydict.get(item, 0) + 1
if mydict[item] >= cnt :
cnt, itm = mydict[item], item

print(itm)


It may not be very clean and it misses elements that tie for most frequent, but it is succinct code. I re-wrote this to C++11 as:

#include <iostream>
#include <unordered_map>
#include <string>

int main(int argc, char const *argv[])
{
using std::cout;

int foo [] = {1,2,4,3,1,3,1,4,5,15,5,2,3,5,4};

std::unordered_map<std::string, int> dict;

std::string item;

int count = 0;

std::string itm;

for (int i : foo) {
item = std::to_string(i);

auto it = dict.find(item);

if (it != dict.end()) {
it->second = it->second++;

if (it->second >= count) {
count = it->second;
itm = item;
}
} else {
dict.insert(std::make_pair<std::string, int>(item, 0));
}

}

std::cout << "The integer most frequent is " << itm << "\n";
return 0;
}


This executes fine and returns 4 which is one of the correct answers. Can someone please offer a re-write of this to make it more succinct.

At present I am not concerned about if there's more than one element in the list that has a tie for most frequent. I am more concerned with cleaner code.

• You could consider changing algorithm, i.e. first sort the array, then go through all elements and see what's most common. – enedil Mar 2 '17 at 22:29
• The most succinct Python solution would be collections.Counter(lst).most_common(1)[0]. – 200_success Mar 2 '17 at 23:01

Your original Python code translates line-for-line into C++11 as:

#include <iostream>
#include <map>
#include <tuple>
#include <vector>

int main()
{
std::vector<int> lst = {1,2,4,3,1,3,1,4,5,15,5,2,3,5,4};
std::map<int, int> mydict = {};
int cnt = 0;
int itm = 0;  // in Python you made this a string '', which seems like a bug

for (auto&& item : lst) {
mydict[item] = mydict.emplace(item, 0).first->second + 1;
if (mydict[item] >= cnt) {
std::tie(cnt, itm) = std::tie(mydict[item], item);
}
}

std::cout << itm << std::endl;
}


The only newly introduced lines here are the #include lines, the lines that define main(), and a couple of closing curly braces.

Your C++ code could definitely be cleaned up by removing a lot of its blank lines and premature declarations; for example, there's no need to put a blank line in between every pair of declarations, and there's no need to pre-declare item outside the for-loop. Just tightening up the style (whitespace and such) will go a long way toward readability.

You have a bug on this line:

it->second = it->second++;


In C++, it->second++ is a side-effecting expression: it means "actually increment it->second, and then return the old value." So (in C++11 and C++14), this statement as a whole has undefined behavior: it's telling the compiler that you want to increment it->second, but also assign a new value to it->second.

In C++17, this statement may or may not have defined behavior; I'll have to read up on it and get back to you. Certainly it->second++ is guaranteed to be evaluated prior to the assignment, but I don't know if that completely solves the problem.

Anyway, what you meant to write was simply

it->second = it->second+1;


or

++it->second;


Stylistically, I advise writing "increment thing" instead of "thing increment", intuitively because that's how English works, but also because it can be an optimization in some cases involving overloaded operator++ (and is never a pessimization).

Your code actually doesn't compile with any C++11 compiler I have access to, because of your misuse of the std::make_pair function template. You wrote

std::make_pair<std::string, int>(item, 0)


but you should have written

std::make_pair(item, 0)


so that the compiler would deduce the types for you. (And in this case it deduces std::make_pair<std::string&, int>; but you as the programmer shouldn't have to care about that. Just let the compiler do its job and you try to stay out of its way as much as possible.)

The function parameters argc and argv are unused, so you should get rid of them. int main() is perfectly fine in both C and C++.

I don't understand why you write using std::cout; but then proceed to use the fully qualified names of std::string, std::make_pair, and so on. I would think that you'd either use the fully qualified names of everything from std:: (my preferred choice), or else go all out and using std::... a ton of things.

Anyway, using std::cout doesn't save you any typing — it actually costs you two lines and about 10 characters — so you'd do well to get rid of it.

As far as improving your C++ skills to the point where you can translate Python line-for-line as I did above, the best advice I can give you is go to cppreference.com and study the standard library! The STL is way better today than it was in 2003, and it takes ideas from many other languages. So for example the C++ equivalent of mydict.get(item, 0) is this humongous ugly expression mydict.emplace(item, 0).first->second (and I'm not actually saying you should write that ugly expression in production code!), but it does exist, and translation from Python to C++ is just a matter of being able to remember vaguely what it's called and look it up. And that just takes a lot of practice.

• I used clang++ and it does compile and print. – Sam Hammamy Mar 2 '17 at 22:40
• As far as std:: .. I was reading about using namespace and avoiding conflicts. I may have not understood it correctly. – Sam Hammamy Mar 2 '17 at 22:43
• mydict[item] = mydict.emplace(item, 0).first->second + 1; Can be simplified to: ++mydict[item]; – Martin York Mar 3 '17 at 4:32
• @LokiAstari: Good call. Since mydict[item] will value-initialize the value (to zero in this case), it works. The ugly way is needed if you're initializing to something that's not value-initialization, though. – Quuxplusone Mar 3 '17 at 5:05
• @LokiAstari: I think we're agreeing. I may have misused the term "value-initialization" (although I didn't think I had). I meant to say that if OP's code had been mydict[item] = mydict.get(item, 42) + 1, then we'd be stuck with the ugly way. The nice short clean way works only if the second argument to the Python .get happens to be the same as the C++ type's zero/default-constructed value. (Which, again, is true in this case. I'm just being defensive. ;)) – Quuxplusone Mar 3 '17 at 7:31

If you want to go python like we can compress it a bit more.

The std::accumulate() function is designed to run over a container and collect information. Normally we do something simple with it; like std::plus to add the elements. But with the quick addition of a lambda we can get it to count each value and return the highest counted value (the return value of each iteration of the lambda is passed back as the first parameter to the lambda).

#include <iostream>
#include <numeric>
#include <map>

int main()
{
int foo [] = {1,2,4,3,1,3,1,4,5,15,5,2,3,5,4};
auto[x, y] = std::accumulate( std::begin(foo), std::end(foo), std::make_pair(0, 0),
[m = std::map<int, int>()](auto const& old, int val)mutable{return (++m[val] > old.first) ? std::make_pair(m[val], val) : old;});
std::cout << "Count: " << x << " Value: " << y << "\n";
}


You will need C++17 to compile that auto[x, y] is a C++17 feature I believe.

Running here:

Note: This was fun. But if I catch you writing this in my code base I would fire you. :-) Stick to the slightly more verbose but readable version presented by @Quuxplusone

• lol. I wouldn't call that python-like. – Matthew James Briggs Mar 3 '17 at 9:49
• @MatthewJamesBriggs: Well the style is different in that C++ seporates out the container accesses and there is probably already an find max defined in pythons libraries: So python: container.accumulate(maxElement) becomes: accumulate(begin(container), end(container), maxElement) in C++. And C++ likes its long winded verbosity. – Martin York Mar 3 '17 at 16:48

## Use the required #includes

The code uses std::make_pair which means that it should #include <utility>. It was not difficult to infer, but it helps reviewers if the code is complete.

## Avoid spurious type conversions

There is no need to convert to and store strings if the array is actually of integers. Conversions such as those only add to time, complexity and storage, so if the goal is efficiency, you should seek to minimize them.

## Omit unused variables

Because argc and argv are unused, you could use the alternative form of main:

int main ()


## Don't use using unless it simplifies your code

The using std::cout; won't make any difference in the performance of the code or probably even any difference in the compiled result. However, in this case it's not ever used, so I'd recommend simply omitting it.

## Use C++ idioms

Rather than using find, this code could be considerably simplified by using operator[]. With a std::unordered_map, the behavior is to return the object that already exists or to insert a new one and return that. We can therefore simplify the code considerably:

std::unordered_map<int, int> dict;
int commonest;
int maxcount = 0;
for (int i: foo) {
if (++dict[i] > maxcount) {
commonest = i;
maxcount = dict[i];
}
}
std::cout << "The most frequent integer is " << commonest << "\n";


## Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

• When you know that ++dict[i] > maxcount, you also know that maxcount needs to be changed by exactly one. So you can increment (++maxcount) here, instead of reassign (maxcount = dict[i]). That may or may not help performance-wise. – moooeeeep Mar 3 '17 at 8:34
• How do you know that dict[i]  will be 0 for new elements? – avitevet Mar 4 '17 at 1:59
• @avitevet: It's how operator[] works. If the key doesn't already exist, its corresponding value is, for the case of a plain int, initialized to zero. – Edward Mar 4 '17 at 2:50

So one final remark, that wasn't said allready.

Currently you check every iteration whether the current value is the maximum. I would argue that this is highly inefficient for nearly all use cases.

In most cases one can assume, that numberOfAlternatives << numberOfElements. So it will be much more efficient, to split the accumulation of the histogram and the finding of the maximum into two loops.