C++ · Etap 3 · Lekcja 18

Zbiór — bez powtórzeń i zawsze po kolei

Ile różnych liczb jest na liście? Czy ten numer już się pojawił? Jaka jest najbliższa wolna godzina? Do tej pory na każde takie pytanie trzeba było pisać pętle, sortować i pilnować powtórzeń. Zbiór (set) robi to sam: wrzucasz do niego liczby, a on trzyma je bez powtórzeń i zawsze posortowane — i odpowiada na pytania błyskawicznie, nawet gdy dane się zmieniają. W tej lekcji poznasz go od pierwszego insert, przez szukanie najbliższej wartości, działania na zbiorach i zbiory par, aż po multiset i unordered_set. Po każdej części czekają ćwiczenia ze sprawdzarką.

64 ćwiczenia w trakcie lekcji28 zadań w bazie na koniec92 ze sprawdzarką C++
Filmy z OKI

Wolisz obejrzeć?

Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

Co już umiesz i czego się nauczysz

Ta lekcja zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo, Tablice, String, Pair, Vector, Sortowanie, Max / Min, Zaokrąglanie, Silnia, Wartość bezwzględna i Złożoność czasowa.

Z tych lekcji przydadzą się szczególnie trzy rzeczy. Z lekcji o vectorze — iteratory, czyli „strzałki” begin() i end(), gwiazdka *it i pętla for (int x : v). Z lekcji o sortowaniu — porządek rosnący, porządek słownikowy napisów, lower_bound i upper_bound. A z lekcji o złożoności — umiejętność liczenia, ile pracy wykona program, i reguła „około 100 milionów operacji na sekundę”.

Zbiór to pierwsza w kursie struktura danych, która sama pilnuje porządku. Vector trzyma to, co do niego włożysz, dokładnie w tej kolejności i z powtórzeniami — porządek musisz zrobić sam. Zbiór porządkuje wszystko w chwili wkładania. Dzięki temu wiele zadań, które wcześniej wymagały kilkunastu linijek, zamienia się w trzy — a programy, które były za wolne, zaczynają zdążać. Uczymy się tak samo jak dotąd: przepisuj przykłady, rozpisuj zbiory na kartce, zanim klikniesz „Pokaż odpowiedź”, i rób ćwiczenia po każdej części.

CZĘŚĆ 01–02

Pierwszy zbiór

insert, size, przechodzenie pętlą, a potem count, erase i pytanie „czy to już było?”.

CZĘŚĆ 03–04

Strzałki i szukanie

Najmniejszy i największy, iteratory, find, lower_bound, upper_bound i najbliższa wartość.

CZĘŚĆ 05–06

Działania, pary, napisy

Suma, część wspólna i różnica zbiorów, podzbiory, a potem zbiory par, punktów i słów.

CZĘŚĆ 07–08

multiset i szybkość

Zbiór z powtórzeniami, okna i zachłanne wybory, unordered_set, drzewo w środku i wybór właściwej struktury.

Jak działa sprawdzarka Każde ćwiczenie otwiera się w sprawdzarce w nowej karcie. Wklejasz cały program, klikasz Wyślij, a sprawdzarka uruchamia go na kilku testach i porównuje wynik z oczekiwanym — znak po znaku, więc wypisuj dokładnie to, o co prosi zadanie, bez „Podaj liczbę:”. Każdy test ma limit czasu (zwykle 1 sekundę). W kilku ćwiczeniach pod koniec lekcji dane są duże, a rozwiązanie „pętla w pętli” nie zdąży — tam zbiór jest potrzebny nie tylko dla wygody, ale i dla szybkości.

Mapa lekcji

Zbiór — worek bez powtórzeń

Zacznijmy od zadania, które już znasz: ile różnych liczb jest na liście? W lekcji o sortowaniu rozwiązywaliśmy je tak: posortuj, a potem policz miejsca, w których liczba różni się od poprzedniej. Po lewej ten sposób, po prawej — ten sam program ze zbiorem.

rozne_sortowanie.cpp
int n;
cin >> n;
vector<int> v(n);
for (int &x : v) cin >> x;
sort(v.begin(), v.end());
int ile = 0;
for (int i = 0; i < n; i++)
    if (i == 0 || v[i] != v[i - 1]) ile++;
cout << ile << "\n";
▶ Wejście
8 5 2 8 5 2 9 5 1
▶ Wyjście
5
rozne_zbior.cpp
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    s.insert(x);
}
cout << s.size() << "\n";
▶ Wejście
8 5 2 8 5 2 9 5 1
▶ Wyjście
5

Lewy program musi pamiętać o sortowaniu, o pierwszym elemencie (i == 0) i o porównywaniu z sąsiadem. Prawy po prostu wrzuca każdą liczbę do zbioru i na końcu pyta, ile w nim jest. Powtórki same odpadają: zbiór nie przyjmuje wartości, którą już ma. Wynik 5 to liczby 1, 2, 5, 8 i 9.

Pierwszy program ze zbiorem

pierwszy_zbior.cpp
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;      // pusty zbiór liczb całkowitych
    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(5);     // 5 już jest — nic się nie zmieni
    s.insert(2);     // 2 też już jest
    cout << s.size() << "\n";
    for (int x : s) cout << x << " ";
    cout << "\n";
    return 0;
}
▶ Wyjście
3 2 5 8

Przeczytajmy go linijka po linijce:

#include <set> — zbiór mieszka w osobnym pliku nagłówkowym, tak jak vector w <vector>. Jeśli piszesz #include <bits/stdc++.h>, zbiór już w nim jest.

set<int> s; — tworzy pusty zbiór o nazwie s. W nawiasach ostrych podajesz typ elementów, dokładnie jak w vector<int>.

s.insert(5); — wkłada 5 do zbioru. Gdy 5 już tam jest, nic się nie dzieje: bez błędu, bez ostrzeżenia.

s.size() — mówi, ile różnych wartości jest w zbiorze. Wstawiliśmy pięć razy, ale różne były tylko trzy.

for (int x : s) — przechodzi zbiór. Elementy wychodzą rosnąco: 2, 5, 8 — chociaż wstawialiśmy je w kolejności 5, 2, 8.

Prześledźmy: co jest w zbiorze po każdej linijce?

instrukcjazbiór s po niejs.size()co się stało
set<int> s;{ }0pusty zbiór
s.insert(5);{5}1dodany
s.insert(2);{2, 5}2dodany — od razu przed 5
s.insert(8);{2, 5, 8}3dodany na końcu
s.insert(5);{2, 5, 8}3już był — bez zmian
s.insert(2);{2, 5, 8}3już był — bez zmian
Tak wygląda zbiór po wszystkich pięciu insertach: trzy liczby, każda raz, rosnąco. Zbiór rysujemy w klamrach i bez numerków pod spodem — za chwilę zobaczysz, dlaczego.

Pobaw się zbiorem sam. Wpisz liczbę i kliknij insert(x) — albo naciśnij Enter. Wrzuć kilka razy tę samą liczbę i porównaj oba wiersze: w górnym jest wszystko, co wrzuciłeś, po kolei, a w dolnym — to, co naprawdę trzyma zbiór. Przyciski multiset i unordered_set na razie zostaw — poznasz je w częściach 7 i 8.

Wrzuć do zbioru — i zobacz, co się stanie
kolejność wstawiania
set
Ta ramka działa po włączeniu JavaScriptu.

Dwie zasady zbioru

Zasada 1: każda wartość najwyżej raz. Zbiór pamięta tylko, czy liczba w nim jest, a nie ile razy ją wstawiono. Dlatego size() zawsze mówi, ile jest różnych wartości.

Zasada 2: zawsze rosnąco. Niezależnie od tego, w jakiej kolejności wstawiasz, przechodzenie pętlą for daje elementy od najmniejszego do największego. Nie musisz wywoływać sort — zbiór układa każdą liczbę na właściwym miejscu w chwili wstawiania.

Obie zasady naraz dają coś, co w lekcji o sortowaniu wymagało sort i unique: posortowaną listę bez powtórzeń.

dwie_zasady.cpp
set<int> s;
s.insert(30);
s.insert(-4);
s.insert(17);
s.insert(30);
s.insert(0);
s.insert(-4);
for (int x : s) cout << x << " ";
cout << "\n" << s.size() << "\n";
▶ Wyjście
-4 0 17 30 4

Wczytywanie liczb do zbioru

wczytaj_n.cpp
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    s.insert(x);
}
for (int x : s) cout << x << " ";
cout << "\n";
▶ Wejście
7 40 10 30 10 20 40 10
▶ Wyjście
10 20 30 40
do_konca.cpp
set<int> s;
int x;
while (cin >> x) {
    s.insert(x);
}
cout << s.size() << "\n";
for (int y : s) cout << y << " ";
cout << "\n";
▶ Wejście
4 4 4 1 9 1
▶ Wyjście
3 1 4 9

Lewy program zna liczbę danych n z pierwszego wiersza — to schemat, który pojawi się w prawie każdym ćwiczeniu. Do zbioru nie da się wczytać „od razu” jak do vectora przez for (int &x : v) cin >> x; — zbiór nie ma miejsc, w które można by wpisać liczbę. Każdą liczbę najpierw wczytujesz do zwykłej zmiennej, a potem wkładasz przez insert.

Prawy program czyta liczby aż do końca danych (while (cin >> x), znasz to z lekcji o vectorze). Zwróć uwagę na nazwy: x służy do wczytywania, a w pętli wypisującej używamy innej nazwy, y, żeby się nie pomylić.

Zbiór od razu z wartościami — i z vectora

klamry.cpp
set<int> s = {7, 3, 7, 1, 3};
for (int x : s) cout << x << " ";
cout << "\n" << s.size() << "\n";
▶ Wyjście
1 3 7 3
z_vectora.cpp
vector<int> v = {4, 1, 4, 2, 1};
set<int> s(v.begin(), v.end());
for (int x : s) cout << x << " ";
cout << "\n";
vector<int> w(s.begin(), s.end());
cout << w[0] << " " << w[w.size() - 1] << "\n";
▶ Wyjście
1 2 4 1 4

Zbiór można utworzyć od razu z listą wartości w klamrach — tak jak vector. Powtórki znikają już w tej chwili: z pięciu liczb zostają trzy.

Można też utworzyć zbiór z całego vectora: set<int> s(v.begin(), v.end());. W nawiasie podajesz zakres od początku do końca, czyli dwie strzałki, które znasz z lekcji o vectorze. To jedna linijka, która usuwa powtórki i sortuje.

W drugą stronę też działa: vector<int> w(s.begin(), s.end()); przepisuje zbiór do vectora — rosnąco. Po co? Bo vector ma indeksy: w[0] to najmniejsza wartość, a w[w.size() - 1] — największa. Zbiór indeksów nie ma, o czym za chwilę.

Zbiór napisów i zbiór liter

zbior_slow.cpp
set<string> s;
s.insert("pies");
s.insert("kot");
s.insert("Ala");
s.insert("kot");
s.insert("ala");
cout << s.size() << "\n";
for (string w : s) cout << w << "\n";
▶ Wyjście
4 Ala ala kot pies

Zbiór może trzymać wartości każdego typu, który da się porównywać: liczby, znaki, napisy, pary. set<string> układa słowa w porządku słownikowym — tym samym, którego używa sort na napisach.

Pamiętasz z lekcji o sortowaniu, że wielkie litery są przed małymi? Dlatego „Ala” stoi przed „ala”. Dla zbioru to dwa różne słowa — różnią się jedną literą. Drugi „kot” odpadł, bo jest identyczny z pierwszym.

litery_slowa.cpp
string slowo = "abrakadabra";
set<char> litery;
for (char c : slowo) litery.insert(c);
cout << litery.size() << "\n";
for (char c : litery) cout << c;
cout << "\n";
▶ Wyjście
5 abdkr

set<char> trzyma pojedyncze znaki. Wrzucamy każdą literę słowa „abrakadabra” — jedenaście liter, ale różnych tylko pięć: a, b, d, k, r. Zbiór wypisuje je alfabetycznie, bo litery porównują się kodami ASCII, a kody liter rosną od a do z.

To samo w jednej linijce: set<char> litery(slowo.begin(), slowo.end()); — napis też ma begin() i end(), tak jak vector.

Zbiór nie ma indeksów

bez_indeksow.cpp
set<int> s = {4, 8, 15};
cout << s[0] << "\n";   // BŁĄD: zbiór nie ma indeksów
▶ Kompilator
error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')

Najważniejsza różnica między zbiorem a vectorem: w zbiorze nie ma numerów miejsc. Nie napiszesz s[0] ani s[i] — program się nie skompiluje.

Dlaczego? Bo zbiór ciągle się przestawia. Gdy wstawisz 1 do zbioru {4, 8, 15}, wszystkie elementy „przesuną się” o jedno miejsce. Numer miejsca nic by nie znaczył. Zbiór to worek, w którym rzeczy leżą po kolei, ale bez etykiet z numerami.

Zbiór przechodzisz pętlą for (int x : s). Najmniejszy i największy element wyjmiesz bez pętli — nauczysz się tego w części 3. A gdy naprawdę potrzebujesz indeksów, przepisz zbiór do vectora.

vector czy set?

vector<int> vset<int> s
powtórzeniazostająznikają same
kolejnośćtaka, w jakiej wkładaszzawsze rosnąca
dodanie elementuv.push_back(x) — na koniecs.insert(x) — na właściwe miejsce
liczba elementówv.size()s.size() — różnych
indeksyv[i]nie ma
przechodzeniefor (int x : v)for (int x : s) — rosnąco

Zasada wyboru jest prosta. Liczy się kolejność z wejścia albo powtórzenia (np. „który był trzeci?”, „ile razy wystąpiło?”) — vector. Liczy się tylko to, jakie wartości wystąpiły (różne, bez powtórzeń, po kolei) — zbiór.

Zapamiętaj set<int> s; — pusty zbiór. s.insert(x) — wkłada x; gdy x już jest, nic się nie dzieje. s.size() — liczba różnych wartości. for (int x : s) — przechodzi zbiór rosnąco. Zbiór nie ma indeksów: s[0] się nie kompiluje. Napisy układają się słownikowo (wielkie litery przed małymi), znaki — alfabetycznie.
Sprawdź się w głowie

Najpierw rozpisz zbiór na kartce — wstawiaj liczby po kolei i skreślaj powtórki — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
set<int> s;
s.insert(4);
s.insert(1);
s.insert(4);
s.insert(9);
s.insert(1);
cout << s.size();
Pokaż odpowiedź
3Pięć wstawień, ale różne wartości to tylko 1, 4 i 9. Powtórzone 4 i 1 zbiór zignorował.
Co wypisze ten fragment?
set<int> s;
s.insert(4);
s.insert(1);
s.insert(4);
s.insert(9);
s.insert(1);
for (int x : s) cout << x << " ";
Pokaż odpowiedź
1 4 9Pętla przechodzi zbiór rosnąco, a każda wartość jest w nim raz — niezależnie od kolejności wstawiania.
Co wypisze ten fragment?
set<int> s = {5, 5, 5, 5};
cout << s.size();
Pokaż odpowiedź
1Cztery piątki to jedna wartość. Zbiór pamięta, że 5 w nim jest, a nie ile razy je podano.
Co wypisze ten fragment?
string t = "mississippi";
set<char> s(t.begin(), t.end());
for (char c : s) cout << c;
Pokaż odpowiedź
impsW słowie są tylko cztery różne litery: m, i, s, p. Zbiór wypisuje je alfabetycznie: i, m, p, s.
Co wypisze ten fragment?
set<string> s = {"b", "a", "B", "a"};
for (string w : s) cout << w << " ";
Pokaż odpowiedź
B a bWielka litera B ma mniejszy kod ASCII niż wszystkie małe litery, więc stoi pierwsza. Drugie „a” odpadło jako powtórka.
Co wypisze ten fragment?
set<int> s;
for (int i = 1; i <= 10; i++) s.insert(i % 3);
cout << s.size();
Pokaż odpowiedź
3Reszty z dzielenia przez 3 to tylko 0, 1 albo 2. Dziesięć wstawień, trzy różne wartości.
Co wypisze ten fragment?
set<string> s = {"10", "9", "100"};
for (string w : s) cout << w << " ";
Pokaż odpowiedź
10 100 9To napisy, a nie liczby — porównują się słownikowo, znak po znaku. „10” jest początkiem „100”, więc stoi przed nim, a „9” zaczyna się od znaku większego niż „1”. Gdyby to był set<int>, kolejność byłaby 9 10 100.
Co wypisze ten fragment?
set<int> s = {-3, 2, -10, 2, 0};
for (int x : s) cout << x << " ";
Pokaż odpowiedź
-10 -3 0 2Rosnąco, czyli od najmniejszej: −10 jest mniejsze od −3. Powtórzona dwójka występuje raz.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

count, erase i empty — czy to już było?

W części 1 zbiór tylko przyjmował liczby. Teraz nauczymy się go pytać i z niego wyjmować. Najczęstsze pytanie w zadaniach brzmi: „czy ta wartość już się pojawiła?”. Ze zbiorem odpowiedź to jedno słowo: count.

count — czy x jest w zbiorze?

count.cpp
set<int> s = {4, 8, 15, 16, 23};
cout << s.count(15) << "\n";
cout << s.count(7) << "\n";
if (s.count(8)) cout << "8 jest\n";
if (!s.count(42)) cout << "42 nie ma\n";
▶ Wyjście
1 0 8 jest 42 nie ma

