c++ - 在 C++ 中返回索引和存储字符串计数的数据结构

Question

我正在构建一个 xlsx 构建器，并且我有一系列字符串要保存在电子表格（xml 文件）中。可能存在重复，所以我想将字符串存储在地图中并增加它们的计数。然后，我可以将它们所在的索引存储在地图中，而不是存储字符串，并将字符串存储在另一个 xml 文件中。但是使用 std::map 检索给定字符串的索引是 O(n)。有没有一种数据结构可以更快地完成这个任务？

Answer 1

除非您的“单独文件”需要按字典顺序排列，否则不要使用地图中的索引，请明确存储索引。

例如 a map<string, gubbins>, with struct gubbins { size_t count; size_t index; }。

每当您向地图插入新键时，为其索引提供递增计数器的“下一个”值。

使用的索引值的范围是连续的，除非您稍后出现并减少引用计数，然后在它达到零时从映射中删除条目。在这种情况下，您可以对索引进行“碎片整理”，但如果您已经使用索引来识别其他地方的字符串，当然不能。

写入字符串文件的操作需要先按索引排序。您可以在线性时间内做到这一点——创建一个足够大的数组，然后遍历地图，将每个字符串存储在正确的索引处。或者您可以随时构建字符串文件，在将每个字符串添加到地图时添加它。

可能有可能用 right 完成整个事情boost:multi_index。

Answer 2

如果您需要按排序顺序存储字符串，您可能需要查看顺序统计树数据结构，它是一个平衡的二叉搜索树，增加了额外的信息，可以有效地确定树中的第 n 个元素（在O(log n) 时间）。这为您提供了 的所有原始功能std::map，以及随机访问。

C++ 标准库中没有顺序统计树的标准实现，但是快速的 Google 搜索应该会出现一些。

希望这可以帮助！