35 баллов

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

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

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

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

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

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

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

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

/*...*/

int main() {

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

	/* Класс 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

	Iterator* i = m->getIterator();
	for (; i->is(); i->next()) {
		MapPair *mp = (MapPair)i->get();
		cout << mp->first()->toString() 
		     << " - " << mp->second()->intValue()
		     << "\n"; 
	}
	delete i;
	
	delete m;

	return 0;
}