c++ - 寻找合适的数据存储和搜索引擎

Question

我有很多对象。每个对象都与许多键值对相关联。 key 是任意字符串(不同对象的键可能不同，没有可能的键的完整列表)，值可以是数字、字符串、日期时间等。

我需要使用复杂的搜索查询来搜索这个集合。在最简单的实现中，用户必须能够指定一个有趣的键列表和每个键值的条件，例如

key1: not present
key2: present
key3: == "value3"
key4: < 42
key5: contains "value5"

引擎必须找到满足所有条件的所有对象(即条件是“与”运算)。在完美的实现中，用户能够使用某种查询语言指定条件，例如

key1 = "value1" AND (key2 < 3 OR key3 < 3)

我在 Windows 上将 C++ 与 Qt 结合使用(Linux 支持不是必需的，但很好)。我不想使用需要安装(特别是管理员权限)的数据库，我希望解决方案是可移植的。

请建议一种从头开始或使用满足我需求的任何库或数据库实现此功能的好方法。

更新:问题是关于在磁盘上存储大量数据并快速搜索它。也许它还与解析和处理搜索查询有关。这与我需要用来表示内存中数据的数据结构无关。这很简单。

Answer 1

如果它们的键是唯一的，请使用 std::map 或 (C++11) std::unordered_map。

如果键不是唯一的，使用 std::multimap 或 (C++11) std::unordered_multimap。

后者的搜索和插入复杂度为 O(1)，但需要您提供高质量的哈希算法(不容易制作)，并可能在 map 增长和缩小时重新哈希。

搜索由容器提供。

序列化留给读者练习。