根据值干净地访问结构数组

Question

我正在尝试创建一个结构数组，其中为每个加入网络的设备和运行程序的设备创建一个条目。应使用感兴趣设备的网络地址访问此数组。

示例:网络上有三个(其他)设备，地址分别为 0x1、0x2 和 0x3(我们在 0x0 上运行)。现在我们要访问与设备0x1相关的数据结构，假设是Table[0]。问题是将地址 (0x1) 与索引 (0) 相关联。

注意:网络地址由软件的其他部分动态分配，不在我的控制之下。它们也不保证是连续的。

最干净的方法是什么？

对我来说最直观的方法是搜索整个表，将每个条目的Address字段与特定地址(在示例中为0x1)进行比较，然后返回索引，但我想知道是否有更合适的方法来执行此常见操作。顺便说一句，它可能有一个专有名称(动态数据结构？)。

Answer 1

1) 快速、简单且肮脏的方法。如果地址是小数字，您可以简单地制作一个查找表，例如:

const struct_ptr* TABLE[n] =
{
  NULL,
  &struct_this,
  &struct_that,
  NULL,
  ...
};

其中索引对应一个地址。如果地址有相应的结构，你得到一个指向该结构的指针，否则为 NULL。

这是最快的方法，它可以直接访问 O(1)。但它会浪费一点数据内存，而且如果您的地址可以是任何类型的数字，则不太可行。

2) 排序查找表和二分查找。如果地址是任何类型的数字，请使用它。在这种情况下，您将不得不制作一个仅包含指向现有结构的指针的查找表，例如:

const struct_ptr* TABLE [NUMBER_OF_EXISTING_STRUCTS] = 
{
  &struct_this,
  &struct_that,
  ...
};

每个结构都需要有一个成员 address 并且它们必须以排序的方式添加到上面的查找表中，最低地址在前。然后您可以对表进行二进制搜索，使用比较每个结构 address 成员的比较函数。这相当快，O(log n)。

3) 哈希表。 最先进的替代方法。这最适合具有大量数据的系统，并且还可以处理重复项。访问时间几乎是确定性的，接近于 O(log n)，但不完全是。取决于您如何实现“链接”等。