STL multimaps / searching

This is a discussion on STL multimaps / searching within the C++ Programming forums, part of the General Programming Boards category; I've just bought an STL tutorial book, and going though it has been lots of fun, but I have some ...

  1. #1
    Registered User
    Join Date
    Dec 2002
    Posts
    119

    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
    ==================================
    If you speak or are learning Spanish, check out this Spanish and English Dictionary, it is a handy online resource.
    What happens is not as important as how you react to what happens. -Thaddeus Golas

  2. #2
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    Well, 771 isn't really a "part" of 771233. Since they are not strings, one really isn't a part of the other.

    Anyways, you could implement it yourself quite easily using integer division and the accompanying truncation. However, it would be a lot easier if you used a string to store the id, for you could implement your search and use the STL functions to search each individual string.

  3. #3
    Registered User
    Join Date
    Dec 2002
    Posts
    119
    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.
    If you speak or are learning Spanish, check out this Spanish and English Dictionary, it is a handy online resource.
    What happens is not as important as how you react to what happens. -Thaddeus Golas

  4. #4
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    You're going to have to create your own. Very simple though.

    Here's a little semi-pseudo code:
    Code:
    for(iterator=MyMap.begin(); iterator!=MyMap.end(); iterator++)
         iterator->Key_string.find(whatever)
    This method will allow you to make your search a lot more expansive as you can search for the simple occurrence of any pattern.

    BTW, for documentation... www.dinkumware.com is God.

  5. #5
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    You have the right idea with equal_range. Hopefully you will have figured it out on your own before you read this, but if you are stuck here is an example that can be placed into your program that uses equal_range:
    Code:
      // output names with 7712323 Phone number
      pair<multimap<unsigned long, string>::iterator, multimap<unsigned long, string>::iterator> num_it_pair = numbers_map.equal_range(7712323);
      for (multimap<unsigned long, string>::iterator find_num_it = num_it_pair.first; find_num_it != num_it_pair.second; ++find_num_it)
        cout << "Phone number: " << (*find_num_it).first << " Name: " << (*find_num_it).second << "\n";
      cout << "==================================\n";
    
      // output Phone number for "Julie" 
      pair<multimap<string, unsigned long>::iterator, multimap<string, unsigned long>::iterator> name_it_pair = names_map.equal_range("Julie");
      for (multimap<string, unsigned long>::iterator find_name_it = name_it_pair.first; find_name_it != name_it_pair.second; ++find_name_it)
        cout << "Name: " << (*find_name_it).first << " Phone number: " << (*find_name_it).second << "\n";
      cout << "==================================\n";
    And as far as finding a partial match like "Alex", you can just search for Alex using lower_bound assuming "Alex" comes before "Alex***" in the string's less than function (which I think is true by default). Then, you loop through until the end of the map or until the current name doesn't start with "Alex". This works even if "Alex" is not in the multimap because lower_bound returns the spot right where "Alex" would be inserted if you were to add it -- that means just before any keys that have "Alex***". The same goes for phone numbers - search for 7712000, which is guaranteed to be less than all numbers starting with 771-2*.

  6. #6
    Registered User
    Join Date
    Dec 2002
    Posts
    119
    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
    ==================================
    Last edited by Codulation; 01-03-2004 at 04:28 AM.
    If you speak or are learning Spanish, check out this Spanish and English Dictionary, it is a handy online resource.
    What happens is not as important as how you react to what happens. -Thaddeus Golas

  7. #7
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Your code looks pretty good.
    Originally posted by Codulation
    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"
    This assumption is incorrect (to my recollection), which is why it doesn't work for "Ale". The equal_range function only returns exact matches. You want the lower_bound and the upper_bound. See this example (using your old code):
    Code:
      // output Phone number for "7714*" 
      multimap<unsigned long, string>::iterator num_lower_it = numbers_map.lower_bound(7714000);
      multimap<unsigned long, string>::iterator num_upper_it = numbers_map.upper_bound(7714999);
      for (multimap<unsigned long, string>::iterator multi_num_it = num_lower_it; multi_num_it != num_upper_it; ++multi_num_it)
        cout << "Phone number: " << (*multi_num_it).first << " Name: " << (*multi_num_it).second << "\n";
      cout << "==================================\n";
    
      // output Phone number for "Alex*" 
      multimap<string, unsigned long>::iterator name_lower_it = names_map.lower_bound("Alex");
      multimap<string, unsigned long>::iterator name_upper_it = names_map.upper_bound("Aley");
      for (multimap<string, unsigned long>::iterator multi_name_it = name_lower_it; multi_name_it != name_upper_it; ++multi_name_it)
        cout << "Name: " << (*multi_name_it).first << " Phone number: " << (*multi_name_it).second << "\n";
      cout << "==================================\n";
    The first one works because there is a specific upper and lower limit for the phone number. You'll have to work a little harder for the name, since using "Alex" as the lower bound and "Aley" as the upper bound will include anybody named "Aley", which you don't want. It just requires an extra check in the loop to fix, I'm sure you can figure out some way to do it.
    Originally posted by Codulation
    Also, how can I search for say *ia* to find all the names that contain "ia" in the middle?
    This is a little harder. I can only think of a way to do it using an algorithm, since names with *ai* can be anywhere in the map. There are lots of good algorithms available to work with depending on what you want to do. I don't have my books with me now, but maybe later for fun I'll play with it and see if I can come up with something that works for that. I'd suggest buying a book - Effective STL by Scott Meyers might be useful and can be bought for $30-$40. Of course The C++ Standard Library by Josuttis is also very good (but a bit more expensive) if you want to invest in books that will help you take full advantage of the STL.
    Originally posted by Codulation
    [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]
    The performance advantage of a map or multimap is that the items are sorted as you put them in. If you want to find a pattern like *ai* in the middle of the string, then there is no other way to do it because you cannot sort the names in such a way that all nams with "ai" somewhere in the name are placed together. So yes, you will have to loop through all the elements in the map. I wouldn't recommend strstr (the find() function in string should suffice), and as I said before and algorithm could be used to easily do this search in one or two lines. It could even be used to copy the results to a list like you are already doing. In fact, just for fun, I'm going to try to change your two FindBy* functions to use an algorithm instead of a simple loop.

    ::Goes away for 20 minutes::

    Never mind, I'll need my books. The back_inserter isn't working inside the copy. Anyway, that was fun for me. Hope the info helps you a little.

  8. #8
    Registered User
    Join Date
    Dec 2002
    Posts
    119
    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;
    }
    If you speak or are learning Spanish, check out this Spanish and English Dictionary, it is a handy online resource.
    What happens is not as important as how you react to what happens. -Thaddeus Golas

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 06:20 AM
  2. C++ std routines
    By siavoshkc in forum C++ Programming
    Replies: 33
    Last Post: 07-28-2006, 01:13 AM
  3. Visual C++ 2005 linking and file sizes
    By Rune Hunter in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2005, 10:41 PM
  4. stl - searching for elements in containers
    By Raven Arkadon in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2005, 11:10 AM
  5. Searching STL Map Inside STL Map Object :: C++
    By kuphryn in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2002, 09:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21