Спроектировать библиотеку коллекций для языка C++. Под коллекцией, в данном контексте, понимается "программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям." (см. http://ru.wikipedia.org/wiki/Коллекция_данных)
Создаваемая вами библиотека должна состоять из трех "слоев":
При проектировании и описании библиотеки следует обратить внимание на различие между интерфейсом коллекции, задающим ее назначение и способ использования, и конкретной реализацией (разница между "множеством вообще" и различными реализациями множества - на основе деревьев, хэш-таблиц и т.д.). Множество, фактически, является интерфейсом, поддерживающим набор стандартных операций (добавление элемента, проверка на наличие, удаление элемента, сложение с другим множеством и т.д.), реализовываться эти операции могут различным образом в зависимости от структур данных, лежащих в основе.
Должна быть предусмотрена возможность получения итератора, с помощью которого можно обойти всю коллекцию (см. STL и паттерн проектирования Итератор).
Необходимо разработать интерфейсы следующих коллекций: множество, ассоциированный
массив, очередь и стек.
Предложить реализацию ассоциированного массива на основе хеша, множества -
на основе сбалансированного дерева поиска (АВЛ, красно-черное или любое
другое, но обязательно с операциями балансировки), а всех
остальных коллекций - на основе массива переменной длины. Массив
переменной длины реализовать самостоятельно (не использовать
std::vector
и т.д.).
Внимание | |
---|---|
Коллекции должны быть реализованы БЕЗ ПРИМЕНЕНИЯ МЕХАНИЗМА ШАБЛОНОВ (TEMPLATES) C++. То есть, коллекции должны быть ориентированы на хранение объектов, являющихся наследниками одного (базового) класса. Необходимо также определить интерфейс этого базового класса. |
Для защиты лабораторной работы необходимо представить:
Разработанная библиотека должна допускать, например, такое использование:
/*...*/ int main() { /* Создается экземпляр множества, основанного на массиве. Указатель на множество сохраняется в переменной абстрактного типа Set (если мы в будущем захотим изменить реализацию множества, то достаточно будет изменить лишь HashSet в этой строке на новый). */ Set *s = new HashSet(); /* Класс IntObject - наследник абстрактного класса Object, предназначенный для хранения чисел типа int. Параметром конструктора является само число. */ Object *o = new IntObject(5); /* Добавляем созданный экземпляр в множество */ s->add(o); Object *o = new IntObject(6); s->add(o); Object *o = new IntObject(5); /* Операция contains возвращает истину, если множество содержит объект */ if (s->contains(o)) cout << "As expected\n"; else cout << "Something wrong\n"; Iterator *i = s->getIterator(); for (; i->is(); i->next()) { cout << ((IntObject *)i)->intValue() << "\n"; } delete i; /* Удаляем объект */ s->remove(o); if (s->contains(o)) cout << "Something wrong\n"; else cout << "As expected\n"; delete s; return 0; }