Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 21, 2012 #1
    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.
     
  2. jcsd
  3. Sep 21, 2012 #2
    Re: Counting the maximum number of equal objects in a vector

    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?
     
  4. Sep 21, 2012 #3

    DavidSnider

    User Avatar
    Gold Member

    Re: Counting the maximum number of equal objects in a vector

    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.
     
    Last edited: Sep 21, 2012
  5. Sep 22, 2012 #4

    rcgldr

    User Avatar
    Homework Helper

    Re: Counting the maximum number of equal objects in a vector

    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.
     
  6. Sep 22, 2012 #5
    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).
     
  7. Sep 22, 2012 #6

    rcgldr

    User Avatar
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook