Iterator trong ngôn ngữ C

Question

Có ai đã cố gắng cung cấp hỗ trợ cho Iterator trong C. Tôi không tìm kiếm chính xác C++ STL :: Iterator nhưng hỗ trợ tối thiểu cho một số ý tưởng để bắt đầu sẽ là điểm tốt cho tôi.

Tôi đang phát triển thư viện chứa giống như stl nhưng với hỗ trợ tối thiểu, Vì vậy, tôi cần loại chức năng này trong các vùng chứa đó.

Tôi mong muốn xác định một số bộ giao diện thuật toán nhất định (tương tự như STL). Ví dụ, sắp xếp, sẽ bắt đầu và kết thúc iterator và nên làm việc với bất kỳ container.

Answer 1

Nếu bạn được phép sử dụng mã GPL trong dự án của mình, hãy xem GLib thay vì phát minh lại bánh xe. GLib cũng cho phép phát triển một cách khá di động ở cấp mã nguồn. Lưu ý rằng nếu bạn sử dụng điều này, bạn phải phát hành mã cũng theo GPL.

Hãy xem g_list_first() và g_list_next() thực hiện chức năng của trình lặp trong danh sách. Thậm chí còn có một g_list_foreach() `

http://library.gnome.org/devel/glib/stable/glib-Doubly-Linked-Lists.html

Answer 2

Bạn cần có cách chuẩn hóa số tăng thêm trình lặp. Trong C++, đó chỉ là quá tải operator++(). Vùng chứa của bạn cần một hàm được liên kết trả về một con trỏ tới phần tử tiếp theo. Hàm incrementing này sẽ cần phải được chuyển như một con trỏ tới bất kỳ thường trình tổng quát nào có thể chấp nhận một trình lặp trong thư viện của bạn.

Ví dụ, Nếu tôi muốn viết một hàm trả về yếu tố max từ container, tôi không chỉ cần các chức năng so sánh (tương đương với operator<()), tôi cần một chức năng iterator-incrementing (tương đương với operator++()).

Vì vậy, đảm bảo rằng tôi có thể chấp nhận một con trỏ đến hàm gia tăng của bạn là yêu cầu quan trọng.

Answer 3

Hãy nhìn vào danh sách liên kết. Một nút bao gồm một "bên cạnh" con trỏ mà ta có thể sử dụng để lặp qua danh sách, theo cách tương tự để lặp C++:

typedef struct Node { 
    ...                                       
    struct Node *next;                                       
} Node; 

... 

Node *iter, *firstNode, *nodeList; 

/* set firstNode and populate nodeList */ 

for (iter = firstNode; iter != NULL; iter = iter->next) { 
    /* iterate through list */ 
} 

Đó không phải là C++ iterator, nhưng hy vọng điều này sẽ cho một ý tưởng về một cách tiếp cận điều này trong C.

Answer 4

Con trỏ có thể phục vụ chức năng này. container.begin() thật dễ dàng và container.end() không mất quá nhiều công sức.

Cân nhắc

Value array[N]; 
typedef Value* iterator; 
iterator array_begin(Value a[]){ return &a[0];} 
iterator array_end(Value a[], int n){ return &a[n];} 
iterator array_next(iterator i) { return ++i;} 

iterator it = array_begin(a); 
iterator end = array_end(a,N); 
for (;it < end; it=array_next(it)) 
{ 
    Value v = *it; 
} 

Đối với container khác như danh sách, bạn có thể sử dụng NULL như kết thúc. Tương tự cho cây, nhưng chức năng next cần duy trì trạng thái. (hoặc iterator là một con trỏ tới một cấu trúc với trạng thái được cập nhật bởi các cuộc gọi đến next(it)).

Answer 5

Tôi đã tìm thấy một dự án nguồn mở đang triển khai STL bằng ngôn ngữ C.

http://sourceforge.net/projects/tstl2cl/

Answer 6

Đây là những gì tôi đã đưa ra:

typedef struct PWDict PWDict; 
typedef struct PWDictIterator PWDictIterator; 

typedef struct PWDictImplementation 
{ 
    PWDict *(*create)(const struct PWDictImplementation *impl, size_t elements); 
    void (*destroy)(PWDict *dict); 

    unsigned int (*size)(const PWDict *dict); 
    unsigned int (*sizeInBytes)(const PWDict *dict); 

    int (*get)(const PWDict *dict, const char *key, char *output, size_t size); 
    int (*set)(PWDict *dict, const char *key, const char *value); 

    PWDictIterator *(*iteratorCreate)(const PWDict *dict); 
    void (*iteratorBegin)(PWDictIterator *it); 
    void (*iteratorEnd)(PWDictIterator *it); 
    void (*iteratorDestroy)(PWDictIterator *it); 

    const char *(*iteratorGetKey)(const PWDictIterator *it); 
    const char *(*iteratorGetValue)(const PWDictIterator *it); 
    int (*iteratorSetValue)(PWDictIterator *it, const char *value); 
    void (*iteratorNext)(PWDictIterator *it); 
} 
PWDictImplementation; 

struct PWDict 
{ 
    PWDictImplementation *impl; 
}; 

struct PWDictIterator 
{ 
    PWDict *dict; /* get iterator implementation from the dict implementation */ 
}; 

PW là tiền tố dự án của chúng tôi. Chúng tôi chỉ cần một từ điển (string-string map) như container.