Trie树主要分为两类，一类是静态的，一次性构建，构建完成后只读，另一类是动态的，随时可以加入新的key。当然，对于动态构建，其写过程，是不一定保证线程安全的。
对于trie的详细分析，见这篇老外的文章：http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/

性能分析

此部分内容为上边文章的摘要

因为大多数trie都是静态的，所以作者还加入了标准库的map等非trie的数据结构作为横向对比
静态的包括：

• libdatrie 0.2.8: double-array trie

• libtrie 0.1.1: double-array trie

• dary 0.1.1: double-array trie

• doar 0.0.13: double-array trie

• Darts 0.32: double-array trie

• Darts-clone 0.32g: directed acyclic word graph

• Darts-clone 0.32e5: Compacted double-array trie

• DASTrie 1.0: Compacted double-array trie

• tx-trie* 0.18: LOUDS (Level-Order Unary Degree Sequence) trie

• ux-trie* 0.1.9: LOUDS double-trie

• marisa-trie* 0.2.4: LOUDS nested patricia trie

动态的包括

• libdatrie 0.2.8: double-array trie

• libtrie 0.1.1: double-array trie

• dary 0.1.1: double-array trie

• doar 0.0.13: double-array trie

• critbit: crit-bit (patricia) tree [4]

• libdict: splay tree [5], treap [6], skiplist [7]

• C Containers library: scapegoat tree [8]

• Andersson tree library: AA tree [9]

• tst_vanilla: ternary search tree [10]

• Judy Array 1.0.5: Judy trie SL [11]

• hat-trie 0.1.0: HAT-trie [12]

• array-hash Array Hash: (cache-conscious) hash table [13]

• CMPH 2.0: hash table (w/ minimal perfect hash function [14])

• std::map <std::string, int> (gcc 4.9.0): red-black tree

• std::unordered_map <std::string, int> (gcc 4.9.0): hash table

• cpp-btree 1.0.1: B-tree

• sparsehash 2.0.2: hash table (sparsetable)

可以看出cedar在动态trie中有是有明显优势的，的败像不太难看的是google的sparsetable，不过sparsetable是hash表，在查询和容量上都更差一些。同样的hash表的unordered map因为实现臃肿，速度更慢。

ceder是动态的，如果传入的key是有序的，会减少内部的操作，所以速度也会提高。静态trie中比较突出的是darts系列。但是cedar与其相比并不逊色，两者终内存占用和查询速度相差无几，但是cedar的构建时间不到darts的1/5。并且，darts系的构建过程会耗费大量内存，即峰值内存是cedar的3倍以上。

综上，选择cedar作为trie是可行的。

使用

使用cedar十分简单，直接包含头文件即可。

template <typename value_type,
          const int     NO_VALUE  = nan<value_type>::N1,
          const int     NO_PATH   = nan<value_type>::N2,
          const bool    ORDERED   = true,
          const int     MAX_TRIAL = 1,
          const size_t  NUM_TRACKING_NODES = >
class da;

NO_VALUE的值是-1，NO_PATH的值是-2
因为其他的模版参数都有默认值，一般只特化value_type即可。 

cedar::da<int> trie;
trie.update("hello", strlen("hello"), 1);

接口

cedar的接口如下，选择一些常用的进行介绍。需要说明的是原始代码中的很多参数有歧义性。这里我对参数名称进行了修改，更符合直观的含义。

template <...>
class da {
  size_t capacity() const;
  size_t size() const;
  size_t total_size() const;
  size_t unit_size() const;
  size_t nonzero_size() const; // warning: O(size)
  size_t num_keys() const; // warning: O(size)
  
  template <typename T>
  T exactMatchSearch(const char* key) const;
  template <typename T>
  T exactMatchSearch(const char* key, size_t len, size_t from=) const;
  
  template <typename T>
  size_t commonPrefixSearch(const char* str, T* result, size_t result_len) const;
  template <typename T>
  size_t commonPrefixSearch(const char* str, T* result, size_t result_len, size_t len,
                            size_t from=) const;
  
  template <typename T>
  size_t commonPrefixPredict(const char* str, T* result, size_t result_len);
  template <typename T>
  size_t commonPrefixPredict(const char* str, T* result, size_t result_len, size_t len,
                             size_t from = );
  
  void suffix(char* key, size_t len, size_t to) const;
  value_type traverse(const char* key, size_t& from, size_t& pos) const;
  value_type traverse(const char* key, size_t& from, size_t& pos, size_t end_pos) const;
  
  value_type& update(const char* key);
  value_type& update(const char* key, size_t len, value_type val=value_type());
  value_type& update(const char* key, size_t& from, size_t& pos, size_t len, 
                      value_type val=value_type());
  template <typename T>
  value_type& update(const char* key, size_t& from, size_t& pos, size_t len, 
                     value_type val, T& cf) 
  
  int erase(const char* key);
  int erase(const char* key, size_t len, size_t from = );
  void erase(size_t from);
  
  int build(size_t num, const char** key, const size_t* len = , const value_type* val = );
  
  template <typename T>
  void dump(T* result, const size_t result_len);
  
  int save(const char* fn, const char* mode = "wb") const;
  int open(const char* fn, const char* mode = "rb",
           const size_t offset = , size_t size_ = );
  
  void restore()
  void set_array(void* p, size_t size_ = );
  const void* array() const;
  void clear(const bool reuse = true);
  
  int begin(size_t& from, size_t& len);
  int next(size_t& from, size_t& len, const size_t root=);
  
  void test(const size_t from=) const;
};

update

value_type& update(const char* key);
// update(key, from=, len=strlen(key), val=)
value_type& update(const char* key, size_t len, value_type val=value_type());
// update(key, from=, len, val)
value_type& update(const char* key, size_t& from, size_t& pos, size_t len, 
                   value_type val=value_type());

int erase(const char* key);
int erase(const char* key, size_t len, size_t from = );
void erase(size_t from);

int build(size_t num, const char** key, const size_t* len=NULL,
          const value_type* val=NULL);

template <typename T>
T exactMatchSearch(const char* key) const;
// exactMatchSearch(key, len=strlen(key), from=0);
template <typename T>
T exactMatchSearch(const char* key, size_t len, size_t from=0) const;

template <typename T>
size_t commonPrefixSearch(const char* str, T* result, size_t result_len) const;
// commonPrefixSearch(str, result, result_len, len=strlen(key), from=0);
template <typename T>
size_t commonPrefixSearch(const char* str, T* result, size_t result_len, size_t len,
                          size_t from=0) const;

template <typename T>
size_t commonPrefixPredict(const char* str, T* result, size_t result_len);
// commonPrefixPredict(str, result, result_len, len=strlen(key), from=0);
template <typename T>
size_t commonPrefixPredict(const char* str, T* result, size_t result_len, size_t len,
                           size_t from = 0);

value_type traverse(const char* key, size_t& from, size_t& pos) const;
// traverse(key, form, pos, end_pos=strlen(key))
value_type traverse(const char* key, size_t& from, size_t& pos, size_t end_pos) const;