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...);
    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);
    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


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.