A multi key/value type "folded" map class template

Question

I have recently come across a use case where I need to lump many maps into a single container. These maps can have different combinations of key/value types, but they all differ from one another.

For a certain set of key types Key1, Key2, ... and value types Val1, Val2,... the obvious implementation is

class LumpedMap {

   std::map<Key1, Val1> map1;
   std::map<Key1, Val2> map2;
   std::map<Key2, Val1> map3;
   std::map<Key2, Val2> map4;
   std::map<Key3, Val2> map4;
   ...

}

but this doesn't scale well for many maps, as if we want to maintain encapsulation we tend to create a vast number of accessors

Val1& at(const Key1&) {...}
Val2& at(const Key1&) {...}
Val1& at(const Key2&) {...}
...

void insert(const Key1&, const Val1&) {...}
void insert(const Key1&, const Val2&) {...}
void insert(const Key2&, const Val1&) {...}
...

etc...

My goal is to have a class template that allows me to instantiate a particular type with a list of key/value types

using MyMap = LumpedMap<std::pair<Key1, Val1>,
                        std::pair<Key1, Val2>,
                        std::pair<Key2, Val1>,
                        std::pair<Key2, Val3>>;

and that can generate automatically all standard methods for any type

MyMap fm;

//...lookup

fm.at<Key2, Val3>();

//...insertion
fm.insert_or_assign(k2, v3);

//...etc

I have come up with the following variadic template implementation that uses fold expressions (for which reason, I will call it FoldedMap ;)):

template<class K, class V>
class MapBase {

public:
    
    using MapType = std::map<K, V>;
    using MapPtr = std::shared_ptr<MapType>;
    
protected:
       
    MapPtr _map{std::make_shared<MapType>()};
    
    MapBase() = default;
    
    MapBase(MapPtr map) : _map{std::move(map)} {
    
    }
    
    V& at(K& key) {
        return _map->at(key);
    }
    
    auto insertOrAssign(const K& key, const V& val) {
        return _map->insert_or_assign(key, val);
    }
    
    const auto& range() {
        return *_map;
    }
    
    void merge(MapBase<K, V>& source) {
        _map->merge(*source._map);
    }
};

template<class ...Pair>
class FoldedMap : public MapBase<typename Pair::first_type, typename Pair::second_type>... {
    
public:
    
    FoldedMap() = default;
    
    FoldedMap(typename MapBase<typename Pair::first_type, typename Pair::second_type>::MapPtr& ...map)
        : MapBase<typename Pair::first_type, typename Pair::second_type>(map)... {
    
    }
    
    template<class K, class V>
    V& at(K& key) {
        return MapBase<K, V>::at(key);
    }
    
    template<class K, class V>
    auto insertOrAssign(const K& key, const V& val) {
        return MapBase<K, V>::insertOrAssign(key, val);
    }
    
    template<class K, class V>
    auto range() {
        return MapBase<K, V>::range();
    }
    
    template<class ...P>
    void merge(FoldedMap<P...>& other) {
        (MapBase<typename P::first_type, typename P::second_type>::merge(other), ...);
    }
    
    template<class ...P>
    FoldedMap<P...> extract() {
        FoldedMap<P...> fm(MapBase<typename P::first_type, typename P::second_type>::_map...);
        return fm;
    }
    
    template<class K, class V>
    void _merge(std::map<K, V>& other) {
        MapBase<K, V>::_merge(other);
    }
};

A few remarks, mostly arbitrary choices I made that can be revised or fine tuned:

• The method extract() takes a slice of the object as a new FoldedMap with a subset of key/value types.

• The choice of using shared pointers is motivated by the intention of supporting shallow-copy semantics in extract() (which maybe could be renamed to emphasize this, and is out of line with the semantics of the same method in std::map).

This is an example test code, showing some usage.

int main(int argc, const char * argv[]) {
        
    Key1 k1 = "k1";
    Key2 k2 = std::make_pair(2, "two");
   
    Val1 val1 = 3.14;
    Val2 val2 = "val2";
    
    FoldedMap<std::pair<Key1, Val1>,
              std::pair<Key1, Val2>,
              std::pair<Key2, Val1>> fm;
    
    FoldedMap<std::pair<Key2, Val1>> fm2;
    
    // Insert elements
    fm.insertOrAssign(k1, val2);
    fm.insertOrAssign(k2, val1);
    fm2.insertOrAssign<Key2, Val1>({3, "three"}, 6.28);
    
    std::cout << fm.at<Key1, Val2>(k1) << "\n";
    
    // Merge operation - follows std::map<T,T>::merge() semantics
    fm.merge(fm2);
    
    // Extract operation - leaves the original object unchanged
    // by sharing data with target object
    auto fm3 = fm.extract<std::pair<Key1, Val1>,std::pair<Key2, Val1>>();
     
    
    for (auto& [k,v]: fm.range<Key1, Val1>())
        std::cout << "Key1 - Val1 range: " << k << v << "\n";
   
    for (auto& [k,v]: fm.range<Key1, Val2>())
        std::cout << "Key1 - Val2 range: " << k << " " << v << " " << "\n";
    
    for (auto& [k,v]: fm.range<Key2, Val1>())
           std::cout << "Key2 - Val1 range: " << k.first << " " << k.second << " " << v << "\n";
    
   
    for (auto& [k,v]: fm3.range<Key1, Val1>())
        std::cout << "from view " << k << v << "\n";

    for (auto& [k,v]: fm3.range<Key2, Val1>())
        std::cout << "from view " << k.first << " " << k.second << " " << v << "\n";
    
    std::cout <<
    std::any_of(fm.range<Key2, Val1>().begin(),
                fm.range<Key2, Val1>().end(),
                [] (const auto& k2) { return k2.first.first == 3;}
                )
    << "\n";
    
    return 0;
}

