5

请注意，这个问题仅与 C++ 有关，我对使用现有数据库不感兴趣，也不是在寻求“c++ 中的数据库”的通用解决方案。我有一个具体的问题，并且正在寻求以下问题的最有效（在时间、空间和最佳实践方面）的解决方案。

假设我有一系列书籍，由Id、ISBN、Author和描述Name。该Name列将是一个与单独的作者表相关的 ID，其中包含列Id、Surname、First Name。我希望能够按姓名和作者进行有效搜索。我将如何构建它，以及我将使用哪些容器？

这个话题已经在SO和其他地方多次提出，但从来没有专门与 C++ 或不使用现有库的实现相关的答案。

天真的解决方案是简单地创建 2 个单独的类：Author和Book：

class Book
{
public:
  int id;
  std::string isbn;
  Author* author;
  std::string name;
};

class Author
{
public:
  int id;
  std::string surname;
  std::string givenName;
};

然后我可以创建 Book 和 Author 的向量（指针）。但是我将如何有效地索引这些？假设我想通过 ISBN 查找一本书；我怎样才能在恒定或至少对数时间内做到这一点？这可能吗？这类问题有标准做法吗？

4

2 回答 2

4

首先，标准容器不支持多键索引——每个容器只支持一个键。这可以是一个复合键，因此如果您有三本由不同作者撰写的具有相同标题的书，您可以同时指定标题和作者以仅查找其中一本书。但是，没有一个标准容器支持按标题或作者单独搜索。

Boost Multi-Index库相当直接地支持每个项目的多个键。多索引教程有创建外键的示例，就像您有兴趣使用一样。

Multi-Index 支持（红黑）基于树的索引和基于哈希的索引。像往常一样，您可以在两者之间进行权衡——散列索引通常可以更快地查找单个项目，但基于树的索引支持不等式，因此如果您想要搜索范围之类的东西，它们通常会更好（例如， “姓氏从'C'到'L'的作者的书籍”）。

于 2013-10-15T00:51:44.367 回答
3

如果您只需要反向映射，则索引的标准数据结构是哈希映射；如果您还需要排序，则使用二叉搜索树。在 C++ 中，它们分别是unordered_map和map。

假设我想通过 ISBN 查找一本书；

创建unordered_map<std::string,Book*>和搜索将是恒定的时间。

于 2013-10-15T00:07:25.127 回答