[C++?] Counting the maximum number of equal objects in a vector

[burritoloco]

Hi, say I have a vector that is currently being populated with some objects. I would like, as each object is added to the vector, to count the maximum number of equal objects currently in the vector. Would you know of any efficient algorithm that does this? Thank you.

 

[burritoloco]

I'm guessing that perhaps continuous sorting (after defining a comparison relation on the objects) as the objects are added, and then counting the equalities could be a way to do this. Probably would take about O(n^2) at worst (n is the total number of objects to be added). Is there another way?

 

[DavidSnider]

Use a hashmap\dictionary. As you add the item to the vector check the dictionary and if the item exists increment the value otherwise add it with a value of 1.

 

[rcgldr]

As an alternative to a hash algorithm, depending on the number of bits in each object, you could use the object's value as an index into a very large array, and increment the array for each object. The overhead would be the time it takes to zero out the array to initialize it, and when done, to scan the array for non-zero values.

 

[burritoloco]

Thanks guys. The hashmap idea looks straightforward. rcgldr, I can define a function to convert these objects into longs (to be used as indices of an array as you suggested), but this would additional time, no? Is there a native c++ way to do this conversion? (the usual type casting doesn't work here).

 

[rcgldr]

The hashmap idea looks straightforward. rcgldr, I can define a function to convert these objects into longs (to be used as indices of an array as you suggested), but this would additional time?

Yes, and assuming you mean 32 bit longs, it would take too much memory, the array size would be 4 billion elements. Using values as indexes is a software alternative to a content addressable (also called associative) memory. A hashmap does the same thing but uses much less space (assuming only a small sub-set of possible values are used). The hash table will have "collisions", and generally you'd want the hash table to end up about 1/2 empty to reduce collision overhead.

You could use assembly code to do a fast search of an array for a value, using repne scas... for 8 (scasb), 16 (scasw), 32 (scasd), or 64 (scasq) bit values, either inline or as a separate module.