Iterate over the unique elements of `std :: multiset`

Question

All I need to do is know if something exists and how many times it exists. I will go over the existing things and ask how many of them exist.

My implementation still uses multiset , I do the following:

 std::multiset<thing> a; auto previous = a.end(); for( auto each = a.begin(); each != a.end(); ++each ) { if( previous == a.end() || *previous != *each ) { a.count(*each); } previous = each; } 

Explanation

I have a thing s vector. But sometimes they repeat the meaning, I want to iterate over a unique thing and do something for each unique one. This "something" should know the amount of time this thing appears on the vector.

The code I wrote above is how I solve my problem right now, this is not the most elegant way to do what I want.

I just follow the recommendations of Stackoverflow: I tell you what my problem is, and I tell my (tried) solution.

If a sentence with a question mark is really necessary, you go: is there a way to iterate over unique elements over multiset ?

Answer 1

Three possible approaches:

• Use std::unique to create a temporary set of unique values. This can make the code more understandable, but less efficient.
• Promote your iterator using std::multiset::upper_bound rather than increasing: for( auto each = a.begin(); each != a.end(); each=a.upper_bound(*each)) - this way you do not need if to check the insider contour, plus it is guaranteed to be logarithmic in size . Pretty cool (I didn’t know that before I watched it). For the next sentence, all credits relate to @MarkRansom : using std::upper_bound from <algorithm> , you can specify the range in which to search for the upper bound. In your case, you already have a good candidate for starting this range, so this method is likely to be more efficient, depending on the implementation in the standard library.
• If this is a real performance issue and the previous solution is still not enough, consider switching to map<thing, unsingned> or even unordered_map<thing,unsigned> , where unsigned just keeps track of how many equivalent thing you have. This involves rewriting your insert / delete code.