Zbiory to jedne z najważniejszych struktur danych w programowaniu, używane do przechowywania unikalnych elementów i wykonywania operacji zbiorowych, takich jak suma, przecięcie i różnica. Zbiory są szeroko stosowane w aplikacjach, które wymagają przechowywania elementów bez duplikatów i szybkiego dostępu do danych. W tej lekcji omówimy, jak działają zbiory, jakie są różne sposoby ich implementacji, oraz jak efektywnie wykorzystywać je w praktycznych projektach.

Podstawy i zasada działania zbiorów

Zbiór (ang. set) to struktura danych, która przechowuje unikalne wartości. W przeciwieństwie do list czy tablic, zbiory nie pozwalają na przechowywanie zduplikowanych elementów. W zależności od implementacji, zbiory mogą być uporządkowane lub nieuporządkowane. W języku C++ mamy do dyspozycji dwa główne typy zbiorów: std::set i std::unordered_set. std::set przechowuje elementy w sposób uporządkowany, korzystając z drzewa czerwono-czarnego, co zapewnia złożoność O(log n) dla operacji, takich jak wstawianie, usuwanie i wyszukiwanie. std::unordered_set jest implementowany jako tablica haszująca, co umożliwia średnią złożoność O(1) dla tych operacji.

Implementacja zbiorów w C++

1. Użycie std::set

std::set to kontener, który przechowuje elementy w sposób uporządkowany i nie pozwala na duplikaty. Elementy są automatycznie sortowane według ich wartości, co jest przydatne w aplikacjach, które wymagają przechowywania danych w określonej kolejności.

#include <iostream>
#include <set>

int main() {
    std::set<int> uniqueNumbers;
    uniqueNumbers.insert(5);
    uniqueNumbers.insert(2);
    uniqueNumbers.insert(8);
    uniqueNumbers.insert(5); // Duplikat nie zostanie dodany

    for (int number : uniqueNumbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;

    return 0;
}

W powyższym przykładzie używamy std::set do przechowywania unikalnych liczb. Elementy są automatycznie sortowane, a próba dodania duplikatu nie ma żadnego efektu. std::set jest idealnym wyborem, gdy potrzebujemy uporządkowanego zbioru danych bez duplikatów.

2. Użycie std::unordered_set

std::unordered_set to kontener, który przechowuje elementy bez określonej kolejności, ale zapewnia szybszy dostęp do danych dzięki zastosowaniu tablicy haszującej. Średnia złożoność operacji wstawiania, usuwania i wyszukiwania wynosi O(1).

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<std::string> uniqueWords;
    uniqueWords.insert("apple");
    uniqueWords.insert("banana");
    uniqueWords.insert("cherry");
    uniqueWords.insert("apple"); // Duplikat nie zostanie dodany

    for (const std::string& word : uniqueWords) {
        std::cout << word << " ";
    }
    std::cout << std::endl;

    return 0;
}

W tym przykładzie używamy std::unordered_set do przechowywania unikalnych słów. Elementy są przechowywane w sposób nieuporządkowany, ale dostęp do nich jest szybki. std::unordered_set jest idealnym wyborem, gdy wydajność jest priorytetem, a kolejność elementów nie ma znaczenia.

Operacje na zbiorach

Zbiory oferują szeroki zakres operacji, które są niezwykle przydatne w przetwarzaniu danych. Oto niektóre z najczęściej używanych operacji:

1. Wstawianie elementów

Operacja insert() służy do dodawania elementów do zbioru. Jeśli element już istnieje, nie zostanie dodany ponownie. W przypadku std::set operacja ma złożoność O(log n), a w przypadku std::unordered_set O(1) w średnim przypadku.

2. Usuwanie elementów

Operacja erase() usuwa element ze zbioru. Podobnie jak w przypadku wstawiania, złożoność operacji zależy od typu zbioru: O(log n) dla std::set i O(1) w średnim przypadku dla std::unordered_set.

3. Wyszukiwanie elementów

