Porting std :: bản đồ đến C?

Question

Tôi đang chuyển một số mã C++ sang c. Một tương đương khả thi của std :: map in c? Tôi biết không có tương đương trong c.

Đây là những gì tôi đang nghĩ đến việc sử dụng:

Trong C++:

std::map< uint, sTexture > m_Textures; 

Trong c:

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

Có phải đó là khả thi hay tôi đơn giản hóa bản đồ quá nhiều? Chỉ trong trường hợp bạn không có được mục đích của nó là Texture Map.

Answer 1

uthash "bảng băm dễ sử dụng cho cấu trúc C".
qua: http://en.wikipedia.org/wiki/Hash_table

Answer 2

Không có thư viện chuẩn nào trong C cung cấp chức năng tương tự như bản đồ. Bạn sẽ cần phải triển khai chức năng giống như bản đồ của mình bằng cách sử dụng một số hình thức chứa có hỗ trợ truy cập các phần tử thông qua các khóa.

Answer 3

Đó chắc chắn là một triển khai có thể có. Bạn có thể muốn xem xét cách bạn sẽ triển khai lập chỉ mục và tác động hiệu suất nào sẽ có. Ví dụ, bạn có thể có danh sách intKey là danh sách các khóa được sắp xếp. Tìm kiếm một khóa sẽ là thời gian O (log N), nhưng chèn một mục mới sẽ là O (N).

Bạn có thể thực hiện nó dưới dạng cây (như std :: map), và sau đó bạn sẽ có O (log N) chèn và tra cứu.

Một giải pháp thay thế khác là triển khai bảng băm, có hiệu suất thời gian chạy tốt hơn, giả sử hàm băm tốt và mảng intKey đủ thưa.

Answer 4

man dbopen

Cung cấp NULL làm đối số tệp và nó sẽ là vùng chứa chỉ trong bộ nhớ cho dữ liệu khóa/giá trị.

Ngoài ra còn có các giao diện thư viện cơ sở dữ liệu Berkeley khác nhau với chức năng khóa/giá trị tương tự (dbm nam, kiểm tra BerkeleyDB từ Sleepycat, thử một số tìm kiếm, v.v.).

Answer 5

Bạn có thể triển khai nó theo cách bạn chọn. Nếu bạn sử dụng cách tiếp cận danh sách liên kết, việc chèn của bạn sẽ là O (1) nhưng việc truy xuất và xóa của bạn sẽ là O (n). Nếu bạn sử dụng một cái gì đó phức tạp hơn như một cây màu đỏ-đen, bạn sẽ có hiệu suất trung bình tốt hơn nhiều.

Nếu bạn tự mình triển khai danh sách liên kết, có thể dễ dàng nhất, nếu không, hãy lấy một số loại màu đỏ đen hoặc loại cây khác được cấp phép thích hợp từ internet sẽ là lựa chọn tốt nhất. Thực hiện cây đỏ-đen của riêng bạn không được khuyến khích ... Tôi đã làm điều này và không muốn làm điều đó một lần nữa.

Và để trả lời câu hỏi bạn không hỏi: có thể bạn nên xem xét lại xem việc chuyển sang C từ C++ có thực sự cung cấp tất cả các lợi ích bạn muốn hay không. Chắc chắn có những tình huống mà nó có thể cần thiết, nhưng không có nhiều.

Answer 6

Nhiều triển khai C hỗ trợ tsearch (3) hoặc hsearch (3). tsearch (3) là một cây nhị phân và bạn có thể cung cấp một cuộc gọi so sánh. Tôi nghĩ rằng đó là về gần như bạn đang đi để có được một std :: bản đồ.

Dưới đây là một số ví dụ mã 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

Tại sao bạn không chỉ quấn một giao diện C xung quanh std::map? Tức là viết một vài hàm C++ trong mô-đun riêng của chúng:

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" 

Và sau đó liên kết với ứng dụng C của bạn.

Answer 8

Tôi đã cố gắng thực hiện một bản đồ trong C, nó được dựa trên void *

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

Nó là công việc cơ bản dở dang, nhưng bản đồ là hoàn tất.

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

Được viết dựa trên cây đỏ đen.