5

「キーと値」のペアを効率的な方法でCに格納して、データをすばやく取得する方法を見つけようとしています。私はオンラインで探していましたが、Javaのようにすばやく簡単に保存する方法はないようです。値に頻繁にアクセスして更新できる必要があります。また、新しいキーを追加して順番に並べ替えることもできる必要があります。qsort()それらの使用と達成について読んだことがbsearch()ありますが、すべてを格納するためにどのデータ構造を使用するかがわかりません。

4

4 に答える 4

3

連想コンテナを探しています。標準ライブラリはデータ構造を提供しないため、Cには「直接的な」方法はありません。機能を提供するサードパーティのライブラリを探すか、独自のソリューションを提供してみてください。

于 2013-03-25T21:14:21.363 に答える
3

これは古いスレッドだと思いますが、それほど複雑ではないソリューションを探している他の人に役立つかもしれない何か貢献できるかもしれません。

私はこれをさまざまな方法で数回行いました。それがどのように行われるかは、いくつかの要因によって異なります。

  1. 追跡する必要のあるキーと値のペアの最大数を知っていますか？
  2. すべての値が同じタイプですか？
  3. これはどれくらい速くする必要がありますか？

1と2の答えが「はい」の場合、それは非常に簡単です。3の答えが「それほど重要ではない」場合、またはペアの最大数が多すぎない場合は、配列または配列として扱われる動的に割り当てられたメモリのブロックを使用します。

このスキームには、次の2つの配列があります。-インデックス配列（キーではない）-キー名と値を含むキー/値ペア構造体の配列

また、インデックスおよびキー/値構造体配列への（最小限の）ポインター、現在定義されているキー/値ペアの数、および可能なキー/値ペアの最大数を含むキー/値リストを追跡する構造もあります。保存されます。

最初は、キーと値のペアの数は0であり、インデックス配列のすべての配列要素には初期値が含まれ（ゼロでもかまいませんが、通常は-1のように、使用されていないことを示すものです）、キー/値ペアの構造体配列はゼロになります（名前も値もありません）。

インデックス配列は、インデックス値が他の配列のキー/値ペア構造を正しい順序で参照するように維持されます。挿入と削除は、既存のペア構造を移動せず、インデックスのみを移動します。キーと値のペアが削除されたら、それを含む構造体をゼロにします。

「qsort（）」またはその兄弟を使用する場合、compare関数はインデックス配列のインデックスを使用して対応するキー/値のペアの名前にアクセスし、exchange関数はインデックス配列のインデックス値を交換します。挿入は、オーバーラップしたインプレースコピー（端から挿入ポイントまで）を実行して、新しいキーの後にあるキーのインデックスをインデックス配列の1つの位置にシャッフルし、削除は、同様の上方シャッフルを実行して、削除された場所のギャップを閉じます。キーはでした。

ストレージにメモリを使用しないこれのわずかに高速なバージョンは、Cユニオンを使用して、フォワードチェーンインデックスを未使用のキー/値ペア要素に格納できるようにし、初期化はそれらをすべてリスト内の「次の空き」インデックスと一緒にチェーンしますコンテクスト。これにより、新しいペアを挿入するときに、リストから空き要素を検索する必要がなくなります。フリーキー/値ペアオブジェクトが必要な場合は、「next free」に格納されているインデックスを新しい要素に使用し、「nextfree」を要求されたばかりのフリーオブジェクトに格納されているチェーンインデックスに設定します。ペアを破棄する場合は、「next free」値を解放されたオブジェクトのチェーンインデックスにコピーし、解放されたオブジェクトのインデックスを「nextfree」の新しい値として設定するだけです。

インデックス配列は、メモリ内のキー/値構造へのポインタを使用して実装することもできます。この場合、フリーオブジェクトリストの「次のフリー」リンクとチェーンリンクもポインタになります。

上記のスキームは、小さなキー/値セットのサイズと単純な値型に適しています。

于 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

注意点の1つは、ワードはネイティブ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 に答える