Простейшая реализация отображений при помощи массивов

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

Допустим, имеется набор данных об избирательных округах. В Украине насчитывается 225 избирательных округов, каждый из которых имеет уникальный номер. Может потребоваться найти информацию о конкретном округе, зная его номер. В качестве ключей здесь выступают номера округов, а в качестве значений - описывающие структуры. Такой случай подходит под реализацию при помощи массивов, поскольку номера могут быть естественно использованы как индексы массивов. Кроме того, будут задействованы все номера в интервале от 1 до 225 включительно.

Пусть имеется структура, описывающая информацию о конкретном округе:

structVotingDistrict

{

shortm_districtNumber;

intm_votersCount;

char* m_locationDescription;

};

А информация обо всех округах хранится в виде массива указателей на объекты для каждого округа:

const intTOTAL_DISTRICTS_COUNT = 255;

VotingDistrict * g_districts[ TOTAL_DISTRICTS_COUNT ] ;

Чтобы заполнить данные о конкретном округе, следует обратиться к соответствующей ячейке массива по номеру округа (со смещением, т.к. массивы индексируются начиная с 0, а округа нумеруются с единицы):

voidaddDataAboutDistrict (

short_districtNumber

, int_votersCount

, const char* _locationDescription

)

{

assert( _districtNumber > 0 && _districtNumber <= TOTAL_DISTRICTS_COUNT );

intdistrictIndex = _districtNumber - 1 ;
assert( ! g_districts[ districtIndex ] );

VotingDistrict * pDistrict = newVotingDistrict;

pDistrict->m_districtNumber = _districtNumber;

pDistrict->m_votersCount = _votersCount;

size_t descriptionLength = strlen( _locationDescription );

pDistrict->m_locationDescription = new char[ _descriptionLength + 1 );

strcpy( pDistrict->m_locationDescription, _locationDescription );

g_districts[ districtIndex ] = pDistrict;

}

Теперь, чтобы получить информацию об интересующем округе достаточно обратиться к массиву, использовав номер округа как индекс:

shortdistrictNumber = 168;

VotingDistrict * pDistrict = g_Districts[ districtNumber - 1 ];

Если информации об округе еще не введено, массив будет содержать нулевой указатель. Если необходимо удалить информацию об округе, достаточно удалить объект в соответствующей ячейке массива и обнулить данную ячейку.

В такой структуре в качестве ключей иногда можно использовать перечисляемые типы, реализуемые в языке C как целые числа. Такие типы удобны для представления фиксированного набора значений, естественного для предметной области. Значения литералов-перечислений можно не указывать, по умолчанию, компилятор назначает значения 0, 1, 2, …, что также подходит для индексирования массивов. Например, по ключу-континенту, реализованному в виде перечисления:

enumContinents

{

Europe // 0

, Asia // 1

, Africa // 2

, NorthAmerica // 3

, SouthAmerica // 4

, Australia // 5

, ContinentsTotal // 6 - обозначает количество литералов в перечислении

};

могут храниться данные о текущей численности населения:

intg_populationByContinent[ ContinentsTotal ];

Соответственно, если появляются новые данные переписи населения Южной Америки, их можно внести в программу следующим образом:

g_populationByContinent[ SouthAmerica ] = 400103516;

Получить суммарную численность населения Австралии и Африки можно так:

intx = g_populationByContinent[ Australia ] + g_populationByContinent[ Africa ];

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

Может существовать ряд факторов, при которых отображение нельзя реализовать в виде подобного массива:

• в качестве ключей выступают типы, отличные от целых чисел, например, строки ;
• в области значений не существует значения “не определено”;
• ключи-числа слишком большие для создания массива, используются не подряд.

Однако, если таких препятствий не существует, предложенное упрощение может быть очень эффективным.

Интерфейс множеств

Ниже представлен заголовочный файл с интерфейсом объекта-множества целых чисел:

#ifndef _INTEGER_SET_HPP_

#define _INTEGER_SET_HPP_

// Форвардное объявление структуры-множества

structIntegerSet;

// Создание объекта-множества

IntegerSet * IntegerSetCreate ();

// Уничтожение объекта-множества

voidIntegerSetDestroy ( IntegerSet * _pSet );

// Очистка множества

voidIntegerSetClear ( IntegerSet & _set );

// Проверка множества на пустоту

boolIntegerSetIsEmpty ( constIntegerSet & _set );

// Возврат количества элементов в множестве

intIntegerSetSize ( constIntegerSet & _set );

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

boolIntegerSetHasKey ( constIntegerSet & _set, int_key );

// Добавление указанного ключа в множество

voidIntegerSetInsertKey ( IntegerSet & _set, int_key );

// Удаление указанного ключа из множества

voidIntegerSetRemoveKey ( IntegerSet & _set, int_key );

// Объединение двух множеств - результат в третьем множестве

voidIntegerSetUnite ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet );

// Пересечение двух множеств - результат в третьем множестве

voidIntegerSetIntersect ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet );

// Разница между двумя множествами - результат в третьем множестве

voidIntegerSetDifference ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet );

// Симметрическая разница между двумя множествами - результат в третьем множестве

voidIntegerSetSymmetricDifference ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet );

#endif // _INTEGER_SET_HPP_

Простая тестовая программа на основе таких множеств представлена ниже:

#include "integer_set.hpp"

#include <cassert>

intmain ()

{

// Создаем первое множество и помещаем в него ключи 10 и 20

IntegerSet * pSet1 = IntegerSetCreate();

IntegerSetInsertKey( * pSet1, 10 );

IntegerSetInsertKey( * pSet1, 20 );

// Создаем второе множество и помещаем в него ключи 20 и 30

IntegerSet * pSet2 = IntegerSetCreate();

IntegerSetInsertKey( * pSet2, 20 );

IntegerSetInsertKey( * pSet2, 30 );

// Создаем пересечение множеств - ожидаем наличия 1 элемента 20

IntegerSet * pSetI = IntegerSetCreate();

IntegerSetIntersect( * pSet1, * pSet2, * pSetI );

assert( IntegerSetSize( * pSetI ) == 1 );

assert( IntegerSetHasKey( * pSetI, 20 ) );

// Создаем объединение множеств - ожидаем наличия 3 элементов - 10 20 30

IntegerSet * pSetU = IntegerSetCreate();

IntegerSetUnite( * pSet1, * pSet2, * pSetU );

assert( IntegerSetSize( * pSetU ) == 3 );

assert( IntegerSetHasKey( * pSetU, 10 ) );

assert( IntegerSetHasKey( * pSetU, 20 ) );

assert( IntegerSetHasKey( * pSetU, 30 ) );

// Создаем разность множеств - ожидаем наличия 1 элементов - 10

IntegerSet * pSetD = IntegerSetCreate();

IntegerSetDifference( * pSet1, * pSet2, * pSetD );

assert( IntegerSetSize( * pSetD ) == 1 );

// Уничтожаем все созданные множества

IntegerSetDestroy( pSet1 );

IntegerSetDestroy( pSet2 );

IntegerSetDestroy( pSetI );

IntegerSetDestroy( pSetU );

IntegerSetDestroy( pSetD );

}