How to iterate/count for a multimap<string,string>

Question

My class is like this:

class Outgoing
{
    multimap<string,string> outgoing;

    public:
    void makeConnection(string key, string value)
    {
        outgoing.insert(pair<string,string>(key,value));
    }

    void iterate()
    {
        multimap<string, string>::iterator it;
        multimap<string, string>::iterator it2;
        pair<multimap<string,string>::iterator,multimap<string,string>::iterator> ret;
        for (it = outgoing.begin();it != outgoing.end();++it)
        {
            ret = outgoing.equal_range((*it));  ??????
            for (it2=ret.first; it2!=ret.second; ++it2)
            {
                ???????

             }
        }
    }
};

background:

I want to represent a graph which can have many nodes. The key won't repeat but can have multiple values.

str1  ----> val1
str1  ----> val2
str2 -----> val3

I want to know how can I get number of values for a particular key? for e.g. in the above question , for str1 it will be 2?

As you can see , I tried to do something after some digging around but in vain.

What is wrong with my code?

thanks

EDIT ::: after templatetypedef's comment, I edited the code to:

for (it = outgoing.begin();it != outgoing.end();++it)
{
    cout<< (*it).first << " "<<  outgoing.count((*it).first); 

}

I can get the count, but the key("str1") comes twice. So the answer I see is 2 2 1.

I would appreciate it very much, if somebody teaches me how to iterate in such a way I get only one key. BTW, thanks, templatetypedef

Solution 1

You can use the count function for this, which returns the number of entries in the multimap with the the given key. In your example, writing

outgoing.count("str1")

would produce the value 2.

In C++, there is no way to iterate over just the unique keys in a multimap. If you want to iterate over just those keys, there are two options you might want to consider:

1. You could change from using a multimap< string, string > to map<string, vector<string> >. That way, each key is unique, and you can easily determine how many values are associated with each key by just looking at the number of elements in the corresponding vector.

2. You could have a top-level loop to iterate over all keys, then have an inner loop to skip duplicate keys.

As an example of option 2, you might try something like this:

for (multimap<string, string>::iterator itr = myMap.begin(); itr != myMap.end(); ) {
    /* ... process *itr ... */

    /* Now, go skip to the first entry with a new key. */
    multimap<string, string>::iterator curr = itr;
    while (itr != myMap.end() && itr->first == curr->first)
        ++itr;
}

Hope this helps!

Solution 2

The function equal_range provides a pair of iterators, with the first and last elements of the map thar share a certain key.

http://www.cplusplus.com/reference/map/multimap/equal_range/

// multimap::equal_range
#include <iostream>
#include <map>

int main ()
{
  std::multimap<char,int> mymm;

  mymm.insert(std::pair<char,int>('a',10));
  mymm.insert(std::pair<char,int>('b',20));
  mymm.insert(std::pair<char,int>('b',30));
  mymm.insert(std::pair<char,int>('b',40));
  mymm.insert(std::pair<char,int>('c',50));
  mymm.insert(std::pair<char,int>('c',60));
  mymm.insert(std::pair<char,int>('d',60));

  std::cout << "mymm contains:\n";
  for (char ch='a'; ch<='d'; ch++)
  {
    std::pair <std::multimap<char,int>::iterator, std::multimap<char,int>::iterator> ret;
    ret = mymm.equal_range(ch);
    std::cout << ch << " =>";
    for (std::multimap<char,int>::iterator it=ret.first; it!=ret.second; ++it)
      std::cout << ' ' << it->second;
    std::cout << '\n';
  }

  return 0;
}

Comments

[Sam]

Quick question, why'd you rollback an edit that removed "fluff"?

[templatetypedef]

@Sam I have a habit of concluding all my answers with "Hope this helps!", so I figured I'd go for consistency. :-)

[MiniScalope]

maybe you should use upper_bound() inside the for loop declaration; instead of looping yourself