Thread: STL multimaps / searching

I've just bought an STL tutorial book, and going though it has been lots of fun, but I have some questions that I haven't been able to answer with the book or researching on the net. I've created a simple program to illustrate.

Notes on the code. There are two multimaps so I can look up by phone numbers or by names, they are multimaps, becuase two or more people can have the same phone number and there can be multiple people with the same name.

My Questions: (finally) How can I find all elements in the multimap that have the same key? ie) I can find the first person with phone num 771-2323 like this:

Code:

multimap<unsigned long, string>::iterator it = numbers_map.find(7712323);

Or the listing for the first "Julie":

Code:

multimap<string, unsigned long>::iterator it2 = names_map.find("Julie");

But how can I find all the listings for "Julie" or all the listings for 771-2323?
Also, how can I search the multimap to find part of a key ie) to find all the phone numbers that begin with 771-2*, or find the listings for all that contain "Alex" (Alex, Alexander, Alexandria...)

I really appreciate your help, also if you have suggestions of other STL containers or any other ways of doing this I would be most grateful. I have already searched the web & this site extensively (already been to sgi's STL ref.) but any other links would be helpful too. Thanks.

Code:

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

using namespace std;

int main()
{

  // set up the mock telephone directory
  multimap <unsigned long, string> numbers_map; // for searching by number
  multimap <string, unsigned long> names_map;   // for searching by name

  // people and their phone numbers to add to the directory
  string names[] = {"John", "Angela", "Juanita", "Alex", "Alexander", "Juan", "Julie", "Julie"};
  unsigned long nums[] = {7712323, 7715874, 7712323, 7714730, 7710386, 7714444, 7718051, 7714895};

  // add names and numbers to the two directories.
  // (one indexed by the name, and the other by the phone number)
  for(int i=0; i<8; ++i)
    numbers_map.insert(pair<unsigned long, string>(nums[i], names[i]));
  for(i=0; i<8; ++i)
    names_map.insert(pair<string, unsigned long>(names[i], nums[i]));

  // output all ordered by Phone number
  for (multimap<unsigned long, string>::iterator num_it = numbers_map.begin(); num_it != numbers_map.end(); ++num_it)
    cout << "Phone number: " << (*num_it).first << " Name: " << (*num_it).second << "\n";
  cout << "==================================\n";

  // output all ordered by Name
  for (multimap<string, unsigned long>::iterator name_it = names_map.begin(); name_it != names_map.end(); ++name_it)
    cout << "Name: " << (*name_it).first << " Phone number: " << (*name_it).second << "\n";
  cout << "==================================\n";

  cin.get();
  return 0;
}

Output:
Phone number: 7710386 Name: Alexander
Phone number: 7712323 Name: John
Phone number: 7712323 Name: Juanita
Phone number: 7714444 Name: Juan
Phone number: 7714730 Name: Alex
Phone number: 7714895 Name: Julie
Phone number: 7715874 Name: Angela
Phone number: 7718051 Name: Julie
==================================
Name: Alex Phone number: 7714730
Name: Alexander Phone number: 7710386
Name: Angela Phone number: 7715874
Name: John Phone number: 7712323
Name: Juan Phone number: 7714444
Name: Juanita Phone number: 7712323
Name: Julie Phone number: 7718051
Name: Julie Phone number: 7714895
==================================

I see a ray of hope with multimap's member functions lower_bound upper_bound and equal_range for finding multiple elements with the same key. I am still looking for some ideas on how to search through the key or value to be able to search the multimap for a key or value that contains the string I'm searching for. golfinguy4 - Sure, the phone number can be a string, I guess what I'm asking is how I can implement this. Having a hard time finding documentation. Thanks.

Thank you both for your replies. I looked at the dinkumware site and I like their reference material- quite comprehensive. As far as your code jlou, I should have come back here sooner- I worked out a similar answer with equal_range. But thank you again.

I'll post the code I have now, it's a little longer, I added some typedef's and a couple of functions to do some searching.

Questions:
1. Is it safe to assume that equal_range will always return the first element in the map if the value is less than the first element?
2. With equal_range it will be posible to do a search for say "Alex", and find "Alex" and "Alexander" but if I do a search for "Ale" it returns nothing because there is no entry for "Ale" Also, how can I search for say *ia* to find all the names that contain "ia" in the middle?

Thanks for any help. In the meantime I will keep searching/trying.
[edit]
I hope I don't have to walk through each element of the multimap doing a strstr() with the key to look for matches. Wouldn't that kill the performance advantages of a map?
[/edit]

Code:

#include <map>
#include <list>
#include <string>
#include <iostream>
//#include <algorithm>

using namespace std;

// for case insensitive ordering of the multimap
struct lessStrNoCase{
  bool operator() (const string s1, const string s2) const {
    return stricmp(s1.c_str(), s2.c_str()) < 0;
  }
};

typedef multimap <unsigned long, string>                NumberNameMap;
typedef multimap <string, unsigned long, lessStrNoCase> NameNumberMap;
typedef pair <unsigned long, string>                    NumberNamePair;
typedef pair <string, unsigned long>                    NameNumberPair;
typedef NumberNameMap::iterator                         NumberNameMapIt;
typedef NameNumberMap::iterator                         NameNumberMapIt;
typedef list<NumberNameMapIt>                           NumberNameMapItList;
typedef list<NameNumberMapIt>                           NameNumberMapItList;

// functions to search in the multimaps Return lists of iterators to the multimaps
NumberNameMapItList FindByNumber(NumberNameMap* nmap, unsigned long num);
NameNumberMapItList FindByName(NameNumberMap* nmap, string name);

int main()
{

  // set up the mock telephone directory
  NumberNameMap numbers_map; // for searching by number
  NameNumberMap names_map;   // for searching by name

  // people and their phone numbers to add to the directory
  string names[] = {"John", "angela", "Juanita", "Alex", "Alexander", 
                    "Juan", "Julie", "Julie", "Juanito", "Daniel",
                    "Mary", "Mary", "Mary", "Brian", "Earl",
                    "Nate", "Nathan", "James", "Bryan", "Bing",
                    "Hiram", "Lizbeth", "Dietrich", "Anna", "Scott"};
  unsigned long nums[] = {7712323, 7715874, 7712323, 7714730, 7710386, 
                          7751654, 7852145, 7854125, 7759987, 7714804,
                          2782326, 2789854, 2785076, 2787451, 7714007,
                          7719874, 7751696, 2785176, 2785176, 2785176,
                          7714444, 7758888, 7718051, 7714895, 7712323};
  const int NUMENTRIES = 25;
  // add names and numbers to the two directories.
  // (one indexed by the name, and the other by the phone number)
  for(int i=0; i<NUMENTRIES; ++i)
    numbers_map.insert(NumberNamePair(nums[i], names[i]));
  for(i=0; i<NUMENTRIES; ++i)
    names_map.insert(NameNumberPair(names[i], nums[i]));

  // output all ordered by Phone number
  cout << "==================================\n";
  for (NumberNameMapIt num_it = numbers_map.begin(); num_it != numbers_map.end(); ++num_it)
    cout << "Phone number: " << (*num_it).first << " Name: " << (*num_it).second << "\n";
  cout << "==================================\n";

  // output all ordered by Name
  for (NameNumberMapIt name_it = names_map.begin(); name_it != names_map.end(); ++name_it)
    cout << "Name: " << (*name_it).first << "\t\tPhone number: " << (*name_it).second << "\n";
  cout << "==================================\n";

  // output a search by number
  unsigned long some_number = 2785176;
  NumberNameMapItList ll = FindByNumber(&numbers_map, some_number);
  if( ll.empty() ){
    cout << "No matches for " << some_number << "\n";
  }else{
    cout << "There were " << ll.size() << " matches for " << some_number << ", here they are:\n";
    for(; !ll.empty(); ll.pop_front() )
      cout << ll.front()->first << " " << ll.front()->second << endl;
  }
  cout << "==================================\n";
  
  // output a search by name
  string some_name = "Julie";
  NameNumberMapItList thelist = FindByName(&names_map, some_name);
  if( thelist.empty() ){
    cout << "No matches for " << some_name << "\n";
  }else{
    cout << "There were " << thelist.size() << " matches for " << some_name << ", here they are:\n";
    for(; !thelist.empty(); thelist.pop_back() )
      cout << thelist.back()->first << " " << thelist.back()->second << endl;
  }
  cout << "==================================\n";

  return 0;
}

NumberNameMapItList FindByNumber(NumberNameMap* nmap, unsigned long num)
{
  NumberNameMapItList nnmil;
  pair<NumberNameMapIt, NumberNameMapIt> range;
  for( range = nmap->equal_range( num ); 
       range.first != range.second && range.first != nmap->end(); 
       ++range.first ){
    nnmil.push_back( range.first );
    //cerr << "range.first " << range.first->first << " " << range.first->second << endl;
  }
  return nnmil;
}

NameNumberMapItList FindByName(NameNumberMap* nmap, string name)
{
  NameNumberMapItList nnmil;
  pair<NameNumberMapIt, NameNumberMapIt> range;
  for( range = nmap->equal_range( name ); 
       range.first != range.second && range.first != nmap->end(); 
       ++range.first ){
    nnmil.push_back( range.first );
    //cerr << "range.first " << range.first->first << " " << range.first->second << endl;
  }
  return nnmil;
}

output:
==================================
Phone number: 2782326 Name: Mary
Phone number: 2785076 Name: Mary
Phone number: 2785176 Name: James
Phone number: 2785176 Name: Bryan
Phone number: 2785176 Name: Bing
Phone number: 2787451 Name: Brian
Phone number: 2789854 Name: Mary
Phone number: 7710386 Name: Alexander
Phone number: 7712323 Name: John
Phone number: 7712323 Name: Juanita
Phone number: 7712323 Name: Scott
Phone number: 7714007 Name: Earl
Phone number: 7714444 Name: Hiram
Phone number: 7714730 Name: Alex
Phone number: 7714804 Name: Daniel
Phone number: 7714895 Name: Anna
Phone number: 7715874 Name: angela
Phone number: 7718051 Name: Dietrich
Phone number: 7719874 Name: Nate
Phone number: 7751654 Name: Juan
Phone number: 7751696 Name: Nathan
Phone number: 7758888 Name: Lizbeth
Phone number: 7759987 Name: Juanito
Phone number: 7852145 Name: Julie
Phone number: 7854125 Name: Julie
==================================
Name: Alex Phone number: 7714730
Name: Alexander Phone number: 7710386
Name: angela Phone number: 7715874
Name: Anna Phone number: 7714895
Name: Bing Phone number: 2785176
Name: Brian Phone number: 2787451
Name: Bryan Phone number: 2785176
Name: Daniel Phone number: 7714804
Name: Dietrich Phone number: 7718051
Name: Earl Phone number: 7714007
Name: Hiram Phone number: 7714444
Name: James Phone number: 2785176
Name: John Phone number: 7712323
Name: Juan Phone number: 7751654
Name: Juanita Phone number: 7712323
Name: Juanito Phone number: 7759987
Name: Julie Phone number: 7852145
Name: Julie Phone number: 7854125
Name: Lizbeth Phone number: 7758888
Name: Mary Phone number: 2782326
Name: Mary Phone number: 2789854
Name: Mary Phone number: 2785076
Name: Nate Phone number: 7719874
Name: Nathan Phone number: 7751696
Name: Scott Phone number: 7712323
==================================
There were 3 matches for 2785176, here they are:
2785176 James
2785176 Bryan
2785176 Bing
==================================
There were 2 matches for Julie, here they are:
Julie 7854125
Julie 7852145
==================================

Well I have changed the Search by name function to walk through every element in the map and search each individual name. I still think there has got to be a better way, maybe some kind of complicated indexing system (I'm still thinking) jlou, your idea of using algorithms instead of loops is great I will be looking into how to do that shortly.

I still welcome all your ideas on how to make this kind of searching more efficient.... I'm afraid that if there were 100,000 entries in the map, the search would noticeable slow. Actually I'm going to test that.

Here's my current FindByName function:

Code:

NameNumberMapItList FindByName(NameNumberMap* nmap, string name)
{
  NameNumberMapItList nnmil;
  pair<NameNumberMapIt, NameNumberMapIt> range;
  // This will search for only an exact match
  //for( range = nmap->equal_range( name ); 
     //  range.first != range.second && range.first != nmap->end();
     //  ++range.first ){
  //  nnmil.push_back( range.first );
  //}

  // This will search for the query in any part of the name
  NameNumberMapIt it;
  for( it = nmap->begin(); it != nmap->end(); ++it ){
    if( it->first.find( name ) != string::npos ){
      nnmil.push_back( it );
    }
  }

  return nnmil;
}