Реализация отображений при помощи векторов

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

structIntegerPairVector

{

intm_nUsed;

intm_nAllocated;

structCell

{

intm_key;

intm_value;

};

Cell * m_pData;

};

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

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

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

Ниже представлена реализация отображения, основанная на предложенной идее:

#include "integer_map.hpp"

#include "integer_vector.hpp"

#include <cassert>

// Структура для отображения из двух отдельных векторов для ключей и значений

structIntegerMap

{

IntegerVector m_keys;

IntegerVector m_values;

};

// Создание объекта-отображения

IntegerMap * IntegerMapCreate ()

{

// Создаем объект-отображение в динамической памяти

IntegerMap * pMap = newIntegerMap;

// Инициализируем оба внутренних вектора

IntegerVectorInit( pMap->m_keys );

IntegerVectorInit( pMap->m_values );

// Возвращаем объект во внешний код

returnpMap;

}

// Уничтожение объекта-отображения

voidIntegerMapDestroy ( IntegerMap * _pMap )

{

// Освобождаем ресурсы внутренних векторов

IntegerVectorDestroy( _pMap->m_keys );

IntegerVectorDestroy( _pMap->m_values );

// Удаляем сам объект-отображение

delete_pMap;

}

// Очистка отображения

voidIntegerMapClear ( IntegerMap & _map )

{

// Очищаем оба внутренних вектора

IntegerVectorClear( _map.m_keys );

IntegerVectorClear( _map.m_values );

}

// Проверка отображения на пустоту

boolIntegerMapIsEmpty ( constIntegerMap & _map )

{

// Отображение пусто, если пусты внутренние векторы.

// Поскольку векторы модифицируются всегда одновременно,

// достаточно проверить один из векторов на пустоту, например, вектор ключей

returnIntegerVectorIsEmpty( _map.m_keys );

}

// Вспомогательная функция для поиска позиции ключа в отображении

intIntegerMapFindKeyPosition ( constIntegerMap & _map, int_key )

{

// Ищем позицию ключа в векторе ключей путем полного перебора

for( inti = 0; i < _map.m_keys.m_nUsed; i++ )

if( _map.m_keys.m_pData[ i ] == _key )

// Позиция найдена

returni;

// Позиция не найдена

return-1;

}

// Проверка отображения на содержание указанного ключа

boolIntegerMapHasKey ( constIntegerMap & _map, int_key )

{

// Ключ есть в отображении, если поиск его позиции дает корректный ответ

returnIntegerMapFindKeyPosition( _map, _key ) != -1;

}

// Поиск значения по указанному ключу в отображении

intIntegerMapFind ( constIntegerMap & _map, int_key )

{

// Ищем позицию ключа в векторе ключей

intposition = IntegerMapFindKeyPosition( _map, _key );

// Ключ должен существовать!

assert( position != -1 );

// Используем найденную позицию для извлечения значения из вектора значений

return_map.m_values.m_pData[ position ];

}

// Вставка пары ключ-значение в отображение

voidIntegerMapInsertKey ( IntegerMap & _map, int_key, int_value )

{

// Ищем позицию ключа в векторе ключей. Возможно такой ключ уже существует

intposition = IntegerMapFindKeyPosition( _map, _key );

// Если такого ключа нет, добавляем ключ и значение в соответствующие вектора

if( position == - 1 )

{

IntegerVectorPushBack( _map.m_keys, _key );

IntegerVectorPushBack( _map.m_values, _value );

}

Else

// В противном случае обновляем значение по существующему ключу

_map.m_values.m_pData[ position ] = _value;

}

// Удаление элемента с указанным ключом из отображения

voidIntegerMapRemoveKey ( IntegerMap & _map, int_key )

{

// Ищем позицию ключа в векторе ключей

intposition = IntegerMapFindKeyPosition( _map, _key );

// Ключ должен существовать!

assert( position != -1 );

// Одновременно удаляем ключ и значение из векторов в найденной позиции

IntegerVectorDeleteAt( _map.m_keys, position );

IntegerVectorDeleteAt( _map.m_values, position );

}