s.count(x) zwraca, ile razy x jest w zbiorze. W zwykłym zbiorze każda wartość jest najwyżej raz, więc wynik to zawsze 1 (jest) albo 0 (nie ma).

Dlatego count świetnie pasuje do if: 1 znaczy prawdę, 0 — fałsz. if (s.count(8)) czytamy „jeśli 8 jest w zbiorze”, a if (!s.count(42)) — „jeśli 42 nie ma w zbiorze”. Wykrzyknik odwraca warunek, znasz go z lekcji o typach.

Nazwa „count” (policz) wydaje się dziwna dla pytania „czy jest?”. Ma sens dopiero w multiset z części 7, gdzie wartość może być kilka razy.

Czy to już było? Najpierw pytaj, potem wkładaj

nowy_czy_znany.cpp
int n;
cin >> n;
set<int> widziane;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (widziane.count(x)) cout << x << " ZNANY\n";
    else cout << x << " NOWY\n";
    widziane.insert(x);
}
▶ Wejście
6 3 7 3 1 7 7
▶ Wyjście
3 NOWY 7 NOWY 3 ZNANY 1 NOWY 7 ZNANY 7 ZNANY

To jeden z najważniejszych schematów tej lekcji. Zbiór widziane pamięta wszystko, co już przeczytaliśmy. Dla każdej nowej liczby:

1) pytamy, czy już ją widzieliśmy (count),
2) wypisujemy odpowiedź,
3) dopisujemy ją do widzianych (insert).

Kolejność kroków 1 i 3 jest kluczowa. Gdybyśmy najpierw wstawili, a potem zapytali, każda liczba byłaby „znana” — przecież przed chwilą ją wstawiliśmy.

krokxwidziane przed krokiemcount(x)wypisz
13{ }03 NOWY
27{3}07 NOWY
33{3, 7}13 ZNANY
41{3, 7}01 NOWY
57{1, 3, 7}17 ZNANY
67{1, 3, 7}17 ZNANY
zla_kolejnosc.cpp
int n;
cin >> n;
set<int> widziane;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    widziane.insert(x);        // ZA WCZEŚNIE!
    if (widziane.count(x)) cout << x << " ZNANY\n";
    else cout << x << " NOWY\n";
}
▶ Wejście
3 5 6 5
▶ Wyjście — źle
5 ZNANY 6 ZNANY 5 ZNANY

Ten program zawsze odpowiada „ZNANY”. Każda liczba jest wstawiana przed pytaniem, więc count zawsze ją znajduje. Program się kompiluje i działa — tylko liczy co innego, niż chcieliśmy. Takie błędy najtrudniej zauważyć, dlatego warto sprawdzać program na małym przykładzie z treści.

Pierwsza powtórka

pierwsza_powtorka.cpp
int n;
cin >> n;
set<int> widziane;
for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if (widziane.count(x)) {
        cout << "powtorka: " << x << " na pozycji " << i << "\n";
        return 0;
    }
    widziane.insert(x);
}
cout << "wszystkie rozne\n";
▶ Wejście 1
7 5 1 9 1 5 2 9
▶ Wyjście 1
powtorka: 1 na pozycji 4
▶ Wejście 2
4 8 6 7 5
▶ Wyjście 2
wszystkie rozne

Szukamy pierwszej liczby, która pojawia się drugi raz. Czytamy po kolei i przy pierwszym trafieniu count od razu kończymy program: return 0; wewnątrz main to natychmiastowy koniec.

Uwaga na słowo „pierwsza”. Liczba 5 też się powtarza, i to wcześniej zaczyna (jest na pozycji 1). Ale jej drugie wystąpienie jest dopiero na pozycji 5, a drugie wystąpienie jedynki — na pozycji 4. Wygrywa ta powtórka, którą spotkamy wcześniej, czytając od lewej.

Jeśli pętla dojdzie do końca bez trafienia, wszystkie liczby były różne.

insert mówi, czy coś dodał

insert_second.cpp
set<int> s;
cout << s.insert(5).second << "\n";
cout << s.insert(5).second << "\n";
cout << s.insert(7).second << "\n";
cout << s.size() << "\n";
▶ Wyjście
1 0 1 2

Dla ciekawych: insert nie tylko wkłada, ale też odpowiada. Zwraca parę (znasz pary z lekcji Pair). Jej second to true, gdy element był nowy i został dodany, albo false, gdy już był. (first to strzałka na element — przyda się w części 4.)

Dzięki temu „nowy czy znany” można napisać jednym if, bez osobnego count:

if (s.insert(x).second) cout << "NOWY\n";
else cout << "ZNANY\n";

Oba sposoby są poprawne. Na początek count + insert jest czytelniejsze.

erase — wyjmij x ze zbioru

erase.cpp
set<int> s = {1, 2, 3, 4, 5};
s.erase(3);
s.erase(10);          // 10 nie ma — nic się nie dzieje
for (int x : s) cout << x << " ";
cout << "\n";
int a = s.erase(1);   // 1 był — usunięty
int b = s.erase(1);   // już go nie ma
cout << a << " " << b << " " << s.size() << "\n";
▶ Wyjście
1 2 4 5 1 0 3

s.erase(x) usuwa wartość x ze zbioru. Reszta elementów zostaje w tym samym porządku — „dziura” po trójce sama się zamyka.

Gdy x nie ma w zbiorze, erase nic nie robi — bez błędu, tak samo jak insert powtórki. Nie musisz sprawdzać count przed usunięciem.

erase zwraca też, ile elementów usunął: 1, gdy x był, i 0, gdy go nie było. Czasem to się przydaje, np. żeby policzyć udane usunięcia.

Zbiór przed usuwaniem — szara trójka zaraz zniknie.
Po erase(3), erase(10) i erase(1) zostają 2, 4 i 5 — wciąż rosnąco, bez dziur.

empty i clear

empty_clear.cpp
set<int> s = {3, 1};
cout << s.empty() << "\n";
s.clear();
cout << s.empty() << " " << s.size() << "\n";
▶ Wyjście
0 1 0

s.empty() odpowiada na pytanie „czy zbiór jest pusty?”: 1 (prawda), gdy nic w nim nie ma, i 0 (fałsz), gdy coś jest. To to samo co s.size() == 0, tylko krócej.

s.clear() usuwa wszystkie elementy naraz. Po nim zbiór jest pusty, jak świeżo utworzony.

Kilka testów w jednym wejściu: nowy zbiór na każdy test

testy_dobrze.cpp
int t;
cin >> t;
while (t--) {
    int n;
    cin >> n;
    set<int> s;      // nowy, pusty zbiór w każdym teście
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size() << "\n";
}
▶ Wejście
3 3 1 1 1 4 1 2 3 4 2 5 6
▶ Wyjście
1 4 2
testy_zle.cpp
int t;
cin >> t;
set<int> s;          // jeden zbiór na wszystkie testy!
while (t--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size() << "\n";
}
▶ Wejście
3 3 1 1 1 4 1 2 3 4 2 5 6
▶ Wyjście — źle
1 4 6

Gdy wejście zawiera kilka niezależnych testów, każdy test potrzebuje własnego, pustego zbioru. Lewy program tworzy zbiór wewnątrz pętli while — przy każdym obrocie powstaje nowy. Prawy ma jeden zbiór na zewnątrz i trzeci test widzi jeszcze liczby z drugiego: zamiast 2 wypisuje 6. Jeśli wolisz trzymać zbiór na zewnątrz, wywołaj s.clear(); na początku każdego testu.

Polecenia: wjazd, wyjazd, pytanie

parking.cpp
int q;
cin >> q;
set<int> parking;
while (q--) {
    string polecenie;
    int nr;
    cin >> polecenie >> nr;
    if (polecenie == "WJAZD") parking.insert(nr);
    else if (polecenie == "WYJAZD") parking.erase(nr);
    else {
        if (parking.count(nr)) cout << "TAK\n";
        else cout << "NIE\n";
    }
}
cout << "aut: " << parking.size() << "\n";
▶ Wejście
6 WJAZD 1234 WJAZD 777 CZY 777 WYJAZD 777 CZY 777 CZY 1234
▶ Wyjście
TAK NIE TAK aut: 1

Zbiór jest idealny do pilnowania, kto teraz jest w środku: auta na parkingu, uczniowie w bibliotece, gracze w pokoju gry. Każde polecenie to jedno słowo i numer. WJAZD wkłada numer do zbioru, WYJAZD go wyjmuje, a CZY pyta o obecność.

Polecenie wczytujemy do string i porównujemy przez ==, jak w lekcji o napisach. Na końcu size() mówi, ile aut zostało. Gdyby numery rejestracyjne były napisami (np. „WA 12345”), wystarczy set<string> — wszystko inne zostaje takie samo.

Lista brakujących

brakujace.cpp
int n, m;
cin >> n >> m;
set<int> mam;
for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    mam.insert(x);
}
for (int k = 1; k <= n; k++)
    if (!mam.count(k)) cout << k << " ";
cout << "\n";
▶ Wejście
10 6 3 9 1 3 10 4
▶ Wyjście
2 5 6 7 8

Kolekcja ma naklejki od 1 do n = 10, a my mamy m = 6 naklejek (z powtórkami). Których brakuje? Wrzucamy posiadane do zbioru, a potem przechodzimy wszystkie numery od 1 do n i wypisujemy te, o które count mówi 0.

To odwrócenie pytania: nie „co mam?”, tylko „czego nie mam?”. Odpowiedź wychodzi od razu rosnąco, bo pętla idzie po numerach od 1 w górę.

Jak szybko działa count?

W vectorze, żeby sprawdzić, czy jest w nim x, trzeba przejrzeć wszystkie elementy po kolei (find albo pętla) — w lekcji o złożoności nazwaliśmy to O(n). Zbiór jest zbudowany sprytniej: trzyma elementy jak w drzewie, gdzie każde pytanie odrzuca połowę tego, co zostało (zobaczysz to w części 8). Dlatego count, insert i erase kosztują O(log n) — dla stu tysięcy elementów to około 17 kroków.

n liczb, dla każdej pytamy „czy już była?”vector + przeglądanieset + count
jedno pytaniedo n krokówokoło log₂ n kroków
n = 1 000ok. 500 000 krokówok. 10 000 kroków
n = 100 000ok. 5 000 000 000 — za wolnook. 1 700 000 — błyskawicznie
Zapamiętaj s.count(x) — 1, gdy x jest, 0, gdy nie ma (idealne do if). „Czy już było?”: najpierw count, potem insert. s.erase(x) — usuwa x; gdy go nie ma, nic się nie dzieje (zwraca 0). s.empty() — czy pusty, s.clear() — usuń wszystko. Przy kilku testach: nowy zbiór (albo clear) w każdym teście. Wszystkie te operacje są szybkie: O(log n).
Sprawdź się w głowie

Rozpisz zbiór na kartce po każdej linijce. Uważaj na kolejność count i insert.

Co wypisze ten fragment?
set<int> s = {2, 4, 6};
cout << s.count(4) + s.count(5);
Pokaż odpowiedź
14 jest w zbiorze (count = 1), 5 nie ma (count = 0). Razem 1.
Co wypisze ten fragment?
set<int> s = {1, 2, 3};
s.erase(2);
s.erase(2);
s.insert(2);
s.erase(3);
cout << s.size();
Pokaż odpowiedź
2Po kolei: {1, 3}, dalej {1, 3} (drugie erase nic nie robi), {1, 2, 3}, {1, 2}. Zostały dwa elementy.
Co wypisze ten program dla podanego wejścia?
int n;
cin >> n;
set<int> w;
int ile = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (!w.count(x)) ile++;
    w.insert(x);
}
cout << ile;
Wejście: 5 4 4 2 4 2
Pokaż odpowiedź
2ile zwiększa się tylko dla nowych liczb: pierwszej czwórki i pierwszej dwójki. To po prostu liczba różnych wartości.
Co wypisze ten fragment?
vector<int> v = {3, 1, 3, 3, 2, 1};
set<int> s;
int nowe = 0;
for (int x : v) nowe += s.insert(x).second;
cout << nowe;
Pokaż odpowiedź
3second jest prawdą (czyli 1) tylko wtedy, gdy liczba została naprawdę dodana: dla pierwszej trójki, jedynki i dwójki.
Co wypisze ten fragment?
set<int> s = {10, 20};
cout << s.erase(7) << s.erase(10) << s.size();
Pokaż odpowiedź
011erase(7) nic nie usuwa — 0. erase(10) usuwa jeden element — 1. Zostaje {20}, więc size() = 1. Liczby są wypisane bez spacji, więc wychodzi 011.
Co wypisze ten fragment?
set<int> s = {5};
s.erase(5);
cout << s.empty() << " ";
s.insert(5);
s.insert(5);
cout << s.empty() << " " << s.size();
Pokaż odpowiedź
1 0 1Po usunięciu jedynej liczby zbiór jest pusty (1). Potem dwa razy wstawiamy 5 — zbiór ma jeden element, więc empty() = 0, a size() = 1.
Ten program ma liczyć liczby, które są powtórkami. Co wypisze?
int n;
cin >> n;
set<int> w;
int powt = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    w.insert(x);
    if (w.count(x)) powt++;
}
cout << powt;
Wejście: 4 9 9 9 9
Pokaż odpowiedź
4To błąd kolejności: insert stoi przed count, więc count zawsze znajduje x i każda liczba liczy się jako powtórka. Poprawna wersja (najpierw count, potem insert) wypisałaby 3.
Co wypisze ten program dla podanego wejścia?
int t;
cin >> t;
set<int> s;
while (t--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size() << " ";
}
Wejście: 2 2 7 7 2 7 8
Pokaż odpowiedź
1 2Zbiór jest jeden dla obu testów. Po pierwszym: {7}, size 1. W drugim siódemka już jest, dochodzi tylko 8: {7, 8}, size 2. Przypadkiem wynik drugiego testu jest dobry — ale tylko dlatego, że 7 występowało w obu. Bez clear() w każdym teście to błąd, który wychodzi na innych danych.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

2.1 Nowy czy znany?łatwe✓ zaliczone Czytelnicy pokazują karty biblioteczne. Kto przyszedł pierwszy raz, a kto już był? countnajpierw pytaj, potem wstaw Rozwiąż 2.2 Pierwsza powtórka w każdej grzełatwe✓ zaliczone Kilka gier w pamięć. W każdej: która karta jako pierwsza pojawiła się drugi raz? Czytaj do końca! countkilka testównowy zbiór w teście Rozwiąż 2.3 Polecenia dla zbiorułatwe✓ zaliczone DODAJ, USUN i CZY — wykonaj polecenia na zbiorze i odpowiadaj na pytania. inserterasecountpolecenia Rozwiąż 2.4 Kto nie przyszedł?łatwe✓ zaliczone Lista klasy i wpisy obecnych. Wypisz nieobecnych w kolejności z dziennika: vector + set. set<string>countkolejność z wejścia Rozwiąż 2.5 Kto jest na imprezie?średnie✓ zaliczone WCHODZI i WYCHODZI. Po każdym wpisie: ile osób w środku? Na koniec — kto został. inserterasesize()set<string> Rozwiąż 2.6 Liczby szczęśliweśrednie✓ zaliczone Zamieniaj liczbę na sumę kwadratów cyfr. Dojdziesz do 1 czy wpadniesz w pętlę? Zbiór wykryje powtórkę. countwykrywanie pętlicyfry liczby Rozwiąż 2.7 Pełna kolekcjałatwe✓ zaliczone Album ma k naklejek. Po której kupionej naklejce jest pełny? A jeśli nigdy — ilu brakuje? insertsize() == kmoment zapełnienia Rozwiąż 2.8 Rejestracja w grześrednie✓ zaliczone Login zajęty? Dopisz najmniejszą liczbę, która daje wolny login. Każdy przyznany login staje się zajęty. set<string>count w pętlito_string Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

begin, rbegin i iteratory — najmniejszy i największy

Zbiór nie ma indeksów, ale za to zawsze jest posortowany. To znaczy, że najmniejszy element stoi na samym początku, a największy — na samym końcu. Żeby je wyjąć, użyjemy strzałek, czyli iteratorów, które znasz z lekcji o vectorze: begin() wskazuje pierwszy element, end() — miejsce za ostatnim, a gwiazdka * mówi „daj to, na co wskazuje strzałka”.

Najmniejszy: *s.begin(), największy: *s.rbegin()

skrajne.cpp
set<int> s = {15, 4, 23, 8, 16};
cout << *s.begin() << "\n";    // najmniejszy
cout << *s.rbegin() << "\n";   // największy
▶ Wyjście
4 23

s.begin() to strzałka na pierwszy element zbioru. Zbiór jest posortowany rosnąco, więc pierwszy element to najmniejszy. Gwiazdka przed nią zamienia strzałkę na wartość: *s.begin() = 4.

s.rbegin() to strzałka „od tyłu” — znasz ją z lekcji o sortowaniu (r jak reverse, odwrotnie). Wskazuje ostatni element, czyli największy: *s.rbegin() = 23.

Bez gwiazdki program się nie skompiluje albo wypisze nie to, co trzeba: strzałka to nie liczba.

begin() wskazuje najmniejszy element, rbegin() — największy, a end() stoi ZA ostatnim elementem, na pustym miejscu. *s.end() to błąd: tam nic nie ma.

prev i next — o jeden w lewo, o jeden w prawo

