Простая реализация C отображения от одного символа к указателю - PullRequest
4 голосов
/ 08 декабря 2011

У меня есть опыт программирования на языках более высокого уровня, и я начал программировать на простом C пару недель назад (по академическим соображениям).Я хочу реализовать структуру данных что-то вроде map<char,myStruct*>.

Если это не достаточно ясно: я хочу "отображение" для каждого возможного SINGLE char на указатель на структуру, которую я определяю где-тоостальное.Если бы был способ обеспечить, чтобы никакие 2 char s не могли указывать на один и тот же struct (без проверки каждого другого char при вставке нового элемента на карту), который был бы аккуратным, но это не является строго необходимым,Мне также нужно иметь возможность удалять пары с карты и заново вставлять пары с одним и тем же ключом, но разными указателями.

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

Тем не менее, я не смог придумать альтернативырешения (учитывая, что я новичок в C, не удивительно).Буду признателен за любые, пусть даже смутные, предложения в правильном направлении.

Ответы [ 3 ]

5 голосов
/ 08 декабря 2011

Как вы говорите (и как предложил комментатор), проще всего сделать массив со статическим размером, равным максимальному значению символьного типа данных:

#include <limits.h>
void * mapping[1u << CHAR_BIT];

Предполагая 64-битные указатели и 8-битные char с, это заняло бы 8 * 256 = 2048 байт памяти для всей карты (исключая, конечно, "пользовательские данные", которые вы храните).Для программы, работающей в 64-битной системе, 2 КБ памяти тривиальны, и простота реализации и скорость, которую вы получаете от этого, на мой взгляд, должны сбалансировать потраченную впустую память.

Самая простая вещьчтобы сделать, если вы все еще хотите ограничить «физический» размер массива, нужно было бы хешировать один символ, но затем вам нужно начать разбираться с коллизиями хешей, что сразу усложняет задачу.

Вы можете сделатьчто-то вроде:

struct ValueChain
{
  struct ValueChain *next;
  void *value;
  char key;
}

#define MAP_SIZE 127 /* This should be prime. */
struct ValueChain* mapping[MAP_SIZE];

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

Вы можете дополнительно сжать его, выполнив, например,

#define MAP_SIZE 31
struct ValueChain mapping[MAP_SIZE];

Здесь каждое значение в массиве является полным ValueChain "заголовок списка ", а не просто указатель на один.На 64-битной машине это, вероятно, использовало бы около 558 байтов для массива mapping, но вам не нужно было бы делать какие-либо динамические выделения, пока вы не обнаружите коллизию.

Хэширование для них может быть простоconst char key = myChar % MAP_SIZE; в первом приближении, я думаю.

0 голосов
/ 08 декабря 2011
struct myStruct array[1u << CHAR_BIT];

#define uchar_to_mystruct_ptr(c) (c >=0 && c < (1u << CHAR_BIT) ? &array[c] : NULL)
0 голосов
/ 08 декабря 2011

Я предполагаю, что ваш ключ является строкой.

Ну ... Если вам не нужно реализовывать это самостоятельно, просто не .

Теоретически это не так сложно.

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

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

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

...