c++ - 大 N 的字符串容器

Question

我正在寻找适合大量字符串 (> 10^9) 的字符串容器。字符串具有可变长度。它的插入和查找速度必须很快，并且内存使用量少。当容器装满时，字符串是无序的。平均字符串长度约为 10 个字节。对精确的字符串值进行查找。可删除性 - 可选。 N 事先未知。对于 64 位架构。用例 - 考虑 AWK 的关联数组。

map<string>每个字符串大约有 20-40 位开销，每次插入调用一个 malloc(或两个)。所以不快不省。

谁能给我指点 C/C++ 库、数据结构或论文？

相关 -- Comparison of Hash Table Libraries

编辑我删除了“大数据”，将 N 提高到更大的值，明确了要求。

Answer 1

没有 Elixir ，只有radix tree给出了 trie 的优势(快速查找和插入，至少是渐近的)- 具有更好的空间消耗。

但是 - 两者都被认为不是“高效缓存” - 这可能很重要，尤其是在某些时候需要对数据进行迭代时。