🔒 Locked

Question about std::map/std::hash_map

Started by Flimflam Oct 28, 2005 at 4:09 AM 10 replies 1k views

Original Post

Oct 28, 2005 at 4:09 AM

Greetings, I have a problem that's been bugging me for quite a while. I'm working on a small game project that uses Lua as a scripting language to interface with the engine itself. Anyway, I have a function written in lua to access some "CVar's" I've setup, such as the resolution, bit depth, etc, like so: GetCVar("screenResolution"); -- this calls a C function, that accesses the map and gets the value, then sends it back to the lua script. As I was saying, I can't quite figure out how to make std::map work like I want it to. Maybe I just can't use it like this, but I'd like to know for sure. This is a small example I've written to illistrate my problem:

#include <iostream>
#include <map>

// value and length, not used in full yet
typedef struct _val {
   char value[128];
   int length;
} val;

// test class to hold map/iterator I use
class cmap {
   public:
      std::map<const char *, val> m_Values;
      std::map<const char *, val>::iterator m_it;
};

// class 
cmap maps;

int main(int argc, char *argv[]) {
   // copy some names
   val vals1, vals2;
   strcpy(vals1.value, "Flimflam");
   strcpy(vals2.value, "Deathwing");

   // add these to the map
   maps.m_Values["characterName"] = vals1;
   maps.m_Values["realmName"] = vals2;
   
   // begin loop to query data
   std::string str;
   while(true) {
      printf("Name: ");
      std::cin >> str;
      if(str == "q") break;

      // uncomment to directly reference realmName. this WORKS
      // maps.m_it = maps.m_Values.find("realmName");

      // use the input as the value to find. Does NOT work
      maps.m_it = maps.m_Values.find(str.c_str());
      
      // print results to the query
      printf(" Results: %s\n\n", (*maps.m_it).second.value);
   }
   
   return 0;
}

Toward the end you can see the problem, I can't use anything other than directly quoted strings as a key. Is there anything I can do to get passed this? Thanks in advance. Edit: To clerify; I do not intend on using std::string for the final code, that was just used to quicker illustrate the problem, and I intend on using a hash map eventially, as I hear they're faster in terms of lookup, etc.

snk_kid

Oct 28, 2005 at 4:26 AM

Quote:
Original post by Flimflam
// uncomment to directly reference realmName. this WORKS      // maps.m_it = maps.m_Values.find("realmName");// use the input as the value to find. Does NOT workmaps.m_it = maps.m_Values.find(str.c_str());
Toward the end you can see the problem, I can't use anything other than directly quoted strings as a key. Is there anything I can do to get passed this?

The reason why it doesn't work is you are using std::map with the default comparator std::less which just uses the relational less than operator and since your using pointers as keys you are only comparing addresses. In this case you need to give std::map a custom predicate to make that work i.e.

#include <cstring>#include <map>struct ltstr {  bool operator()(const char* s1, const char* s2) const {      return strcmp(s1, s2) < 0;  }};typedef  map<const char*, val, ltstr> my_map;

Any type can be a key so long as it has some means of comparison for which there are various methods, overloading the relational less than operator, a free-function, a bound pointer to member function, functors. The comparator must impose a strict weak ordering of elements.

Quote:
Original post by Flimflam
Edit: To clerify; I do not intend on using std::string for the final code

Well why not? You wouldn't have add this problem in first place if you used it as a key type since std::basic_string has overloaded the relational less than operator. If you only need immutable strings as keys then you might be better off with const char* but to be used a key you need a custom predicate for it.

dalleboy

Oct 28, 2005 at 4:27 AM

Quote:
Original post by Flimflam
Edit: To clerify; I do not intend on using std::string for the final code, that was just used to quicker illustrate the problem, and I intend on using a hash map eventially, as I hear they're faster in terms of lookup, etc.

Well, you should use std::string in the final code, as it would fix all your problems.

class cmap {   public:      std::map<std::string, val> m_Values;      std::map<std::string, val>::iterator m_it;};

Or you could specify a predicate to use in std::map:

class MyPred {   public:      bool operator(const char *lhs, const char *rhs) const      {         return strcmp(lhs, rhs) < 0;      }};class cmap {   public:      std::map<const char *, val, MyPred> m_Values;      std::map<const char *, val, MyPred>::iterator m_it;};

Enigma

Oct 28, 2005 at 4:29 AM

Your problem is that your map is using std::less< char const * > to do it's comparisons, which is just comparing pointer values, not lexographically comparing c-strings. You need to provide a comparison functor that works with c-strings:

struct cstringless	:	public std::binary_function< char const *, char const *, bool >{	bool operator()(char const * lhs, char const * rhs)	{		return std::strcmp(lhs, rhs) < 0;	}};std::map< char const *, val, cstringless > values;

Quote:
Original Post by Flimflam
Edit: To clerify; I do not intend on using std::string for the final code, that was just used to quicker illustrate the problem

Why not?

Quote:
and I intend on using a hash map eventially, as I hear they're faster in terms of lookup, etc.

