Параметр шаблона контейнера 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!!! 
    } 
} 

Эта реализация работала достаточно хорошо для меня, кроме того факта, что станд :: карта не уважает порядок введения в дереве. Для некоторых приложений мне нужно сохранить порядок вставки, но для других приложений важна необходимость быстрого извлечения информации.

Следовательно 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)); 
    } 

    // ... 
}; 

Templatize ваш класс узла дерева на самой упаковке:

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