Есть ли какой-либо сложный способ реализовать заданную структуру данных (набор уникальных значений) в C? Все элементы в наборе будут одного типа и есть огромная оперативная память.
Как я знаю, для целых чисел это можно сделать очень быстро'N'easy, используя массивы с индексированными значениями. Но я бы хотел иметь очень общий тип данных Set. И было бы неплохо, если бы набор мог включить себя.
Существует несколько способов реализации функций набора (и карты), например:
Поскольку вы упомянули массивы с индексированными значениями, попробуйте использовать хэш-подход, который строит естественно поверх метода массива с индексированным значением.
Остерегайтесь преимуществ и недостатков основанных на хеше или на основе дерева подходов.
Вы можете создать хэш-набор (специальный случай хеш-таблицы) указателей на хеширование POD s, цепочка, внутренне представленная как фиксированный размер массив ведер hashables, где:
Благодаря большому объему памяти в вашем распоряжении вы можете значительно увеличить свой массив ведер и в сочетании с хорошим хэш-методом резко уменьшить вероятность collision, обеспечивая практически постоянную производительность.
Вам нужно будет реализовать:
contains/insert/remove.Вы также можете использовать открытую адресацию в качестве альтернативы поддержанию и управлению ковшими.
Наборы обычно реализуются как несколько разновидностей двоичного дерева . Красные черные деревья имеют хорошую производительность в худшем случае.
Они также могут быть использованы для создания map, чтобы разрешить поиск ключей/значений.
Этот подход требует определенного порядка упорядочивания элементов набора и значений ключа на карте.
Я не уверен, как вы могли бы управлять набором, который мог бы содержать себя с использованием двоичных деревьев, если вы ограничиваете членство в определенных типах в C... сравнение таких конструкций может быть проблематичным. Вы могли бы сделать это достаточно легко на С++.
Если максимальное количество элементов в наборе (мощность базового типа данных) достаточно мало, вы можете захотеть использовать простой старый массив бит (или что бы вы не назвали их на своем любимом языке).
Тогда у вас есть простая проверка членства: бит n равен 1, если элемент n находится в наборе. Вы даже можете считать "обычные" члены от 1 и только сделать бит 0 равным 1, если набор содержит сам.
Этот подход, вероятно, потребует какой-то другой структуры данных (или функции) для перевода из типа данных члена в позицию в битовом массиве (и обратно), но он выполняет базовые операции набора (объединение, пересечение, тест принадлежности), разница, вставка, удаление, принудительный) очень очень легко. И он подходит только для относительно небольших наборов, вы бы не хотели использовать его для наборов 32-битных целых чисел, которые я не предполагаю.
Путем получения универсальности в C является void *, поэтому вы все равно будете использовать указатели, а указатели на разные объекты уникальны. Это означает, что вам нужна карта хэша или двоичное дерево, содержащее указатели, и это будет работать для всех объектов данных.
Недостатком этого является то, что вы не можете вводить rvalues самостоятельно. У вас не может быть набора, содержащего значение 5; вам нужно назначить 5 переменной, что означает, что она не будет соответствовать случайному 5. Вы можете ввести ее как (void *) 5, и для практических целей это, скорее всего, будет работать с малыми целыми числами, но если ваши целые числа могут попасть в большую достаточно размеров, чтобы конкурировать с указателями, это имеет очень небольшую вероятность сбоя.
И это не работает со строковыми значениями. Учитывая char a[] = "Hello, World!"; char b[] = "Hello, World!";, набор указателей найдет a и b для разных. Вероятно, вы захотите хэш-значения, но если вас беспокоят хеш-коллизии, вы должны сохранить строку в наборе и сделать strncmp() для сравнения сохраненной строки с пробной строкой.
(Аналогичные проблемы с числами с плавающей запятой, но попытка представить числа с плавающей запятой в наборах - это, во-первых, плохая идея.)
Следовательно, вам, вероятно, понадобится тегированное значение, один тег для любого типа объекта, один для целочисленного значения и один для строкового значения и, возможно, больше для разных значений. Это сложно, но выполнимо.