15

All I need is to know if something exists and how many times it exist. I will iterate over the existent things and query how much of that exists.

My implementation so far uses multiset, I do as follow:

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;
}

Clarifications

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

The code I posted above is how I am resolving my problem right now, it does not seems to be the most elegant way to do what I want.

I am just following the Stackoverflow guidelines: I tell what is my problem, and I tell my (tried) solution.

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

André Puel
  • 8,741
  • 9
  • 52
  • 83
  • 1
    **what** are you trying to do again? – Ivaylo Strandjev Feb 07 '13 at 13:15
  • 1
    Just use `.count` *only*? If it exists, you get back how many times. If not, you get back `0`. – Xeo Feb 07 '13 at 13:16
  • 1
    The problem with `.count` only surely is that you don't know what to call it on until you have iterated through the set. – us2012 Feb 07 '13 at 13:22
  • @ArmenTsirunyan What I want to know is described in the first paragraph. The others paragraphs show how I am doing that by now. – André Puel Feb 07 '13 at 13:37
  • Edited my question for clarifications, please re-read it – André Puel Feb 07 '13 at 13:42
  • 1
    There is a way requiring less code (create a temporary collection with `std::unique` and iterate through that), but it's certainly less efficient and only really saves one line! I don't think the STL provides a ready-made solution for your problem. – us2012 Feb 07 '13 at 14:03

2 Answers2

16

Three possible approaches:

  • Use std::unique to create a temporary collection of unique values. This might make the code a little more readable, but less efficient.
  • Advance your iterator by using std::multiset::upper_bound rather than increments: for( auto each = a.begin(); each != a.end(); each=a.upper_bound(*each)) - that way you don't need the if check insider your loop, plus it is guaranteed to be logarithmic in size. Pretty cool (didn't know that before I looked it up). For the following suggestion, all credit goes to @MarkRansom: Using std::upper_bound from <algorithm>, you can specify a range in which to look for the upper bound. In your case, you already have a good candidate for the start of that range, so this method is likely to be more efficient, depending on the implementation in your standard library.
  • If this is a real performance problem for you and the previous solution still isn't good enough, consider switching to map<thing, unsigned> or even unordered_map<thing,unsigned> where the unsigned just keeps track of the number of equivalent things you have. That implies rewriting your insertion/deletion code though.
rturrado
  • 7,699
  • 6
  • 42
  • 62
us2012
  • 16,083
  • 3
  • 46
  • 62
  • 1
    upper_bound is exactly what I was looking for. – André Puel Feb 07 '13 at 14:54
  • 4
    @AndréPuel if the average number of repeats in the `multiset` are expected to be small, the free form of `upper_bound` might be faster than the member function since you specify the start of the search. P.S. I think there's a typo, `*it` should be `*each`. – Mark Ransom Feb 07 '13 at 15:19
  • @MarkRansom Thanks, very helpful! I've edited my answer accordingly. – us2012 Feb 07 '13 at 15:37
  • AIUI `std::unique` can't be applied to a `std::multiset` though it is possible to simply iterate over the multiset into a set. – dranxo Feb 16 '18 at 21:07
0

Use equal_range (defined in multiset) in a while loop.

Mic
  • 810
  • 10
  • 15