std::set i std::map – kontenery asocjacyjne, złożoność operacji i przykłady użycia

Kompleksowy przewodnik po kontenerach asocjacyjnych: std::set i std::map w c++

Kontenery asocjacyjne std::set i std::map stanowią fundamentalną część biblioteki STL w C++, oferując wydajne mechanizmy przechowywania i zarządzania danymi w postaci posortowanych zbiorów lub par klucz-wartość. Niniejsza analiza szczegółowo przedstawia ich charakterystykę, złożoność operacji oraz praktyczne zastosowania, opierając się na aktualnej specyfikacji standardu C++17/C++20 i implementacjach bibliotecznych.

1. Charakterystyka kontenerów asocjacyjnych

Kontenery std::set i std::map należą do kategorii kontenerów asocjacyjnych, których kluczową cechą jest automatyczne sortowanie elementów według zadanego kryterium porównywania. Implementowane są zwykle przy użyciu drzew czerwono-czarnych (red-black trees), co gwarantuje optymalną równowagę między wydajnością operacji a kosztem utrzymania struktury.

• std::set – przechowuje unikalne wartości kluczy bez powiązanych danych dodatkowych; elementy są niepowtarzalne i posortowane rosnąco (domyślnie);
• std::map – przechowuje pary klucz-wartość (std::pair<const Key, T>), gdzie klucze są unikalne i posortowane; umożliwia bezpośredni dostęp do wartości poprzez klucz.

Oba kontenery oferują iteratory dwukierunkowe, pozwalające na przeglądanie elementów w kolejności posortowanej.

2. Złożoność czasowa operacji

Złożoność operacji w std::set i std::map wynika z ich drzewiastej implementacji:

Uwagi –

• Wstawianie N elementów do pustego kontenera ma łączną złożoność O(N log N);
• Operacje na iteratorach (inkrementacja/dekrementacja) mają złożoność amortyzowaną stałą O(1) w praktyce, mimo teoretycznego O(log N).

3. Deklaracja i inicjalizacja

Przykłady dla std::set –

#include <set>
std::set<int> pustyZbior; // Zbiór liczb całkowitych
std::set<std::string> imiona = {"Anna", "Jan", "Ewa"}; // Inicjalizacja listą
std::set<int> liczby(wektor.begin(), wektor.end()); // Inicjalizacja z innego kontenera

Przykłady dla std::map –

#include <map>
std::map<std::string, int> mapaWiek; // Mapa: nazwisko → wiek
std::map<int, float> punkty = {{1, 4.5}, {2, 3.8}}; // Inicjalizacja par

4. Podstawowe operacje

Wstawianie –

• set: insert(wartość) zwraca parę std::pair<iterator, bool> (iterator + flaga sukcesu);
• map: insert({klucz, wartość}) lub emplace(klucz, wartość).

Usuwanie –

• erase(iterator) – O(1) przy usuwaniu przez iterator;
• erase(klucz) – O(log N) przy wyszukaniu klucza.

Wyszukiwanie –

// Dla set:
auto it = zbior.find(42);
if (it != zbior.end()) { /* znaleziono */ }
// Dla map:
auto it = mapa.find("Kowalski");
if (it != mapa.end()) {
    int wiek = it->second; // dostęp do wartości
}

Iteracja –

// Range-based for loop (C++11)
for (const auto& elem : zbior) { /* ... */ }
// Dla map:
for (const auto& [klucz, wartosc] : mapa) { // C++17
    std::cout << klucz << ": " << wartosc;
}

5. Operacje zaawansowane

Operacje mnogościowe (dla std::set) –

#include <algorithm>
#include <iterator>
std::set<int> A = {1, 2, 3}, B = {3, 4, 5};
std::set<int> suma, iloczyn, roznica;
// Suma mnogościowa
std::set_union(A.begin(), A.end(), B.begin(), B.end(), std::inserter(suma, suma.begin())); // {1,2,3,4,5}
// Iloczyn mnogościowy
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::inserter(iloczyn, iloczyn.begin())); // {3}
// Różnica A-B
std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::inserter(roznica, roznica.begin())); // {1,2}

