By Jack


2010-01-26 01:26:33 8 Comments

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

Should 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 the compiler not to inline functions, but my inefficient 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 any better than having an if..else chain.. otherwise I could minimize the number of comparisons by checking a character at runtime (will be longer but faster).

7 comments

@Ia Rigby 2019-02-04 21:57:37

I've managed to modify the example from Mohit to work on member function pointers:

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <typeinfo>
#include <typeindex>
#include <cassert>


template <typename A>
using voidFunctionType = void (A::*)(void);

template <typename A>
struct Interface{

    std::map<std::string,std::pair<voidFunctionType<A>,std::type_index>> m1;

    template<typename T>
    void insert(std::string s1, T f1){
        auto tt = std::type_index(typeid(f1));
        m1.insert(std::make_pair(s1,
                        std::make_pair((voidFunctionType<A>)f1,tt)));
    }

    template<typename T,typename... Args>
    T searchAndCall(A a, std::string s1, Args&&... args){
        auto mapIter = m1.find(s1);
        auto mapVal = mapIter->second;  

        auto typeCastedFun = (T(A::*)(Args ...))(mapVal.first); 

        assert(mapVal.second == std::type_index(typeid(typeCastedFun)));
        return (a.*typeCastedFun)(std::forward<Args>(args)...);
    }
};

class someclass {
    public:
        void fun1(void);
        int fun2();
        int fun3(int a);
        std::vector<int> fun4();
};

void someclass::fun1(void){
    std::cout<<"inside fun1\n";
}

int someclass::fun2(){
    std::cout<<"inside fun2\n";
    return 2;
}

int someclass::fun3(int a){
    std::cout<<"inside fun3\n";
    return a;
}

std::vector<int> someclass::fun4(){
    std::cout<<"inside fun4\n";
    std::vector<int> v(4,100);
    return v;
}

int main(){
    Interface<someclass> a1;
    a1.insert("fun3",&someclass::fun3);
     someclass s;
    int retVal = a1.searchAndCall<int>(s, "fun3", 3);
    return 0;
}

@Jacob 2010-01-26 01:39:50

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


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

@Ben J 2012-10-17 15:38:47

Actually, I find this very useful. You can basically write your own functions that wrap up the reinterpreting (i.e. float my_b(){ return reinterpret.....}.

@LB-- 2013-10-01 18:48:32

Did you really just write void main in a C++ program?

@Jacob 2013-10-01 22:03:56

@LB--: Why don't you edit it? Oh wait .. 140 rep.

@GManNickG 2010-01-26 01:30:03

Whatever your function signatures are:

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

// ...

void some_function()
{
}

// ...

script_map m;
m.emplace("blah", &some_function);

// ...

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

    (*iter->second)();
}

Note that the ScriptFunction type could be generalized to std::function</* whatever*/> so you can support any callable thing, not just exactly function pointers.

@sth 2010-01-26 01:41:01

Also there really is no need to use a real hash table like unordered_map. There won't be that many elements that a hash table would bring performance advantages, I even wouldn't be surprised if map were faster in this case.

@GManNickG 2010-01-26 01:46:07

Actually, I've done some similar stuff and unordered_map was much faster. I had only about 10,000 things in it, and I profiled both map and unordered_map.

@peterchen 2010-01-26 08:35:39

I'd expect "many builtin functions" << 10.000. Hasmap in the OP's case has the clear advantage of being "true O(1)" since it doesn't have to grow, and a collision-free hash could be constructed for the strings. I doubt that it makes a significant difference compared to a map for even a few 100 items.

@Jack 2010-01-26 14:19:13

Actually "many builtin functions" is like ~100. Of course they can grow with time but undoubtely they'll reach 1000. I'll try with the map. Also because I didn't use Boost so far and I would avoid that (just because I really finished everything apart from some optimizations).

@Ben Farmer 2014-05-07 03:30:09

Does this actually work? Don't you still need to retrieve the function pointer out of the map? i.e. the second last line should be (*(iter->second))(); or something.

@GManNickG 2014-05-08 12:23:35

@BenFarmer: Yup, thanks for pointing that out. Such an old answer, too!

@Nic Hartley 2016-08-29 15:14:09

This is now out-of-date, because there is an unordered_map as part of the standard library.

@GManNickG 2016-08-29 17:44:48

@QPaysTaxes: Thanks for pinging! Fixed.

@Mohit 2015-11-20 22:48:36

In C++11 you can do something like this : This Interface needs only the return type and it takes care of everything else from the caller side.

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <typeinfo>
#include <typeindex>
#include <cassert>

