컨테이너 템플릿 매개 변수 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 내가 내 TreeNode 클래스의 구현에 문제가 없음 아직 명시 적으로 std::map의 인터페이스를 사용하여

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

또는

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

유형 중 하나가 될 필요가있다. 특히 멤버 함수 find, erase, insert을 사용합니다. 두 컨테이너 유형의 구현이 매우 구체적 인 일반 항목으로 대체해야합니다.

예를 들어 std::vector 구현을 플러그인 할 때마다 childs.find(key)을 find(childs.begin(), childs.end(), key)으로 바꿔야합니다.

아마도 내가 알지 못하는 다른 해결책이있을 수 있습니다. 아마 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>>;