Чисто доступ к массиву структур на основе значения

Question

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

Пример: в сети есть три других устройства с адресами 0x1, 0x2 и 0x3 (мы работаем на 0x0). Теперь мы хотим получить доступ к структуре данных, связанной с устройством 0x1, и предположим, что это таблица [0]. Проблема состоит в том, чтобы связать адрес (0x1) с индексом (0).

ПРИМЕЧАНИЕ. Сетевые адреса динамически назначаются другими частями программного обеспечения и являются не под моим контролем. Они также не гарантированно будут последовательными.

Каков самый чистый способ сделать это?

Самый интуитивный способ для меня, чтобы найти всю таблицу сравнения Address поле каждой записи с конкретным адресом (в данном примере 0x1), а затем возвращая индекс, но мне было интересно, если есть более подходящее способ сделать эту общую операцию. Что, кстати, вероятно, имеет собственное имя (динамическая структура данных?).

Answer 1

1) Быстрый, простой & грязный способ. Если адреса являются небольшими числами, вы можете просто составить таблицу поиска, такую ​​как:

const struct_ptr* TABLE[n] = 
{ 
    NULL, 
    &struct_this, 
    &struct_that, 
    NULL, 
    ... 
}; 

Где индекс соответствует адресу. Если адрес имеет соответствующую структуру, вы получаете указатель на структуру, иначе NULL.

Это самый быстрый способ, он имеет прямой доступ O (1). Но он отнимает немного памяти данных и не является реально выполнимым, если ваши адреса могут быть любыми номерами.

2) Сортировка таблицы поиска и двоичного поиска. Используйте это, если адреса представляют собой любые номера. В этом случае вам придется сделать таблицу поиска, состоящую только из указателей на существующие структуры, такие как:

const struct_ptr* TABLE [NUMBER_OF_EXISTING_STRUCTS] = 
{ 
    &struct_this, 
    &struct_that, 
    ... 
}; 

Каждой структура должна иметь член address и они должны быть добавлены к приведенной выше таблице перекодировки в отсортированный способ, самый низкий адрес. Затем вы можете выполнить двоичный поиск по таблице, используя функцию сравнения, которая сравнивает каждый элемент структуры address.Это довольно быстро, O (log n).

3) Hash table. Самая передовая альтернатива. Это лучше всего подходит для систем с огромным количеством данных и может также обрабатывать дубликаты. Время доступа почти детерминировано, близко к O (log n), но не совсем. Зависит от того, как вы реализуете «цепочку» и т. Д.

Answer 2

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

На cprogramming.com, относительно Hash tables:

Одним из самых больших недостатков языка как C является то, что нет Keyed массивов. В обычном массиве C (также называемом индексированным массивом) единственным способом доступа к элементу будет его номер индекса.

Поэтому я должен на самом деле сканировать массив для записи с этим адресом и получить от него индекс.