void fun1(void){
    std::cout<<"inside fun1\n";
}

int fun2(){
    std::cout<<"inside fun2\n";
    return 2;
}

int fun3(int a){
    std::cout<<"inside fun3\n";
    return a;
}

std::vector<int> fun4(){
    std::cout<<"inside fun4\n";
    std::vector<int> v(4,100);
    return v;
}

// every function pointer will be stored as this type
typedef void (*voidFunctionType)(void); 

struct Interface{

    std::map<std::string,std::pair<voidFunctionType,std::type_index>> m1;

    template<typename T>
    void insert(std::string s1, T f1){
        auto tt = std::type_index(typeid(f1));
        m1.insert(std::make_pair(s1,
                        std::make_pair((voidFunctionType)f1,tt)));
    }

    template<typename T,typename... Args>
    T searchAndCall(std::string s1, Args&&... args){
        auto mapIter = m1.find(s1);
        /*chk if not end*/
        auto mapVal = mapIter->second;

        // auto typeCastedFun = reinterpret_cast<T(*)(Args ...)>(mapVal.first); 
        auto typeCastedFun = (T(*)(Args ...))(mapVal.first); 

        //compare the types is equal or not
        assert(mapVal.second == std::type_index(typeid(typeCastedFun)));
        return typeCastedFun(std::forward<Args>(args)...);
    }
};

int main(){
    Interface a1;
    a1.insert("fun1",fun1);
    a1.insert("fun2",fun2);
    a1.insert("fun3",fun3);
    a1.insert("fun4",fun4);

    a1.searchAndCall<void>("fun1");
    int retVal = a1.searchAndCall<int>("fun3",2);
    a1.searchAndCall<int>("fun2");
    auto temp = a1.searchAndCall<std::vector<int>>("fun4");

    return 0;
}

@Manspider 2017-11-25 06:00:17

This is gold. Is it possible to add member functions to the mix ? Maybe by casting it to a non-member type at some point ? Thanks

@rem45acp 2018-10-10 15:32:54

How does the call look like if it is a pointer to member function? I would like to do the same thing. If I have this: typedef int(ObjectT::*Command)(); And calling throws an error. int result = (*itr->second)(); Invalid use of unary * on pointer to member.

@EckhardN 2014-04-21 09:47:37

I tried to use the second answer with c++11. I had to change the last line from:
(*iter)();
to:
(*iter->second)();

so the code is now:

    #include <map>

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

    // ...

    void some_function(void)
    {
    }
    script_map m;

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

    int main(int argc, const char * argv[])
    {
        //..
        m.insert(std::make_pair("blah", &some_function));

        call_script("blah");
        //..
        return 0;
    }

@AndreasT 2010-01-26 08:21:41

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.

@mloskot 2010-01-26 01:40:28

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.

@excray 2011-03-22 11:35:50

This didnt' work for me. i got a compiler error. 'boost::function' : too many template arguments

@mloskot 2011-03-22 15:59:45

@vivek-g, there are many problems possible, compiler version, missing include, etc. It does compile and run for me as well as for codepad: codepad.org/ciKTrh2r

@Vitaly Isaev 2014-03-19 14:50:13

@mloskot, thank you for awesome example!

Related Questions

Sponsored Content

37 Answered Questions

21 Answered Questions

[SOLVED] Why should I use a pointer rather than the object itself?

  • 2014-03-03 11:54:16
  • gEdringer
  • 294559 View
  • 1521 Score
  • 21 Answer
  • Tags:   c++ pointers c++11

13 Answered Questions

[SOLVED] What is a smart pointer and when should I use one?

9 Answered Questions

[SOLVED] Pretty-print C++ STL containers

11 Answered Questions

[SOLVED] How do function pointers in C work?

  • 2009-05-08 15:49:17
  • Yuval Adam
  • 767521 View
  • 1160 Score
  • 11 Answer
  • Tags:   c function-pointers

25 Answered Questions

[SOLVED] Why do we need virtual functions in C++?

5 Answered Questions

13 Answered Questions

[SOLVED] How to convert a Map to List in Java?

12 Answered Questions

[SOLVED] In STL maps, is it better to use map::insert than []?

  • 2008-11-28 15:42:52
  • danio
  • 158498 View
  • 199 Score
  • 12 Answer
  • Tags:   c++ stl map stdmap

11 Answered Questions

[SOLVED] STL in embedded environment

  • 2010-10-04 07:35:21
  • Alok Save
  • 3917 View
  • 10 Score
  • 11 Answer
  • Tags:   c++ stl embedded

Sponsored Content