Operacja find() sprawdza, czy dany element istnieje w zbiorze. Zwraca iterator wskazujący na element, jeśli został znaleziony, lub end(), jeśli element nie istnieje.

if (uniqueNumbers.find(5) != uniqueNumbers.end()) {
    std::cout << "Element found" << std::endl;
} else {
    std::cout << "Element not found" << std::endl;
}

Operacje zbiorowe

Zbiory umożliwiają wykonywanie operacji zbiorowych, takich jak suma, przecięcie i różnica, które są szczególnie przydatne w analizie danych i algorytmach teorii zbiorów.

1. Suma zbiorów

Suma dwóch zbiorów zawiera wszystkie unikalne elementy z obu zbiorów. Oto przykład implementacji sumy zbiorów:

std::set<int> set1 = {1, 2, 3};
std::set<int> set2 = {3, 4, 5};
std::set<int> unionSet;

unionSet.insert(set1.begin(), set1.end());
unionSet.insert(set2.begin(), set2.end());

for (int element : unionSet) {
    std::cout << element << " ";
}

W tym przykładzie wszystkie unikalne elementy z set1 i set2 są dodawane do unionSet, co daje wynik {1, 2, 3, 4, 5}.

2. Przecięcie zbiorów

Przecięcie dwóch zbiorów zawiera tylko te elementy, które występują w obu zbiorach. Oto przykład:

std::set<int> intersectionSet;
for (int element : set1) {
    if (set2.find(element) != set2.end()) {
        intersectionSet.insert(element);
    }
}

Przecięcie set1 i set2 zwraca zbiór {3}, ponieważ tylko ten element występuje w obu zbiorach.

3. Różnica zbiorów

Różnica dwóch zbiorów zawiera elementy, które występują w pierwszym zbiorze, ale nie w drugim. Przykład:

std::set<int> differenceSet;
for (int element : set1) {
    if (set2.find(element) == set2.end()) {
        differenceSet.insert(element);
    }
}

Różnica set1 i set2 zwraca {1, 2}, ponieważ te elementy nie występują w set2.

Zastosowania zbiorów

Zbiory są niezwykle wszechstronne i znajdują zastosowanie w różnych dziedzinach informatyki:

• Filtrowanie duplikatów: Zbiory są idealne do usuwania duplikatów z listy danych, co jest przydatne w analizie danych i przetwarzaniu dużych zbiorów danych.
• Systemy kontroli dostępu: W aplikacjach, gdzie trzeba śledzić unikalne identyfikatory użytkowników lub zasobów, zbiory są używane do implementacji systemów kontroli dostępu.
• Analiza grafów: Zbiory są używane w algorytmach grafowych, takich jak BFS i DFS, do śledzenia odwiedzonych węzłów.
• Przetwarzanie języka naturalnego (NLP): W analizie tekstu zbiory są używane do przechowywania unikalnych słów w dokumencie lub eliminowania duplikatów podczas analizy korpusów tekstowych.

Porównanie std::set i std::unordered_set

Wybór między std::set a std::unordered_set zależy od wymagań aplikacji:

• std::set: Gwarantuje uporządkowanie elementów i oferuje złożoność O(log n) dla operacji. Jest odpowiedni, gdy kolejność ma znaczenie lub gdy potrzebujemy uporządkowanych danych.
• std::unordered_set: Oferuje średnią złożoność O(1) dla operacji, ale elementy nie są uporządkowane. Jest idealny, gdy wydajność jest kluczowa, a kolejność nie ma znaczenia.

Podsumowanie

Zbiory to potężna i elastyczna struktura danych, która umożliwia efektywne przechowywanie i przetwarzanie unikalnych wartości. Dzięki operacjom takim jak suma, przecięcie i różnica, zbiory są nieocenione w analizie danych i algorytmach teorii zbiorów. Wybór między std::set a std::unordered_set zależy od specyfiki problemu, ale zrozumienie obu tych struktur pozwala na optymalizację wydajności aplikacji. Niezależnie od zastosowania, zbiory są kluczowym narzędziem w arsenale każdego programisty.

Następny temat ==> Kolejki i ich zastosowanie