Using a STL map of function pointers

Question

Hello, I developed a scripting engine that has many builtin functions, so far to call any function code just went into a if .. else if .. else if wall checking the name but I would like to develop a more efficient solution.

Shoul I use a hashmap with strings as keys and pointers as values. How could I do it by using an STL map?

EDIT: Another point that came into my mind: of course using a map will force compiler not to inline functions but my unefficient approach didn't have any overhead generated by the necessity of function calls, it just executes code.

So I wonder if the overhead generated by the function call will be anyway better than having a if..else chain.. otherwise I could minimize the number of comparisons by checking a character at time (will be longer but faster).

Answer 1

Whatever your function signatures are:

typedef void (*ScriptFunction)(void); // function pointer type
typedef std::map<std::string, ScriptFunction> script_map;

// ...

void some_function(void)
{
}

// ...

script_map m;
m.insert(std::make_pair("blah", &some_function));

// ...

void call_script(const std::string& pFunction)
{
    script_map::const_iterator iter = m.find(pFuntion);
    if (iter == m.end())
    {
        // not found
    }

    (*iter)();
}

STL doesn't have a hash-map implementation. But you can use either TR1 or Boost to get unordered_map, which is your hash map.

Answer 2

Well, you can use any_map to store functions with different signatures (but calling it will be messy) and you can use int_map to call functions with a specific signature (looks nicer).

int FuncA()
{
    return 1;
}

float FuncB()
{
    return 2;
}


void main()
{
    // Int map
    map<string,int(*)()> int_map;
    int_map["A"] = FuncA;
    // Call it
    cout<<int_map["A"]()<<endl;

    // Add it to your map
    map<string, void(*)> any_map;
    any_map["A"] = FuncA;
    any_map["B"] = FuncB;

    // Call
    cout<<reinterpret_cast<float(*)()>(any_map["B"])()<<endl;
}

Answer 3

You can also use Boost.Function and Boost.Bind what even allows you, to some degree, to have map of heterogeneous functions:

typedef boost::function<void, void> fun_t;
typedef std::map<std::string, fun_t> funs_t;
funs_t f;

void foo() {}
void goo(std::string& p) {}
void bar(int& p) {}

f["foo"] = foo;
f["goo"] = boost::bind(goo, "I am goo");
f["bar"] = boost::bind(bar, int(17));

It can be a map of functions of compatible prototypes as well, of course.

Answer 4

Above answers seem to give a complete overview, this regards only your second question:

Map element retrieval by key has O(log n) complexity. Hashmap retrieval by key has O(1) complexity + a little stuff on the side in case of collisions. So if theres a good hash function for your function names, use it. Your implementation will have a standard one. It should be fine.

But be aware, that anything below a hundred elements will not benefit all too much.

The only downside of a hash map is collision. In your case, the hashmap will be relatively static. You know the function names you support. So I advise you to create a simple test case, where you call unordered_map<...>::hash_function with all your keys to make sure that nothing collides. After that, you can forget about it.

A quick google for potential improvements on hash functions got me there:

A fiew good hash functions

Maybe, depending on your naming conventions, you can improve on some aspects of the function.