Note that the standard hashing containers are named unordered_map and unordered_set (and probably muti versions too). A hashing container may not actually be faster depending on the size of the dataset and your hashing function. Also a balanced binary tree has more consistent overhead (verses ocassional slow rehashes of a hashing container).

Enigma

Flimflam

Oct 28, 2005 at 4:33 AM

Thanks everyone, that fixed it. :)

To clerify my statement about not using std::string, I suppose it's due to a lot of friends and other acquaintances of mine who talk about performance of the class itself, and memory use. To be honest, I've never personally done any checks myself for the performance, but I'm looking for the best performance possible given the rendering and such I'm going to be doing, adding on the load of running lua scripts constantly, and given that, people would tell me that's a nono. I'd rather use a string class, to be honest with you. hehe.

Can anyone tell me if I will really see a performance issue with using std::string?

Nitage

Oct 28, 2005 at 4:33 AM

Use a std::map instead of a std::map

When the map compares 2 const char*s it is comparing the address the pointer points to - not the contents of the string.

EDIT: I need to reply faster

Enigma

Oct 28, 2005 at 4:44 AM

Quote:
Original post by Flimflam
To clerify my statement about not using std::string, I suppose it's due to a lot of friends and other acquaintances of mine who talk about performance of the class itself, and memory use. To be honest, I've never personally done any checks myself for the performance, but I'm looking for the best performance possible given the rendering and such I'm going to be doing, adding on the load of running lua scripts constantly, and given that, people would tell me that's a nono. I'd rather use a string class, to be honest with you. hehe.

Can anyone tell me if I will really see a performance issue with using std::string?

Yes, you likely will see a performance issue. Your performance will likely INCREASE if you use std::string. Here's a link to a benchmark I posted a previous time somebody suggested that manually messing around with raw c-strings would be faster: linky (not entirely accurate, since he was using a class wrapping a c-string that tracked length).

EDIT: Just to point out that this only applies if you are dynamically adding and/or removing entries to/from the map at runtime. If you just setup the map at startup time and only perform lookups subsequently then c-strings may be faster than std::string, but only fractionally. In this case my previous comment about balanced binary trees having more consistent overhead than hashing containers also ceases to apply since there is no rehashing after the container is filled.

Enigma

Flimflam

Oct 28, 2005 at 4:54 AM

Quote:
Original post by Enigma
Quote:
Original post by Flimflam
To clerify my statement about not using std::string, I suppose it's due to a lot of friends and other acquaintances of mine who talk about performance of the class itself, and memory use. To be honest, I've never personally done any checks myself for the performance, but I'm looking for the best performance possible given the rendering and such I'm going to be doing, adding on the load of running lua scripts constantly, and given that, people would tell me that's a nono. I'd rather use a string class, to be honest with you. hehe.

Can anyone tell me if I will really see a performance issue with using std::string?

Yes, you likely will see a performance issue. Your performance will likely INCREASE if you use std::string. Here's a link to a benchmark I posted a previous time somebody suggested that manually messing around with raw c-strings would be faster: linky (not entirely accurate, since he was using a class wrapping a c-string that tracked length).

Enigma

Oh now that's interesting... Would you say std::string is good in general or only good in various situations? I appologise for my most likely dumb questions, but to be honest with you, I haven't used a lot of the STL library before.

Also, recently I changed my version of STL (the one that came standard with visual studio .net 2003) to the stlport release. Will I likely see any differences between the .net std::string and the stlport version?

Enigma

Oct 28, 2005 at 4:59 AM

In general use std::string by default. If a profiler proves it's a bottleneck, no algorithmic optimisation is possible and it looks like a candidate for c-strings (i.e. const strings, no/few operations that must check the length of the string) then consider using c-strings.

Enigma

Flimflam

Oct 28, 2005 at 5:23 AM

Thank you very much :)

snk_kid

Oct 28, 2005 at 5:26 AM

Quote:
Original post by Flimflam
... I suppose it's due to a lot of friends and other acquaintances of mine who talk about performance of the class itself, and memory use.

Ah no wonder you've been speaking to those mediocre, self-proclaimed C++ programmers who don't know more about C++ than C with (plain vanilla) classes, the C++ community has moved on alot from a ~10-15 year old inferior technique on it's own.

They will randomly tell you things like "STL is slow" with either nothing to back up there claims or have a pathetic attempt with a pathetic example on a pathetic, inferior C++ compiler that is nearly 10 years old (like VC++ 6.0) where C++ had only just been ISO standardized. The only thing they have shown is how mediocre they really are.

Don't worry you get that often here and else where 98% of there talking rubbish, like when you mentioned memory usage all the standard library containers (including std::basic_string) are parameterized by allocator type so you can use custom memory models/schemes like pooling, using the stack instead of the heap etc.

Oct 29, 2005 at 5:22 AM

A good rule is to think about strategically optimizing code. Don't write fast code all the time from instinct. That's inefficient human wise. To tell the truth, STL is pretty damn hard to beat. One greatest benefit of stl is the disappearance of pointers and memory handling. Those two are major sources of bugs in code. The optimal would be to use garbage collection especially for system gdi stuff.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.