When creating a map, such as..
map<key, mystruct> mymap;
how would you set the Key value to something that looks for character arrays? i'm trying to pass a string to my map without having to use the string class.
A brief search on google reveals: http://www.sgi.com/tech/stl/Map.html
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
int main()
{
map<const char*, int, ltstr> months;
months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
cout << "june -> " << months["june"] << endl;
map<const char*, int, ltstr>::iterator cur = months.find("june");
map<const char*, int, ltstr>::iterator prev = cur;
map<const char*, int, ltstr>::iterator next = cur;
++next;
--prev;
cout << "Previous (in alphabetical order) is " << (*prev).first << endl;
cout << "Next (in alphabetical order) is " << (*next).first << endl;
}
Id also considering using a hashtable instead of a map. A map uses a binary tree internally to search for the key you want and return the value. Correct me if im wrong but thats O(log(n)). A hashtable can calculate the offset of the value using the key so it only takes one operation to search, O(1).
That's theoretical, though. A hashtable with O(1) efficiency assumes the hash is perfect (IE: no collisions ever) which doesn't exist. Depending on the type of hash you use as the key, a hashtable can be extremely inefficient.
Quote from: rabbit on March 29, 2006, 04:42 PM
That's theoretical, though. A hashtable with O(1) efficiency assumes the hash is perfect (IE: no collisions ever) which doesn't exist. Depending on the type of hash you use as the key, a hashtable can be extremely inefficient.
Indeed, however with keys like this which are varied length and characters, along with a hash function designed for string use, a hashtable would probably be preferable to a binary tree search.