Фрагмент для ознакомления
[Электронный ресурс] // Википедия. – Режим доступа: ru.wikipedia.org/wiki/МножествоC++ [Электронный ресурс] // Википедия. – Режим доступа: https://ru.wikipedia.org/wiki/C%2B%2BФундаментальная теория тестирования [Электронный ресурс] // Хабр. – Режим доступа: https://habr.com/ru/articles/549054/ПриложенияПриложение АЛистинг 1// main.cpp#include #include #include #include #include #include #include #include #include #include #include #include "LinkedListSet.h"#include "ListSet.h"#include "SetSet.h"#include "PriorityQueueSet.h"#include "UnorderedSetSet.h"#include "MyListSet.h"using namespace std;// Функция для форматирования и печати результатовvoid printResult(double duration, int width) {cout << setw(width - 2) << fixed << setprecision(0) << duration << "ms |";}// Шаблонная функция для измерения времени операций множестваtemplate vector testSet(const vector& elementsA, const vector& elementsB) {vector timings;SetType setA;SetType setB;auto start = chrono::high_resolution_clock::now();auto end = start;// Timing insertions for set Astart = chrono::high_resolution_clock::now();for (int i : elementsA) setA.insert(i);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing insertions for set Bstart = chrono::high_resolution_clock::now();for (int i : elementsB) setB.insert(i);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing sizestart = chrono::high_resolution_clock::now();setA.getSize();end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing subset A-Astart = chrono::high_resolution_clock::now();setA.isSubsetOf(setA);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing subset B-Astart = chrono::high_resolution_clock::now();setB.isSubsetOf(setA);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing equality A-Astart = chrono::high_resolution_clock::now();setA.isEqualTo(setA);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing equality B-Astart = chrono::high_resolution_clock::now();setB.isEqualTo(setA);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing unionstart = chrono::high_resolution_clock::now();setA.unionWith(setB);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing intersectionstart = chrono::high_resolution_clock::now();setA.intersectWith(setB);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing difference A-Bstart = chrono::high_resolution_clock::now();setA.differenceWith(setB);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing difference B-Astart = chrono::high_resolution_clock::now();setB.differenceWith(setA);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());// Timing symmetric differencestart = chrono::high_resolution_clock::now();setA.symmetricDifferenceWith(setB);end = chrono::high_resolution_clock::now();timings.push_back(chrono::duration_cast(end - start).count());return timings;}// Шаблонная функция для вывода на консоль тестовых наборовtemplate void testsetResult(const vector& elementsA, const vector& elementsB) {vector timings;SetType setA;SetType setB;//used to out current typeauto getType = [&](const string& str) { string res = ""; for (auto const& ch: str) { if (!isdigit(ch)) res = res + ch; } return res;};cout << getType(typeid(setA).name()) << ": " << endl;// Result A - insertions for set Acout << "A = ";for (int el : elementsA) {setA.insert(el);cout << el << (el == elementsA.back() ? "" : ", ");} cout << endl;// Result B - insertions for set Bcout << "B = ";for (int el : elementsB) {setB.insert(el);cout << el << (el == elementsB.back() ? "" : ", ");} cout << endl;// Result sizecout << "Мощность: " << setA.getSize() << endl;// Result subset A-Acout << "Подмножество A-A: " << setA.isSubsetOf(setA) << endl;// Result subset B-Acout << "Подмножество B-A: " << setB.isSubsetOf(setA) << endl;// Result equality A-Acout << "Равенство A-A: " << setA.isEqualTo(setA) << endl;// Result equality B-Acout << "Равенство B-A: " << setB.isEqualTo(setA) << endl;// Result unionSetType unionRes = setA.unionWith(setB);cout << "Объединение A и B = ";unionRes.view();// Result intersectionSetType aintersectionb = setA.intersectWith(setB);cout << "Пересечение A и B = ";aintersectionb.view();// Result difference A-BSetType aDiffB = setA.differenceWith(setB);cout << "Разность A и B = ";aDiffB.view();// Result difference B-ASetType bDiffA = setB.differenceWith(setA);cout << "Разность B и A = ";bDiffA.view();// Result symmetric differenceSetType aSymDiffB = setA.symmetricDifferenceWith(setB);cout << "Симметричная разность A и B = ";aSymDiffB.view();cout << "--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------" << endl;}// Функция для печати заголовок таблицыvoid printTableHeader(const vector& headers, const vector& columnWidths) {cout << "----------------------------------------------------------------------------------------------------------------------------------------------" << endl;for (size_t i = 0; i < headers.size(); ++i) {cout << setw(columnWidths[i]) << headers[i] << " |";}cout << endl;cout << "----------------------------------------------------------------------------------------------------------------------------------------------" << endl;}// Функция для печати строк таблицыvoid printTableRow(const string& operation, const vector& timings, const vector& columnWidths) {cout << setw(columnWidths[0]) << operation << " |";for (size_t i = 0; i < timings.size(); ++i) {printResult(timings[i], columnWidths[i + 1]);}cout << endl;cout << "----------------------------------------------------------------------------------------------------------------------------------------------" << endl;}int main(){SetConsoleCP(1251);SetConsoleOutputCP(1251);GetConsoleOutputCP();std::ios::sync_with_stdio(false); // Отключение синхронизации для ускорения I/Osrand((unsigned int)(time(0))); // Инициализация генератора случайных чиселint N = 10;cout << "Введите мощность: "; cin >> N;vector elementsA;vector elementsB;for (int i = 0; i < N; ++i) {elementsA.push_back(rand() % 100000 + 1); // Генерация случайных чиселelementsB.push_back(rand() % 100000 + 1);}// Вывод результаты операций множеств/*testsetResult<LinkedListSet>(elementsA, elementsB);testsetResult(elementsA, elementsB);testsetResult(elementsA, elementsB);testsetResult(elementsA, elementsB);testsetResult(elementsA, elementsB);testsetResult(elementsA, elementsB);*/// Заголовки столбцовvector headers = {"Операция","Класс Список","Односвязный список","List","Set","priorityqueue_set","unordered_set"};// Измерение времени// testSet return = [creating sets, size, subset A - A, subset B - A, A = A, B = A, UNION, Intersect, A - B, B - A, Symmetric difference]vector timingsLinkedList = testSet<LinkedListSet>(elementsA, elementsB);vector timingsMyListSet = testSet(elementsA, elementsB);vector timingsListSet = testSet(elementsA, elementsB);vector timingsSetSet = testSet(elementsA, elementsB);vector timingsPriorityQueueSet = testSet(elementsA, elementsB);vector timingsUnorderedSetSet = testSet(elementsA, elementsB);// список операцийvector operations = {"Создание множества A","Создание множества B","Мощность","Подмножество A-A","Подмножество B-A","Равенство A-A","Равенство B-A","Объединение","Пересечение","Разность A-B","Разность B-A","Симметричная разность"};// динамическое определение ширины столбцовvector columnWidths(headers.size(), 0);// установка ширины столбца на максимальную длину между заголовком и даннымиfor (size_t i = 0; i < headers.size(); ++i) {int lenh = headers[i].length() + 2;columnWidths[i] = max(columnWidths[i], lenh); // +2 для отступа}for (const auto& operation : operations) {columnWidths[0] = max(columnWidths[0], (int)operation.length() + 2);}// функция для вычисления максимальной ширины для каждого таймингаauto computeColumnWidths = [&](const vector& timings) {for (size_t k = 0; k < columnWidths.size(); ++k) {for (size_t i = 0; i < timings.size(); ++i) {if (k + 1 == columnWidths.size() - 1) return;string timingstr = to_string(timings[i]) + "ms";columnWidths[k + 1] = max(columnWidths[k + 1], (int)(timingstr.length()) + 2);}}};// вычисление ширины столбцов для каждого набора тайминговcomputeColumnWidths(timingsLinkedList);computeColumnWidths(timingsMyListSet);computeColumnWidths(timingsListSet);computeColumnWidths(timingsSetSet);computeColumnWidths(timingsPriorityQueueSet);computeColumnWidths(timingsUnorderedSetSet);// печать таблицыprintTableHeader(headers, columnWidths);for (size_t i = 0; i < operations.size(); ++i) {vector rowtimings = {timingsLinkedList[i],timingsMyListSet[i],timingsListSet[i],timingsSetSet[i],timingsPriorityQueueSet[i],timingsUnorderedSetSet[i]};printTableRow(operations[i], rowtimings, columnWidths);}system("pause");return 0;}Листинг 2// LinkedListSet.h#pragma once#include #include class LinkedListSet {private:struct Node {int value;Node* next;Node(int val) : value(val), next(nullptr) {}};Node* head;void destroy(Node* node) {while (node) {Node* next = node->next;delete node;node = next;}}Node* copy(Node* node) const {if (!node) return nullptr;Node* newHead = new Node(node->value);Node* current = newHead;node = node->next;while (node) {current->next = new Node(node->value);current = current->next;node = node->next;}return newHead;}public:LinkedListSet() : head(nullptr) {}LinkedListSet(const LinkedListSet& other) : head(copy(other.head)) {}~LinkedListSet() { destroy(head); }void insert(int val) {if (contains(val)) return;Node* newNode = new Node(val);newNode->next = head;head = newNode;}void view() {Node* current = head;while (current) {std::cout << current->value << (current->next == NULL ? "" : ", ");current = current->next;} std::cout << '\n';}bool contains(int val) const {Node* current = head;while (current) {if (current->value == val) return true;current = current->next;}return false;}int getSize() const {int size = 0;Node* current = head;while (current) {size++;current = current->next;}return size;}bool isSubsetOf(const LinkedListSet& other) const {Node* current = head;while (current) {if (!other.contains(current->value)) return false;current = current->next;}return true;}bool isEqualTo(const LinkedListSet& other) const {return isSubsetOf(other) && other.isSubsetOf(*this);}LinkedListSet unionWith(const LinkedListSet& other) const {LinkedListSet resultSet(*this);Node* current = other.head;while (current) {resultSet.insert(current->value);current = current->next;}return resultSet;}LinkedListSet intersectWith(const LinkedListSet& other) const {LinkedListSet resultSet;Node* current = head;while (current) {if (other.contains(current->value)) resultSet.insert(current->value);current = current->next;}return resultSet;}LinkedListSet differenceWith(const LinkedListSet& other) const {LinkedListSet resultSet;Node* current = head;while (current) {if (!other.contains(current->value)) resultSet.insert(current->value);current = current->next;}return resultSet;}LinkedListSet symmetricDifferenceWith(const LinkedListSet& other) const {LinkedListSet resultSet;Node* current = head;while (current) {if (!other.contains(current->value)) resultSet.insert(current->value);current = current->next;}current = other.head;while (current) {if (!contains(current->value)) resultSet.insert(current->value);current = current->next;}return resultSet;}};Листинг 2// MyListSet.h#pragma once#include #include using namespace std;const int MAX_SIZE = 10000;class MyListSet {private:int list[MAX_SIZE]; // Массив для хранения элементовint size; // Текущий размер спискаpublic:MyListSet();bool insert(int element);bool contains(int element) const;bool remove(int element); int getSize() const; bool isSubsetOf(const MyListSet& other) const; bool isEqualTo(const MyListSet& other) const; MyListSet unionWith(const MyListSet& other) const;MyListSet intersectWith(const MyListSet& other) const;MyListSet differenceWith(const MyListSet& other) const; MyListSet symmetricDifferenceWith(const MyListSet& other) const;void view() const; };MyListSet::MyListSet() {size = 0; // Изначально список пуст}bool MyListSet::insert(int element) {if (size >= MAX_SIZE) {cerr << "Ошибка: Превышен максимальный размер списка." << endl;return false;}if (contains(element)) {return false; }list[size++] = element;return true;}bool MyListSet::contains(int element) const {for (int i = 0; i < size; ++i) {if (list[i] == element) {return true; // Элемент найден в списке}}return false; // Элемент не найден}// Удаление элементаbool MyListSet::remove(int element) {for (int i = 0; i < size; ++i) {if (list[i] == element) {// Сдвиг всех элементов после удаленного на одну позицию влевоfor (int j = i; j < size - 1; ++j) {list[j] = list[j + 1];}--size; return true;}}return false; // Элемент не найден}int MyListSet::getSize() const {return size;}bool MyListSet::isSubsetOf(const MyListSet& other) const {for (int i = 0; i < size; ++i) {if (!other.contains(list[i])) {return false;}}return true;}bool MyListSet::isEqualTo(const MyListSet& other) const {if (size != other.size) {return false; }for (int i = 0; i < size; ++i) {if (!other.contains(list[i])) {return false; }}return true;}MyListSet MyListSet::unionWith(const MyListSet& other) const {MyListSet result;for (int i = 0; i < size; ++i) {result.insert(list[i]);}for (int i = 0; i < other.size; ++i) {result.insert(other.list[i]);}return result;}MyListSet MyListSet::intersectWith(const MyListSet& other) const {MyListSet result;for (int i = 0; i < size; ++i) {if (other.contains(list[i])) {result.insert(list[i]);}}return result;}MyListSet MyListSet::differenceWith(const MyListSet& other) const {MyListSet result;for (int i = 0; i < size; ++i) {if (!other.contains(list[i])) {result.insert(list[i]);}}return result;}MyListSet MyListSet::symmetricDifferenceWith(const MyListSet& other) const {MyListSet result;for (int i = 0; i < size; ++i) {if (!other.contains(list[i])) {result.insert(list[i]);}}for (int i = 0; i < other.size; ++i) {if (!contains(other.list[i])) {result.insert(other.list[i]);}}return result;}void MyListSet::view() const {if (size == 0) {cout << "[]" << endl;}else {for (int i = 0; i < size; ++i) {cout << list[i];if (i < size - 1) {cout << ", ";}}cout << endl;}}Листинг 3// ListSet.h#pragma once#include #include #include class ListSet {private:std::list elements;public:ListSet() = default;void insert(int val) {if (std::find(elements.begin(), elements.end(), val) == elements.end()) {elements.push_back(val);}}void view() {for (int el : elements) {std::cout << el << (el == elements.back() ? "" : ", ");} std::cout << '\n';}bool contains(int val) const {return std::find(elements.begin(), elements.end(), val) != elements.end();}int getSize() const {return elements.size();}bool isSubsetOf(const ListSet& other) const {for (int el : elements) {if (!other.contains(el)) return false;}return true;}bool isEqualTo(const ListSet& other) const {return isSubsetOf(other) && other.isSubsetOf(*this);}ListSet unionWith(const ListSet& other) const {ListSet resultSet;resultSet.elements = elements;for (int el : other.elements) {resultSet.insert(el);}return resultSet;}ListSet intersectWith(const ListSet& other) const {ListSet resultSet;for (int el : elements) {if (other.contains(el)) resultSet.insert(el);}return resultSet;}ListSet differenceWith(const ListSet& other) const {ListSet resultSet;for (int el : elements) {if (!other.contains(el)) resultSet.insert(el);}return resultSet;}ListSet symmetricDifferenceWith(const ListSet& other) const {ListSet resultSet;for (int el : elements) {if (!other.contains(el)) resultSet.insert(el);}for (int el : other.elements) {if (!contains(el)) resultSet.insert(el);}return resultSet;}};Листинг 4// SetSet.h#pragma once#include #include #include #include class SetSet {private:std::set elements;auto lastEl() {auto itend = elements.end(); itend--;return *itend;}public:SetSet() = default;void insert(int val) {elements.insert(val);}void view() {for (int el : elements) {std::cout << el << (el == lastEl() ? "" : ", ");} std::cout << '\n';}bool contains(int val) const {return elements.find(val) != elements.end();}int getSize() const {return elements.size();}bool isSubsetOf(const SetSet& other) const {return std::all_of(elements.begin(), elements.end(), [&other](int el) { return other.contains(el); });}bool isEqualTo(const SetSet& other) const {return elements == other.elements;}SetSet unionWith(const SetSet& other) const {SetSet resultSet;resultSet.elements = elements;resultSet.elements.insert(other.elements.begin(), other.elements.end());return resultSet;}SetSet intersectWith(const SetSet& other) const {SetSet resultSet;std::set_intersection(elements.begin(), elements.end(),other.elements.begin(), other.elements.end(),std::inserter(resultSet.elements, resultSet.elements.end()));return resultSet;}SetSet differenceWith(const SetSet& other) const {SetSet resultSet;std::set_difference(elements.begin(), elements.end(),other.elements.begin(), other.elements.end(),std::inserter(resultSet.elements, resultSet.elements.end()));return resultSet;}SetSet symmetricDifferenceWith(const SetSet& other) const {SetSet resultSet;std::set_symmetric_difference(elements.begin(), elements.end(),other.elements.begin(), other.elements.end(),std::inserter(resultSet.elements, resultSet.elements.end()));return resultSet;}};Листинг 5//PriorityQueueSet.h#pragma once#include #include #include #include class PriorityQueueSet {private:std::priority_queue elements;public:PriorityQueueSet() = default;void insert(int val) {if (!contains(val)) elements.push(val);}void view() {for (; !elements.empty(); elements.pop())std::cout << elements.top() << (elements.size() == 1 ? "" : ", ");std::cout << '\n';}bool contains(int val) const {auto copy = elements;while (!copy.empty()) {if (copy.top() == val) return true;copy.pop();}return false;}int getSize() const {auto copy = elements;int size = 0;while (!copy.empty()) {size++;copy.pop();}return size;}bool isSubsetOf(const PriorityQueueSet& other) const {auto copy = elements;while (!copy.empty()) {if (!other.contains(copy.top())) return false;copy.pop();}return true;}bool isEqualTo(const PriorityQueueSet& other) const {return isSubsetOf(other) && other.isSubsetOf(*this);}PriorityQueueSet unionWith(const PriorityQueueSet& other) const {PriorityQueueSet resultSet;auto copy = elements;while (!copy.empty()) {resultSet.insert(copy.top());copy.pop();}copy = other.elements;while (!copy.empty()) {resultSet.insert(copy.top());copy.pop();}return resultSet;}PriorityQueueSet intersectWith(const PriorityQueueSet& other) const {PriorityQueueSet resultSet;auto copy = elements;while (!copy.empty()) {if (other.contains(copy.top())) resultSet.insert(copy.top());copy.pop();}return resultSet;}PriorityQueueSet differenceWith(const PriorityQueueSet& other) const {PriorityQueueSet resultSet;auto copy = elements;while (!copy.empty()) {if (!other.contains(copy.top())) resultSet.insert(copy.top());copy.pop();}return resultSet;}PriorityQueueSet symmetricDifferenceWith(const PriorityQueueSet& other) const {PriorityQueueSet resultSet;auto copy = elements;while (!copy.empty()) {if (!other.contains(copy.top())) resultSet.insert(copy.top());copy.pop();}copy = other.elements;while (!copy.empty()) {if (!contains(copy.top())) resultSet.insert(copy.top());copy.pop();}return resultSet;}};Листинг 6// UnorderedSetSet.h#pragma once#include #include #include class UnorderedSetSet {private:std::unordered_set elements;public:UnorderedSetSet() = default;void insert(int val) {elements.insert(val);}void view() {auto lastit = elements.begin();for (auto it = elements.begin(); it != elements.end(); it++)lastit = it;for (auto el : elements)std::cout << el << (el == *lastit ? "" : ", ");std::cout << '\n';}bool contains(int val) const {return elements.find(val) != elements.end();}int getSize() const {return elements.size();}bool isSubsetOf(const UnorderedSetSet& other) const {return std::all_of(elements.begin(), elements.end(), [&other](int el) { return other.contains(el); });}bool isEqualTo(const UnorderedSetSet& other) const {return elements == other.elements;}UnorderedSetSet unionWith(const UnorderedSetSet& other) const {UnorderedSetSet resultSet;resultSet.elements = elements;resultSet.elements.insert(other.elements.begin(), other.elements.end());return resultSet;}UnorderedSetSet intersectWith(const UnorderedSetSet& other) const {UnorderedSetSet resultSet;for (int el : elements) {if (other.contains(el)) resultSet.insert(el);}return resultSet;}UnorderedSetSet differenceWith(const UnorderedSetSet& other) const {UnorderedSetSet resultSet;for (int el : elements) {if (!other.contains(el)) resultSet.insert(el);}return resultSet;}UnorderedSetSet symmetricDifferenceWith(const UnorderedSetSet& other) const {UnorderedSetSet resultSet;for (int el : elements) {if (!other.contains(el)) resultSet.insert(el);}for (int el : other.elements) {if (!contains(el)) resultSet.insert(el);}return resultSet;}};
