Спроектировать библиотеку коллекций для языка C++. Под коллекцией, в данном контексте, понимается "программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям." (см. http://ru.wikipedia.org/wiki/Коллекция_данных)
Создаваемая вами библиотека должна состоять из трех "слоев":
Предусмотреть также возможность определения пользователем библиотеки собственных структур данных и проблемно-ориентированных коллекций, и обеспечить удобное их использование, наряду с имеющимися изначально в проекте.
Библиотека должна поддерживать возможность динамического определения типа хранилища (структуры данных) для абстрактного типа (см. пример). Возможно разбиение классов структур данных на группы (с помощью отношения наследования), и ограничения исходного типа хранилища для проблемно-ориентированной коллекции классом одной из групп (либо определение различных реализаций проблемно-ориентированной коллекции для хранилищ разных групп). Например, вы можете выделить обобщенную струкуру данных бинарное дерево поиска и сделать классы RnBTree и AVLTree наследниками этой структуры. После чего, описать реализацию абстрактного типа данных множество уже не относительно RnBTree, а относительно бинарного дерева поиска.
Должна быть предусмотрена возможность получения итератора, с помощью которого можно обойти всю коллекцию (см. STL и паттерн проектирования Итератор).
Из структур данных необходимо реализовать балансируемое (алгоритм балансировки не столь важен - это может быть АВЛ, красно-черное и т.д.) дерево и связный список, а из проблемно-ориентированных коллекций - ассоциированный массив, множество и очередь.
Внимание | |
---|---|
Коллекции должны быть реализованы БЕЗ ПРИМЕНЕНИЯ МЕХАНИЗМА ШАБЛОНОВ (TEMPLATES) C++. То есть, коллекции должны быть ориентированы на хранение объектов, являющихся наследниками одного (базового) класса. Необходимо также определить интерфейс этого базового класса. |
Для защиты лабораторной работы необходимо представить:
Разработанная библиотека должна допускать, например, такое использование:
/*...*/ int main() { /* Создается экземпляр ассоциированного массива, основанного на списке. Указатель на множество сохраняется в переменной абстрактного типа Map. Следует обратить внимание на аргумент, передаваемый конструктору MapIntf - это экземпляр структуры данных. Если бы при создании m в качестве параметра конструктору был передан экземпляр AVLTree, то пары ассоциированного массива сохранялись бы в дереве поиска (что улучшило бы производительность). Кроме того, пользователь может реализовать свою структуру данных (например, RnBTree - Red and Black, а не то, что вы подумали) и создавать ассоциированный массив, используя именно эту структуру в качестве хранилища. Очевидно, такой способ программирования требует очень внимательной проработки интерфейсов классов. */ Map *m = new MapIntf(new LinkedList()); /* Класс 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; }