Playing with Multimap

[crochunter]

Lets suppose I want to get only the first key value pair of each key.

I mean in refernce to the below example something like this:

Johnson, J. 12345
Smith, P. 54321

OR I want to print only the last values like this:-

Johnson, J. 10000
Smith, P. 60000

How can I do this ?
Here is what I have till now.

typedef multimap <char*, long, compare> MMap;
 
void main()
{
     MMap D;
     D.insert(MMap::value_type("Johnson,J.", 12345));
     D.insert(MMap::value_type("Smith,P.", 54321));
     D.insert(MMap::value_type("Johnson,J.", 10000));
     D.insert(MMap::value_type("Smith,P.", 20000));
     D.insert(MMap::value_type("Smith,P.", 60000));
 
     MMap::iterator ii;
     for(ii=D.begin(); ii!=D.end(); ii++)
     {
          cout<< (*ii).first<< " "<<
                     (*ii).second<<endl;
     }
     cout<<"There are "<<D.size()<<" elements.\n";
}
 

Output:
Johnson, J. 12345
Johnson, J. 10000
Smith, P. 54321
Smith, P. 20000
Smith, P. 60000
There are 5 elements.

Thanks

[Banfa]

I think I would say that you have chosen the wrong data type. You actually want a relationship between records with the same key, however multimap does not implement this, it just allows non-unique keys in the map but there is no implied relationship between items with the same key.

rather than multimap<char *, long> maybe you should consider something different such as map<char *, list<long> >. That is a map of unique keys where each key has a list of associated long values. Then it would be easy to extract the first long value for each key.

Just a thought, obviously I do not know your whole system design so I can't truely tell how suitable this approach is.

[Banfa]

By the way using you multimap as written you would have to iterate through the multimap and each time you print an entry first check to see if you have already printed an entry for that key and if not print the entry and temporarily store the key in a list of printed keys.

[weaknessforcats]

What you have to do is extract all of the pairs with the duplicate keys.

You do this using multimap::lower_bound and multimap::upper_bound.

multimap::lower_bound returns an iterator to the first pair with that key.
multimap::upper_bound returns an intrerator one beyond the last pair with that key.

Now you can run a loop using the two iterators in the same way that you use the begin and end iterators and pick out the correct record.

BTW, there is an equal_range algorithm that calls multimap::lower_bound and
multimap::upper_bound for you ans returns a pair where first is the iterator returned from multimap::lower_bound and second is the iterator returned from multimap::upper_bound.

I would ditch your code and start over.

[cowboyrocks2009]

Great :) good suggestions.

[crochunter]

Thanks guys :) I am very happy to get some guidance finally :) I discussed this problem with many people but unfortunately didn't get any replies.
I will start over again and post my codes for your cross checking..

Thanks

[crochunter]

Hi do you mean something like this :-

// multimap::count
#include <iostream>
#include <map>
using namespace std;
 
int main ()
{
  multimap<char,int> mymm;
  multimap<char,int>::iterator it;
  char c;
 
  mymm.insert(pair<char,int>('x',50));
  mymm.insert(pair<char,int>('y',100));
  mymm.insert(pair<char,int>('y',150));
  mymm.insert(pair<char,int>('y',200));
  mymm.insert(pair<char,int>('z',250));
  mymm.insert(pair<char,int>('z',300));
 
  for (c='x'; c<='z'; c++)
  {
    cout << "There are " << (int)mymm.count(c);
    cout << " elements with key " << c << ":";
    for (it=mymm.equal_range(c).first; it!=mymm.equal_range(c).second; ++it)
      cout << " " << (*it).second;
    cout << endl;
  }
 
  return 0;
}

I am working on this to enhance for my purpose.

The results come something like this :-

There are 1 elements with key x: 50
There are 3 elements with key y: 100 150 200
There are 2 elements with key z: 250 300

I can see some hope there I guess :)

Thanks

[crochunter]

Ok I am able to build a logic which does exactly how I wanted it to work but when I add more records there are some problems in flagging.

