Вариант 2

Стоимость

25 баллов

Описание

Спроектировать библиотеку коллекций для языка C++. Под коллекцией, в данном контексте, понимается "программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям." (см. http://ru.wikipedia.org/wiki/Коллекция_данных)

Создаваемая вами библиотека должна состоять из трех "слоев":

Слой абстрактных типов данных (верхний). Слой состоит из описаний интерфейсов основных видов коллекций и стратегий доступа: множество, стек, дек, очередь, ассоциированный массив и т.д.
Слой структур данных (самый нижний). На этом слое располагаются реализации типовых струкур данных: динамический список, массив, АВЛ-дерево, красно-черное дерево и т.д.
Слой реализаций (промежуточный), на котором располагаются классы, предлагающие реализацию того или иного типа данных на основе заданной структуры хранения. Например, на этом слое может находиться класс ArrayStack, реализующий абстрактный тип данных стек на основе структуры данных массив или ListMap, реализующий ассоциативный массив на основе структуры данных связный список.

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

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

	Внимание
Коллекции должны быть реализованы БЕЗ ПРИМЕНЕНИЯ МЕХАНИЗМА ШАБЛОНОВ (TEMPLATES) C++. То есть, коллекции должны быть ориентированы на хранение объектов, являющихся наследниками одного (базового) класса. Необходимо также определить интерфейс этого базового класса.

Внимание

Коллекции должны быть реализованы БЕЗ ПРИМЕНЕНИЯ МЕХАНИЗМА ШАБЛОНОВ (TEMPLATES) C++. То есть, коллекции должны быть ориентированы на хранение объектов, являющихся наследниками одного (базового) класса. Необходимо также определить интерфейс этого базового класса.

Защита

Для защиты лабораторной работы необходимо представить:

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

Пример

Разработанная библиотека должна допускать, например, такое использование:

/*...*/

int main() {

	/* Создается экземпляр ассоциированного массива, основанного на списке.
	   Указатель на множество сохраняется в переменной абстрактного типа
	   Map (если мы в будущем захотим изменить реализацию множества, то
	   достаточно будет изменить лишь ListMap в этой строке на новый,
	   например HashMap).
	 */
	Map *m = new ListMap();

	
	/* Класс StrObject - наследник абстрактного класса Object, предназначенный
	   для хранения строк. Параметром конструктора является строка.
	 */
	Object *k = new StrObject("Some str");
	/* Класс IntObject - наследник абстрактного класса Object, предназначенный
	   для хранения чисел типа int. Параметром конструктора является 
	   само число.
	 */
	Object *v = new IntObject(6);

	/* В ячейку массива, адресуемую объектом k добавляется объект v.
	   С учетом типов, смысл этой операции в установлении связи между
	   "Some str" и 6. Если отвлечься от синтаксиса, то это было
	   бы равноценно SomeArray["SomeStr"] = 6, если бы в C++ такая
	   конструкция была допустима.
	 */
	m->set(k, v);    

	Object *o = new IntObject(5);
	/* В эту же ячейку теперь помещается 5.
	 */
	m->set(k, o);

	/* contains_key() предназначен для проверки наличия ключа в массиве.
	 */
	if (m->contains_key(k)) cout << "As expected\n"; else cout << "Something wrong\n";

	/* value() возвращает значение ячейки с заданным ключом.
	 */
	v = m->value(k);
	cout << v->intValue() << "\n";   // должно вывести 5
	
	delete m;

	return 0;
}