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

  • C/C++
  • Thread starter burritoloco
  • Start date
  • #1
burritoloco
83
0
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.
 

Answers and Replies

  • #2
burritoloco
83
0


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?
 
  • #3
DavidSnider
Gold Member
510
146


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:
  • #4
rcgldr
Homework Helper
8,791
579


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.
 
  • #5
burritoloco
83
0
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).
 
  • #6
rcgldr
Homework Helper
8,791
579
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.
 

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

Replies
10
Views
332
Replies
10
Views
531
  • Last Post
Replies
9
Views
682
Replies
35
Views
1K
  • Last Post
Replies
34
Views
309
Replies
14
Views
282
Replies
1
Views
309
Top