Переход от C ++ к C: альтернатива std :: map?

Question

Я ищу минималистичную альтернативу для std :: map , которая бы входила в драйвер ядра Windows, поэтому он должен быть достаточно быстрым .. ожидается, что он будет относительно небольшим (~ 200 в рабочем наборе) ) количество клавиш и большое количество вставок.

В поисках решения, которое может снизить стоимость поиска по ключевым словам.

Answer 1

Уже сделано для вас.

См. Вызовы RtlXxxGenericTable и RtlXxxGenericTableAvl.

• RtlInitializeElementGenericTable
• RtlDeleGenteRtlEnumerateGenericTable
• RtlEnumerateGenericTableWithoutSplaying
• RtlGetElementGenericTable
• RtlInsertElementGenericTable
• RtlNumberGenericTableElementsAvl

Answer 2

В прошлом, для карт с менее чем несколькими тысячами объектов, я обнаружил, что создание std :: vector, отсортированного по значению ключа, которое затем ищется с помощью бинарного поиска, значительно быстрее, чем с использованием std: :. карта

Answer 3

Вы также можете реализовать семантику std::map в Си.Только то, что оно не будет template.

Вот начало:

struct KeyValuePair
{
   KeyType key;
   ValueType value;
};

struct Map
{
   KeyValuePair *list; //it can be linkedlist as well
};

//these are the interfaces which operate on map
void Insert(Map * map, KeyType key, ValueType value);
void Update(Map * map, KeyType key, ValueType value);
int Find(Map * map, KeyType key, ValueType *outValue);

//Implement Get in terms of Find
ValueType Get(Map * map, KeyType key)
{
     ValueType value;
     Find(map, key, &value);
     return value;
}

Answer 4

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

Answer 5

Реализация карты STL - это красно-черное дерево, я верю

http://en.wikipedia.org/wiki/Map_%28C%2B%2B%29

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Answer 6

Если вам нужна простая реализация словаря в C, забавнее реализовать словарь в C однажды ... но у нас не всегда есть время это сделать.

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

Answer 7

Вам понадобятся два сопутствующих массива в C: один для ключей, другой для значений. Было бы полезно, если бы вы могли инкапсулировать два, чтобы пользователи могли придерживаться семантики сопоставления.