Finding mode in an array of strings

[Thomas_25]

If i have an array of names char *names[100]; (stored as pointers to strings), how to find the name that appears the most times in the array and how many times it appears.

(a) if only one “mode”
(b) multiple “modes”

I'm thinking of implementing something similar to selection sort where each element will be compared to every other element in the array and use a counter to keep track of the duplicates. If i use this technique, i need a counter for each element in the array and i think that's not a smart technique.

There should be a better way to do this. Please give some insights. Thanks

[rubberman]

1. Sort the array (qsort works well for this).
2. Iterate through the sorted array and keep the pointer and incremented count in a separate array (one entry for each string). When the string changes, add the new one to the counter array with a count of 1 and then increment for each copy until a new string is encountered.

You will end up with a sorted array of strings, with the count of instances found for each. You can do this without sorting the original array, but then you will have to look up each element in the counter array which is much more expensive time-wise than sorting the original array in the first place, especially if it is quite big.

[tinstaafl]

Another way is with a map<string,int>. Accessing an index that isn't present automatically adds it. So that a simple single iteration through the names will give you a count for each unique name:

map<string, int> mapNames;
for (auto n : names)
{
    mapNames[*(n)]++;
}

Now in each element of mapNames, the key is a unique name and it's value is how times that name is present.

[David W]

@tinstaafl, I aways appreciate your insights, and was wondering about the syntax of using ...

'auto'

in C++ 11

with the 'map' container ...

(and in the context of the OP, I was pleasently surprised to see that C++ 11 'knows' the size of arrays.)

This is the syntax that I found to work ok:

// map_test.cpp //

// compile with C++11 or newer compiler ... //

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>


int main()
{
    using std::cout; using std::string; using std::setw;
    using std::vector; using std::map;

    vector< string > names =
    { "sam", "peter", "joe", "joe", "peter" };

    map< string, int > mapNames;

    for( auto &n : names ) ++ mapNames[n]  ;



    cout << "COUNT, NAME\n";

    for( auto &n : mapNames )
        cout << setw(5) << n.second << ", " << n.first << '\n';



    cout << "\nNow doing an other way, traversing the same names ...\n\n";

    const char* names2[] = { "sam", "peter", "joe", "joe", "peter" };

    for( auto n : names2 ) ++ mapNames[n] ;

    for( auto &n : mapNames )
        cout << setw(5) << n.second << ", " << n.first << '\n';
}

[tinstaafl]

Sorry about that, I mistakenly tested the code with

string*names[100]

instead of

 char*names[100]

The correct code is here:

map<string, int> mapNames;
for (auto n : names)
{
    mapNames[n]++;
}

[Thomas_25]

Thanks Everyone

[tinstaafl]

Please remember to mark the post solved if your question is answered Thank You