prev_next.cpp
set<int> s = {15, 4, 23, 8, 16};
auto ost = prev(s.end());      // ostatni element
cout << *ost << "\n";
auto drugi = next(s.begin());  // drugi element
cout << *drugi << "\n";
cout << *prev(ost) << "\n";    // przedostatni
▶ Wyjście
23 8 16

next(it) daje strzałkę o jeden element dalej, a prev(it) — o jeden wcześniej. Sama strzałka it się przy tym nie zmienia.

Największy element można więc wyjąć też tak: *prev(s.end()) — „jeden przed miejscem za końcem”, czyli ostatni. To ten sam element co *s.rbegin(), ale strzałka jest „zwykła” — przyda się, gdy będziemy go usuwać.

Słowo auto poznałeś przy iteratorach vectora: prawdziwa nazwa typu strzałki to set<int>::iterator. Za długa — niech kompilator zgadnie.

next przesuwa strzałkę o jeden element w prawo, prev — o jeden w lewo.

Uwaga na pusty zbiór

pusty.cpp
set<int> s;
if (s.empty()) cout << "pusty - nie ma najmniejszego\n";
else cout << *s.begin() << "\n";
s.insert(7);
if (s.empty()) cout << "pusty - nie ma najmniejszego\n";
else cout << *s.begin() << "\n";
▶ Wyjście
pusty - nie ma najmniejszego 7

W pustym zbiorze begin() i end() to ta sama strzałka — wskazuje miejsce, w którym nic nie ma. *s.begin() na pustym zbiorze to błąd: program może wypisać przypadkową liczbę albo się wysypać. Kompilator Cię nie ostrzeże.

Dlatego zanim sięgniesz po najmniejszy albo największy element, zawsze sprawdź !s.empty(). Szczególnie wtedy, gdy elementy są usuwane — zbiór, który był pełny, w pewnej chwili może się opróżnić.

Strzałka idzie przez zbiór: it++

petla_iterator.cpp
set<int> s = {30, 10, 20};
for (auto it = s.begin(); it != s.end(); it++)
    cout << *it << " ";
cout << "\n";
for (int x : s) cout << x << " ";
cout << "\n";
▶ Wyjście
10 20 30 10 20 30

Obie pętle robią to samo. Pierwsza pokazuje, co dzieje się „pod spodem” pętli for (int x : s): strzałka startuje na begin(), w każdym obrocie przesuwa się o jeden (it++) i kończy, gdy dojdzie do end().

Po co pisać dłużej? Bo strzałka wie, gdzie jesteśmy. Mając it, możemy zajrzeć do sąsiada: *prev(it) albo *next(it). Pętla for (int x : s) daje tylko wartość, bez sąsiadów.

Strzałki w zbiorze nie skaczą

skok_blad.cpp
set<int> s = {4, 8, 15};
auto it = s.begin() + 1;   // BŁĄD: w zbiorze nie ma skoków
cout << *it << "\n";
▶ Kompilator
error: no match for 'operator+' (operand types are 'std::set<int>::iterator' … and 'int')

W vectorze można było napisać v.begin() + 2 — strzałka skakała od razu o dwa miejsca. W zbiorze nie: strzałka umie iść tylko krok po kroku, it++ albo it--. Elementy zbioru nie leżą w pamięci obok siebie jak w vectorze, więc nie da się „przeskoczyć” policzonej liczby miejsc.

Zamiast + 1 pisz next(it), a zamiast + k — next(it, k). Ale uwaga: next(it, k) po cichu robi k kroków, więc kosztuje O(k), a nie jeden krok.

Od największego: rbegin i rend albo greater

malejaco.cpp
set<int> s = {3, 9, 1, 7};
for (auto it = s.rbegin(); it != s.rend(); it++)
    cout << *it << " ";
cout << "\n";
set<int, greater<int>> m = {3, 9, 1, 7};
for (int x : m) cout << x << " ";
cout << "\n";
cout << *m.begin() << "\n";
▶ Wyjście
9 7 3 1 9 7 3 1 9

Dwa sposoby na przechodzenie od największego. Pierwszy: strzałki od tyłu — rbegin() wskazuje ostatni element, a rend() to miejsce „przed pierwszym”. it++ na takiej strzałce idzie w lewo.

Drugi: zbiór, który sam trzyma elementy malejąco. W nawiasach ostrych dopisujemy regułę greater<int> — tę samą, której używaliśmy w sort. Wtedy begin() wskazuje największy element, a pętla for idzie od góry.

Uwaga na >> w set<int, greater<int>>: dwa nawiasy ostre obok siebie są w porządku od C++11.

Wyjmowanie najmniejszego i największego

usun_skrajne.cpp
set<int> s = {5, 1, 9, 3, 7};
s.erase(s.begin());        // usuwa najmniejszy (1)
s.erase(prev(s.end()));    // usuwa największy (9)
for (int x : s) cout << x << " ";
cout << "\n";
▶ Wyjście
3 5 7
po_kolei_najmniejszy.cpp
set<int> s = {40, 10, 30, 20};
while (!s.empty()) {
    int x = *s.begin();
    s.erase(s.begin());
    cout << "biore " << x << ", zostalo " << s.size() << "\n";
}
▶ Wyjście
biore 10, zostalo 3 biore 20, zostalo 2 biore 30, zostalo 1 biore 40, zostalo 0

erase przyjmuje nie tylko wartość, ale też strzałkę: s.erase(s.begin()) usuwa element, na który wskazuje begin(), czyli najmniejszy. Największy usuwamy przez s.erase(prev(s.end())). (Strzałki od tyłu, rbegin(), do erase nie pasują — stąd prev(end()).)

Drugi program to ważny schemat: bierz zawsze najmniejszy. Pętla działa, dopóki zbiór nie jest pusty; w każdym obrocie zapamiętuje najmniejszą wartość, usuwa ją i coś z nią robi. Najpierw zapamiętaj wartość (int x = *s.begin();), potem usuwaj — po erase strzałka wskazuje już nieistniejący element i nie wolno jej używać.

Sąsiedzi w zbiorze: różnice między kolejnymi

sasiedzi.cpp
set<int> s = {3, 10, 4, 20, 12};
for (auto it = next(s.begin()); it != s.end(); it++)
    cout << *prev(it) << "->" << *it << " roznica " << *it - *prev(it) << "\n";
▶ Wyjście
3->4 roznica 1 4->10 roznica 6 10->12 roznica 2 12->20 roznica 8

Zbiór jest posortowany, więc sąsiedzi w zbiorze to najbliższe sobie liczby — tak jak sąsiedzi w posortowanym vectorze z lekcji o sortowaniu. Pętla startuje od drugiego elementu (next(s.begin())) i dla każdego zagląda do poprzedniego (*prev(it)).

Z takich różnic łatwo wyciągnąć najmniejszą albo największą przerwę między różnymi liczbami. Uwaga: pętla zakłada, że zbiór ma co najmniej jeden element — next(begin()) w pustym zbiorze to błąd. Gdy element jest jeden, next(begin()) to już end() i pętla po prostu się nie wykona.

k-ty najmniejszy: k − 1 kroków

kty.cpp
set<int> s = {50, 20, 40, 10, 30, 20};
int k = 3;
auto it = s.begin();
for (int i = 1; i < k; i++) it++;
cout << *it << "\n";
cout << *next(s.begin(), k - 1) << "\n";
▶ Wyjście
30 30

Trzeci najmniejszy różny element to ten, do którego dojdziemy z begin() po dwóch krokach. Dwa sposoby: pętla z it++ albo next(s.begin(), k - 1). Pierwszy element to krok zero — stąd k − 1.

Przed takim chodzeniem sprawdź, czy k <= s.size(). Inaczej strzałka wyjdzie za koniec zbioru. I pamiętaj, że to kosztuje k kroków — dla jednego pytania to nic, ale dla tysięcy pytań o duże k lepiej przepisać zbiór do vectora i używać w[k - 1].

Elementów zbioru nie zmienia się na miejscu

zmiana_blad.cpp
set<int> s = {1, 5, 9};
for (int &x : s) x = x * 10;   // BŁĄD
▶ Kompilator
error: binding reference of type 'int&' to 'const int' discards qualifiers
zmiana_dobrze.cpp
set<int> s = {1, 5, 9};
s.erase(5);
s.insert(50);     // „zmiana” 5 na 50 = usuń i wstaw
for (int x : s) cout << x << " ";
cout << "\n";
▶ Wyjście
1 9 50

W vectorze pętla for (int &x : v) zmieniała elementy. W zbiorze to się nie skompiluje: elementy zbioru są stałe (const). Gdyby dało się zmienić 5 na 50 w miejscu, zbiór przestałby być posortowany — a całe jego działanie opiera się na tym, że zawsze jest.

Zmiana wartości w zbiorze to zawsze dwa kroki: usuń starą, wstaw nową. Zbiór sam postawi nową wartość na właściwym miejscu — 50 trafia na koniec.

Zapamiętaj Najmniejszy: *s.begin(). Największy: *s.rbegin() albo *prev(s.end()). Zawsze najpierw sprawdź !s.empty(). next(it) i prev(it) — sąsiedzi strzałki. W zbiorze strzałka chodzi tylko krokami (it++, it--), nie ma it + 2. Usuwanie skrajnych: s.erase(s.begin()), s.erase(prev(s.end())). Malejąco: set<int, greater<int>> albo rbegin()…rend(). Zmiana elementu = erase + insert.
Sprawdź się w głowie

Narysuj zbiór na kartce jako rząd kulek i zaznacz, gdzie wskazuje każda strzałka.

Co wypisze ten fragment?
set<int> s = {5, 1, 9};
cout << *s.begin() + *s.rbegin();
Pokaż odpowiedź
10Najmniejszy to 1, największy to 9 — razem 10.
Co wypisze ten fragment?
set<int> s = {30, 10, 20};
cout << *next(s.begin());
Pokaż odpowiedź
20Zbiór to {10, 20, 30}. begin() wskazuje 10, a next o jeden dalej — 20.
Co wypisze ten fragment?
set<int> s = {2, 8, 2, 8};
cout << *prev(s.end()) << " " << s.size();
Pokaż odpowiedź
8 2Zbiór to {2, 8}. Element tuż przed end() to ostatni, czyli 8. Różne wartości są dwie.
Co wypisze ten fragment?
set<int> s = {4, 1, 3, 2};
s.erase(s.begin());
s.erase(s.begin());
for (int x : s) cout << x << " ";
Pokaż odpowiedź
3 4Za każdym razem usuwamy najmniejszy: najpierw 1, potem 2. Zostają 3 i 4.
Co wypisze ten fragment?
set<int, greater<int>> s = {1, 5, 3};
cout << *s.begin() << " " << *s.rbegin();
Pokaż odpowiedź
5 1Z regułą greater zbiór jest posortowany malejąco: {5, 3, 1}. begin() wskazuje teraz największy, a rbegin() — najmniejszy.
Co wypisze ten fragment?
set<int> s = {7, 2, 9, 4};
int ile = 0;
for (auto it = s.rbegin(); it != s.rend() && ile < 2; it++) {
    cout << *it << " ";
    ile++;
}
Pokaż odpowiedź
9 7Strzałka od tyłu zaczyna od największego. Pętla kończy się po dwóch elementach — to dwa największe.
Co wypisze ten fragment?
set<int> s = {10, 20, 30, 40};
auto it = s.begin();
it++;
it++;
cout << *it << " " << *prev(it);
Pokaż odpowiedź
30 20Dwa kroki od początku: 10 → 20 → 30. Element przed nim to 20.
Co wypisze ten fragment?
set<int> s = {8, 3, 5, 3, 1};
cout << *next(s.begin(), 2);
Pokaż odpowiedź
5Zbiór to {1, 3, 5, 8} — druga trójka odpadła. Dwa kroki od początku: 1 → 3 → 5. To trzecia najmniejsza różna wartość.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

3.1 Różne, od największejłatwe✓ zaliczone Wypisz różne wartości malejąco: rbegin i rend albo set z regułą greater. rbegin / rendgreater<int>malejąco Rozwiąż 3.2 Drugi najlepszy wynikłatwe✓ zaliczone Srebro dostają wszyscy z drugim najlepszym różnym wynikiem. Jaki to wynik i ilu jest srebrnych? next(s.rbegin())size() >= 2vector + set Rozwiąż 3.3 k-ta najmniejsza różnałatwe✓ zaliczone Wiele pytań o k-tą najmniejszą różną wartość. Zbiór do vectora — i masz indeksy. vector(s.begin(), s.end())k − 1BRAK Rozwiąż 3.4 Najmniejszy i największy na żywośrednie✓ zaliczone DODAJ, USUN, MIN, MAX. Pamiętaj o pustym zbiorze przed *begin(). *s.begin()*s.rbegin()empty() Rozwiąż 3.5 Odstępy między słupkamiśrednie✓ zaliczone Słupki na osi, niektóre wpisane kilka razy. Najmniejszy i największy odstęp między sąsiednimi. sąsiedzi w zbiorzeprev(it)min i max Rozwiąż 3.6 Zabieranie z obu końcówśrednie✓ zaliczone Ala bierze największą kartkę, Bartek najmniejszą, na zmianę. Ile zbierze każde z nich? erase(s.begin())erase(prev(s.end()))long long Rozwiąż 3.7 Rozrzut po każdym dniułatwe✓ zaliczone Po każdym pomiarze: ile różnych temperatur było i ile wynosi różnica między skrajnymi. size()*rbegin() − *begin()po każdym kroku Rozwiąż 3.8 Ciąg z dwóch regułtrudne✓ zaliczone Z x powstają 2x + 1 i 3x + 1. Jaka jest n-ta najmniejsza liczba? Zbiór jako kolejka „zawsze najmniejszy”. *s.begin() i erasezbiór jako kolejkalong long Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

find, lower_bound i upper_bound — szukanie w zbiorze

count odpowiada tylko „jest” albo „nie ma”. Często chcemy więcej: gdzie jest dana wartość, jaka jest najbliższa większa, jaka najbliższa mniejsza. W lekcji o sortowaniu takie pytania zadawaliśmy posortowanemu vectorowi przez lower_bound i upper_bound. Zbiór jest zawsze posortowany, więc ma te same polecenia — i działają one nawet wtedy, gdy elementy ciągle dochodzą i znikają.

find — strzałka na x albo end()

find.cpp
set<int> s = {3, 8, 15, 21, 30};
auto it = s.find(15);
if (it != s.end()) cout << "jest: " << *it << "\n";
if (s.find(16) == s.end()) cout << "16 nie ma\n";
s.erase(s.find(8));        // usuwanie przez strzałkę
for (int x : s) cout << x << " ";
cout << "\n";
▶ Wyjście
jest: 15 16 nie ma 3 15 21 30

s.find(x) szuka x i zwraca strzałkę na niego. Gdy x nie ma, zwraca s.end() — strzałkę „za końcem”, która znaczy „nie znaleziono”. Dlatego wynik find zawsze porównujemy z s.end().

Kiedy find, a kiedy count? Do pytania „czy jest?” wystarczy count. find przydaje się, gdy chcesz potem coś zrobić z tym miejscem: usunąć element strzałką, zajrzeć do jego sąsiadów prev i next.

Uwaga: s.erase(s.find(x)) jest bezpieczne tylko wtedy, gdy x na pewno jest. Gdy go nie ma, to erase(end()) — błąd, który potrafi wysypać program. Do usuwania wartości wystarczy zwykłe s.erase(x).

lower_bound i upper_bound — pierwszy ≥ x i pierwszy > x

lower_upper.cpp
set<int> s = {3, 8, 15, 21, 30};
cout << *s.lower_bound(10) << "\n";   // pierwszy >= 10
cout << *s.lower_bound(15) << "\n";   // pierwszy >= 15
cout << *s.upper_bound(15) << "\n";   // pierwszy > 15
if (s.lower_bound(31) == s.end()) cout << "nic >= 31\n";
▶ Wyjście
15 15 21 nic >= 31

s.lower_bound(x) zwraca strzałkę na pierwszy element większy lub równy x. Dla x = 10 to 15 — w zbiorze nie ma 10, więc dostajemy najbliższą większą. Dla x = 15 to samo 15, bo „lub równy”.

s.upper_bound(x) zwraca strzałkę na pierwszy element ściśle większy od x. Dla 15 to już 21 — sama piętnastka jest pomijana.

Gdy takiego elementu nie ma, obie zwracają s.end(). Gwiazdka na end() to błąd, więc przed wypisaniem zawsze sprawdź != s.end(). To dokładnie te same pojęcia co w lekcji o sortowaniu — tylko zapisane z kropką, jako polecenie zbioru.

Strzałki dla trzech pytań z programu obok. Dla 31 nie ma elementu ≥ 31 — strzałka stoi na end().

Przesuwaj suwak i obserwuj, jak zmieniają się strzałki. Zwróć uwagę, co się dzieje, gdy x jest w zbiorze (lower i upper rozjeżdżają się o jeden element), a co, gdy go nie ma (wskazują to samo miejsce). Sprawdź też krańce: x mniejsze od wszystkich i większe od wszystkich.

Szukanie w zbiorze — przesuń x
Ta ramka działa po włączeniu JavaScriptu.
W zbiorze szukaj z kropką Z lekcji o sortowaniu znasz zapis lower_bound(v.begin(), v.end(), x). Na zbiorze też się skompiluje i da dobry wynik — ale będzie wolny. Strzałki zbioru nie umieją skakać (część 3), więc ta wersja przechodzi elementy po kolei: O(n) zamiast O(log n). W zbiorze zawsze pisz z kropką: s.lower_bound(x), s.upper_bound(x), s.find(x).

