Maps & character array

[warz]

When creating a map, such as..

Code Select Expand


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.

[tA-Kane]

A brief search on google reveals: http://www.sgi.com/tech/stl/Map.html

Code Select Expand

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

[SecretShop]

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).

[rabbit]

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.

[SecretShop]

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.