как хранить и искать для ipv4 ipaddress в c более эффективно

Question

У меня есть такое требование, как эффективная структура данных в c должна принимать в качестве входных данных адрес ipv4 и сохранять его, осуществлять поиск в этом хранимом структуре данных по запросу. мы можем преобразовать ipaddress в строку и сохранить его в структуре данных и проверить его существование? если да, то как мы можем этого добиться! Можете ли вы дать мне ваши ценные материалы, чтобы продолжить.

спасибо заранее.

Answer 1

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

Лично я бы использовал массив во многих случаях.Это означает, что вставка является более сложной (так как вам нужно скопировать элементы выше позиции вставки на 1, но это относительно быстро (пока вы не начнете говорить о тысячах записей).

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

Answer 2

Вы, вероятно, можете реализовать набор и использовать его.

Вы также можете создать своего рода дерево, в котором каждый узел содержит октет и имеет до 256 дочерних элементов (которые являются следующим октетом).Корень будет просто иметь указатели на первые наборы октетов.

Другой вариант - хранить их как целые числа без знака в BST или что-то в этом роде.

Answer 3

IP-адрес составляет 4 октета. Октет состоит из 8 битов, то есть байтов, поэтому вы можете хранить IP-адрес в 4 байта или int на 32-битных компьютерах, если используемая вами реализация имеет 32-битный int.

Answer 4

Если вам нужно хранить и искать множество IP-адресов, вы можете использовать radix tree .

Я считаю, что ядро ​​Linux использует свой собственный вариант radixдревовидная структура для его IP-кода, такого как таблицы маршрутизации.Возможно, вам захочется взглянуть на него в поисках идей.

Если у вас мало адресов или вы просто хотите что-то простое, используйте хэш-набор.

Если это для реального приложения и вы хотите бытьЗаглядывая вперед, вы должны включить поддержку адресов IPv6.С течением времени все больше компьютерных систем каждый год будут использовать адресацию IPv6 с адресами IPv4 NAT только в качестве резервной копии.