Ostatni ≤ x i ostatni < x — strzałka o jeden w lewo

poprzednik.cpp
set<int> s = {3, 8, 15, 21, 30};
int x;
cin >> x;
auto it = s.upper_bound(x);       // pierwszy > x
if (it == s.begin()) cout << "nic <= x\n";
else cout << "ostatni <= x: " << *prev(it) << "\n";
auto jt = s.lower_bound(x);       // pierwszy >= x
if (jt == s.begin()) cout << "nic < x\n";
else cout << "ostatni < x: " << *prev(jt) << "\n";
▶ Wejście 1
21
▶ Wyjście 1
ostatni <= x: 21 ostatni < x: 15
▶ Wejście 2
2
▶ Wyjście 2
nic <= x nic < x

Zbiór nie ma osobnego polecenia „największy element ≤ x”. Ale łatwo go zbudować: weź upper_bound(x) — pierwszy element większy od x — i cofnij strzałkę o jeden. Element tuż przed nim jest ostatnim, który nie jest większy od x, czyli ostatnim ≤ x.

Tak samo z lower_bound(x): cofnięcie daje ostatni element mniejszy od x.

Pułapka: cofać wolno tylko wtedy, gdy strzałka nie stoi na begin(). Jeśli upper_bound(x) == s.begin(), to wszystkie elementy są większe od x i przed strzałką nic nie ma. Dla x = 2 tak właśnie jest.

pytaniestrzałkabrak odpowiedzi, gdy
czy x jest? gdzie?s.find(x)== s.end()
pierwszy ≥ xs.lower_bound(x)== s.end()
pierwszy > xs.upper_bound(x)== s.end()
ostatni ≤ xprev(s.upper_bound(x))s.upper_bound(x) == s.begin()
ostatni < xprev(s.lower_bound(x))s.lower_bound(x) == s.begin()

Najbliższa wartość: sprawdź sąsiada z prawej i z lewej

najblizsza.cpp
set<int> s = {3, 8, 15, 21, 30};
int x;
cin >> x;
auto it = s.lower_bound(x);       // kandydat z prawej (>= x)
int odp;
if (it == s.end()) odp = *prev(it);        // wszystkie < x
else if (it == s.begin()) odp = *it;       // wszystkie >= x
else {
    int prawy = *it, lewy = *prev(it);
    if (x - lewy <= prawy - x) odp = lewy;  // remis: mniejszy
    else odp = prawy;
}
cout << odp << "\n";
▶ Wejście 1
11
▶ Wyjście 1
8
▶ Wejście 2
18
▶ Wyjście 2
15
▶ Wejście 3
100
▶ Wyjście 3
30

Najbliższa x wartość w zbiorze jest albo pierwszą ≥ x, albo ostatnią < x — czyli jednym z dwóch sąsiadów miejsca, w którym x by stał. Nie trzeba przeglądać całego zbioru: wystarczy porównać tych dwóch kandydatów.

Dla x = 11 kandydaci to 15 (odległość 4) i 8 (odległość 3) — wygrywa 8. Dla x = 18 obaj, 15 i 21, są w odległości 3; przy remisie bierzemy mniejszy. Dla x = 100 nie ma kandydata z prawej (it == s.end()), więc odpowiedzią jest ostatni element.

Program zakłada, że zbiór nie jest pusty. Trzy przypadki — koniec, początek i środek — to stały element każdego programu z najbliższą wartością.

Zbiór, który rośnie: pytania przeplatane z dodawaniem

dworce.cpp
int q;
cin >> q;
set<int> dworce;
while (q--) {
    string p;
    int x;
    cin >> p >> x;
    if (p == "BUDUJ") dworce.insert(x);
    else {
        auto it = dworce.lower_bound(x);
        if (it == dworce.end()) cout << "BRAK\n";
        else cout << *it << "\n";
    }
}
▶ Wejście
6 BUDUJ 50 JEDZ 10 BUDUJ 20 JEDZ 10 JEDZ 51 JEDZ 50
▶ Wyjście
50 20 BRAK 50

Wzdłuż prostej drogi budowane są dworce (pozycja x). Podróżny, który rusza z punktu x i jedzie w prawo, zatrzyma się na pierwszym dworcu o pozycji ≥ x. Polecenia budowy i pytania przychodzą na przemian.

Tu widać, po co zbiór, skoro mamy posortowany vector i lower_bound. Vector trzeba by sortować po każdym BUDUJ albo wstawiać w środek — a wstawienie w środek vectora przesuwa wszystkie dalsze elementy, czyli kosztuje O(n). Zbiór wstawia w O(log n) i od razu jest gotowy na następne pytanie.

Zasada: dane się nie zmieniają — wystarczy posortowany vector. Dane się zmieniają (dochodzą, znikają) i ciągle pytamy o najbliższe — zbiór.

Sąsiedzi nowego elementu: insert zwraca strzałkę

sasiedzi_nowego.cpp
set<int> s = {10, 40};
auto it = s.insert(25).first;      // strzałka na 25
cout << "lewy: " << *prev(it) << ", prawy: " << *next(it) << "\n";
auto jt = s.insert(5).first;       // strzałka na 5
if (jt == s.begin()) cout << "5 jest najmniejsze\n";
cout << "prawy: " << *next(jt) << "\n";
▶ Wyjście
lewy: 10, prawy: 40 5 jest najmniejsze prawy: 10

W części 2 widzieliśmy, że insert zwraca parę, a jej second mówi, czy element był nowy. Teraz przyda się first: to strzałka na wstawiony element (albo na ten, który już był).

Mając strzałkę, od razu sięgamy do sąsiadów: prev(it) to największy element mniejszy od nowego, next(it) — najmniejszy większy. Jak zawsze pilnujemy brzegów: przed prev sprawdzamy it != s.begin(), a przed użyciem next(it) — czy nie jest równe s.end().

A ile elementów jest w przedziale?

Pytanie „ile elementów zbioru leży w przedziale [a, b]?” wydaje się podobne, ale zbiór nie odpowiada na nie szybko. Strzałki lower_bound(a) i upper_bound(b) znajdziesz od razu, tylko że policzenie elementów między nimi wymaga przejścia ich krok po kroku (strzałek w zbiorze nie da się odjąć jak w vectorze). Gdy dane się nie zmieniają, użyj posortowanego vectora i odejmowania z lekcji o sortowaniu: upper_bound(…, b) - lower_bound(…, a).

Zapamiętaj s.find(x) — strzałka na x albo s.end(). s.lower_bound(x) — pierwszy ≥ x, s.upper_bound(x) — pierwszy > x (obie: s.end(), gdy brak). Ostatni ≤ x: prev(s.upper_bound(x)), ostatni < x: prev(s.lower_bound(x)) — tylko gdy strzałka nie stoi na begin(). Najbliższa wartość: porównaj dwóch kandydatów. Zawsze z kropką: s.lower_bound(x), bo wersja z s.begin(), s.end() działa wolno.
Sprawdź się w głowie

Narysuj zbiór jako rząd kulek z pustym miejscem end() na końcu i zaznacz strzałki.

Co wypisze ten fragment?
set<int> s = {2, 4, 9, 12};
cout << *s.lower_bound(9) << " " << *s.lower_bound(5);
Pokaż odpowiedź
9 9Pierwszy element ≥ 9 to samo 9. Pierwszy ≥ 5 to też 9, bo między 4 a 9 nic nie ma.
Co wypisze ten fragment?
set<int> s = {2, 4, 9, 12};
cout << *s.upper_bound(9) << " " << *s.upper_bound(1);
Pokaż odpowiedź
12 2upper_bound szuka ściśle większego: dla 9 to 12, a dla 1 — najmniejszy element, 2.
Co wypisze ten fragment?
set<int> s = {2, 4, 9, 12};
cout << (s.lower_bound(13) == s.end());
Pokaż odpowiedź
1Nie ma elementu ≥ 13, więc lower_bound zwraca end(). Porównanie jest prawdziwe — wypisuje się 1.
Co wypisze ten fragment?
set<int> s = {2, 4, 9, 12};
cout << *prev(s.lower_bound(9)) << " " << *prev(s.upper_bound(9));
Pokaż odpowiedź
4 9lower_bound(9) wskazuje 9, a element przed nim to 4 — ostatni < 9. upper_bound(9) wskazuje 12, a przed nim jest 9 — ostatni ≤ 9.
Co wypisze ten fragment?
set<int> s = {1, 5, 9};
if (s.find(7) != s.end()) cout << "jest";
else cout << "brak";
Pokaż odpowiedź
brak7 nie ma w zbiorze, więc find zwraca end() i warunek jest fałszywy.
Co wypisze ten fragment?
set<int> s = {1, 3, 5, 7, 9};
int ile = 0;
for (auto it = s.lower_bound(4); it != s.end(); it++) ile++;
cout << ile;
Pokaż odpowiedź
3Pętla zaczyna od pierwszego elementu ≥ 4, czyli od 5, i idzie do końca: 5, 7, 9 — trzy elementy. (Zauważ, że to liczenie krok po kroku.)
Co wypisze ten program dla podanego wejścia?
set<int> s = {1, 4, 9};
int x;
cin >> x;
auto it = s.lower_bound(x);
int prawy = *it, lewy = *prev(it);
if (x - lewy <= prawy - x) cout << lewy;
else cout << prawy;
Wejście: 6
Pokaż odpowiedź
4Dla x = 6 kandydaci to 9 (odległość 3) i 4 (odległość 2). Bliżej jest 4. (Ten skrót bez sprawdzania brzegów działa tylko dlatego, że 6 leży między 1 a 9.)
Co wypisze ten fragment?
set<int> s = {10, 20, 30};
auto it = s.insert(15).first;
cout << *prev(it) << " " << *next(it);
Pokaż odpowiedź
10 2015 trafia między 10 a 20. Strzałka z insert wskazuje 15, jej sąsiedzi to 10 i 20.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

4.1 Najbliższy dzień otwarciałatwe✓ zaliczone Basen jest otwarty w wybrane dni. Kiedy najwcześniej popływasz, jeśli przyjdziesz w dniu d? lower_bound. lower_boundend()pytania Rozwiąż 4.2 Ostatni autobusłatwe✓ zaliczone O której odjechał ostatni autobus nie później niż t? upper_bound i krok w lewo. upper_boundprevbegin() Rozwiąż 4.3 Mniejszy i większy sąsiadłatwe✓ zaliczone Dla x podaj największy element mniejszy od x i najmniejszy większy od x — ściśle! prev(lower_bound)upper_boundściśle mniejszy / większy Rozwiąż 4.4 Najbliższa liczba w rosnącym zbiorześrednie✓ zaliczone Liczby dochodzą, a w międzyczasie pytamy o najbliższą. Dwóch kandydatów i remis dla mniejszej. lower_bounddwóch kandydatówlong long Rozwiąż 4.5 Nowy w szereguśrednie✓ zaliczone Uczniowie dołączają do szeregu według wzrostu. Kto stoi obok nowego? insert().first i sąsiedzi. insert().firstprev i nextbrzegi Rozwiąż 4.6 Stacje ładowaniaśrednie✓ zaliczone Stacje powstają i znikają. Gdzie jest pierwsza stacja na prawo od x? Zbiór zmienia się między pytaniami. insert i eraselower_bounddane się zmieniają Rozwiąż 4.7 Szafki na basenietrudne✓ zaliczone Zbiór WOLNYCH szafek: pierwsza wolna ≥ p, a gdy brak — od początku. Oddana szafka wraca do zbioru. zbiór wolnych miejsclower_boundzawijanie do begin() Rozwiąż 4.8 Najmniejsza różnica na żywotrudne✓ zaliczone Po każdej nowej liczbie: najmniejsza różnica między dwiema liczbami w zbiorze. Liczą się tylko sąsiedzi nowej. insert().firstsąsiedzi nowegobieżące minimum Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Działania na zbiorach — suma, część wspólna, różnica

Zbiory znasz też z matematyki. Tam na dwóch zbiorach A i B wykonuje się działania: łączy się je, szuka wspólnych elementów, odejmuje. Zadania programistyczne pełne są takich pytań: które gry mają oboje?, kto był na obu wycieczkach?, czego brakuje w drugiej liście?. Ze zbiorami w C++ każde z tych działań to jedna krótka pętla.

Na rysunku poniżej A = {1, 2, 3, 5, 8} i B = {2, 3, 4, 8, 9}. Środek, gdzie koła na siebie zachodzą, to elementy obu zbiorów naraz. Kliknij każde działanie i zobacz, które obszary trafiają do wyniku.

Diagram Venna — kliknij działanie
AB1523849
A = {1, 2, 3, 5, 8}
B = {2, 3, 4, 8, 9}
Kliknij jedno z działań nad rysunkiem — podświetlą się obszary i liczby, które trafią do wyniku.
działanieznakco zawieradla A i B z rysunku
sumaA ∪ Bto, co jest w A lub w B{1, 2, 3, 4, 5, 8, 9}
część wspólna (iloczyn)A ∩ Bto, co jest w A i w B{2, 3, 8}
różnicaA \ Bto, co jest w A, ale nie w B{1, 5}
różnicaB \ Ato, co jest w B, ale nie w A{4, 9}
różnica symetrycznaA △ Bto, co jest dokładnie w jednym{1, 4, 5, 9}

Część wspólna: przejdź A, pytaj B

czesc_wspolna.cpp
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> C;
for (int x : A)
    if (B.count(x)) C.insert(x);
for (int x : C) cout << x << " ";
cout << "\n";
▶ Wyjście
2 3 8

Pomysł: weź po kolei każdy element A i zapytaj zbiór B, czy też go ma. Jeśli tak — element jest wspólny. Wynik zbieramy do nowego zbioru C.

Ponieważ przechodzimy A rosnąco, elementy wspólne też wychodzą rosnąco. Moglibyśmy je od razu wypisywać, bez zbioru C — ale C przyda się, gdy z wynikiem trzeba coś dalej robić.

Ile to kosztuje? Dla każdego z |A| elementów jedno count w B, czyli O(|A| · log |B|). Opłaca się przechodzić mniejszy zbiór, a pytać większy.

Suma: wrzuć wszystko do jednego worka

suma.cpp
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> S = A;              // kopia zbioru A
for (int x : B) S.insert(x);
for (int x : S) cout << x << " ";
cout << "\n";
cout << S.size() << " = " << A.size() << " + " << B.size() << " - 3\n";
▶ Wyjście
1 2 3 4 5 8 9 7 = 5 + 5 - 3

Suma to najprostsze działanie: zaczynamy od kopii A (set<int> S = A; kopiuje cały zbiór, tak jak przy vectorze) i dorzucamy wszystko z B. Elementy wspólne zbiór przyjmie tylko raz — o powtórki nie musimy dbać.

Zauważ wzór z drugiego wiersza. Gdy dodajemy rozmiary A i B, elementy wspólne liczymy dwa razy, więc trzeba je raz odjąć: |A ∪ B| = |A| + |B| − |A ∩ B|. To ta sama zasada włączania i wyłączania, której używałeś w lekcji o złożoności przy liczbach podzielnych przez 3 lub 5.

Różnica: tylko w jednym, nie w drugim

roznica.cpp
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
for (int x : A)
    if (!B.count(x)) cout << x << " ";
cout << "\n";
for (int x : B)
    if (!A.count(x)) cout << x << " ";
cout << "\n";
▶ Wyjście
1 5 4 9

Różnica A \ B to elementy A, których B nie ma. Ta sama pętla co przy części wspólnej, tylko z wykrzyknikiem w warunku.

W odróżnieniu od sumy i części wspólnej kolejność ma znaczenie: A \ B to {1, 5}, a B \ A to {4, 9}. „Czego Ala nie dała Oli” to co innego niż „czego Ola nie dała Ali”. Zawsze czytaj w treści, który zbiór jest „pierwszy”.

Różnica symetryczna: dokładnie w jednym

symetryczna.cpp
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> W;
for (int x : A) if (!B.count(x)) W.insert(x);
for (int x : B) if (!A.count(x)) W.insert(x);
for (int x : W) cout << x << " ";
cout << "\n" << W.size() << "\n";
▶ Wyjście
1 4 5 9 4

Różnica symetryczna to obie różnice razem: elementy, które ma tylko jeden z dwóch zbiorów. Na rysunku to dwa „księżyce” bez środka. Zbieramy je do zbioru W, który sam ułoży je rosnąco.

Można też policzyć jej rozmiar bez budowania: |A △ B| = |A| + |B| − 2 · |A ∩ B|. Tym razem część wspólną odejmujemy dwa razy, bo jej w ogóle nie chcemy.

Podzbiór, równość, rozłączność

