Thread: 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;
}

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;
    }
}

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?

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.

Originally Posted by EVOEx

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 .

Originally Posted by laserlight

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

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?"

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

Originally Posted by laserlight

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

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 ?

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;

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.

tanx alot dears