MAP oraz SET

std::map jest kolejnym kontenerem w bibliotece standardowej C++, który implementuje strukturę danych zwanej mapą lub słownikiem. Jest to kolekcja par klucz-wartość, gdzie klucze są unikalne i posortowane, a wartości są powiązane z nimi. W kontenerze std::map każdy klucz może być przypisany do jednej wartości.

Oto kilka cech std::map:

Unikalność kluczy: Każdy klucz w mapie jest unikalny. Nie może istnieć dwa identyczne klucze w jednej mapie.

Sortowanie: Elementy mapy są automatycznie sortowane względem kluczy zgodnie z określonym porządkiem. Domyślnie porządek ten jest porządkiem rosnącym.

Efektywne wyszukiwanie: Wyszukiwanie elementów w mapie jest bardzo efektywne, ponieważ jest to implementowane w oparciu o drzewo poszukiwań binarnych lub równoważną strukturę danych.

Dynamiczna struktura: Mapa automatycznie dostosowuje swoją strukturę do zmian w liczbie elementów, co oznacza, że ​​możesz dodawać i usuwać elementy dynamicznie.

Przykład załóżmy że mamy takie liczby: 3, 5, 8, 6, 3, 2, 1, 3, 5, 7, 4, czy można za pomocą set zliczyć ile jest jakich elementów?

Rozwiązanie Tak, możemy użyć kontenera std::set, aby zliczyć, ile razy każdy element występuje w zestawie. Jednak sama klasa std::set przechowuje tylko unikalne elementy, więc w przypadku, gdy potrzebujesz zliczyć wystąpienia każdego elementu, możesz użyć std::multiset, który pozwala przechowywać duplikaty. Oto jak to zrobić:

#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> mySet = {3, 5, 8, 6, 3, 2, 1, 3, 5, 7, 4};
// Mapa do przechowywania liczby wystąpień każdego elementu
std::map<int, int> occurrences;
//Iterujemy przez zbiór i zliczamy wystąpienia każdego elementu
for (int num : mySet) {
occurrences[num]++;
}
// Wyświetlamy wyniki
for (const auto& pair : occurrences) {
cout << "Liczba " << pair.first << " występuje " << pair.second << " razy." << endl;
}
return 0;
}

W tym kodzie używamy std::multiset do przechowywania wszystkich liczb, a następnie iterujemy po zestawie, korzystając z mapy occurrences, aby zliczyć wystąpienia każdej liczby. Na końcu wypisujemy liczbę wystąpień każdego elementu.

Przykład
Dany jest plik tekstowy zawierająy np.: liczby całkowite. Wczytaj te liczby to struktury set a następnie wyświetl

Rozwiązanie
Aby wczytać liczby z pliku tekstowego do zbioru (set) w C++, możesz użyć strumieni wejściowych ifstream oraz operacji na zbiorze. Oto przykładowy kod realizujący to zadanie:

#include <iostream>
#include <fstream>
#include <set>
using namespace std;
int main() {
ifstream plik("nazwa_pliku.txt"); // Otwieramy plik do odczytu
set<int> zbior;
int liczba;
while (plik >> liczba) { // Odczytujemy liczby z pliku
zbior.insert(liczba); // Wstawiamy odczytaną liczbę do zbioru
}
plik.close(); // Zamykamy plik
// Wyświetlamy zawartość zbioru
cout << "Liczby wczytane do zbioru:" << endl;
for (const auto& element : zbior) {
cout << element << endl;
}
return 0;
}

Ten kod otwiera plik o nazwie "nazwa_pliku.txt" i wczytuje kolejne liczby ze strumienia do zbioru. Następnie wyświetla zawartość zbioru. Upewnij się, że plik "nazwa_pliku.txt" zawiera jedną liczbę na linię, aby ten kod działał poprawnie.

Linia for (const auto& element : zbior) to tzw. pętla zakresowa (ang. range-based for loop) w C++. Pozwala ona iterować przez wszystkie elementy w kontenerze, takim jak zbiór (std::set), bez potrzeby korzystania z iteratorów w sposób jawny.
Termin const auto& element oznacza, że dla każdego elementu w zbiorze zbior, typ elementu będzie automatycznie wydedukowany przez kompilator (dzięki auto), a następnie użyty do zadeklarowania zmiennej element.
const oznacza, że element będzie traktowany jako stała, więc nie możemy jej modyfikować.
auto oznacza, że typ element będzie automatycznie dedukowany przez kompilator na podstawie typu elementów w zbiorze.
& oznacza, że element będzie przekazywany przez referencję, co pozwala uniknąć kopiowania elementów.
Wewnątrz pętli, dla każdego elementu w zbiorze, kod wykonuje się z użyciem zmiennej element, która reprezentuje aktualnie przetwarzany element zbioru.
Na przykład, w kontekście kodu wczytującego liczby z pliku do zbioru, linia ta iteruje przez każdą liczbę wczytaną do zbioru i wyświetla ją na ekranie.

Ćwiczenia

Wczytaj przykład:

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <utility>

using namespace std;

int main()
{
   unordered_multiset<string> names;
   names.insert("Romeo");
   names.insert("Julia");
   names.insert("Romeo"); // Funkcja names.count("Romeo") zwraca teraz liczbę 2
   cout << "Liczba Romeow: " << names.count("Romeo") << endl;
   cout << "Liczba Julii: " << names.count("Julia") << endl;
   names.erase("Julia"); // Funkcja names.count("Julia") zwraca teraz liczbę 0
   cout << "Liczba Julii: " << names.count("Julia") << endl;
   names.erase("Julia");
      // Nie ma żadnego skutku: w wielozbiorze nie ma już ciągu "Julia"
   cout << "Liczba Julii: " << names.count("Julia") << endl;

   unordered_multimap<string, string> friends;
   friends.insert(make_pair("Tomasz", "Daria")); // Daria przyjaźni się z Tomaszem.
   friends.insert(make_pair("Tomasz", "Henryk")); // Henryk też się z nim przyjaźni.

   auto tom_range = friends.equal_range("Tomasz");
      // pair::iterator>
   cout << "Przyjaciele Tomasza: ";
   for (auto pos = tom_range.first; pos != tom_range.second; pos++)
   {
      cout << pos->second << " ";
   }
   cout << endl;

   bool found = false;
   for (auto pos = tom_range.first; !found && pos != tom_range.second; pos++)
   {
      if (pos->second == "Daria")
      {
         found = true;
         friends.erase(pos);
         cout << "Daria nie przyjazni sie juz z Tomaszem" << endl;
      }
   }

   cout << "Liczba pozostalych przyjaciol Tomasza: "
      << friends.count("Tomasz") << endl;

   return 0;
}