podzbior.cpp
set<int> A = {2, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> C = {1, 5};
bool podzbior = true;
for (int x : A)
    if (!B.count(x)) podzbior = false;
bool rozlaczne = true;
for (int x : C)
    if (B.count(x)) rozlaczne = false;
cout << podzbior << " " << rozlaczne << " " << (A == B) << "\n";
set<int> D = {8, 2, 8};
cout << (A == D) << "\n";
▶ Wyjście
1 1 0 1

A jest podzbiorem B (A ⊆ B), gdy każdy element A jest też w B. Zakładamy, że tak jest, i szukamy kontrprzykładu: jeden element A, którego B nie ma, wystarczy, żeby odpowiedź brzmiała „nie”. Ten sam schemat „zakładam prawdę, szukam wyjątku” znasz z lekcji o pętlach.

Zbiory rozłączne nie mają ani jednego wspólnego elementu — część wspólna jest pusta.

Równość sprawdza operator ==: dwa zbiory są równe, gdy mają dokładnie te same elementy. Kolejność wstawiania ani powtórki nie mają znaczenia — {2, 8} i zbiór zbudowany z 8, 2, 8 są równe.

Dwa zbiory z wejścia

dwa_zbiory.cpp
int n, m;
cin >> n >> m;
set<int> A, B;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    A.insert(x);
}
for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    B.insert(x);
}
int wspolne = 0;
for (int x : A)
    if (B.count(x)) wspolne++;
int suma = A.size() + B.size() - wspolne;
cout << wspolne << " " << suma << "\n";
▶ Wejście
5 4 1 2 2 3 4 3 4 5 3
▶ Wyjście
2 5

Typowe wejście zadania: dwie liczby n i m, potem n liczb pierwszej listy i m liczb drugiej. Listy mogą mieć powtórki — zbiory je usuną. Tu A = {1, 2, 3, 4}, B = {3, 4, 5}.

Program liczy, ile jest wartości wspólnych (3 i 4), a rozmiar sumy wylicza wzorem, bez budowania trzeciego zbioru: 4 + 3 − 2 = 5.

Dwa zbiory tworzymy w jednej linijce: set<int> A, B; — tak samo jak dwie zmienne int.

Wspólne litery dwóch słów

wspolne_litery.cpp
string a, b;
cin >> a >> b;
set<char> A(a.begin(), a.end());
set<char> B(b.begin(), b.end());
for (char c : A)
    if (B.count(c)) cout << c;
cout << "\n";
▶ Wejście
programowanie olimpiada
▶ Wyjście
aimop

Działania na zbiorach działają tak samo dla liter. Zbiór liter słowa „programowanie” to {a, e, g, i, m, n, o, p, r, w}, a słowa „olimpiada” — {a, d, i, l, m, o, p}. Wspólne litery to a, i, m, o, p.

Zbiór liter tworzymy jedną linijką z całego napisu — begin() i end() napisu, jak w części 1.

Część wspólna wielu zbiorów

wiele_zbiorow.cpp
int n;
cin >> n;
set<int> wspolne;
for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    set<int> teraz;
    for (int j = 0; j < k; j++) {
        int x;
        cin >> x;
        teraz.insert(x);
    }
    if (i == 0) wspolne = teraz;
    else {
        set<int> nowe;
        for (int x : wspolne)
            if (teraz.count(x)) nowe.insert(x);
        wspolne = nowe;
    }
}
for (int x : wspolne) cout << x << " ";
cout << "\n";
▶ Wejście
3 4 1 2 3 4 3 2 4 6 5 4 2 9 2 7
▶ Wyjście
2 4

Co mają wspólnego wszystkie z n list? Część wspólną buduje się krok po kroku. Po pierwszej liście „wspólne” to cała pierwsza lista. Każda kolejna lista może tylko zmniejszyć ten zbiór: zostawiamy z niego tylko te elementy, które ma też nowa lista.

Po liście 1: {1, 2, 3, 4}. Po liście 2: {2, 4} — 1 i 3 odpadają. Po liście 3: dalej {2, 4}.

Przypisanie wspolne = nowe; kopiuje cały zbiór, a nowy zbiór teraz powstaje w każdym obrocie pętli od zera.

Zapamiętaj Część wspólna: dla x z A — if (B.count(x)). Różnica A \ B: if (!B.count(x)) — kolejność zbiorów ma znaczenie. Suma: kopia A (set<int> S = A;) i insert wszystkiego z B. Różnica symetryczna: obie różnice razem. Podzbiór: zakładaj „tak”, szukaj elementu A, którego B nie ma. Równość: A == B. Wzór: |A ∪ B| = |A| + |B| − |A ∩ B|.
Sprawdź się w głowie

Narysuj sobie dwa koła i wpisz liczby w obszary — wtedy każde działanie widać od razu.

Co wypisze ten fragment?
set<int> A = {1, 2, 3}, B = {2, 3, 4};
int ile = 0;
for (int x : A) if (B.count(x)) ile++;
cout << ile;
Pokaż odpowiedź
2Wspólne są 2 i 3.
Co wypisze ten fragment?
set<int> A = {1, 2}, B = {2, 3, 4};
set<int> S = A;
for (int x : B) S.insert(x);
cout << S.size();
Pokaż odpowiedź
4Suma to {1, 2, 3, 4}. Wzorem: 2 + 3 − 1 = 4 (wspólna jest tylko dwójka).
Co wypisze ten fragment?
set<int> A = {5, 6, 7}, B = {6, 10};
for (int x : A) if (!B.count(x)) cout << x << " ";
Pokaż odpowiedź
5 7Różnica A \ B: z A wyrzucamy to, co ma B. B ma szóstkę, a dziesiątka nas nie obchodzi, bo nie ma jej w A.
Co wypisze ten fragment?
set<int> A = {1, 2, 3}, B = {3, 4};
set<int> W;
for (int x : A) if (!B.count(x)) W.insert(x);
for (int x : B) if (!A.count(x)) W.insert(x);
for (int x : W) cout << x << " ";
Pokaż odpowiedź
1 2 4Dokładnie w jednym zbiorze: 1 i 2 (tylko w A) oraz 4 (tylko w B). Trójka jest w obu, więc odpada.
Co wypisze ten fragment?
set<int> A;
set<int> B = {1, 2};
bool podzbior = true;
for (int x : A) if (!B.count(x)) podzbior = false;
cout << podzbior;
Pokaż odpowiedź
1A jest pusty, więc pętla nie wykona się ani razu i nie znajdzie kontrprzykładu. Zbiór pusty jest podzbiorem każdego zbioru — także w matematyce.
Co wypisze ten fragment?
set<int> A = {3, 1, 2};
set<int> B = {1, 2, 3, 3};
cout << (A == B);
Pokaż odpowiedź
1Oba zbiory to {1, 2, 3}. Kolejność wstawiania i powtórzona trójka nie mają znaczenia.
Co wypisze ten fragment?
set<int> A, B;
for (int i = 1; i <= 5; i++) A.insert(i);
for (int i = 3; i <= 9; i++) B.insert(i);
int w = 0;
for (int x : A) if (B.count(x)) w++;
cout << A.size() + B.size() - w;
Pokaż odpowiedź
9A = {1…5} (5 elementów), B = {3…9} (7 elementów), wspólne 3, 4, 5. Suma ma 5 + 7 − 3 = 9 elementów: liczby od 1 do 9.
Co wypisze ten fragment?
string a = "kot", b = "pies";
set<char> A(a.begin(), a.end()), B(b.begin(), b.end());
int w = 0;
for (char c : A) if (B.count(c)) w++;
cout << w;
Pokaż odpowiedź
0„kot” i „pies” nie mają wspólnej litery — zbiory liter są rozłączne.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Zbiór par i napisów

Zbiór umie trzymać wszystko, co da się porównać. Pary porównują się same — najpierw first, a przy remisie second (lekcja Pair). Dlatego set<pair<int, int>> działa od razu: trzyma różne pary, ułożone tak, jak ułożyłby je sort. To otwiera mnóstwo zadań: różne punkty na planszy, odwiedzone pola, znajomości, rankingi.

Różne punkty: set<pair<int, int>>

punkty.cpp
set<pair<int, int>> punkty;
punkty.insert({2, 5});
punkty.insert({1, 7});
punkty.insert({2, 3});
punkty.insert({1, 7});        // ten sam punkt — odpada
cout << punkty.size() << "\n";
for (auto p : punkty)
    cout << "(" << p.first << ", " << p.second << ") ";
cout << "\n";
▶ Wyjście
3 (1, 7) (2, 3) (2, 5)

Parę wstawiamy w klamrach: punkty.insert({2, 5}); — tak samo jak tworzyliśmy pary w lekcji Pair. Dwa punkty są tym samym punktem, gdy mają oba pola równe — dlatego drugie (1, 7) odpadło, a (2, 3) i (2, 5) zostały jako różne.

Kolejność: najpierw według first (1 przed 2), a przy remisie według second (3 przed 5). Zbiór par to więc „posortowana lista różnych par” — bez wywoływania sort i unique.

W pętli używamy auto p, bo pełna nazwa typu to pair<int, int>.

count i rozpakowywanie

pary_count.cpp
set<pair<int, int>> pola = {{0, 0}, {0, 1}, {1, 1}};
cout << pola.count({0, 1}) << pola.count({1, 0}) << "\n";
for (auto [x, y] : pola) cout << x << "," << y << " ";
cout << "\n";
▶ Wyjście
10 0,0 0,1 1,1

count, insert, erase, find przyjmują całą parę. Uwaga na kolejność w parze: (0, 1) to inne pole niż (1, 0). Pierwsze jest w zbiorze, drugiego nie ma.

Zapis for (auto [x, y] : pola) rozpakowuje każdą parę na dwie zmienne o wygodnych nazwach — znasz go z lekcji Pair. Zamiast p.first i p.second piszesz po prostu x i y.

Para bez kolejności: najpierw mniejszy

mecze.cpp
int m;
cin >> m;
set<pair<int, int>> mecze;
for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    mecze.insert({min(a, b), max(a, b)});
}
cout << mecze.size() << "\n";
for (auto [a, b] : mecze) cout << a << "-" << b << " ";
cout << "\n";
▶ Wejście
5 1 2 2 1 3 1 1 3 2 3
▶ Wyjście
3 1-2 1-3 2-3

Drużyny 1 i 2 grały mecz. Zapis „1 2” i „2 1” oznacza ten sam mecz — tu kolejność w parze nie ma znaczenia. Ale dla zbioru (1, 2) i (2, 1) to różne pary!

Rozwiązanie: zanim wstawisz parę, ustaw ją w jednej, ustalonej kolejności — mniejszy pierwszy: {min(a, b), max(a, b)}. Wtedy „2 1” zamienia się w (1, 2) i trafia na tę samą parę co „1 2”. Ten sam pomysł działa przy znajomościach, drogach między miastami i krawędziach figur.

Robot i odwiedzone pola

robot.cpp
string ruchy;
cin >> ruchy;
int x = 0, y = 0;
set<pair<int, int>> odwiedzone;
odwiedzone.insert({x, y});
for (char c : ruchy) {
    if (c == 'G') y++;
    else if (c == 'D') y--;
    else if (c == 'L') x--;
    else if (c == 'P') x++;
    odwiedzone.insert({x, y});
}
cout << odwiedzone.size() << "\n";
▶ Wejście
GGPDDL
▶ Wyjście
6

Robot zaczyna w punkcie (0, 0) i wykonuje ruchy: G (góra), D (dół), L (lewo), P (prawo). Na ilu różnych polach stanął? Każde pole, na które wejdzie, wrzucamy do zbioru par — powtórki odpadną same.

Trasa: (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 1) → (1, 0) → (0, 0). Siedem postojów, ale ostatni to powrót na start — różnych pól jest 6.

Pamiętaj o polu startowym: wstawiamy je przed pętlą. Bez tego wynik byłby za mały o jeden, gdyby robot na start już nie wrócił.

Ranking: para (−punkty, numer)

ranking.cpp
vector<int> pkt(4, 0);                 // pkt[1..3]
set<pair<int, int>> ranking;           // (-punkty, numer)
for (int i = 1; i <= 3; i++) ranking.insert({0, i});
// gracz 2 dostaje 5 punktów
ranking.erase({-pkt[2], 2});
pkt[2] += 5;
ranking.insert({-pkt[2], 2});
// gracz 3 dostaje 5 punktów
ranking.erase({-pkt[3], 3});
pkt[3] += 5;
ranking.insert({-pkt[3], 3});
auto [minusPkt, lider] = *ranking.begin();
cout << "lider: " << lider << " (" << -minusPkt << " pkt)\n";
for (auto [m, nr] : ranking) cout << nr << ":" << -m << " ";
cout << "\n";
▶ Wyjście
lider: 2 (5 pkt) 2:5 3:5 1:0

Chcemy w każdej chwili znać lidera: najwięcej punktów, a przy remisie — mniejszy numer. Zbiór par zrobi to sam, jeśli dobrze ułożymy parę: (−punkty, numer). Zbiór sortuje rosnąco, więc minus odwraca kolejność punktów (więcej punktów = mniejsza liczba = wcześniej), a przy remisie wygrywa mniejszy numer. To „sztuczka z minusem” z lekcji o sortowaniu i parach.

Lider to zawsze *ranking.begin().

Najważniejsze: elementu zbioru nie da się zmienić na miejscu (część 3). Zmiana punktów to usuń starą parę, wstaw nową. Żeby usunąć starą, trzeba znać stare punkty — dlatego trzymamy je osobno w vectorze pkt.

lower_bound na parach: pierwszy w wierszu

kamienie.cpp
set<pair<int, int>> kamienie = {{1, 5}, {1, 9}, {2, 3}, {4, 4}};
// pierwszy kamień w wierszu 1, w kolumnie >= 6
auto it = kamienie.lower_bound({1, 6});
if (it != kamienie.end() && it->first == 1) cout << it->second << "\n";
else cout << "BRAK\n";
// pierwszy kamień w wierszu 3, w dowolnej kolumnie
auto jt = kamienie.lower_bound({3, INT_MIN});
if (jt != kamienie.end() && jt->first == 3) cout << jt->second << "\n";
else cout << "BRAK\n";
▶ Wyjście
9 BRAK

Kamienie leżą na planszy w polach (wiersz, kolumna). Pytanie: idąc wierszem 1 w prawo od kolumny 6, na który kamień trafię? lower_bound({1, 6}) szuka pierwszej pary ≥ (1, 6) — w kolejności par to właśnie pierwszy kamień w wierszu 1 o kolumnie ≥ 6, czyli (1, 9).

Pułapka: jeśli w wierszu nie ma już kamieni, lower_bound przeskoczy do następnego wiersza. Dla wiersza 3 zwraca (4, 4) — kamień z innego wiersza. Dlatego zawsze sprawdzamy, czy first się zgadza.

it->first to skrót od (*it).first — „pole first elementu, na który wskazuje strzałka”. A INT_MIN (najmniejszy int, z lekcji Max / Min) jako drugie pole daje pierwszą parę w wierszu, niezależnie od kolumny.

Zbiór słów: wielkie i małe litery

male_litery.cpp
int n;
cin >> n;
set<string> slowa;
for (int i = 0; i < n; i++) {
    string w;
    cin >> w;
    for (char &c : w) c = tolower(c);
    slowa.insert(w);
}
cout << slowa.size() << "\n";
for (string w : slowa) cout << w << " ";
cout << "\n";
▶ Wejście
6 Kot kot KOT Pies pies Ala
▶ Wyjście
3 ala kot pies

Dla zbioru „Kot”, „kot” i „KOT” to trzy różne napisy. Często jednak chcemy je traktować jak jedno słowo. Wtedy przed wstawieniem zamieniamy słowo na małe litery: pętla z referencją char &c zmienia każdą literę przez tolower (lekcja String).

Ogólna zasada, którą widzieliśmy już przy meczach: zanim wstawisz, sprowadź do jednej postaci. Wszystko, co ma się liczyć jako „to samo”, musi w zbiorze wyglądać identycznie.

Klucz zamiast słowa: anagramy

anagramy.cpp
int n;
cin >> n;
set<string> klucze;
for (int i = 0; i < n; i++) {
    string w;
    cin >> w;
    sort(w.begin(), w.end());   // klucz: litery po kolei
    klucze.insert(w);
}
cout << klucze.size() << "\n";
for (string k : klucze) cout << k << " ";
cout << "\n";
▶ Wejście
5 kot tok okt pies spie
▶ Wyjście
2 eips kot

Anagramy to słowa z tych samych liter: „kot”, „tok”, „okt”. Ile jest różnych grup anagramów? Każde słowo zamieniamy na klucz: jego litery posortowane. Wszystkie anagramy mają ten sam klucz („kot” → „kot”, „tok” → „kot”), a słowa z innych liter — inny.

Zbiór kluczy ma tyle elementów, ile jest grup. To kolejny przykład „sprowadzania do jednej postaci” — tylko postać jest sprytniejsza niż małe litery.

Zapamiętaj set<pair<int, int>> trzyma różne pary, ułożone według first, a przy remisie second. Wstawianie i pytanie: s.insert({a, b}), s.count({a, b}). Para bez kolejności: {min(a, b), max(a, b)}. Ranking: para (-punkty, numer), zmiana = erase starej + insert nowej. lower_bound({w, k}) na parach — sprawdź, czy it->first to wciąż ten sam wiersz. Zanim wstawisz, sprowadź do jednej postaci (małe litery, posortowany klucz).
Sprawdź się w głowie

Pary porównuj jak w lekcji Pair: najpierw pierwsze pole, przy remisie drugie.

