Ассоциативный массив на С, где ключ-строка

GLIB?

С помощью это штуки можно организовать массив с ключем по строке, встаку/удаление/поиск элементов?

можно: http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html

упомянутый уже glib и классический #include <search.h> с его hsearch tsearch :)

Взять sys/tree.h из BSD.

стандартнейшая задача
получаеш с строки - через какую нить функцию ее хеш
и по хешу заносиш ее в базу

а база - массив указателей на список элементов в один и темже хешом

http://uthash.sourceforge.net/ ?

Если lookup существенно преобладает над insert'ом, можно обойтись динамическим массивом с пузырьком и bsearch. А тащить glib ради хеша.. ну не знаю, есть варианты попроще.

Про GLib на ibm гдето в статьях или где там ищи, там несколько статей

Посмотри здесь (red-black trees): http://sglib.sourceforge.net

Посмотрел здесь http://uthash.sourceforge.net/userguide.html и вроде все устраивает: сделано как *.h-файл, в котором прописан ряд макросов. Попробовал-никакой головной боли. Хэширует по строкам (не нужно самому заморачиваться с операциями сравнения), по целым числам и указателям.

Что можете сказать о надежности?
Мож кто использовал?

rtfm hashing, hash table и т.п.

А что, уже нереально сложно написать красно-черное дерево, 2-3 дерево или хотя бы обычное несбалансированное бинарное дерево поиска?

Что можете сказать о надежности?
Мож кто использовал?

да вроде довольно таки стабильная либа, просто работает

А что, уже нереально сложно написать красно-черное дерево, 2-3 дерево или хотя бы обычное несбалансированное бинарное дерево поиска?

если не стоит задача научиться - это лишнее, проще взять проверенный вариант

Да. Но на то, чтобы получить достойный ответ на ЛОРе и использовать его на практике, уйдет намного больше времени, чем на написание меньше 50 строк кода обычного или рандомизированого бинарного дерева поиска. Поэтому в данном случае от уже написаного решения профита не будет.

PS. Решения данной задачи легко нагугливаются, а уже готовые реализации бинарных деревьев и хэшей легко ищутся в pastebin и gist.

Если это серверная реализация то я стараюсь использовать что-то уже давно проверенное, типа glib. Если будет потом время то можно переписать. Но получать баги внутри хеша, тем более тратить время на его написание и смотреть оптимальным методом написано или нет - это уж слишком.

А вообще вчем проблемма glib статиком вкомпитить и отстрипать потом?

Что можете сказать о надежности?

Мож кто использовал?

Там нужно круто извратится, чтобы сделать эту штуку ненадежной...

Если массив редкоменяющийся - то тупо qsort и половинный поиск.

Второй вариант - считаем хеш (ну например, ксорим по 4 байта строки, затем берём остаток от деления на 1000). Соответственно, строим массив из 1000 элементов. в каждой ячейке - связанный список строк (в твоем варианте - несколько десятков строк).

Кароче, сильно зависит от задачи и требуемого быстродействия.

http://ru.wikipedia.org/wiki/Berkeley_DB ?

Да. Но на то, чтобы получить достойный ответ на ЛОРе и использовать его на практике, уйдет намного больше времени, чем на написание меньше 50 строк кода обычного или рандомизированого бинарного дерева поиска. Поэтому в данном случае от уже написаного решения профита не будет.

поэтому надо задавать вопрос заранее :) а пока заниматься текущими делами

просто иногда ломает велосипед писать, ну ладно там какое-нибудь хитро-специальное дерево, но когда 100500 раз реализованный велосипед.... короче, можно boost переписывать, но проще использовать :) хотя, это зависит

А вообще вчем проблемма glib статиком вкомпитить и отстрипать потом?

Это не ко мне, а к ТСу. Я бы тоже заюзал glib.

Но получать баги внутри хеша, тем более тратить время на его написание и смотреть оптимальным методом написано или нет - это уж слишком.

Раз критично к производительности в худшем случае, то зачем выбирать именно хэш-таблицы? Они не дают никакой гарантии производительности (в худшем случае сложность поиска O(N), что очень плохо). Я бы юзал красно-черные деревья или другие сбалансированные деревья (гарантируется, что в худшем случае сложность поиска O(log(N))).

Как уже сказали - бинарный поиск. Посмотри реализацию. Это раз. Во вторых - хэшмапа. Тоже можно несложным образом сделать. В третьих - специально для тебя могу подсказать книгу: Исскуство программирования на C. Думаю там ты найдешь что тебе надо и в простом для понимания языке.

поэтому надо задавать вопрос...

Гуглу. На поиск готового кода в данном случае тратится меньше времени, чем, я думаю, ушло на написание первого поста. И вариант лучше любого велосипеда.

гугл не всегда объективен и может рассказать о своём опыте

в любом разе коллективный разум, вне всякого сомнения, обладает некоторой инерцией, но позволяет получить более репрезентативную выборку

это означает что про hello world спрашивать неэффективно, но про что-то сложное могут и подсказать довольно таки ловко :)

а ещё есть «срач», в результате которого вообще самые невероятные штуки могут выясниться

Сделай биндинги к питону, там есть хеш-таблицы.

glib http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html

gnulib http://www.gnu.org/s/gnulib/MODULES.html#module=hash

CCAN http://ccan.ozlabs.org/info/htable.html

GHashTable

чем Вас плюсы ты не устраивают?