|
Напишите шаблонный класс Set для представления АТД "множество" на основе рандомизированного двоичного дерева, хеш-таблицы или другой структуры, обеспечивающей требуемую производительность (использование класса std::set не допускается).
Интерфейс класса должен выглядеть следующим образом:
template <class T>
class Set {
//закрытые данные (какие считаете нужными)
public:
//конструкторы (если нужны)
Set();
Set(const Set &s);
//вставка элемента в множество
Set operator + (const T &t) const;
friend Set operator + (const T &t, const Set &s);
Set &operator += (const T &t);
//удаление элемента из множества
Set operator - (const T &t) const;
Set &operator -= (const T &t);
//проверка наличия элемента в множестве
bool exists(const T &t) const;
//объединение множеств
Set operator + (const Set &s) const;
Set& operator += (const Set &s);
//разность множеств
Set operator - (const Set &s) const;
Set& operator -= (const Set &s);
//операции сравнения
bool operator == (const Set &s) const;
bool operator != (const Set &s) const;
//мощность множества (число элементов)
int size(void) const;
//вывод элементов в порядке возрастания, разделяя их пробелом
friend ostream& operator << (ostream& os, const Set &s) {
//поместите соответствующий код сюда
}
//операция присваивания (если нужна)
Set &operator = (const Set &s);
//деструктор (если нужен)
~Set();
};
|
Гарантируется, что для шаблонного типа T определены операции сравнения < и ==.
В проверяющую систему отправляется полная реализация класса без какого-либо дополнительного кода. В
том числе ваша программа не должна содержать функцию main! Вместо этого в конце программы
поставьте строчку:
Тем самым вы подключите функцию main (её текст вам недоступен), которая и будет тестировать ваш класс.
Гарантируется, что корректная реализация на базе рандомизированного двоичного дерева поиска проходит все
тесты, укладываясь в отведенное время и память.
Пример некоторых проверок, которые могут выполняться над вашим классом:
int main(void)
{
Set<int> a;
for (int i=50; i>=0; i--) a+=i;
for (int i=0; i<=50; i+=2) a-=i;
for (int i=0; i<=50; i+=3) a-=i;
cout << a << endl;
Set<int> b = ((a + 999)+9999) - 89;
cout << b.size() << endl;
cout << b.exists(1) << b.exists(2)
<< b.exists(3) << b.exists(4)
<< b.exists(5) << endl;
Set<int> *c = new Set<int>;
*c +=1; *c +=5; *c +=6;
cout << c->size() << endl;
cout << a-*c << endl;
*c += 1111;
cout << a+*c << endl;
delete c;
return 0;
}
|
Правильный результат:
1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
19
10001
3
7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
1 5 6 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 1111
|
| 
