Thread: searching vector using maps

  1. #1
    Registered User
    Join Date
    Sep 2014
    Location
    sacramento, CA
    Posts
    6

    searching vector using maps

    Currently im creating a simple phone directory. I am having a problem when searching the vector. It only lets me search for the exact key in the directory when I need to to search for strings that are close to the name. For example when I search "car" it will state that its not in the directory when it should pull up Carr, Derek and Carr David. Please help Thank you.
    Code:
    #include <string>
    #include <map>
    #include <vector>
    #include <ostream>
    #include <iostream>
    
    int main()
    {
    std::map<std::string, std::vector <std::string> > directory;
    
    directory["Carr"].push_back("Derek 916-667-6761");
    directory["Carr"].push_back("David 916-667-6766");
    directory["Mcfadden"].push_back("Darren 510-667-0000");
    directory["Streater"].push_back("Rod 510-667-0001");
    directory["Jones"].push_back("James 510-667-0020");
    directory["Mack"].push_back("Khalil 707-557-6700");
    directory["Woodson"].push_back("Charles 707-557-0061");
    directory["Tuck"].push_back("Justin 707-557-6001");
    directory["Moore"].push_back("Sio 415-600-5551");
    directory["Roach"].push_back("Nick 415-600-4461");
    directory["Woodson"].push_back("Rod 415-600-4441");
    
    std::string str;
    int yesno;
    std::cout <<"Would you like to search a name in the phone directory?(yes=1, no=0)" <<std::endl;
    std::cin>>yesno;
    while (yesno==1)
    {
        std::cout << "Enter name you would like to find: ";
        std::cin >> str;
    
        std::map<std::string, std::vector <std::string> >::iterator p;
    
        p = directory.find(str);
        if(p != directory.end())
        {
          std::string key = p->first;
          std::vector<std::string> names = p->second;
    
          for (int i = 0; i < names.size(); ++i)
             std::cout << key << " " << names[i] << std::endl;
    
        }
        else
        {
            std::cout << "Name not in phone directory.\n";
        }
       std::cout <<"Do you have another name you would like to look up?(yes=1, no=0)"<<std::endl;
       std::cin>>yesno;
       }
       system("pause");
       return 0;
      }

  2. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Can't you just use a multimap instead?

  3. #3
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    Quote Originally Posted by MutantJohn View Post
    Can't you just use a multimap instead?
    You need multimap to have multiple mappings for Carr.

    I think mutimap::find needs the spelling of the key to be exact, so that won't help you.

    Instead, you can iterate through each element of the multimap and do p->first.find(str), this use the string::find to determine if str is a substring of first. that will match every word with the word car in there: car, carr, carrie etc. Btw, case matters.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Instead of iterating over the list to test if a key is identical to the search term, you need to test if the key is "simmilar" to the search term, and return the top N rated entires. Then look up those entries to get the details. You just need a function to evaluate how similar two strings are on a scale.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You may want to use find_if for the algorithm.

    >> std::map<std::string, std::vector <std::string> >::iterator p;
    >> p = directory.find(str);
    Can be simplified to
    auto p = directory.find(str);
    if your compiler supports C++11. You may also want to look up lambdas in case you are unfamiliar with them. Again, this requires a C++11 compliant compiler.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Why not search the map using lower_bound? I'm assuming that given search string XXX you want to match all XXX* (for example, "car" matches "carr", "carson" and "car" but not "casper" or "caproom"), right? In other words, "xxx" finds ["xxx","xxy").

    If so, lower_bound would work. I was able to make a couple small changes to your program that uses a map<string, vector<string>> and get proper results. The key hint is in the ["xxx","xxy") notation. Because strings can be sorted, you can identify which ones belong to that set if you can identify those endpoints.

    Finally, you may get better success if you use names like Willis, Smith and Kaepernick in your sample data.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Perhaps
    Code:
    class fuzzyString {
      std::string s;
    public:
      // overload operator == to be fuzzy
    };
    
    ...
    
    std::map<fuzzyString, std::vector <std::string> > directory;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Salem View Post
    Perhaps
    Code:
    class fuzzyString {
      std::string s;
    public:
      // overload operator == to be fuzzy
    };
    
    ...
    
    std::map<fuzzyString, std::vector <std::string> > directory;
    That could run into problems when a string is similar to two others, which aren't themselves similar to each other. For example, scar and carr are both similar to car, but not so similar to each other. You can try to work around it, but then you're effectively back to iterating over the whole list.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Vincent Dotts
    I am having a problem when searching the vector. It only lets me search for the exact key in the directory when I need to to search for strings that are close to the name. For example when I search "car" it will state that its not in the directory when it should pull up Carr, Derek and Carr David.
    Maybe a trie would be more appropriate? Unfortunately, the C++ standard library does not provide such a container.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Wait, have we suggested just writing a custom key comparator?

    Code:
    template<
        class Key,
        class T,
        class Compare = std::less<Key>,
        class Allocator = std::allocator<std::pair<const Key, T> >
    > class multimap;
    You just have to write the Compare class to use something not std::less<Key>.

    I just double-checked and std::multimap::find uses the internal comparator defined in the multimap's declaration.

    Will this work?

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MutantJohn
    You just have to write the Compare class to use something not std::less<Key>.
    Yes, but what? The replacement must have the same "less than" semantics that is used when inserting into the container. In this case, the search is based on some prefix that is only known at run time after the elements have been inserted into the container. This is why a trie sounds like a possibly good match to me, but Daved's idea in post #6 of using lower_bound (with a std::map) should also work.

    A multimap seems impractical to me, unless the idea is to get rid of the vector and directly map strings to strings: you would need to store a mapping for each possible search prefix.
    Last edited by laserlight; 09-20-2014 at 01:29 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    My idea did imply ditching the use of a vector.

    You are right about the idea of a false equivalency. Hmm... I thought about it earlier and assuming your input is good (i.e. no two keys contain substrings of each other) then the algorithm would work.

    It might be easiest to ditch the STL and make a truly custom class.

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by MutantJohn View Post
    It might be easiest to ditch the STL and make a truly custom class.
    Don't regress to being a C developer now!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Elysia View Post
    Don't regress to being a C developer now!
    The STL is not a silver bullet. And even if we assume that no container will do the job, you can retrofit a class to work with standard algos and the like.

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Or you can take advantage of other stuff in STL so as to not make everything from scratch. find_if might work. Other suggestions might work. So you could use them instead of re-inventing from scratch. Use existing solutions.
    Of course it's not a silver bullet, but sometimes you can piece things together from several solutions when there is no single solution. Reuse existing, tested code.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-10-2014, 11:07 AM
  2. Iterating through a vector of maps and a map of vectors...
    By alaa_137 in forum C++ Programming
    Replies: 7
    Last Post: 08-18-2012, 08:46 AM
  3. Searching for an int in a vector
    By go_loco in forum C++ Programming
    Replies: 14
    Last Post: 04-22-2010, 06:11 PM
  4. searching an element of a vector
    By strickey in forum C++ Programming
    Replies: 4
    Last Post: 02-15-2005, 08:29 AM
  5. Searching the contents of a vector
    By Sparkle1984 in forum C++ Programming
    Replies: 4
    Last Post: 10-16-2003, 07:14 AM

Tags for this Thread