5

我试图找到一种以有效方式在 C 中存储“键、值”对的方法，以便快速检索数据。我一直在网上寻找，似乎没有一种快速简便的方法来存储它们，例如在 Java 中。我需要能够频繁地访问和更新值，还需要能够添加新键并将它们按顺序排序。我已经阅读了有关使用qsort()和bsearch()完成这些的信息，但我不确定使用什么数据结构来存储它们。

4

4 回答 4

3

您正在寻找关联容器。C 中没有“直接”方式，因为标准库不提供任何数据结构。您可以尝试寻找提供该功能的第三方库，或推出您自己的解决方案。

于 2013-03-25T21:14:21.363 回答
3

我意识到这是一个旧线程，但我可能有一些贡献，可能对寻求不是很复杂的解决方案的其他人有用。

我已经以不同的方式多次这样做了。如何完成取决于几个因素：

  1. 您知道需要跟踪的最大键/值对数吗？
  2. 所有的值都是同一类型吗？
  3. 这需要多快？

如果 1 和 2 的答案是“是”，那么它可以很简单。当 3 的答案是“没那么重要”，或者当对的最大数量不是太高时，我使用数组或动态分配的内存块作为数组。

在这个方案中，有两个数组： - 索引数组（不是键） - 包含键名和值的键/值对结构数组

您还有一个结构可以跟踪键/值列表，该列表包含（最少）指向索引和键/值结构数组的指针、当前定义的键/值对的数量以及可以存储的键/值对的最大数量存储。

最初，键/值对的计数为 0，索引数组中的每个数组元素都包含一个初始值（可以为零，但通常表示它没有被使用，例如 -1），以及键/值对结构数组被清零（没有名称，没有值）。

维护索引数组，以便索引值以正确的顺序引用另一个数组中的键/值对结构。插入和删除不会移动任何现有的对结构，只会移动索引。删除键/值对时，将包含它的结构清零。

当使用“qsort()”或其兄弟时，您的比较函数使用索引数组中的索引来访问相应键/值对的名称，并且您的交换函数交换索引数组中的索引值。Insert 执行重叠的就地复制（从结尾到插入点）以将新键之后的键的索引在索引数组中向下移动一个位置，并且 delete 执行类似的向上洗牌以缩小被删除的位置的间隙关键是。

一个稍微快一点的版本，它不使用更多内存进行存储，它使用 C 联合来允许将前向链索引存储在未使用的键/值对元素中，并且初始化将它们与列表中的“下一个空闲”索引链接在一起语境。这样可以避免在插入新对时必须在列表中搜索空闲元素。当您需要一个空闲的键/值对对象时，将存储在“next free”中的索引用于新元素，并将“next free”设置为刚刚声明的空闲对象中存储的链索引。当您丢弃一对时，只需将“下一个空闲”值复制到已释放对象中的链索引中，并将已释放对象的索引设置为“下一个空闲”的新值。

索引数组也可以使用指向内存中键/值结构的指针来实现。在这种情况下，空闲对象列表中的“下一个空闲”和链链接也成为指针。

上述方案适用于较小的键/值集大小和简单的值类型。

于 2015-10-04T21:02:37.490 回答
1

正如 Baltasarq 所说，C 没有为此目的的数据结构。但是，您可以使用基于必须支持的结构的实现：初始化、获取、添加和删除操作。这里提出了一些好的设计。

于 2013-03-25T22:03:20.640 回答
0

一种非常快速且内存高效的方法是使用 Judy 数组。只要你不害怕指针，它就很容易使用。

http://judy.sourceforge.net/

它在 LGPL 下获得许可

可以安装在 Debian/Ubuntu 上：sudo apt-get install libjudy-dev

一个警告是，一个词是本机 CPU 词的长度。这使其速度更快，但在使用 Judy1 或 JudyL 时可能会影响 32/64 位机器之间的可移植性。

有以下类型可用：

Judy1  - maps an Index (word) to a bit
JudyL  - maps an Index (word) to a Value (word/pointer)
JudySL - maps an Index (null terminated string) to a Value
JudyHS - maps an Index (array-of-bytes) of Length to a Value

使用字符串作为键的示例代码 (JudySL)：

#include <stdio.h>
#include <Judy.h>

#define DIE(x) { fprintf(stderr,"%s\n",x); exit(-1); }

int main() {

    Pvoid_t   PJArray = (PWord_t)NULL;  // Judy array.
    PWord_t   PValue;                   // Judy array element.
    Word_t    Bytes;                    // size of JudySL array.

    uint8_t   key[100]; //max len for key is 100
    const char *value1="Value One";
    const char *value2="Value Two";

    JSLI(PValue, PJArray, "key1");          // Insert key
    if (PValue == PJERR) DIE("Out of memory\n");
    *PValue=(Word_t)value1;                 // Set pointer to value

    JSLI(PValue, PJArray, "key2");          // Insert key
    if (PValue == PJERR) DIE("Out of memory\n");
    *PValue=(Word_t)value2;                 // Set pointer to value

    key[0]='\0';                            // start with smallest string.

    JSLF(PValue, PJArray, key);             // get first key/value
    while (PValue != NULL) {
            printf("key=%s, value=%s\n",key,(char*)*PValue);
            JSLN(PValue, PJArray, key);     // get next key/value
    }

    JSLG(PValue, PJArray, "key2");             // lookup a key
    printf("key2:%s\n",(char*)*PValue);

    JSLFA(Bytes, PJArray);              // free array

    return 0;
}

编译：gcc judy_sample.c -o judy_sample -lJudy

于 2017-05-31T11:50:38.360 回答