108. Множества — представяне и основни операции
Множество е съвкупност от различни елементи. Важно е кои елементи принадлежат към него. Две множества са равни, когато съдържат едни и същи елементи. A е подмножество на B, когато всеки елемент на A принадлежи и на B.
Множество може да се представи чрез сортиран масив, дърво или хеш-таблица. Тук използваме set<int> от C++. Той пази всяко цяло число най-много веднъж и при обхождане ги дава във възходящ ред. Балансираното дърво е обичайна реализация на set. За математическото множество редът на изброяване е без значение.
Представяне на множество в разширената разработка · М. Тодорова, §2.3.3.5, печатни с. 104–107 (PDF с. 99–102) · Проект на стандарта C++ — set
Самостоятелна задача
Условие
Библиотеката пази номерата на записаните за първата среща на читателския клуб. Първоначално са записани №17 и №42. Един читател се брои само веднъж. В програмата insert(x) записва номер x, erase(x) го отписва, size() дава броя на записаните, а contains(x) проверява дали номерът присъства. При извеждане true се показва като 1, а false като 0.
За последния въпрос наречи крайното множество от програмата A. За втората среща са записани читатели B = {42, 73}. Обединението съдържа номерата от поне едната среща, сечението съдържа общите номера, а разликата A − B съдържа номерата само от първата среща. Цикълът for (int number : множество) взема поред всеки номер от даденото множество.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
#include <set> // Включваме библиотеката за множества от тип set.
using namespace std; // Така можем да пишем cout вместо std::cout.
int main() { // Оттук започва изпълнението на програмата.
set<int> readers = {17, 42}; // Създаваме множество от номера на записани читатели.
readers.insert(42); // Опитваме да запишем читател с номер 42.
cout << readers.size() << '\n'; // Печатаме колко различни номера съдържа множеството.
readers.insert(58); // Добавяме към записаните номер 58.
readers.erase(17); // Премахваме номер 17 от множеството.
cout << readers.contains(17) << ' ' << readers.contains(58) << '\n'; // С contains проверяваме поотделно дали всеки от двата номера присъства и печатаме резултатите.
set<int> secondMeeting = {42, 73}; // Създаваме множество с номерата за втората среща.
set<int> combined = readers; // Започваме ново множество, като копираме записаните за първата среща.
for (int number : secondMeeting) // Вземаме поред всеки номер от втората среща.
combined.insert(number); // Добавяме текущия номер към общото множество.
set<int> common; // Подготвяме празно множество за номерата, които се срещат и на двете места.
set<int> onlyFirst; // Подготвяме празно множество за номерата само от първата среща.
for (int number : readers) { // Вземаме поред всеки номер от първата среща.
if (secondMeeting.contains(number)) // Проверяваме дали текущият номер присъства и на втората среща.
common.insert(number); // Записваме номера сред общите за двете срещи.
else // Изпълняваме следващия ред, ако проверката в if е невярна.
onlyFirst.insert(number); // Записваме номера сред тези само от първата среща.
} // Край на цикъла.
} // Край на програмата.
- Какво извежда първият
coutи защо? - Кои номера остават в
readersследinsert(58)иerase(17)? - Кои две числа извежда последният
coutи какво означават? - Какви са
combined,commonиonlyFirstслед циклите? Кое е обединението, кое е сечението и кое е разликата A − B?
Отговори за самопроверка
1. Брой записани
Извежда 2. №42 вече присъства и повторното записване оставя броя същия.
2. Крайно множество
{42, 58}. Добавяме №58 и премахваме №17.
3. Проверка за принадлежност
Извежда 0 1. №17 е отписан, а №58 е записан.
4. Операции с две множества
Обединението е {42, 58, 73}, сечението е {42}, а разликата A − B е {58}.