c++ - 我应该使用哪种数据结构

Question

我正在尝试找出解决此问题的最佳数据结构。我正在使用字符串键实现键值存储。这些值被频繁添加，通常只会被查找 1 或 2 次。最初我使用了 std::map，但我发现性能不是最优的，因为添加键和重新平衡红黑树的开销掩盖了搜索值时间的减少。目前我正在使用修改后的单链表。它使用一个包含 c 字符串 (const char *)、字节长度和存储值的结构。当我想使用键查找值时，我遍历列表并比较键的大小，如果它们匹配，我使用 memcmp 检查字符串是否相同。如果它们相同，我返回值。通过使用此方法，我的性能比 std::map 提高了大约 10 倍。但是，我需要使它的效率提高大约 2 倍。谁能针对这个问题推荐一种更好的数据结构类型？

Answer 1

在不了解实际问题的情况下很难快速找到解决方案。特别是，你的数据集有多大，真正的数据存储在哪里(是存储在容器中还是其他地方？)。您还需要对容器执行哪些其他操作？您需要从容器中删除元素吗？

作为对其他问题之一的评论，您声明需要在 std::unordered_map 中复制 key ...如果 key 已经存储在其他地方，我建议您使用 map ，但避免复制字符串。使用指针作为键，并使用自定义比较器取消引用并在结果中进行操作:

// Assuming that the data is stored in std::string somewhere else
struct custom_compare {
   bool operator()( std::string* lhs, std::string* rhs ) const {
      return lhs!=rhs && (lhs->size() < rhs->size() || lhs->compare( *rhs ) < 0);
   }
};
std::map< std::string*, data, custom_compare > mymap;

通过存储指针而不是实际的字符串，这将消除复制。自定义比较器基本上与您在列表中实现的比较器一样快，树将平衡内容，允许 O(log n) 查找。根据集合的大小(如果有很多元素)，这将是对线性搜索的改进，而如果大小较小，则线性搜索会更好。

此外，根据数据的多样性，您可能希望遵循线性搜索，但根据一些快速计算的标准来划分搜索空间，同时尽可能均匀地划分集合。例如，您可以使用线性搜索，但不是保留单个列表，而是根据 key 长度保留不同的列表。

如果标准实际上是基于字符串的内容(字母，而不是大小)，那么您近似于 trie 的定义。如果你得到一个已经实现了一个的库，或者你愿意花时间这样做，那么 trie 可能是这种类型查找最快的容器之一，因为它将“size”变量从元素到字符串的长度。