Is There an Iterator Across Unique Keys in a Std::Multimap

is there an iterator across unique keys in a std::multimap?

You can use upper_bound to increment the iterator position instead of ++:

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
  multimap<int,string> mm;
  mm.insert(make_pair(1, "a"));
  mm.insert(make_pair(1, "lemon"));
  mm.insert(make_pair(2, "peacock"));
  mm.insert(make_pair(3, "angel"));

  for( auto it = mm.begin(), end = mm.end();
       it != end;
       it = mm.upper_bound(it->first)
  )
    cout << it->first << ' ' << it->second << endl;
  return 0;
}

This results in:

1 a
2 peacock
3 angel

How can I get all the unique keys in a multimap

I tried this and it worked

for(  multimap<char,int>::iterator it = mymm.begin(), end = mymm.end(); it != end; it = mymm.upper_bound(it->first))
  {
      cout << it->first << ' ' << it->second << endl;
  }

how to iterate multimap backwards for unique key?

A std::multimap::iterator is not directly convertible to a std::reverse_iterator. You need to make the result of std::lower_bound the base iterator of it:

typedef ... multimap_type;
typedef std::reverse_iterator<multimap_type::iterator> reverse_iterator;

for (auto it = mmap.rbegin(),
          end = mmap.rend();
     it != end;
     it = reverse_iterator(mmap.lower_bound(it->first)))
{
  // ...
}

The expression reverse_iterator(mmap.lower_bound(it->first)) will construct a std::reverse_iterator with the result of lower_bound as its base iterator.

How do I determine if a particular key is unique in a multimap?

Could you check if the std::multimap::count(key) == 1?

Skip same multimap values when iterating

You could change inverts into map<string,set<string>>, mapping each word to the set of file names where it appears.

Is There a way to Find the Number of Keys in a multimap Inline?

1^st, multimap doesn't contain a key count naively. So your question then is about how to use something from the algorithm library to find the count. The 2 constraints you have placed that preclude everything in the library are:

1. Must be used inline, so a count, not an iterator must be returned
2. Must perform at least as well as upper_bound used in a lambda, which has time complexity: O(log n)

1 leaves us with: count, count_if, for_each, as well as most of the algorithms in the numeric library

2 eliminates consideration of all of these as each of them has time complexity: O(n)

As such your getKeyCount is preferable to any other option that the standard supplies.

---

Just a comment about another option that may be presented: the maintenance of keyCount whenever something is added or removed from foo, this may seem workable, but it requires a check before each insert if the inserted key exists, and a check after each removal if the removed key still exists. Aside from this, there is also the consideration of the danger of multi-threaded inoperability and the loss of code readability, where it's not clear that this keyCount must be maintained along with foo. Ultimately this a bad idea unless the key count is taken significantly more frequently than foo is updated.

boost unordered_multimap loop over the unique keys

What you want to do is find a way to get the iterator following a certain key. In multimap I'd usually use upper_bound. But since unordered_multimap doesn't have that - I'll have to use equal_range.second:

for (auto iter=valueMap.begin();
     iter!=valueMap.end();
     iter=ValueMap.equal_range(iter->first)->second){
  uniq_key=iter->first;
  // Do whatever you want with uniq_key
}

But your example is weird to me - because you DO go over all the element . If I wanted to write your code, doing what you do, this is how I'd do it:

for (auto iter=valueMap.begin()
     iter!=valueMap.end();
     ){ // Notice the lack of ++iter!!!
  auto end=valueMap.equal_range(ier->first)->second;
  for (;iter!=end;++iter)
    // Do something
}

---

Related Topics