容器模板参数std :: map或std :: vector

Question

在我的一个项目中，我使用树实现，其中我使用容器 C=std::map<K,V>来维护每个树节点的子项列表。每个树节点都有一个唯一的名称密钥K，通常为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!!! 
    } 
} 

这个实现对我来说工作得非常好，除了std :: map没有考虑树中插入的顺序。对于某些应用程序，我需要保持插入的顺序，但对于其他应用程序来说，快速信息反转的需求更重要。

因此C必须要么

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

或

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

不，我有我的TreeNode类的实现问题，依然采用明确的std::map接口类型。尤其是，它使用的成员函数find,erase,insert需要被泛型替换，其中两种容器类型的实现都非常具体。

例如childs.find(key)需要替换find(childs.begin(), childs.end(), key)，只要我插入std::vector实现。

也许有另一种解决方案，我不知道。这可能是boost::multi_index，但我对此很不确定。

什么可能是解决我的问题最简单的方法？

Answer 1

您可能创建专用的过载功能，并使用它们

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

Answer 2

创建具有相同的界面为你想要的容器“选择”通用包装：

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

    // ... 
}; 

模板化的包装本身你的树节点类：

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

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

您现在可以定义方便类型别名在用户代码中的容器之间进行选择：

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