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);                     // Записваме номера сред тези само от първата среща.
    }                                                     // Край на цикъла.
}                                                         // Край на програмата.
  1. Какво извежда първият cout и защо?
  2. Кои номера остават в readers след insert(58) и erase(17)?
  3. Кои две числа извежда последният cout и какво означават?
  4. Какви са 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}.

Изтегли main.cpp.