容器模板參數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>>;