Сап, прогач. Появилась идейка запилить для языка си подобие библиотеки STL из крестов. Чисто по приколу. Стек, лист, вектор, дек, очередь уже в принципе есть. Остается вопрос, который мучает меня уже долго - не могу въехать как лучше реализовать множество и ассоциативный массив, чтобы их сложность не превышала сложность их реализаций из СТЛ. Можешь подскажешь что-нибудь, анон? Вроде где-то видел реализацию с хеш-таблицей, но никак не могу просечь, как лучше это реализовать. Пикрандом
бамп
>>790634 (OP)начинай со словаря(ключ значение), из него все твои новые коллекции легко и непринужденно вытекут.
>>790644нахуй пошёлбамп
>>790644словарь, как я понял - это и есть ассоциативный массив. Т.е. мап из СТЛ. В этом и проблема, как их реализовать. Сет пытался реализовать с помощью бинарного дерева, но там вообще полная дичь выходит.
>>790646забей на деревья, хэш-таблица - это единственный правильный вариант.
>>790651а можно поподробнее про хэш? Гуглить гуглил, но для себя на пальцах что либо понятное я не особо отыскал. Да, я наверно чуточку туповат...
>>790651Тут два варинта, либа ебать мозг с хэн функцией которая не даст коллизий, либо тупо коллизии складывать в в связанный список, как во многих языках реализовано.
>>790652Все просто тебе нужна такая хэш функция которая даст от ключа адресс в массиве в котором будет значение, но такие функция обсираются на малом наборе элементов, поэтому можно слегка принеберечь константным поиском элемента и вместо значения хранить связанный список, где по значению уже будет поиск.
>>790655ну и естественно, там будет оверхеды на перестройку массива, без этого никуда.
>>790655то есть я предположу, что сам элемент множества будет примерно такимtypedef struct elem_{void data;struct elem_ next;};И будет массив из таких элементов, где будет открытое хеширование. Так? Сложность не будет вылезать за O(Log(n))?
>>790657в самом худщем случае ты получешь O(n) когда хэш таблица выродится в список, но это при самой ебнутой хэш функции будет, которая всегда будет возращать одно и тоже.
>>790658но вставка элемента всегда будет O(1), такчто гуляем.
>>790659Нет, нихуя не будет, мы не хотим дубликатов, такчто по списку придется пройтись, O(n) при всех раскладах
>>790661бля, пишите пиздатую хэш-функцию и этой хуйни не будет никогда.
>>790662деление ключа на длину массива не прокатит?
>>790667ты встретишь коллизии на все ключах по модулю длины массива, тут нужно поизящнее.
>>790667на самом деле гляньте реалтзацию в джаве, там хорошая хэш функция с логикой перестройки массива, не изобретайте велосипед
Посмотри как сделаны эти структуры данных в ядре Linux. Я думаю, ты найдешь много чего интересного для себя там.
>>790634 (OP)>множествоБери любое сбалансированное дерево. Проще всего красно-черное.
>>790787Охуеть. Интрузивные списки нынче что-то интересное и заслуживающее особого внимания.
>>790651Как ты определил, что хэш-таблицы "правильнее" деревьев?
В Джаве есть HashSet - динамически расширяемая хэш-таблица (рехеширование когда load factor > 0.75)и TreeSet - реализация на деревьях. Он еще и Sorted.
>>791849А HashSet - это HashMap, у которого одно и то же значение для всех ключей, если они входят в множество.
>>791849Тут должны были быть TreeMap и HashMap - описка
glib, там уже реализовано
>>790634 (OP)stl - библиотека реализующая типонезависимость посредством контейнеров на шаблонах и обобщенные алгоритмы, которые можно применить над любыми данными-контейнерамикакими средствами ты планируешь сделать это в си? что используешь - на макросах, на void, или комбинация, будешь ли делать variant на объединениях, будешь ли использовать идеи компонентного программирования (как в com или gtk), эмулируя интерфейсы, будешь ли эмулировать делегаты или будешь делать на голых указателях на функцию? или вообще сделаешь ооп-оберткой, сделав v-table?
>>790634 (OP)Ну там два типа хранения ключей: Hash и Sorted.В первом случае для поиска ключей используется хеш-таблица, во втором случае - бинарное сбалансированное дерево поиска (например, АВЛ или красно-черное). Для первого случая среднее время поиска O(1), но худшее - O(n). Для второго среднее и худшее - O(log n). Преимущество первого варианта в том, что ключи не обязаны реализовывать Comparable.
>>790634 (OP)Еще один велосипедист.
>>793668Полезно для обучения же.
