a question about mapping

This is a discussion on a question about mapping within the C++ Programming forums, part of the General Programming Boards category; hello, how is it possible to search a string in a mapped array? eg consider the following example : how ...

  1. #1
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493

    a question about mapping

    hello, how is it possible to search a string in a mapped array? eg consider the following example : how is it possible to search specific string in the following codes?
    //how to search for example label in the maped array ? and how to retrieve its line number?
    Code:
    #include <iostream>
    #include <map>
    using namespace std;
    
    int main ()
    {
      map<int,string> mymap;
      map<int,string>::iterator it;
      int line=0;
     char *label="Start"; 
    mymap[line+1]=label;
      mymap[line]="another element";
      mymap[line+2]=mymap['b'];
    
      cout << "mymap['line '] is " << mymap[line+1] << endl;
      cout << "mymap[line+1] is " << mymap[line] << endl;
      cout << "mymap[line+2] is " << mymap[line+2] << endl;
      cout << "mymap['d'] is " << mymap[line+3] << endl;
    
      cout << "mymap now contains " << (int) mymap.size() << " elements." << endl;
    
    //search??
    //how to search for example label in the maped array ? and how to retrieve its line number?
    
      return 0;
    }
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by Masterx
    how is it possible to search a string in a mapped array?
    Yes, but it is slow since you would be performing a linear search, e.g.,
    Code:
    #include <iostream>
    #include <map>
    #include <string>
    #include <algorithm>
    
    template<typename K, typename V>
    class MatchSecond
    {
    public:
        MatchSecond(const V& value) : value(value) {}
    
        bool operator()(const std::pair<K,V>& element) const
        {
            return element.second == value;
        }
    private:
        V value;
    };
    
    using namespace std;
    
    int main()
    {
        map<int,string> mymap;
        mymap[2] = "hello";
        mymap[3] = "world";
        mymap[5] = "today";
    
        // Search for "world" in mymap.
        map<int,string>::iterator iter = find_if(mymap.begin(), mymap.end(), MatchSecond<int,string>("world"));
        if (iter != mymap.end())
        {
            cout << "'world' is at " << iter->first << endl;
        }
        else
        {
            cout << "'world' could not be found" << endl;
        }
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    tanx laserlight , but isnt it there any other way to search in a mapped array ? or any equivalence to mapped array ? i mean can i achive the same task using sth else ? (saving a string with an integer just like mapped aray using sth else so that we are not bound to used linear search?
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    If you want faster than linear search of the mapped_type, then create another map that mirrors this one, but in the opposite direction (or use a container from Boost that does this for you).

    Actually, if the line numbers are contiguous, then you probably should just map strings to line numbers instead of line numbers to strings, in which case finding a line number of a given string can use the map's find() member function, which takes logarithmic time.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by laserlight View Post
    Actually, if the line numbers are contiguous, then you probably should just map strings to line numbers instead of line numbers to strings, in which case finding a line number of a given string can use the map's find() member function, which takes logarithmic time.
    That would work if one would search for an entire line. If this is like an editor, where people would have to search for one word or set of characters somewhere in the middle of a line, that won't work. But if you have no information of what is to be searched, there is no better algorithm than O(n+m). And the usual implementation is even O(n*m). Where n is the length of the text and m is the length of the searched string (See the KMP algorithm).

    So, Masterx, do you have any information on what is going to be searched? Full lines, or just words in it?

  6. #6
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by EVOEx View Post
    That would work if one would search for an entire line. If this is like an editor, where people would have to search for one word or set of characters somewhere in the middle of a line, that won't work. But if you have no information of what is to be searched, there is no better algorithm than O(n+m). And the usual implementation is even O(n*m). Where n is the length of the text and m is the length of the searched string (See the KMP algorithm).

    So, Masterx, do you have any information on what is going to be searched? Full lines, or just words in it?
    Dear EvoEx tanx and to answer your question : i should say both of them will be searched! with this requirement that whichever is being searched it should return its adjusting counter part meaning if i search line 5 , it should return string "STart" if we have [5]="STart";as an example and vice versa .
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  7. #7
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by laserlight View Post
    If you want faster than linear search of the mapped_type, then create another map that mirrors this one, but in the opposite direction (or use a container from Boost that does this for you).

    Actually, if the line numbers are contiguous, then you probably should just map strings to line numbers instead of line numbers to strings, in which case finding a line number of a given string can use the map's find() member function, which takes logarithmic time.
    tanx dear Laserlight , but i have no background knowledge about boost libraries , just heard sth saying thats a rich library for C++ programmers. would you please guide me with the container name or how it is doable using BOOST ?

    tanx
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by Masterx
    Dear EvoEx tanx and to answer your question : i should say both of them will be searched!
    Note that by "KMP" EVOEx probably means "Knuth-Morris-Pratt", i.e., an algorithm for matching substrings within strings. On the other hand, I assumed that you were matching entire strings within some container. With this in mind answer EVOEx's question again: "So, Masterx, do you have any information on what is going to be searched? Full lines, or just words in it?"

    Quote Originally Posted by Masterx
    i have no background knowledge about boost libraries , just heard sth saying thats a rich library for C++ programmers. would you please guide me with the container name or how it is doable using BOOST ?
    Boost bimap
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by laserlight View Post
    Note that by "KMP" EVOEx probably means "Knuth-Morris-Pratt", i.e., an algorithm for matching substrings within strings. On the other hand, I assumed that you were matching entire strings within some container. With this in mind answer EVOEx's question again: "So, Masterx, do you have any information on what is going to be searched? Full lines, or just words in it?"


    Boost bimap
    tanx for explanation , its just word
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  10. #10
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    by the way can any one tell me how to access one specific element in a mapped array ? eg the example i gave you is it possible that i use a loop to access the elements of the array ? by a simple for () statement ?
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  11. #11
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    You mean this?
    Code:
    map<type1, type2>::iterator it;
    map<type1, type2> mymap;
    for (it = mymap.begin(); it != mymyap.end(); ++it)
    {
        (*it).first;               // the key value
        (*it).second;            // the mapped value)
    }
    Codeform is cool
    Code:
    map<type1, type2>::iterator it;
    map<type1, type2> mymap;
    for (it = mymap.begin(); it != mymyap.end(); ++it)
    {
        (*it).first;               // the key value
        (*it).second;            // the mapped value)
    }

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by Masterx
    by the way can any one tell me how to access one specific element in a mapped array ?
    I gave you an example in post #2, where the element that is found has its key printed:
    Code:
    cout << "'world' is at " << iter->first << endl;
    Quote Originally Posted by Masterx
    eg the example i gave you is it possible that i use a loop to access the elements of the array ? by a simple for () statement ?
    Instead of explicitly using a for loop I used a standard generic algorithm. C_ntua gave an example using an explicit for loop, but note that we typically write (*it).first as it->first, and (*it).second as it->second.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    tanx alot dears
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  2. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  4. Question about linked lists.
    By cheeisme123 in forum C++ Programming
    Replies: 6
    Last Post: 02-25-2003, 12:36 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

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