Here is and example:-
when my input is :

  mymm.insert(pair<char,int>('a',50));
  mymm.insert(pair<char,int>('b',100));
  mymm.insert(pair<char,int>('b',150));
  mymm.insert(pair<char,int>('b',200));
  mymm.insert(pair<char,int>('c',250));
  mymm.insert(pair<char,int>('c',300));
  mymm.insert(pair<char,int>('d',300));

output is correct :-

single      50
starterminal       100
middle       150
terminal       200
starterminal       250
terminal       300
single      300

But when I change my input like this:-

  mymm.insert(pair<char,int>('a',50));
  mymm.insert(pair<char,int>('b',100));
  mymm.insert(pair<char,int>('b',150));
  mymm.insert(pair<char,int>('b',200));
  mymm.insert(pair<char,int>('c',250));
  mymm.insert(pair<char,int>('c',300));
  mymm.insert(pair<char,int>('d',300));
  mymm.insert(pair<char,int>('e',250));
  mymm.insert(pair<char,int>('e',300));

The output is not correct:-

single      50
starterminal       100
middle       150
terminal       200
starterminal       250
terminal       300
single      300
terminal       250
terminal       300

Here is my code:-

// multimap::count
#include <iostream>
#include <map>
#include<vector>
using namespace std;
 
int main ()
{
  multimap<char,int> mymm;
  multimap<char,int>::iterator it;
  multimap<char, int>::const_iterator m1_cIter;
  char c;
 
  mymm.insert(pair<char,int>('a',50));
  mymm.insert(pair<char,int>('b',100));
  mymm.insert(pair<char,int>('b',150));
  mymm.insert(pair<char,int>('b',200));
  mymm.insert(pair<char,int>('c',250));
  mymm.insert(pair<char,int>('c',300));
  mymm.insert(pair<char,int>('d',300));
  mymm.insert(pair<char,int>('e',250));
  mymm.insert(pair<char,int>('e',300));
 
 
  int i = 0;
  int k = 0;
  for (c='a'; c<='z'; c++)
  {
    for (it=mymm.equal_range(c).first; it!=mymm.equal_range(c).second; ++it)
      if((int)mymm.count(c)>2){      
         if(i==0){
            cout << "start"<<"\t"<<(*it).second << endl;
         }    
         else if(i>0 && i < ( mymm.count(c) - 1)){
            cout << "middle"<<"\t"<<(*it).second << endl;
         }
         else {     
            cout << "terminal"<<"\t"<<(*it).second << endl;
         }
       i++;
      }
/////////////
      else if((int)mymm.count(c)==1){      
            cout << "single"<<"\t"<<(*it).second << endl;   
      }
/////////////
/////////////
      else if((int)mymm.count(c)==2){      
         if(k==0){
            cout << "start" << "\t"<< (*it).second << endl;
         }
         else {
            cout << "terminal" << "\t" << (*it).second << endl; 
         } 
         k++;
      }
////////////
  }
  return 0;
}

Can you point out the where I am making the mistake ?
One more thing if I change <char, int> to <string , string> will it work ? What changes do I need to make ?

  mymm.insert(pair<string,string>("a","50"));

Thanks and do reply :)

[Banfa]

The problem is your use of k and i, you would have a similar problem if you had a second group of 3 or more.

This is because you only ever initialise i and k once before the loop.

In fact use of k and i is, in my opinion, poor design. You would be much better off testing your iterator against the end conditions mymm.equal_range(c).first and mymm.equal_range(c).second. That would also allow you to reduce you loop complexity by reducing the program to 2 conditions inside the loop, 1 and more than 1 rather than 1, 2 and more than 2. Actually eliminating i or k and correctly initialising the other may allow a similar reduction.


And on a final but not directly related note this is definitely poor practice

for (c='a'; c<='z'; c++)

The problem is that while C and C++ does guarantee that '0' + 1 == '1' and '1' + 1 == '2' up to '8' + 1 == '9', i.e. does guarantee that if you add 1 onto a character representation of a digit that you get the next digit it does not guarantee that

'a' + 1 == 'b'

and in fact there are some platforms where you loop will not work because they use a run time character set where the letters are not contiguous.

You should avoid any code relying on 'a' + 1 == 'b' in production code especially if it has to be portable. You can easily get round it with a vector of char.