Trie реализация с использованием карты

Простой способ реализации структуры данных Trie - использовать std::map<char,*NodeTrie>. Что может произойти неправильно, если я использую это. Мне нужно сериализовать и десериализовать Trie. Таким образом, каждая карта в узле является AVL-деревом. Может, у меня накладные расходы? Но на карте я могу быстрее искать, если я использую список.Trie реализация с использованием карты

template < typename T > 
struct NodeTrie{ 
    std::map<char,*NodeTrie>` 
    bool isWord; 
    T & val; 
};

источник

2013-08-30 YYY

У вас есть структура данных, схожая с hashmap? вы можете использовать это для минимальных накладных расходов. Или, если нет, подумайте о привязке символа к чему-то более управляемому. – dchhetri

Мне нужно точно Trie, для лексического поиска. – YYY

Вместо использования std :: map используйте std :: unordered_map или что-то похожее на это внутри. Это то, что я предлагал – dchhetri

Мне нравится ваша идея. Ошибки - важные структуры данных, и я имел приятный опыт работы с картами <> s в качестве эффективных контейнеров.

Просто некоторые замечания: если ваш компилятор поддерживает его, вы можете избежать потери памяти с отдельным распределением для каждого узла.

template< typename T > 
struct NodeTrie { 
    NodeTrie(const T& val = T(), bool isWord = bool()) : val(val), isWord(isWord) {} 

    std::map<char, NodeTrie> span; 
    T val; 
    bool isWord; 
};

Чтобы использовать этот способ:

int main() { 
    typedef NodeTrie<int> iTree; 
    iTree t(0); 
    t.span['a'] = iTree(3); 
    ... 
}

Также я изменил val элемента должна быть копия конструктивен объектом: с помощью ссылки здесь, кажется, неправильного дизайн мне ...

источник

2013-08-30 17:58:28 CapelliC

Просто FYI, GNU libC++ имеет шаблон trie уже в своей библиотеке структуры данных на основе политик. Вы можете использовать его как:

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/trie_policy.hpp> 
using namespace std; 
using namespace pb_ds; 

trie <string, int> myTrie;

Для некоторых примеров использования этого класса вы можете обратиться к this.

источник

2013-08-30 18:09:12

Trie реализация с использованием карты

ответ

Смежные вопросы