Any feedback on the above implementation is welcome. Has someone seen something similar in any library?

Answer 1

This looks quite good already, and it's an interesting problem to solve. However, I'll first try to give some arguments why you perhaps shouldn't, and then mention some things that could be improved.

Encapsulation

but this doesn't scale well for many maps, as if we want to maintain encapsulation we tend to create a vast number of accessors

I guess it depends on what you call "encapsulation", but I think that having multiple member variables grouped inside a class is also perfectly fine encapsulation. You don't need a vast number of accessors, since instead of writing:

fm.at<Key1, Val1>();

You can write:

fm.map1.at();

You have to provide information of which map you want to access anyway, so either it's via a member name, or via a template parameter. The only time I see the latter as being more desirable is if you have some other templated code that only knows about the pair type it needs to access, not the map name.

Consider using std::tuple

Your FoldedMap basically looks like a std::tuple over std::maps. Instead of:

FoldedMap<std::pair<Key1, Val1>, std::pair<Key2, Val2>> fm;

You could write:

std::tuple<std::map<Key1, Val1>, std::map<Key2, Val2>> fm;

The only drawback of this is that it doesn't have the convenience member function insertOrAssign() that can deduce the desired element type from its arguments. However, you could write an out-of-class function to do that:

template<typename FoldedMap, typename Key, typename Val>
insertOrAssign(FoldedMap &fm, const Key &key, const Val &val) {
    fm.get<std::map<Key, Val>>().insert_or_assign(key, val);
}

The same goes for the other member functions.

Avoid starting identifiers with underscores

The standard has some rules regarding identifiers starting with underscores. While your use is safe, I would just avoid starting names with underscores completely, as it's too easy to make a mistake, as not everyone knows these rules by heart. I suggest you either use m_ as a prefix for member variables, or use a single underscore as a suffix.

Use the standard library's naming conventions

You are trying to make the FoldedMap container look and feel the same as STL containers. However, while at() and merge() are spelled the same as the corresponding member functions of std::map, you used insertOrAssign() instead of insert_or_assign(). I recommend you use exactly the same naming conventions as the STL, so as to avoid surpises and make it easier to use it as a drop-in replacement for STL types.

Also note that extract() also exists for std::map, but does something different from your extract(). Although I think that your extract() makes sense, consider that someone might want to extract a node from one of the MapBases, and later insert() it again. You could overload FoldedMap::extract() to handle both these things, but it might be better if these things have clearly distinct names. Perhaps you could rename your current extract() to get(), as it does something similar to std::get().

Match the standard library's function signatures exactly

If you look at the documentation of std::map<>::insert_or_assign(), you'll notice that it takes the value not as a const V&, but as a M&&. This avoids unnecessary casting (for example, when passing a C string literal when V is std::string), and also allows efficient moving from temporaries. So your MapBase::insert_or_assign() should look like:

template<typename M>
auto insert_or_assign(const K& key, M&& val) {
        return m_map->insert_or_assign(key, std::forward<M>(val));
}

For FoldedMap::insert_or_assign() you can't do this of course, since it depends on the value having type V to correctly deduce which underlying MapBase to use. However, you should still take the val as a forwarding reference.

Your at() is taking key as a non-const reference, this should be const. Also, std::map<>::at() has a const function overload, which you should probably also implement.

About _merge()

Your FoldedMap has a member function _merge(), which doesn't work (there's no corresponding _merge() in MapBase), but also it should just be renamed to merge(); function overloading should work just fine.

Pass Pairs where possible

Instead of making MapBase be a template of two types, make it a template of just Pair:

template<typename Pair>
class MapBase {
    using K = typename Pair::first_type;
    using V = typename Pair::second_type;
    ...
    void merge(MapBase& source) {...}
};

This simpifies most of FoldedMap, although some member functions do need to keep the template<class K, class V> for type deduction to work, in which case you need to use MapBase<std::pair<K, v>> to access the underlying map:

template<class ...Pair>
class FoldedMap : public MapBase<Pair>... {
    ...
    FoldedMap(typename MapBase<Pair>::MapPtr& ...map): MapBase<Pair>(map)... {}

    template<class K, class V>
    V& at(const K& key) {
        return MapBase<std::pair<K, V>>::at(key);
    }
    ...
    template<class ...P>
    void merge(FoldedMap<P...>& other) {
        (MapBase<P>::merge(other), ...);
    }
    ...
};

Use of std::shared_ptr

I would avoid using std::shared_ptr, and instead store the underlying std::maps by value. Value semantics are always much easier to reason with. For example, if I would write:

FoldedMap<std::pair<std::string, std::string>> fm1;
auto fm2 = fm1; // copy?
fm1.insert_or_assign(std::string{"Hello,"}, std::string{"world!"});
std::cout << fm2.at<std::string, std::string>("Hello,") << "\n";

If fm1 were a regular std::map<std::string, std::string>, then I expect the last line to throw an exception, because the copy was made when fm1 was still empty. However, your class basically has reference semantics, and lets this code print "world!", which for most C++ programmers would be unexpected.

If someone really needs shallow copy semantics, they could just create a std::shared_ptr<FoldedMap<...>> themselves. If you want to make a shallow copy that restricts the number of underlying MapBases that are accessible, perhaps you could create some kind of FoldedMapView type? Both of these solutions would make the shallow copy semantics explicit.