Co wypisze ten fragment?
set<pair<int, int>> s = {{2, 1}, {1, 2}, {1, 1}};
for (auto [a, b] : s) cout << a << b << " ";
Pokaż odpowiedź
11 12 21Najpierw pary z first = 1, uporządkowane według second: (1, 1), (1, 2). Potem (2, 1).
Co wypisze ten fragment?
set<pair<int, int>> s;
s.insert({1, 2});
s.insert({2, 1});
s.insert({1, 2});
cout << s.size();
Pokaż odpowiedź
2(1, 2) i (2, 1) to różne pary. Drugie (1, 2) odpada jako powtórka.
Co wypisze ten fragment?
set<pair<int, int>> s = {{3, 4}};
cout << s.count({3, 4}) << s.count({4, 3});
Pokaż odpowiedź
10Para (3, 4) jest w zbiorze, a (4, 3) — nie. Kolejność w parze ma znaczenie.
Co wypisze ten fragment?
set<pair<int, int>> s;
int a = 3, b = 1;
s.insert({min(a, b), max(a, b)});
s.insert({min(b, a), max(b, a)});
s.insert({1, 3});
cout << s.size();
Pokaż odpowiedź
1Wszystkie trzy wstawienia dają tę samą parę (1, 3) — mniejszy zawsze idzie pierwszy.
Co wypisze ten fragment?
set<pair<int, int>> r = {{-5, 2}, {-7, 1}, {-7, 3}};
cout << r.begin()->second;
Pokaż odpowiedź
1Najmniejsza para to (−7, 1): −7 jest mniejsze od −5, a przy remisie −7 wygrywa mniejszy numer. To gracz 1 z 7 punktami.
Co wypisze ten fragment?
set<pair<int, int>> s = {{1, 5}, {2, 3}, {2, 8}};
auto it = s.lower_bound({1, 6});
cout << it->first << " " << it->second;
Pokaż odpowiedź
2 3W wierszu 1 nie ma kamienia o kolumnie ≥ 6, więc lower_bound przeskakuje do następnej pary: (2, 3). Dlatego trzeba sprawdzać, czy first się zgadza.
Co wypisze ten fragment?
set<string> s;
vector<string> w = {"Ala", "ALA", "ala", "As"};
for (string x : w) {
    for (char &c : x) c = tolower(c);
    s.insert(x);
}
cout << s.size();
Pokaż odpowiedź
2Po zamianie na małe litery mamy „ala”, „ala”, „ala” i „as” — dwa różne słowa.
Co wypisze ten fragment?
set<string> k;
vector<string> w = {"abc", "cab", "bca", "abd"};
for (string x : w) {
    sort(x.begin(), x.end());
    k.insert(x);
}
cout << k.size();
Pokaż odpowiedź
2„abc”, „cab” i „bca” mają klucz „abc”, a „abd” — klucz „abd”. Dwie grupy anagramów.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

6.1 Różne punktyłatwe✓ zaliczone Niektóre punkty zapisano kilka razy. Ile jest różnych i jakie — po kolei według x, potem y? set<pair<int, int>>insert({x, y})auto [x, y] Rozwiąż 6.2 Znajomości bez powtórzeńłatwe✓ zaliczone „4 2” i „2 4” to ta sama znajomość. Ile jest różnych i jakie? Para {min, max}. {min(a, b), max(a, b)}set<pair>para bez kolejności Rozwiąż 6.3 Te same słowa?łatwe✓ zaliczone Czy dwa zdania używają tego samego zestawu słów, nie licząc wielkości liter? tolower i A == B. tolowerset<string>A == B Rozwiąż 6.4 Robot na kratceśrednie✓ zaliczone Na ilu różnych polach stanął robot i w którym ruchu pierwszy raz wrócił na pole, na którym już był? set<pair<int, int>>countpole startowe Rozwiąż 6.5 Różne ułamkiśrednie✓ zaliczone 1/2, 2/4 i 3/6 to ta sama liczba. Skróć każdy ułamek przez NWD i wstaw parę do zbioru. NWDpostać nieskracalnaset<pair> Rozwiąż 6.6 Ten sam zestaw literśrednie✓ zaliczone Słowa są spokrewnione, gdy używają tych samych liter (bez liczenia powtórzeń). Ile jest grup? Klucz ze zbioru liter. kluczset<char> → stringset<string> Rozwiąż 6.7 Ranking na żywotrudne✓ zaliczone Punkty spływają, a lider ma być znany po każdym wyniku. Para (−punkty, numer), erase i insert. set<pair>(−punkty, numer)erase + insert*begin() Rozwiąż 6.8 Kamienie na planszytrudne✓ zaliczone Kamienie kładzione i zdejmowane. Pierwszy kamień w wierszu na prawo od kolumny c? lower_bound na parach. set<pair>lower_bound({r, c})it->first Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

multiset — gdy powtórzenia się liczą

Zwykły zbiór gubi informację, ile razy coś wystąpiło. Czasem to dokładnie to, czego chcemy („ile różnych?”), ale czasem przeszkadza: na półce mogą leżeć dwa produkty za 10 zł, w klasie może być trzech uczniów o wzroście 150 cm. Wtedy używamy multiset — zbioru, który trzyma powtórzenia, a poza tym działa prawie tak samo jak set: wszystko jest zawsze posortowane i szybkie.

Pierwszy multiset

multiset.cpp
multiset<int> m;
m.insert(5);
m.insert(2);
m.insert(5);
m.insert(8);
m.insert(2);
m.insert(5);
cout << m.size() << " " << m.count(5) << " " << m.count(7) << "\n";
for (int x : m) cout << x << " ";
cout << "\n";
▶ Wyjście
6 3 0 2 2 5 5 5 8

multiset<int> m; tworzy pusty multizbiór. Mieszka w tym samym nagłówku <set>.

Każdy insert naprawdę coś dodaje — także powtórkę. Dlatego size() to 6, czyli wszystkie wstawione liczby, a nie liczba różnych.

count(x) wreszcie robi to, co sugeruje nazwa: mówi, ile kopii x jest w środku. Piątek jest 3.

Przechodzenie pętlą daje wszystkie elementy rosnąco, z powtórzeniami obok siebie. Multiset to więc „vector, który sam się sortuje przy każdym wstawieniu”.

Ta sama ramka co w części 1, tym razem w trybie multiset. Wrzuć kilka razy tę samą liczbę, a potem porównaj erase(x) z erase(find(x)) — to najważniejsza różnica w tej części.

Wrzuć do zbioru — i zobacz, co się stanie
kolejność wstawiania
set
Ta ramka działa po włączeniu JavaScriptu.

Pułapka: erase(x) usuwa wszystkie kopie

erase_wszystkie.cpp
multiset<int> m = {1, 3, 3, 3, 7};
m.erase(3);
for (int x : m) cout << x << " ";
cout << "\n";
▶ Wyjście
1 7
erase_jedna.cpp
multiset<int> m = {1, 3, 3, 3, 7};
auto it = m.find(3);
if (it != m.end()) m.erase(it);   // usuwa JEDNĄ trójkę
for (int x : m) cout << x << " ";
cout << "\n";
▶ Wyjście
1 3 3 7

To najczęstszy błąd z multisetem. m.erase(3) usuwa wszystkie trójki naraz — wszystkie elementy równe 3. Jeśli sprzedajesz jeden produkt za 3 zł, a na półce były trzy takie, nagle znikają wszystkie.

Żeby usunąć jedną kopię, trzeba wskazać ją strzałką: m.find(3) zwraca strzałkę na jedną z trójek, a m.erase(it) usuwa dokładnie ten jeden element.

Pamiętaj o sprawdzeniu it != m.end(): gdy wartości nie ma, find zwraca end(), a erase(end()) to błąd.

Jedna kopia czy wszystkie? W multisecie m.erase(x) usuwa wszystkie elementy równe x. Jedną kopię usuwa m.erase(m.find(x)) — po sprawdzeniu, że m.find(x) != m.end(). Tak samo działa m.erase(m.begin()): strzałka wskazuje jeden element, więc znika jedna najmniejsza wartość, nawet jeśli było ich kilka.

Najmniejszy i największy z powtórzeniami

ceny.cpp
multiset<int> ceny = {30, 10, 20, 10};
cout << *ceny.begin() << " " << *ceny.rbegin() << "\n";
ceny.erase(ceny.begin());        // sprzedajemy JEDEN najtańszy
cout << *ceny.begin() << " " << ceny.size() << "\n";
ceny.erase(ceny.begin());
cout << *ceny.begin() << " " << ceny.size() << "\n";
▶ Wyjście
10 30 10 3 20 2

Wszystko z części 3 działa bez zmian: *begin() to najmniejszy element, *rbegin() — największy, erase(begin()) usuwa jeden najmniejszy.

Na półce leżą dwa produkty za 10 zł. Po sprzedaży jednego najtańszym produktem dalej jest 10 zł — bo była druga dziesiątka. Dopiero po drugiej sprzedaży najtańszy kosztuje 20. W zwykłym set druga dziesiątka by zginęła już przy wstawianiu i wynik byłby zły.

Sortowanie multisetem i count, który bywa wolny

sortowanie_multiset.cpp
multiset<int> m;
int x;
while (cin >> x) m.insert(x);
for (int y : m) cout << y << " ";
cout << "\n";
▶ Wejście
5 3 5 1 3
▶ Wyjście
1 3 3 5 5
count_find.cpp
multiset<int> m;
for (int i = 0; i < 5; i++) m.insert(7);
cout << m.count(7) << " " << (m.find(7) != m.end()) << "\n";
▶ Wyjście
5 1

Wrzucenie wszystkich liczb do multisetu i przejście go pętlą daje to samo co sort — z powtórzeniami. Też O(n log n). Gdy wszystkie dane masz od razu, sort na vectorze jest prostszy i szybszy. Multiset wygrywa, gdy liczby dochodzą i znikają, a po drodze ciągle trzeba znać najmniejszą czy największą.

Uwaga na count w multisecie: żeby policzyć kopie, musi przejść je wszystkie. Gdy x występuje 100 000 razy, jedno count(x) robi 100 000 kroków. Jeśli pytasz tylko „czy jest?”, użyj m.find(x) != m.end() — to zawsze O(log n).

Największy w każdym oknie

okno_max.cpp
int n, k;
cin >> n >> k;
vector<int> t(n);
for (int &x : t) cin >> x;
multiset<int> okno;
for (int i = 0; i < n; i++) {
    okno.insert(t[i]);                            // wchodzi nowy
    if (i >= k) okno.erase(okno.find(t[i - k]));  // wychodzi stary
    if (i >= k - 1) cout << *okno.rbegin() << " ";
}
cout << "\n";
▶ Wejście
8 3 4 1 7 3 7 2 5 6
▶ Wyjście
7 7 7 7 7 6

Okno to k kolejnych elementów tablicy (znasz je z lekcji o vectorze i o złożoności). Okno przesuwa się o jeden: z prawej wchodzi nowy element, z lewej wychodzi ten sprzed k kroków. W każdym położeniu chcemy znać największy element okna.

Multiset trzyma dokładnie elementy bieżącego okna. Wejście to insert, wyjście to usunięcie jednej kopii, a największy to *rbegin(). Każdy krok kosztuje O(log k), całość O(n log k) — zamiast O(n · k), gdybyśmy za każdym razem przeglądali całe okno.

Największy w każdym oknie — multiset krok po kroku
multiset okna
Ta ramka działa po włączeniu JavaScriptu.
okno_zle.cpp
int n, k;
cin >> n >> k;
vector<int> t(n);
for (int &x : t) cin >> x;
multiset<int> okno;
for (int i = 0; i < n; i++) {
    okno.insert(t[i]);
    if (i >= k) okno.erase(t[i - k]);    // usuwa WSZYSTKIE kopie!
    if (i >= k - 1) cout << *okno.rbegin() << " ";
}
cout << "\n";
▶ Wejście
8 3 4 1 7 3 7 2 5 6
▶ Wyjście — źle
7 7 7 3 5 6

Ten sam program z jedną zmianą: okno.erase(t[i - k]) zamiast okno.erase(okno.find(t[i - k])). Dopóki w oknie nie ma powtórzeń, oba działają tak samo. Ale gdy z okna [3, 7, 2] ma wyjść siódemka sprzed trzech kroków, erase(7) usuwa obie siódemki — także tę, która wciąż jest w oknie. Od tej chwili wyniki są złe.

Na małym teście bez powtórek tego błędu nie zobaczysz. Dlatego przy multisecie zawsze zadawaj sobie pytanie: usuwam jedną kopię czy wszystkie?

Weź największy, który się mieści

bilety.cpp
multiset<int> bilety = {50, 30, 80, 30};
vector<int> klienci = {60, 20, 30, 100};
for (int budzet : klienci) {
    auto it = bilety.upper_bound(budzet);   // pierwszy > budżet
    if (it == bilety.begin()) cout << "-1\n";
    else {
        it--;                                // ostatni <= budżet
        cout << *it << "\n";
        bilety.erase(it);                    // ten bilet sprzedany
    }
}
▶ Wyjście
50 -1 30 80

Kasa ma bilety w różnych cenach (ceny mogą się powtarzać). Każdy klient kupuje najdroższy bilet, na który go stać — czyli największy ≤ jego budżet. Sprzedany bilet znika.

To połączenie wszystkiego, co znamy: upper_bound(budżet) to pierwszy bilet za drogi, cofnięcie strzałki daje ostatni, który się mieści (część 4), a erase(it) usuwa dokładnie ten jeden bilet.

Bilety: {30, 30, 50, 80}. Klient z 60 kupuje 50. Klient z 20 nie kupi nic — upper_bound(20) to już pierwszy bilet. Klient z 30 kupuje jedną z trzydziestek. Klient ze 100 kupuje 80.

Dwa największe naraz: gra w kamienie

kamienie_gra.cpp
multiset<int> k = {2, 7, 4, 1, 8, 1};
while (k.size() >= 2) {
    int a = *k.rbegin();
    k.erase(prev(k.end()));
    int b = *k.rbegin();
    k.erase(prev(k.end()));
    if (a != b) k.insert(a - b);
}
if (k.empty()) cout << 0 << "\n";
else cout << *k.begin() << "\n";
▶ Wyjście
1

W każdej rundzie bierzemy dwa najcięższe kamienie i zderzamy je. Jeśli ważą tyle samo — oba znikają. Jeśli nie — zostaje kamień o wadze równej różnicy. Jaki kamień zostanie na końcu?

{1, 1, 2, 4, 7, 8}: zderzamy 8 i 7, zostaje 1 → {1, 1, 1, 2, 4}. Potem 4 i 2 → 2. Potem 2 i 1 → 1. Potem 1 i 1 — znikają oba. Zostaje {1}.

Multiset jest tu konieczny: kamienie o tej samej wadze to różne kamienie. Każde wyjęcie to erase(prev(end())) — strzałka na jeden, największy element.

Zapamiętaj multiset<int> trzyma powtórzenia, zawsze rosnąco. size() — wszystkie elementy, count(x) — liczba kopii (dla wielu kopii wolne; „czy jest?” sprawdzaj przez find). erase(x) usuwa wszystkie kopie, erase(find(x)) i erase(it) — jedną. Najmniejszy *begin(), największy *rbegin(), lower_bound i upper_bound — jak w set. Multiset wybieraj, gdy elementy dochodzą i znikają, a powtórzenia są różnymi rzeczami.
Sprawdź się w głowie

Zapisuj multiset jako rosnący rząd liczb — z powtórzeniami — i skreślaj tyle kopii, ile naprawdę znika.

Co wypisze ten fragment?
multiset<int> m = {4, 4, 1, 4};
cout << m.size() << " " << m.count(4);
Pokaż odpowiedź
4 3Multiset trzyma wszystkie cztery liczby, w tym trzy czwórki.
Co wypisze ten fragment?
multiset<int> m = {2, 2, 2, 5};
m.erase(2);
cout << m.size();
Pokaż odpowiedź
1erase(2) usuwa wszystkie dwójki. Zostaje tylko 5.
Co wypisze ten fragment?
multiset<int> m = {2, 2, 2, 5};
m.erase(m.find(2));
cout << m.size() << " " << m.count(2);
Pokaż odpowiedź
3 2Usuwamy jedną dwójkę wskazaną strzałką. Zostają dwie dwójki i piątka.
Co wypisze ten fragment?
multiset<int> m = {9, 3, 3, 6};
m.erase(m.begin());
cout << *m.begin();
Pokaż odpowiedź
3Multiset to {3, 3, 6, 9}. Usuwamy jeden najmniejszy element — jedną trójkę. Najmniejszy dalej to 3.
Co wypisze ten fragment?
vector<int> v = {3, 1, 3, 2, 1};
multiset<int> m(v.begin(), v.end());
for (int x : m) cout << x;
Pokaż odpowiedź
11233Multiset z całego vectora: wszystkie liczby, posortowane, z powtórzeniami.
Co wypisze ten fragment?
multiset<int> m = {1, 3, 3, 5};
cout << *m.lower_bound(3) << " " << *m.upper_bound(3);
Pokaż odpowiedź
3 5lower_bound(3) wskazuje pierwszą trójkę, upper_bound(3) — pierwszy element za wszystkimi trójkami, czyli 5.
Co wypisze ten fragment?
multiset<int, greater<int>> m = {3, 5, 1, 5};
for (int x : m) cout << x << " ";
Pokaż odpowiedź
5 5 3 1Reguła greater działa też w multisecie: malejąco, z powtórzeniami.
Co wypisze ten fragment?
multiset<int> m;
for (int i = 1; i <= 9; i++) m.insert(i % 2);
m.erase(m.find(1));
cout << m.count(0) << " " << m.count(1);
Pokaż odpowiedź
4 4Reszty z dzielenia przez 2 dla liczb od 1 do 9: pięć jedynek (liczby nieparzyste) i cztery zera. Usuwamy jedną jedynkę — zostają po cztery.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

