我一直在考虑用C ++实现一个地址簿。由于它是为移动应用程序开发的，因此地址簿应尽可能少地使用内存，并且用户仍应能够快速按名称搜索或排序联系人（我知道悖论）。
在我研究了一下之后，我发现大多数人都认为Trie是最适合我需要的数据结构。更准确地说是radix tree（Patricia Trie）。使用这种数据结构也非常适合实现自动完成。
还有其他可行的解决方案，或者如果我开始使用这个想法进行编码是否可以？
小心尝试小集合。虽然它们确实提供了良好的渐近行为，但它们在时间和空间上的隐藏常数可能太大了。
特别是，尝试往往具有较差的缓存性能，这应该是小型集合的主要关注点。
假设您的数据相对较小[<10,000个条目]，std::vector可以提供良好的缓存性能，这可能会比尺寸因素影响更大。因此，即使它的搜索时间渐近地高于trie或std :: set，实际上 - 由于良好的缓存行为，它可能比两者更好。
如果您还可以使用vector维护binary search排序 - 您可以从对数搜索时间和良好的缓存行为中受益。
（*）这个答案假定部署应用程序的硬件有CPU-Cache。
尝试是最好的，因为它们提供快速搜索，插入和删除。