std :: mapをCに移植しますか？

Question

私はいくつかのC++コードをcに移植しています。 cでstd :: mapと実行可能なものは何ですか？ 私はcに相当するものがないことを知っています。

C++で：

std::map< uint, sTexture > m_Textures; 

はC：

これは私が使用して考えていますものです

typedef struct 
{ 
    uint* intKey; 
    sTexture* textureValue; 
} sTMTextureMap; 

は、その実行可能であるか、私はあまりマップを簡素化するのですか？テクスチャマップの目的を理解できなかった場合に備えて。

Answer 1

uthash "使いやすいC構造のハッシュテーブル"
via：http://en.wikipedia.org/wiki/Hash_table

Answer 2

マップに類似した機能を提供するC言語の標準ライブラリはありません。キーを介して要素にアクセスすることをサポートする何らかの形式のコンテナを使用して、独自のマップライクな機能を実装する必要があります。

Answer 3

確かに1つの可能な実装です。索引付けをどのように実装するのか、およびパフォーマンスにどのような影響があるかを考慮する必要があります。たとえば、intKeyリストをソートされたキーのリストにすることができます。キーを検索するとO（log N）時間になりますが、新しい項目を挿入するとO（N）になります。

これをツリー（std :: mapなど）として実装して、O（ログN）の挿入と参照を行うことができます。

もう1つの方法として、ハッシュテーブルとして実装する方法があります。ハッシュテーブルは、優れたハッシュ関数と十分な量のintKey配列を前提として、実行時のパフォーマンスが向上します。

dbopenを

Answer 4

男は、ファイル引数としてNULLを提供し、それがキー/値データのインメモリのみのコンテナになるでしょう。

同様のキー/バリュー機能（man dbm、SleepycatのBerkeleyDBのチェックアウト、いくつかの検索など）を持つさまざまなBerkeleyデータベースライブラリインターフェイスもあります。

Answer 5

あなたが選択することはできますが、実装することはできます。リンクリストアプローチを使用すると、挿入はO（1）になりますが、検索と削除はO（n）になります。赤黒の木のようなもっと複雑なものを使うと、平均的なパフォーマンスがはるかに向上します。

リンクリストはおそらく最も簡単です。そうでない場合は、適切にライセンスされた赤黒またはその他のタイプのツリーをインターネットから取得するのが最適なオプションです。あなた自身の赤黒のツリーを実装することはお勧めできません...私はこれを行い、再びそれをしたくないです。

あなたが質問しなかった質問に答えるには、C++からCへの移植が本当に必要なすべての利点を提供するかどうか再検討すべきでしょう。確かにそれが必要かもしれない状況がありますが、多くはありません。

Answer 6

多くのC実装は、tsearch（3）またはhsearch（3）をサポートしています。 tsearch（3）はバイナリツリーで、コンパレータコールバックを提供することができます。私はそれがあなたがstd :: mapに行くのと同じくらい近いと思う。ここで

はあなただけstd::mapの周りにCインタフェースをラップしていないのはなぜいくつかのC99のサンプルコード

#include <search.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 

typedef struct 
{ 
     int key; 
     char* value; 
} intStrMap; 

int compar(const void *l, const void *r) 
{ 
    const intStrMap *lm = l; 
    const intStrMap *lr = r; 
    return lm->key - lr->key; 
} 

int main(int argc, char **argv) 
{ 
    void *root = 0; 

    intStrMap *a = malloc(sizeof(intStrMap)); 
    a->key = 2; 
    a->value = strdup("two"); 
    tsearch(a, &root, compar); /* insert */ 

    intStrMap *find_a = malloc(sizeof(intStrMap)); 
    find_a->key = 2; 

    void *r = tfind(find_a, &root, compar); /* read */ 
    printf("%s", (*(intStrMap**)r)->value); 

    return 0; 
} 

Answer 7

ですか？つまり、自分のモジュールにいくつかのC++関数を書く：

typedef std::map<int, char*> Map; 

extern "C" { 

void* map_create() { 
    return reinterpret_cast<void*> (new Map); 
} 

void map_put(void* map, int k, char* v) { 
    Map* m = reinterpret_cast<Map*> (map); 
    m->insert(std::pair<int, char*>(k, v)); 
} 

// etc... 

} // extern "C" 

そして、あなたのCアプリにリンクしてください。

Answer 8

私はCでマップを実装しようとしている、それが空に基づいているに*

http://code.google.com/p/cstl/

それは進行中の作業ですが、マップは完了です。

http://code.google.com/p/cstl/source/browse/src/c_map.c

それは赤黒木に基づいて書かれています。