1
\$\begingroup\$

A bit of background: some time ago I wrote a piece of code that can be used for memoization with functions taking one parameter. Now I want to extend this to deal with functions with arbitrary number of parameters. However, thats a different story and here I want to focus only on one part of it: When memoizing the parameters and return values I could use a map<tuple<parameter_types...>,return_type>, but instead I was in the mood to get in touch with variadic templates and tried this:

#include <map>
#include <iostream>

template<typename VALUE,typename KEY,typename...MORE_KEYS>
struct VariadicMap {
    typedef VariadicMap<VALUE,MORE_KEYS...> inner_map_type;
    typedef std::map<KEY,inner_map_type>    map_type;
    VALUE& get_ref(const KEY& k, const MORE_KEYS&...more_keys){ 
        return map[k].get_ref(more_keys...); 
    }
    VALUE* find(const KEY& k,const MORE_KEYS&...more_keys){
        auto it = map.find(k);
        if (it == map.end()) { return nullptr; }
        return it->second.find(more_keys...);
    }
private:     
    map_type map;
};

template <typename VALUE,typename KEY>
struct VariadicMap<VALUE,KEY> {
    VALUE& get_ref(const KEY& k){ 
        return map[k]; 
    }
    VALUE* find(const KEY& k) {
        auto it = map.find(k);
        if (it == map.end()) { return nullptr; }
        return &(it->second);
    }
private: 
    std::map<KEY,VALUE> map;
};

used like this:

int main() {
    VariadicMap<double,int,int,int> vm;
    vm.get_ref(1,2,3) = 1;
    std::cout << "x = " << vm.get_ref(1,2,3) << "\n";
    auto x = vm.find(1,2,3);
    if (x != nullptr) { std::cout << "x = " << *x << "\n";}
    return 0;
}

The rationale was that I would expect it to be much faster to search n maps of size m instead of searching a huge map of size n*m, where n is the number of parameters and m the number of values for each parameter. Especially to find that a key is not in the map it can be sufficient to consider only one parameter.

Indeed, when I compared the performance to a map<tuple<parameter_types...>,return_type> both inserting and finding values was faster (or at least not slower) with this VariadicMap for the examples I tried. However, what I dont like is...

  • I didnt know how to avoid the ugly inversion of <key,value> to <value,keys>, because of keys being a parameter pack.
  • the get_ref method mimics the operator[], but I cannot implement it as operator[] because it is only allowed to take a single parameter.

Please note that this was mainly an excercise, but harsh critisism is of course welcome ;). Code also here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.