Напишите шаблонный класс 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 определены операции сравнения < и ==.
Гарантируется, что корректная реализация на базе рандомизированного двоичного дерева поиска проходит все тесты, укладываясь в отведенное время и память.
Пример некоторых проверок, которые могут выполняться над вашим классом:
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
Aleksasha
ИвГУ
Спасибо , Катерина, за помощь на онлайн! Сложные задачи решены! и хорошо!
Антон
ИрНИТУ (бывш. ИрГТУ)
Работа выполнена профессионально! Мария действительно сделает всё, чтобы вы остались с за...
Aleksasha
ИвГУ
Спасибо, Виктория! За профессионализм и ответственное отношение к работе!
Дарья
СПБГУ
На мой взгляд, у Людмилы, лучшие решения по геометрии с подробными комментариями! Как все...