Złożoność – O(N+M) dla operacji na posortowanych kontenerach.

6. Optymalizacje i best practices

• Wskazówka przy wstawianiu – użyj emplace zamiast insert dla uniknięcia tworzenia tymczasowych obiektów;
• Przesunięcie węzłów (C++17) – extract + insert pozwala na modyfikację klucza bez alokacji:

auto node = mapa.extract("stary_klucz");
node.key() = "nowy_klucz";
mapa.insert(std::move(node));

• Unikaj operator[] w pętlach – dla nieistniejących kluczy tworzy domyślne wartości, co może prowadzić do błędów; zamiast tego używaj at() lub find().

7. Porównanie z std::unordered_set/map

Zastosowania –

• std::set/map: gdy wymagane jest iterowanie w kolejności posortowanej lub zakresowe zapytania (np. lower_bound);
• std::unordered_set/map: gdy priorytetem jest szybkość wstawiania/wyszukiwania, a porządek nieistotny.

8. Przykłady praktyczne

Przykład 1: Statystyka słów

std::map<std::string, int> licznikSlow;
std::string slowo;
while (std::cin >> slowo) {
    licznikSlow[slowo]++;
}
// Wyświetl w kolejności alfabetycznej
for (const auto& [slowo, liczba] : licznikSlow) {
    std::cout << slowo << ": " << liczba << "\n";
}

Przykład 2: System indeksowania

std::map<std::string, std::set<int>> indeks;
// Dodajemy pozycje: "algorytm" → {2, 5, 10}
indeks["algorytm"].insert(2);
indeks["algorytm"].insert(5);
// Sprawdzenie stron z terminem
if (indeks.find("algorytm") != indeks.end()) {
    for (int strona : indeks["algorytm"]) {
        std::cout << "Strona: " << strona << "\n";
    }
}

9. Ograniczenia i wyjątki

• Modyfikacja klucza – klucze w std::map i elementy std::set są niemodyfikowalne (poprzez iteratory); modyfikacja wymaga usunięcia i ponownego wstawienia;
• Wskaźniki jako klucze – wymagają własnych funktorów porównujących (np. std::greater<>);
• Wydajność dla małych zbiorów – dla N < 100 liniowe kontenery (np. std::vector) mogą być szybsze ze względu na brak narzutu drzewa.

Podsumowanie

Kontenery std::set i std::map oferują optymalną równowagę między wydajnością a funkcjonalnością dla scenariuszy wymagających posortowanych danych i szybkiego wyszukiwania. Ich złożoność logarytmiczna dla kluczowych operacji (wstawianie, usuwanie, wyszukiwanie) czyni je niezbędnymi w narzędziach takich jak bazy danych, systemy indeksujące czy algorytmy analizy danych. Wybór między nimi a kontenerami mieszającymi (unordered_set/map) powinien być podyktowany wymaganiami dotyczącymi porządku danych i charakterystyki dostępu.

Rekomendacje –

• Użyj std::set dla unikalnych, posortowanych wartości;
• Wybierz std::map dla par klucz-wartość z szybkim dostępem przez klucz;
• Zawsze testuj wydajność w scenariuszach brzegowych (duże zbiory, częste modyfikacje).

Źródła –
Scaler Topics: Set in C++ (2023)
CodeSignal: C++ Sets and Their Operations (2024)
LWG Issue 632: Time complexity of size() for std::set (2016)
Runtime complexity of inserting N items into an empty std::set (video)
HackerEarth: Standard Template Library
std::set::find (cplusplus.com)
Kontenery asocjacyjne — STL (Bitbucket)
Sandor Dargo: C++: The most important complexities (2023)
Map performance (Google Groups, 2008)
std::map::find (cplusplus.com)
C++17 i STL (PDF, Uniwersytet Wrocławski)
std::set (cppreference.com)
W3Schools: C++ Sets (2024)
Programiz: C++ Map (2000-2023)
Kurs C++: Kontenery asocjacyjne (2025)