choosing the element with more duplicates on an array in plain C

Question

This question brings me back to my college days, but since I haven't coded since those days (more than 20 years ago) I am a bit rusty.

Basically I have an array of 256 elements. there might be 1 element on the array, 14 or 256. This array contains the usernames of people requesting data from the system. I am trying to count the duplicates on the list so I can give the priority to the user with most requests. So, if I have a list such as:

{john, john, paul, james, john, david, charles, charles, paul, john}

I would choose John because it appeared 4 times. I can iterate the array and copy the elements to another and start counting but it gets complicated after a while. As I said, I am very rusty.

I am sure there is an easy way to do this. Any ideas? Code would be very helpful here. Thank you!

EDIT:

The buffer is declared as:

static WCHAR userbuffer[150][128];

There could be up to 150 users and each username is up to 128 chars long.

Answer 1

Using std::map as proposed by AraK, you can stock your names without duplicates, and associate your names to a value.

A quick example :

std::map<string, long> names;

names["john"]++;
names["david"]++;

You can then search which key has the biggest value.

Answer 2

1 - sort your array.

2 - set maxcount = 0;

3 - iterate array and count until visitNEXT username.

4 - if count > maxcount then set maxcount to count and save name as a candidate.

5 - after loop finished, pickup the candidate.

Answer 3

What did you mean with "there might be 1 element on the array, 14 or 256". Are 14 and 256 element numbers?

If you can change the array definition I think the best way will be to define a structure with two fields, username and numberOfRequests. When a user requests, if usernames exists in the list the numberOfRequest will be increased. If it is the first time the user is requesting username should be added to list and numberOfRequests would be 1.

If you can not change the array definition, one is to sort the array with quick sort or another algorithm. It will be easy to count the number of request after that.

However, maybe there is a library with this functionality, but I doubt that you can find something in Standard Library!

Answer 4

Here's how I would solve it:

First, define a structure to hold user names and frequency counts and make an array of them with the same number of elements as your userbuffer array (150 in your example).

struct user {
    WCHAR   name[128];
    int     count;
} users[150];

Now, loop through userbuffer and for each entry, check and see if you have an entry in users that has the same name. If you find a match, increment the count for that entry in users. If you don't find a match, copy the user's name from userbuffer into a blank entry in users and set that user's count to 1.

After you have processed the entire userbuffer array, you can use the count values from your users array to see who has the most requests. You can either iterate through it manually to find the max or use qsort.

It's not the most efficient algorithm, but it's direct and doesn't do anything too clever or fancy.

Edit: To qsort the users array, you will need to define a simple function that qsort can use to sort by. For this example, something like this should work:

static int compare_users(const void *p1, const void *p2) {
    struct user *u1 = (struct user*)p1;
    struct user *u2 = (struct user*)p2;

    if (u1->count > u2->count)
        return 1;
    if (u1->count < u2->count)
        return -1;
    return 0;
}

Now, you can pass this function to qsort like:

qsort(users, 150, sizeof(struct user), compare_users);