7.1 Dziennik ocenłatwe✓ zaliczone Oceny się powtarzają, a poprawiona ocena znika — tylko jedna! multiset, count i erase(find). multisetcounterase(find(x)) Rozwiąż 7.2 Jedno czy wszystkie?łatwe✓ zaliczone JEDNO x usuwa jedną kopię, WSZYSTKIE x — każdą. Dwie różne linijki z erase. erase(x)erase(find(x))multiset Rozwiąż 7.3 Ceny na półceśrednie✓ zaliczone Dostawy i sprzedaż, a w międzyczasie pytania o najtańszy i najdroższy produkt. Dwa produkty w tej samej cenie to dwa produkty! multiset*begin() i *rbegin()erase(find(c)) Rozwiąż 7.4 Najcieplej w każdym tygodniuśrednie✓ zaliczone Dla każdego okna k kolejnych dni — najwyższa temperatura. Okno w multisecie, wychodzi jedna kopia. okno w multisecieerase(find)*rbegin() Rozwiąż 7.5 Najspokojniejszy tydzieńśrednie✓ zaliczone W którym okresie k dni różnica między najcieplejszym a najzimniejszym dniem była najmniejsza? okno w multisecie*rbegin() − *begin()pierwsze minimum Rozwiąż 7.6 Sklep z butamiśrednie✓ zaliczone Każdy klient kupuje najmniejszą parę, która na niego pasuje. lower_bound w multisecie i erase(it). multisetlower_bounderase(it) Rozwiąż 7.7 Sklejanie linśrednie✓ zaliczone Zawsze sklejaj dwie najkrótsze liny. Ile kosztuje sklejenie wszystkich? Dwa razy begin(), wstaw sumę. multisetdwa najmniejszelong long Rozwiąż 7.8 Pralniatrudne✓ zaliczone k pralek, klienci w kolejce. Każdy bierze pralkę, która zwolni się najwcześniej. Kiedy koniec i ile czekania? multiset czasówzawsze najmniejszymax(przyjście, wolna)long long Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

unordered_set i szybkość — który zbiór wybrać?

Przez całą lekcję powtarzaliśmy, że operacje na zbiorze są szybkie: O(log n). Czas zobaczyć, skąd ta szybkość się bierze, poznać jeszcze szybszego kuzyna — unordered_set — i nauczyć się wybierać właściwą strukturę do zadania. W ćwiczeniach z tej części dane są duże: pomysł „pętla w pętli” nie zdąży, a zbiór — tak.

Jak set szuka tak szybko? Drzewo

W środku set trzyma elementy w drzewie poszukiwań. Na górze stoi jeden element. Na lewo od niego są tylko mniejsze, na prawo — tylko większe. I tak samo w każdym miejscu drzewa. Żeby sprawdzić, czy x jest w zbiorze, zaczynamy od góry: jeśli x jest mniejszy — schodzimy w lewo, jeśli większy — w prawo. Każdy krok w dół odrzuca połowę tego, co zostało — dokładnie jak zgadywanie liczby z lekcji o złożoności.

Wybierz liczbę i przejdź szukanie krok po kroku. Spróbuj też liczb, których w zbiorze nie ma — zobaczysz, gdzie zatrzyma się szukanie i gdzie insert dołożyłby nowy element.

Jak set szuka? Drzewo poszukiwań
Ta ramka działa po włączeniu JavaScriptu.

Drzewo z 15 elementów ma 4 poziomy, więc każde szukanie kończy się po najwyżej 4 porównaniach. Zbiór dba o to, żeby drzewo było zawsze wyważone — po każdym insert i erase sam je poprawia. Dzięki temu poziomów jest około log₂ n: dla tysiąca elementów 10, dla miliona 20, dla miliarda 30. Stąd O(log n) dla insert, count, erase, find, lower_bound i upper_bound.

Ile kosztuje każda operacja?

operacjavectorposortowany vectorsetunordered_set
dodaj xO(1) — push_backO(n) — wstaw w środekO(log n)O(1) średnio
czy x jest?O(n)O(log n)O(log n)O(1) średnio
usuń xO(n)O(n)O(log n)O(1) średnio
najmniejszy, największyO(n)O(1)O(1)O(n)
pierwszy ≥ xO(n)O(log n)O(log n)brak
przechodzeniekolejność dodawaniarosnącorosnącodowolna kolejność

unordered_set — bez kolejności, za to szybciej

unordered.cpp
#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> u;
    u.insert(5);
    u.insert(2);
    u.insert(8);
    u.insert(5);
    cout << u.size() << " " << u.count(2) << " " << u.count(7) << "\n";
    u.erase(2);
    cout << u.size() << "\n";
    return 0;
}
▶ Wyjście
3 1 0 2
kolejnosc.cpp
unordered_set<int> u = {9, 4, 15, 20, 6};
for (int x : u) cout << x << " ";
cout << "\n";
▶ Wyjście — u Ciebie kolejność może być inna
6 20 15 4 9

unordered_set (nagłówek <unordered_set>) ma te same podstawowe polecenia: insert, count, erase, size, empty, clear, find. Też nie trzyma powtórzeń.

Różnica: nie trzyma kolejności. Przechodzenie pętlą daje elementy w kolejności, która zależy od wnętrza struktury — może być inna na innym komputerze i zmieniać się po dodaniu elementów. Nie ma też lower_bound ani „najmniejszego na początku”.

W zamian insert, count i erase działają średnio w O(1). Liczba trafia do „kubełka” wybranego przez obliczenie z jej wartości (coś jak reszta z dzielenia przez liczbę kubełków), a count zagląda tylko do jednego kubełka. Zobacz to w ramce poniżej.

Wrzuć do zbioru — i zobacz, co się stanie
kolejność wstawiania
set
Ta ramka działa po włączeniu JavaScriptu.

Ramka to uproszczony model: ma 7 kubełków i wybiera kubełek resztą z dzielenia przez 7. Prawdziwy unordered_set sam dobiera liczbę kubełków (i zmienia ją, gdy elementów przybywa), dlatego program wyżej wypisał te same liczby w innej kolejności. Ważne jest jedno: ta kolejność nie jest rosnąca i nie wolno na niej polegać.

„Średnio” jest ważne: gdy wiele liczb trafi do jednego kubełka, count musi przejrzeć je wszystkie. Na zwykłych danych zdarza się to rzadko, ale autorzy zadań olimpijskich potrafią przygotować dane, które celowo zapychają jeden kubełek. Dlatego set z gwarantowanym O(log n) jest bezpieczniejszym wyborem, a unordered_set — szybszym, gdy liczy się każda milisekunda i kolejność jest niepotrzebna.

Gdy liczby są małe: zwykła tablica

tablica_bool.cpp
int n;
cin >> n;
vector<bool> byla(1000001, false);
int rozne = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (!byla[x]) {
        byla[x] = true;
        rozne++;
    }
}
cout << rozne << "\n";
▶ Wejście
6 5 3 5 1000000 3 0
▶ Wyjście
4

Gdy wszystkie wartości są małymi liczbami nieujemnymi — powiedzmy od 0 do miliona — zbiór można zastąpić tablicą: byla[x] mówi, czy x już się pojawił. To tablica zliczeń z lekcji o tablicach. Sprawdzenie i zaznaczenie to jeden krok, O(1) — szybciej niż jakikolwiek zbiór.

Ale tablica ma granice: nie zmieści wartości do 10¹⁸, nie przyjmie liczb ujemnych ani napisów, a tablica na miliard pól nie zmieści się w pamięci. Zbiór działa z dowolnymi wartościami — płaci za to logarytmem.

Który wybrać?

w zadaniu potrzebujesz…wybierz
tylko „czy było?” i „ile różnych?”, wartości małe (do ok. 10⁷)tablica bool / zliczeń
tylko „czy było?” i „ile różnych?”, wartości dowolneset albo unordered_set
kolejności, najmniejszego, największego, najbliższego (lower_bound)set
tego samego, ale powtórzenia to różne rzeczymultiset
wszystkie dane od razu, potem tylko pytaniaposortowany vector (sort, lower_bound)
kolejności z wejścia, indeksów, „który był trzeci?”vector

Ten sam problem: pętla w pętli kontra zbiór

para_wolno.cpp
int n;
long long k;
cin >> n >> k;
vector<long long> t(n);
for (long long &x : t) cin >> x;
bool jest = false;
for (int i = 0; i < n; i++)          // O(n²)
    for (int j = i + 1; j < n; j++)
        if (t[i] + t[j] == k) jest = true;
cout << (jest ? "TAK" : "NIE") << "\n";
▶ Wejście
5 10 3 8 4 7 1
▶ Wyjście
TAK
para_zbior.cpp
int n;
long long k;
cin >> n >> k;
set<long long> widziane;
bool jest = false;
for (int i = 0; i < n; i++) {        // O(n log n)
    long long x;
    cin >> x;
    if (widziane.count(k - x)) jest = true;
    widziane.insert(x);
}
cout << (jest ? "TAK" : "NIE") << "\n";
▶ Wejście
5 10 3 8 4 7 1
▶ Wyjście
TAK

Czy jakieś dwie liczby z listy dają w sumie k? Lewy program sprawdza każdą parę — dla n = 200 000 to 20 miliardów par, kilka minut liczenia. Prawy czyta liczby po kolei i dla każdej pyta: czy widziałem już jej „dopełnienie” k − x? Dla x = 7 dopełnieniem jest 3, a trójkę widzieliśmy wcześniej. Jedno count na liczbę — razem O(n log n), ułamek sekundy.

Kolejność „najpierw pytaj, potem wstaw” znów jest ważna: gwarantuje, że parę tworzą dwie różne pozycje. Dla k = 10 i listy z jedną piątką odpowiedź brzmi NIE — sama piątka nie może być parą sama ze sobą.

Dwa wskaźniki ze zbiorem: najdłuższy fragment bez powtórzeń

bez_powtorzen.cpp
int n;
cin >> n;
vector<int> t(n);
for (int &x : t) cin >> x;
set<int> okno;
int l = 0, best = 0;
for (int r = 0; r < n; r++) {
    while (okno.count(t[r])) {   // t[r] już jest — zwijamy z lewej
        okno.erase(t[l]);
        l++;
    }
    okno.insert(t[r]);
    best = max(best, r - l + 1);
}
cout << best << "\n";
▶ Wejście
8 1 2 3 1 4 5 3 2
▶ Wyjście
5

Szukamy najdłuższego fragmentu (kawałka bez przerw), w którym wszystkie liczby są różne. Okno [l, r] trzyma zbiór swoich elementów. Prawy koniec idzie po kolei. Gdy nowa liczba t[r] już jest w oknie, przesuwamy lewy koniec i wyrzucamy elementy, aż powtórka zniknie.

Pętla while w środku for wygląda groźnie, ale — jak w dwóch wskaźnikach z lekcji o złożoności — lewy koniec tylko rośnie, więc łącznie wykona najwyżej n kroków. Całość: O(n log n).

Tu wynik 5 daje fragment 2, 3, 1, 4, 5 (albo 1, 4, 5, 3, 2).

Zbiór sum prefiksowych: fragment o sumie 0

suma_zero.cpp
int n;
cin >> n;
set<long long> sumy = {0};    // suma pustego początku
long long s = 0;
bool jest = false;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    s += x;
    if (sumy.count(s)) jest = true;
    sumy.insert(s);
}
cout << (jest ? "TAK" : "NIE") << "\n";
▶ Wejście 1
6 3 -1 4 -3 5 2
▶ Wyjście 1
TAK
▶ Wejście 2
3 1 2 3
▶ Wyjście 2
NIE

Czy jest fragment o sumie dokładnie 0? Pomysł z sum prefiksowych: suma fragmentu od l do r to P[r] − P[l − 1]. Równa się zero wtedy, gdy dwie sumy prefiksowe są równe. Zbieramy więc kolejne sumy prefiksowe do zbioru i pytamy, czy nowa już była.

Sumy dla pierwszego wejścia: 0, 3, 2, 6, 3 — trójka powtórzyła się, więc fragment między nimi (−1, 4, −3) sumuje się do zera. Zero na starcie oznacza pusty początek — dzięki niemu złapiemy też fragment zaczynający się od pierwszej liczby.

Wielkie dane z generatora

generator.cpp
long long n, s, a, b, m;
cin >> n >> s >> a >> b >> m;
unordered_set<long long> u;
long long x = s;
for (long long i = 0; i < n; i++) {
    u.insert(x);
    x = (x * a + b) % m;
}
cout << u.size() << "\n";
▶ Wejście
10 1 2 3 7
▶ Wyjście
3

W kilku ćwiczeniach z tej części liczby nie są podane wprost — za dużo by ich było. Zamiast tego dostajesz pięć liczb n, s, a, b, m i generator z lekcji o złożoności: x₁ = s, a każda następna to xᵢ = (xᵢ₋₁ · a + b) mod m. Licz w long long — iloczyn może sięgać 10¹⁸.

Dla wejścia z przykładu: 1, 5, 6, 1, 5, 6, … — ciąg się zapętla i różne są tylko trzy liczby. Zbiór sam to wyłapał.

Ukryte koszty, które psują szybkość lower_bound(s.begin(), s.end(), x) na zbiorze — O(n), pisz s.lower_bound(x). count(x) w multisecie z wieloma kopiami — O(liczba kopii), do „czy jest?” użyj find. next(it, k) — k kroków. Kopia zbioru (set<int> t = s;) albo wypisanie całego zbioru w każdym obrocie pętli — O(n) za każdym razem, czyli O(n²) razem.
Zapamiętaj set to wyważone drzewo poszukiwań: insert, count, erase, find, lower_bound — O(log n). unordered_set — bez kolejności i bez lower_bound, za to średnio O(1). Małe wartości — tablica bool. „Czy jest para o sumie k?” — pytaj o k - x przed wstawieniem x. Fragment bez powtórzeń — okno ze zbiorem. Fragment o sumie 0 — powtórzona suma prefiksowa.
Sprawdź się w głowie

Licz w głowie albo na kartce — tak jak w lekcji o złożoności.

Ile poziomów (mniej więcej) ma drzewo zbioru z miliona elementów? Ten fragment liczy, ile razy da się podzielić milion na pół:
int n = 1000000, kroki = 0;
while (n > 1) {
    n /= 2;
    kroki++;
}
cout << kroki;
Pokaż odpowiedź
19Około 20 — log₂ miliona. Tyle porównań wystarcza zbiorowi, żeby znaleźć dowolny element wśród miliona.
Co wypisze ten fragment?
unordered_set<int> u = {3, 3, 1, 2, 1};
cout << u.size() << u.count(3) << u.count(4);
Pokaż odpowiedź
310Bez powtórzeń zostają 1, 2, 3 — trzy elementy. 3 jest (1), 4 nie ma (0).
Co wypisze ten program dla podanego wejścia?
int n;
cin >> n;
vector<bool> byla(10, false);
int ile = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (!byla[x]) { byla[x] = true; ile++; }
}
cout << ile;
Wejście: 5 2 7 2 7 9
Pokaż odpowiedź
3Różne wartości to 2, 7 i 9. Tablica bool działa tu jak zbiór, bo wartości są małe (od 0 do 9).
Co wypisze ten program dla podanego wejścia?
int n, k;
cin >> n >> k;
set<int> w;
bool jest = false;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (w.count(k - x)) jest = true;
    w.insert(x);
}
cout << (jest ? "TAK" : "NIE");
Wejście: 4 12 6 2 5 7
Pokaż odpowiedź
TAK5 + 7 = 12: gdy przychodzi 7, piątka już jest w zbiorze. Szóstka nie pomogła, bo jest tylko jedna (6 + 6 wymagałoby dwóch szóstek).
Co wypisze ten program dla podanego wejścia?
int n;
cin >> n;
set<long long> sumy = {0};
long long s = 0;
bool jest = false;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    s += x;
    if (sumy.count(s)) jest = true;
    sumy.insert(s);
}
cout << (jest ? "TAK" : "NIE");
Wejście: 4 2 -2 5 1
Pokaż odpowiedź
TAKSumy prefiksowe: 0, 2, 0 — zero się powtórzyło. Fragment 2, −2 ma sumę 0.
Co wypisze ten program dla podanego wejścia?
int n;
cin >> n;
vector<int> t(n);
for (int &x : t) cin >> x;
set<int> okno;
int l = 0, best = 0;
for (int r = 0; r < n; r++) {
    while (okno.count(t[r])) { okno.erase(t[l]); l++; }
    okno.insert(t[r]);
    best = max(best, r - l + 1);
}
cout << best;
Wejście: 6 5 5 5 5 5 5
Pokaż odpowiedź
1Same piątki: każdy fragment dłuższy niż 1 ma powtórkę. Okno nigdy nie urośnie powyżej jednego elementu.
Co wypisze ten fragment?
set<int> s;
for (int i = 0; i < 1000; i++) s.insert(i % 10);
cout << s.size();
Pokaż odpowiedź
10Tysiąc wstawień, ale tylko 10 różnych reszt: od 0 do 9. Każde insert powtórki kosztuje O(log n) i nic nie zmienia.
Co wypisze ten program dla podanego wejścia?
long long n, s, a, b, m;
cin >> n >> s >> a >> b >> m;
set<long long> u;
long long x = s;
for (int i = 0; i < n; i++) {
    u.insert(x);
    x = (x * a + b) % m;
}
cout << u.size();
Wejście: 6 0 1 2 6
Pokaż odpowiedź
3Ciąg: 0, 2, 4, 0, 2, 4 (każdy kolejny to poprzedni + 2, modulo 6). Różne są trzy liczby.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

