CODEWITHSUNDEEP
c++templatesstltemplate-meta-programmingboost-multi-index
Aleph0
Aleph0

Reputation: 6084

Container template parameter std::map or std::vector

In one of my projects I'm using a tree implementation, where I used the container C=std::map<K,V> to maintain a list of children for each tree node. Each tree node has a unique name key K being normally a std::string.

template<typename V, template<typename Key=std::string,typename Type=TreeNode<V>,typename ...> typename C>
class TreeNode {
    typedef C<std::string, Value> cont_type;    
    typedef V data_type;

    cont_type childs;
    data_type value;

    cont_type::iterator genericFind(const K& k) {
        // Something generic here!!! 
    }
}

This implementation worked quite well for me besides the fact, that std::map doesn't respects the order of insertion in the tree. For some applications I need to keep the order of insertion, but for other applications the need for fast information retrivial is more important.

Hence C needs to be either of type

std::vector<std::pair<K, V>> // keeping insertion order

or 

std::map<K,V> // fast information retrivial

No I have a problem with the implementation of my TreeNode class, still using explicitly the interface of std::map. Especially, it uses the member functions find, erase, insert that needed to be replaced by something generic, where the implementation for the both container types is quite concrete.

For example childs.find(key) needs to be replaced by find(childs.begin(), childs.end(), key), whenever I plugin the std::vector implementation.

Maybe there is another solution, that I'm not aware of. This might be maybe boost::multi_index, but I'm quite unsure about this.

What might be the easiest way to solve my issue?

Upvotes: 2

Views: 2320

Answers (2)

Jarod42
Jarod42

Reputation: 217275

You may create dedicated overload functions, and use them

template <typename Key, typename V>
auto my_find(std::map<Key, V>& m, const Key& key)
{
    return m.find(key);
}

template <typename Key, typename V>
auto my_find(std::vector<std::pair<Key, V>>& v, const Key& key)
{
    return std::find_if(v.begin(), v.end(), [&](const auto& p) {
        return p.first == key;
    });
}

Upvotes: 3

Vittorio Romeo
Vittorio Romeo

Reputation: 93274

Create generic wrappers for your desired container "choices" with the same interface:

template <typename TKey, typename TValue>
class my_map_wrapper
{
private:
    std::map<TKey, TValue> _map;

public:
    // Same interface as 'my_vector_wrapper'.
    template <typename TEKey, typename TEValue>
    void emplace(TEKey&& key, TEValue&& value)
    {
        _map.emplace(std::make_pair(std::forward<TEKey>(key),
                                    std::forward<TEValue>(value)));
    }

    // ...
};


template <typename TKey, typename TValue>
class my_vector_wrapper
{
private:
    std::vector<std::pair<TKey, TValue>> _vec;

public:
    // Same interface as 'my_map_wrapper'.
    template <typename TEKey, typename TEValue>
    void emplace(TEKey&& key, TEValue&& value)
    {
        _vec.emplace_back(std::forward<TEKey>(key),
                          std::forward<TEValue>(value));
    }

    // ...
};

Templatize your tree node class on the wrapper itself:

template <typename TWrapper>
class TreeNode
{
private:
    TWrapper _container;

public:
    // Use "uniform" container interface...
};

You can now define convenient type aliases to choose between containers in user code:

template <typename TKey, typename TValue>
using MapTreeNode = TreeNode<my_map_wrapper<TKey, TValue>>;

template <typename TKey, typename TValue>
using VectorTreeNode = TreeNode<my_vector_wrapper<TKey, TValue>>;

Upvotes: 2

Related Questions