1

我正在尝试在 C++ 中为表或关系（具有唯一行的无序表）构建数据结构。我以前用过很多次，但从来没有自己建造过。

所以表应该是任意类型的任意数量的列的集合。我可以使用std::vector<some_type>或一些派生类来表示一列。

我的问题是我可以使用什么语言结构来定义总体表数据结构？我意识到我可以以某种方式包装std::vector<some_type>到某个类中，该类本身可以派生出某个基类，然后将表表示为指向基类的指针向量，但我很想知道是否有替代方法来进行表示，也许使用一些模板签名？在使用表格的列时，我宁愿不要投太多。

给一些背景。我很乐意使用我所描述的那种现有数据结构。我已经看到这种结构在软件行业中非常积极地与关系代数算法一起使用，但我还没有在 boost 中找到这种结构。我对在其上实现基本的关系运算符特别感兴趣，例如联接、产品等...

编辑：更多细节。我不想创建具有基于行的内存连续性的数据结构。连续性是基于列的，这一点很重要，因此拥有一组向量似乎是正确的做法。

4

1 回答 1

1

您使用的数据结构可能取决于您最常执行的关系操作。

例如，如果您要在两个表上执行连接，有多种方法可以做到这一点。您可以使用嵌套循环连接，在这种情况下，无需通过特定键快速访问表中的特定行。另一方面，如果使用散列连接，则可以通过给定键快速获取特定行。

但是选择使用什么类型的连接是查询优化中的一个相关问题，它有几个因素（数据库中数据的基数估计等）。

但总的来说，我会做以下事情：

  1. 创建一个对象来表示数据中的一行。此对象可以包含您拥有的不同列的列表。如果您有一个通常对其执行操作的键，请将其存储在其自己的变量中。否则，您可以存储列值的哈希集以进行快速查找（仅当您有很多列时才值得这样做）。
  2. 在您拥有此对象来表示数据“行”之后，请确定您最常执行的操作类型。例如，如果您需要需要排序的操作，您可以使用 stl map按特定键存储这些行，它实现了红黑树，并且可以有效地取回键。如果您需要在给定时间快速访问特定行（例如，由于查询中的过滤器），那么您可以使用hashmap。

tl/dr：以最佳方式存储行取决于您最常期望的操作类型和数据分布。无论如何，我认为创建一个类来存储“行”的概念是合乎逻辑的，然后您可以根据您的用例使用各种数据结构排列这些行。

于 2013-01-31T19:31:25.690 回答