8.1 Ile różnych — wielkie danełatwe✓ zaliczone Do 200 000 liczb z generatora. Ile różnych? Pętla w pętli nie zdąży, zbiór — tak. generatorset / unordered_setO(n log n) Rozwiąż 8.2 Para o sumie k — wielkie daneśrednie✓ zaliczone Czy dwie różne pozycje ciągu dają w sumie k? Pytaj o k − x przed wstawieniem x. generatorcount(k − x)long long Rozwiąż 8.3 Saldo jak kiedyśśrednie✓ zaliczone Pierwszy dzień, w którym saldo konta jest takie samo jak w którymś wcześniejszym dniu. Zbiór sum prefiksowych. sumy prefiksowecountlong long Rozwiąż 8.4 Playlista bez powtórekśrednie✓ zaliczone Najdłuższy fragment playlisty, w którym żaden utwór się nie powtarza. Dwa wskaźniki i set<string>. dwa wskaźnikiokno ze zbioremset<string> Rozwiąż 8.5 Wspólne liczby — wielkie daneśrednie✓ zaliczone Dwa długie ciągi z generatora. Ile różnych wartości występuje w obu? Część wspólna na dużych danych. generatorczęść wspólnaO(n log n) Rozwiąż 8.6 Kiedy generator się zapętli?średnie✓ zaliczone Generator w końcu powtórzy liczbę i zacznie krążyć. Na której pozycji i jak długa jest pętla? wykrywanie powtórkizbiór albo tablicadługość cyklu Rozwiąż 8.7 Różne w każdym oknietrudne✓ zaliczone Dla każdego okna k kolejnych liczb — ile w nim różnych? Wypisz największą i najmniejszą z tych wartości. okno w multiseciefind zamiast countlicznik różnych Rozwiąż 8.8 Szybkie pytaniaśrednie✓ zaliczone 200 000 liczb i 200 000 pytań „czy jest?”. Zbiór raz, potem każde pytanie w O(log n) — albo O(1). generatorcountunordered_set Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Baza zadań: zbiory w praktyce

Znasz już cały zestaw: insert, size i przechodzenie zbioru, count i erase z pytaniem „czy to już było?”, najmniejszy i największy z begin i rbegin, iteratory, find, lower_bound i upper_bound z najbliższą wartością, działania na zbiorach, zbiory par i napisów, multiset z oknami i zachłannymi wyborami, a na koniec unordered_set i wybór właściwej struktury. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka, potem zadania średnie, a na końcu trudne — z wielkim finałem.

Przy każdym zadaniu widać, jakich zagadnień używa — jeśli coś brzmi obco, wróć do odpowiedniej części, mapa lekcji jest na górze strony. A tu masz najważniejsze schematy w jednym miejscu:

Ściąga: gotowe schematy

Podstawy

set<int> s;
s.insert(x);       // powtórka: nic
s.size();          // ile różnych
for (int x : s)    // rosnąco
s.count(x);        // 1 albo 0
s.erase(x);        // brak: nic
s.empty(); s.clear();

Zbiór nie ma indeksów: zamiast s[i] — pętla albo kopia do vectora.

Czy to już było?

set<int> widziane;
for (…) {
    cin >> x;
    if (widziane.count(x)) …
    widziane.insert(x);
}

Najpierw pytaj, potem wstaw. Przy kilku testach — nowy zbiór w każdym.

Skrajne i strzałki

*s.begin()          // najmniejszy
*s.rbegin()         // największy
s.erase(s.begin());
s.erase(prev(s.end()));
next(it), prev(it)

Zawsze najpierw !s.empty(). Zmiana elementu = erase + insert.

Szukanie

s.find(x)           // albo end()
s.lower_bound(x)    // pierwszy >= x
s.upper_bound(x)    // pierwszy > x
prev(s.upper_bound(x))  // ost. <= x
prev(s.lower_bound(x))  // ost. < x

Przed prev sprawdź != begin(), przed gwiazdką — != end().

Działania

A ∩ B:  x z A, B.count(x)
A \ B:  x z A, !B.count(x)
A ∪ B:  S = A; S.insert(B…)
|A∪B| = |A| + |B| - |A∩B|
A == B  // te same elementy

Przechodź mniejszy zbiór, pytaj większy.

Pary i klucze

set<pair<int,int>> p;
p.insert({min(a,b), max(a,b)});
ranking: {-punkty, numer}
p.lower_bound({w, INT_MIN})
sort(w.begin(), w.end()); // klucz

Zanim wstawisz, sprowadź do jednej postaci.

multiset

multiset<int> m;
m.erase(m.find(x)); // JEDNA kopia
m.erase(x);         // WSZYSTKIE
okno: insert(t[i]),
  erase(find(t[i-k])),
  *m.rbegin()

„Czy jest?” w multisecie — przez find, nie count.

Który wybrać?

małe wartości → bool[]
czy było, ile różnych → set /
                 unordered_set
kolejność, najbliższy → set
powtórzenia → multiset
dane się nie zmieniają →
  sort + lower_bound

Każda operacja na zbiorze: O(log n).

Jak rozwiązywać zadania ze zbiorem 1) Zastanów się, o co naprawdę pyta zadanie: o różne wartości? o to, czy coś już było? o najbliższą wartość? o najmniejszy element, gdy dane się zmieniają? 2) Wybierz strukturę — ściąga „Który wybrać?” wyżej. 3) Zdecyduj, czy powtórzenia są różnymi rzeczami (multiset), czy tym samym (set). 4) Pilnuj brzegów: pusty zbiór, begin() przed prev, end() przed gwiazdką. 5) Duże liczby i sumy — long long. 6) Sprawdź program na przykładzie z treści, a potem pomyśl o największym teście.
łatwe

Rozgrzewka · zadania 1–10

Rozgrzewka ze zbiorem: lotto, słowa użyte tylko raz, różne kawałki napisu, liczby o różnych cyfrach, spotkanie ciągów Collatza, reszty z potęg, pomalowany płot, najbardziej różnorodne słowo, szyfr z kluczem i sprawdzanie sudoku.

1 Lottołatwe✓ zaliczone Wylosowano 6 liczb. Ile trafień ma każdy kupon? Zbiór wylosowanych i count. countczęść wspólnakilka kuponów Rozwiąż 2 Słowa użyte tylko razłatwe✓ zaliczone Które słowa pojawiły się w tekście dokładnie raz? Dwa zbiory: „raz” i „więcej”. dwa zbioryeraseset<string> Rozwiąż 3 Różne kawałki napisułatwe✓ zaliczone Ile różnych kawałków długości k ma napis? substr i set<string>. substrset<string>size() Rozwiąż 4 Liczby o różnych cyfrachłatwe✓ zaliczone Ile liczb z przedziału [a, b] ma same różne cyfry? Zbiór cyfr ma tyle elementów, ile liczba ma cyfr. set<char>to_stringsize() == długość Rozwiąż 5 Spotkanie ciągów Collatzałatwe✓ zaliczone Dwa ciągi Collatza w końcu się spotykają. Która liczba pierwszego ciągu jako pierwsza pojawia się w drugim? zbiór ciągucountlong long Rozwiąż 6 Reszty z potęgłatwe✓ zaliczone a¹, a², a³, … modulo m w końcu się zapętlają. Ile różnych reszt się pojawi? zbiór resztwykrywanie pętlilong long Rozwiąż 7 Pomalowany płotłatwe✓ zaliczone Malarze malują kawałki płotu, często te same deski. Ile różnych desek jest pomalowanych? insert w pętlisize()nakładające się przedziały Rozwiąż 8 Najbardziej różnorodne słowołatwe✓ zaliczone Które słowo ma najwięcej różnych liter? Przy remisie — pierwsze z listy. set<char>maksimumremis: pierwsze Rozwiąż 9 Szyfr z kluczemłatwe✓ zaliczone Alfabet szyfru: litery klucza bez powtórzeń, potem reszta alfabetu. Zaszyfruj wiadomość. zbiór „już użyte”kolejność z wejściagetline Rozwiąż 10 Poprawne sudoku?łatwe✓ zaliczone Każdy wiersz, kolumna i kwadrat 3 × 3 muszą mieć 9 różnych cyfr. Zbiór o rozmiarze 9. zbiór 9 cyfrclear()kwadraty 3 × 3 Rozwiąż
średnie

Średnie · zadania 11–20

Wspólni znajomi (vector zbiorów), ciąg Recamána, odważniki na jednej i na dwóch szalkach, izba przyjęć, fragment podzielny przez k, rezerwacje sali, najdłuższy ciąg kolejnych liczb, pierwsza niepowtórzona litera i k-ta dozwolona liczba.

11 Wspólni znajomiśrednie✓ zaliczone Każdy uczeń ma swój zbiór znajomych — vector zbiorów. Ilu wspólnych znajomych mają x i y? vector<set<int>>część wspólnapytania Rozwiąż 12 Ciąg Recamánaśrednie✓ zaliczone Cofnij się o k, jeśli wolno i jeszcze tam nie byłeś — inaczej idź o k do przodu. Zbiór odwiedzonych. zbiór wartości ciągucountsymulacja Rozwiąż 13 Odważnikiśrednie✓ zaliczone Jakie masy zważysz kompletem odważników na jednej szalce? Zbiór sum, który rośnie z każdym odważnikiem. zbiór sumkopia zbiorupierwsza brakująca Rozwiąż 14 Odważniki na dwóch szalkachśrednie✓ zaliczone Odważnik może leżeć przy przedmiocie, na drugiej szalce albo zostać w pudełku. Ile mas zważysz? zbiór różnictrzy możliwościliczby ujemne Rozwiąż 15 Izba przyjęćśrednie✓ zaliczone Najpierw najpilniejsi, przy remisie — kto pierwszy przyszedł. Zbiór par (−priorytet, numer przyjścia). set<pair>sztuczka z minusemkolejka priorytetowa Rozwiąż 16 Fragment podzielny przez kśrednie✓ zaliczone Pierwszy fragment o sumie podzielnej przez k. Dwie sumy prefiksowe z tą samą resztą. sumy prefiksowezbiór resztlong long Rozwiąż 17 Rezerwacje saliśrednie✓ zaliczone Rezerwacja wchodzi, jeśli nie nachodzi na żadną przyjętą. Sprawdź tylko dwie sąsiednie — lower_bound na parach. set<pair>lower_boundsąsiedzi przedziału Rozwiąż 18 Najdłuższy ciąg kolejnych liczbśrednie✓ zaliczone Jaki najdłuższy ciąg x, x + 1, x + 2, … da się złożyć z liczb na liście? Zbiór i przejście rosnąco. zbiór rosnącoseriesąsiad o 1 większy Rozwiąż 19 Pierwsza niepowtórzona literaśrednie✓ zaliczone Po każdej literze: która litera jako pierwsza wystąpiła dotąd tylko raz? Zbiór par (pozycja, litera). set<pair<int, char>>erasena bieżąco Rozwiąż 20 k-ta dozwolona liczbaśrednie✓ zaliczone Niektóre liczby są zakazane. Jaka jest k-ta dozwolona dodatnia liczba? Przesuwaj odpowiedź o każdą zakazaną po drodze. zbiór rosnącoprzesuwanie odpowiedzilong long Rozwiąż
trudne

Trudne · zadania 21–28

Najmniejsza wolna liczba na żywo, drzewa w alei, łączenie odcinków, przydział pokoi, sala egzaminacyjna, bliskie wartości w pobliżu, najdłuższy rosnący podciąg w O(n log n) — a na koniec wielki finał: giełda.

21 Najmniejsza wolna liczba na żywotrudne✓ zaliczone Liczby dochodzą i znikają, a pytamy o najmniejszą nieobecną. Trzymaj zbiór BRAKUJĄCYCH liczb. zbiór brakujących*begin()dwa zbiory Rozwiąż 22 Drzewa w aleitrudne✓ zaliczone Po każdym posadzonym drzewie: najdłuższy pusty odcinek alei. Zbiór pozycji i multiset długości przerw. set + multisetsąsiedzi nowegoerase(find) Rozwiąż 23 Łączenie odcinkówtrudne✓ zaliczone Odcinki dokładane po kolei sklejają się, gdy nachodzą albo się stykają. Ile kawałków po każdym kroku? set<pair>scalanieit = s.erase(it) Rozwiąż 24 Przydział pokoitrudne✓ zaliczone Goście w hotelu, każdy na swoje dni. Pokój zwalnia się dzień po wyjeździe. Ile pokoi i kto gdzie śpi? dwa zbioryset<pair> zajętychset wolnych numerów Rozwiąż 25 Sala egzaminacyjnatrudne✓ zaliczone Każdy wchodzący siada jak najdalej od innych. Który to fotel? Przejdź zbiór zajętych i porównaj przerwy. set zajętychprzerwy między sąsiadamiremis: najmniejszy numer Rozwiąż 26 Bliskie wartości w pobliżutrudne✓ zaliczone Czy są dwie pozycje odległe o najwyżej k, których wartości różnią się o najwyżej t? Okno w multisecie i lower_bound. okno w multisecielower_bound(x − t)pierwsze trafienie Rozwiąż 27 Najdłuższy rosnący podciąg — szybkotrudne✓ zaliczone 200 000 liczb z generatora. Najdłuższy ściśle rosnący podciąg w O(n log n) — sztuczka ze zbiorem. generatorinsert + erase(next(it))O(n log n) Rozwiąż 28 Wielki finał: giełdatrudne✓ zaliczone Oferty kupna i sprzedaży czekają w dwóch multisetach. Nowa oferta zawiera transakcję z najlepszą pasującą — albo czeka. dwa multisetybegin i rbeginerase(it)finał Rozwiąż

Częste błędy i dobre praktyki

🔁
Najpierw pytaj, potem wstaw
„Czy to już było?” — count przed insert. W odwrotnej kolejności każda liczba wyjdzie „znana”, bo przed chwilą sam ją wstawiłeś.
🫙
Pusty zbiór nie ma końców
*s.begin() i *s.rbegin() na pustym zbiorze to błąd bez ostrzeżenia. Gdy elementy znikają, sprawdzaj !s.empty() przed każdym sięgnięciem po skrajny element.
⬅️
prev tylko, gdy nie begin()
Ostatni ≤ x to prev(s.upper_bound(x)) — ale gdy upper_bound zwróci begin(), przed nim nic nie ma. A przed gwiazdką na wyniku lower_bound — sprawdź != s.end().
🔢
Zbiór nie ma indeksów
s[0] się nie skompiluje, a s.begin() + 2 też nie. Przechodź pętlą, używaj next, a gdy naprawdę potrzebujesz numerów — przepisz zbiór do vectora.
✏️
Zmiana = usuń i wstaw
Elementów zbioru nie zmienia się na miejscu — zbiór przestałby być posortowany. Zmiana punktów w rankingu to erase starej pary i insert nowej, więc stare wartości trzymaj osobno.
🔍
Szukaj z kropką
s.lower_bound(x) — O(log n). lower_bound(s.begin(), s.end(), x) daje ten sam wynik, ale przechodzi zbiór krok po kroku — O(n). Na dużych danych to różnica między OK a przekroczonym czasem.
✂️
multiset: jedna czy wszystkie?
m.erase(x) usuwa wszystkie kopie x. Jedną usuwa m.erase(m.find(x)) — po sprawdzeniu, że find nie zwrócił end(). Ten błąd nie wychodzi na testach bez powtórek.
🧺
Nowy zbiór na każdy test
Gdy wejście ma kilka testów, zbiór utworzony przed pętlą pamięta poprzednie. Twórz go wewnątrz pętli albo wywołuj clear() na początku każdego testu.
🔤
Jedna postać przed wstawieniem
„Kot” i „kot”, para (2, 1) i (1, 2), anagramy — dla zbioru to różne rzeczy. Sprowadź je do jednej postaci: małe litery, {min, max}, posortowane litery jako klucz.
🎲
unordered_set nie ma kolejności
Jest szybszy, ale przechodzi elementy w przypadkowej kolejności i nie ma lower_bound. Gdy wynik trzeba wypisać rosnąco, użyj set albo posortuj na końcu.
➖
size() nie ma znaku
s.size() zwraca liczbę bez znaku. s.size() - 1 na pustym zbiorze to nie −1, tylko ogromna liczba. Gdy odejmujesz od rozmiaru, zapisz go najpierw do int.
⚖️
Dobierz narzędzie
Małe wartości — tablica bool. Dane się nie zmieniają — sort i lower_bound. Dane się zmieniają i liczy się porządek — set. Powtórzenia — multiset. Nie każdy problem z „różnymi” potrzebuje zbioru.

Co dalej?

Zbiór to pierwsza struktura danych w kursie, która sama pilnuje porządku — i będzie wracać w prawie każdym trudniejszym zadaniu: w symulacjach, zachłannych wyborach i wszędzie tam, gdzie trzeba szybko znaleźć najbliższą wartość. Następna lekcja to Input i Output (+): zaawansowane wczytywanie i wypisywanie, szybkie wejście (ios::sync_with_stdio) i pliki — przyda się, gdy danych jest tak dużo, że samo ich czytanie zaczyna mieć znaczenie. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.