C++ predicting majority of string array elegantly

Question

I have an array of 5 strings and I want to be able to compare the strings to each other to find out if there is a majority, and return that majority. So if:

a[0] = "dog";
a[1] = "dog";
a[2] = "dog";
a[3] = "dog";
a[4] = "cat";

I want to return "dog." In cases like 2 same, 2 same, and one, I want it to return "no majority". Is there a way to do this without a tremendous amount of if statements, in other words elegantly?

Are there _always_ 5 strings or do you plan on this some day processing more than those 5? — stefan, Mar 02 '14 at 17:52

score 4 · Answer 1 · answered Mar 02 '14 at 17:48

4

You could use a dictionary:

std::unordered_map<std::string, unsigned int> historgram;
std::string most_popular;
unsigned int m = 0;
bool unique = false;

for (s : a)
{
    unsigned int & i = histogram[s];
    ++i; 
    if (i == m) { unique = false; }
    else if (i > m) { unique = true; m = i; most_popular = s; }
}

return unique ? most_popular : "no majority"'

answered Mar 02 '14 at 17:48

Kerrek SB

464,522
92
875
1,084

what is the condition of the for loop? – user3371287 Mar 02 '14 at 18:03
@user3371287, It's a range-based for loop. There is no explicit condition. – chris Mar 02 '14 at 18:04

score 2 · Answer 2 · answered Mar 02 '14 at 17:47

2

Put them in a hash table where the key is the word and the value the number of occurences. As you place them in the hash table check for the max count.

Not only you avoid the ifs, but (most important) it works whatever the length of the array is.

answered Mar 02 '14 at 17:47

Nicolas Defranoux

2,646
1
10
13

score 1 · Answer 3 · answered Mar 02 '14 at 17:49

A simple method is to have a std::map<std::string, int> which maps each string to its frequency in the array.

for (auto str : a) {
  frequencies[str]++;
}

You can then either search through the map afterwards for the highest frequency, or you can keep track of the maximum so far during the loop above.

C++ predicting majority of string array elegantly

3 Answers3