C++ Trie树：cedar

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)