I want to create something using a stl::map, except I want it to give me the value when I provide it with three keys.

Specifically, the idea is to create a collection of bitmaps that are pre-rendered strings of text, and I want the stl::map to return the bitmap, given 3 search factors:
1. the font name (as a string)
2. the font size (as a signed int)
3. the string of text that has been rendered

something like map<BITMAP*, string_key, int_key, string_key> text_render_bin.

If this isn't possible, I would probably do something like create a struct with two of the keys and the BITMAP*, put the third key in a map, then find() the key in the container, and just loop through all them until the right one is found. But that doesn't seem like the best way to do it.

I'm wondering, is a more efficient way to do it using a map or something else? Is it possible to create a 3-key map, or an n-key map?

1) Create structure containing members for font name, size and string
2) Add comparison operators and a hash function to it
3) std::hash_map<infostruct, BITMAP*>

Also you've consistently put the BITMAP* in with the keys twice in your post, when it's actually the value you want to look up. Make sure you understand how maps work.

You can also hack it up by using a string representation of the font properties. Though a proper wraper class is probably better.

I second what Thomas said (if I got it right), putting all your data (font name, font size, text) in a string and leaving the hashing to stl::map will be easier.

That if you are going to handle a bunch of strings, if we're talking about several hundreds of them maybe an ad hoc structure will probably be more efficient.

std::map is not a hashing container.

(It's generally implemented as a red-black tree, but implementation details aside it can't be implemented as a hash map anyway because of the ordering constraint.)

a comparison operator for two structs? would an operand== suffice?

struct text_render_info
{
   const char *font_filename;
   const char *text;
   int font_size;
};
bool operator==(const &text_render_info, const &text_render_info) const
{
    return (strcmp(info1.text, info2.text) == 0
     && strcmp(info1.font_filename, info2.font_filename) == 0
     && info1.font_size == info2.font_size);
}

How do I create the hash function? In the example it looks like all I have to do is pass hash<text_render_info> in my declaration.

"Operand" means one of the arguments to an operator. Yes, the equality operator is all you need.

Like it says on the documentation page, one of the template arguments to the hash map is a hash function. Write one, pass it.

I thought it was the less-than (<) operator you needed for std::map, since the key lookup uses a binary search?

I don't know how to do this. A hash function converts the data struct into an index? How is this any different from Thomas' suggestion putting everything into a single string index?

I've coded this last year when I found out C++ lacked Hash structures.

There you have a base. But it can only store (void *) so you'll have to cast your pointers

EDIT: Sorry for giving no explanation.
Basically, you use HashString class and push_back() elements with a string identifier and void *. The you use the get function with the string identifier.

For std::map, yes. But not std::hash_map, which X-G was referring to.

You can use boost::tuple to create the 3-item container:

   std::map<boost::tuple<BITMAP*, std::string, int>, std::string> table;

   table[boost::make_tuple(my_bitmap, "Courrier New", 5)] = "some string";

Hope this helps.

When using hash_map:

When using unordered_map:

C++ is a beautiful language.

I like this, but it doesn't like the tuple argument when assigning it to a map.

#include "boost/tuple/tuple.hpp"
#include "boost/tuple/tuple_comparison.hpp"

class text_render_bin
{
public:
  map<boost::tuple<string, int, string>, ALLEGRO_BITMAP*> table;
  table[boost::make_tuple("string", 12, "my_bitmap")] = al_get_target_bitmap(); //<-- errors here
};

errors:

1>------ Build started: Project: game framework 01, Configuration: Debug Win32 ------
1>  main.cpp
1>c:\users\mark\documents\visual studio 2010\projects\game framework 01\game framework 01\text_render_manager.h(84): error C2057: expected constant expression
1>c:\users\mark\documents\visual studio 2010\projects\game framework 01\game framework 01\text_render_manager.h(84): error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>c:\users\mark\documents\visual studio 2010\projects\game framework 01\game framework 01\text_render_manager.h(84): error C2864: 'text_render_bin::table' : only static const integral data members can be initialized within a class
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

[edit] I'm retarded.

ok, it looks like that works so far!

Switching from a map to an unordered_map took my top secret C++ program down from processing 1.1M records in 2+ minutes to 44 seconds.

Not bad considering the same program took PHP over five hours.

I should probably take a look at boost one of these days. Looks like it makes for even better job security.

1. The hash is a 32/64-bit integer as opposed to a string and is thus much faster to deal with than a string.
2. Thomas suggested using a map, which does a binary search, which is thus slower than a hash table lookup. You can do it if you like, but in that case I'd recommand having the struct and implementing the < operator instead.

Never had that problem. But I try to use stlport whenever possible.

Is he ready for the awesome magic of boost? Can he contain the power?

... that's in the middle of the declaration. Statements go in functions. Forgotten your elementary C++?

Only because thats what the code was using.

In this case, I would probably use a hash_map, or unordered_map (which is what its called now?), since it lends itself very well to the kind of data you're trying to store. That and you really don't need the ordering constraint, all it does is slow you down.

A hash map looks up the integer hash first, which is very fast: An integer comparison typically executes in a single clock tick, and requires no branching except the final decision (greater / less / equal). A string comparison, OTOH, requires a loop that compares on each iteration, and typically finishes at relatively unpredictable indices. So instead of doing a binary search on the string keys (or worse), you do a binary search on the faster integer keys. Once you have found your match by hash, you may have to search through a few entries if your hash collides, but with a good hash function, the chances for such a collision are relatively low (with the perfect hash function, the chances for any two hashes to collide would be 1 : 2³² for 32-bit hashes).
The challenge is to write a hash function that balances hashing speed (the time required to create a hash) against entropy (the probability of a collision).