Итератор на языке Си

Question

Кто-нибудь пытался обеспечить поддержку Iterator в C. Я не ищу точный C ++ STL :: Iterator, но минимальная поддержка какой-либо идеи для запуска была бы хорошим моментом для меня.

Я занимаюсь разработкой библиотеки контейнеровто же самое, что и stl, но с минимальной поддержкой, поэтому мне нужны такие функции в этом контейнере.

Я с нетерпением жду определения определенных наборов интерфейсов алгоритмов (аналогично STL).Например, sort, который будет принимать начальный и конечный итератор и должен работать с любым контейнером.

Answer 1

Указатели могут выполнять эту функцию.container.begin() легко, а container.end() не требует много работы.

Рассмотрим

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;
}

Для других контейнеров, таких как списки, вы можете использовать NULL в качестве конца.То же самое для деревьев, но функция next должна поддерживать состояние.(или итератор - это указатель на структуру, состояние которой обновляется вызовами next(it)).

Answer 2

Посмотрите на связанные списки. Узел содержит указатель «следующий», который можно использовать для перебора списка, аналогично итераторам С ++:

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 */
}

Это не итератор C ++, но, надеюсь, это дает представление о том, как подойти к этому в C.

Answer 3

Если вам разрешено использовать код GPL в вашем проекте, взгляните на GLib вместо того, чтобы заново изобретать колесо.GLib также позволяет развиваться на портативном уровне на уровне исходного кода.Обратите внимание, что если вы используете это, вы должны выпустить код также под GPL.

Посмотрите на g_list_first() и g_list_next(), которые реализуют функциональность итератора в списке.Существует даже g_list_foreach () `

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

Answer 4

Вот что я придумал:

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 - префикс нашего проекта.Нам просто нужен был словарь (строка-строка) как контейнер.

Answer 5

Вам понадобится стандартизированный способ увеличения итератора.В C ++ это просто перегруженный operator++().Вашему контейнеру нужна связанная функция, которая возвращает указатель на следующий элемент.Эта инкрементная функция должна передаваться как указатель на любую обобщенную подпрограмму, которая может принять итератор в вашей библиотеке.

Например, если я хочу написать функцию, которая возвращает max элемент из контейнера, мне нужна не только функция сравнения (эквивалент operator<()), мне нужна функция, увеличивающая итератор (эквивалент operator++()).

Таким образом, гарантируя, что я могу принятьуказатель на вашу функцию приращения является ключевым требованием.

Answer 6

Я нашел один проект с открытым исходным кодом, который представляет собой реализацию STL на языке C.

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