Set

RNO-Wiki

Zbiór (ang. set)

W stl-u mamy wspaniałą strukturę set - realizującą zbiór uporządkowany.

Dostępne są dla niej następujące instrukcje

  • clear() - czyści zbiór
  • size() - zwraca liczbę elementów w zbiorze
  • insert(x) - wstawia do zbioru nowy element (jeśli taki już istnieje, to nic nie robi)
  • erase(x) - usuwa element x ze zbioru (jeśli go nie ma w zbiorze, to nic nie robi)
  • find(x) - znajduje element x w zbiorze
  • lower_bound(x) - znajduje najmniejszy element większy lub równy x
  • upper_bound(x) - znajduje najmniejszy element większy x
  • .. więcej na stronie [1]

W C++ zbiór np. int'ów bardzo łatwo uzyskać. Wystarczy 

 #include<set>

i mamy już typ z wzorcem (ang. templatem) 

 set<type> A; // A jest zbiorem elementów typu 'type'

Na przykład zbiór liczb całkowitych Z otrzymujemy następująco 

 set<int> Z;

Iteratory

Tak jak każdy kontener STL'owy, set ma iteratory, które pozwalają przeglądać zawartość zbioru np. od początku do końca.

W tym celu mamy typ 

 set<int>::iterator iter;

Teraz zmienna o nazwie 'iter' jest iteratorem w zbiorze liczb całkowitych. Tak więc możemy dorwać się do początku zbioru 'Z' 

 iter = Z.begin();

albo do końca zbioru 

 iter = Z.end();

Uwaga : Z.end() wskazuje na element tuż za ostatnim elementem zbioru.

Zróbmy więc jakiś zbiór 

 set<int> Z;
 set<int>::iterator iter;
 Z.insert(10); Z.insert(13); Z.insert(8); Z.insert(5);

Cały bajer polega na tym, że nasz zbiór jest uporządkowany według realcji <

Nastepujący kawałek kodu wypisze liczby posortowane od najmniejszej do największej: 

 iter = Z.begin();
 while(iter != Z.end()) {
   cout << *iter << ", ";
   ++iter;
 }

Przykład

Najwięcej nauczysz się, gdy dokładnie przeanalizujesz poniższy kod w C++. Skopiuj go sobie i skompiluj. 

#include<iostream>
#include<vector>
#include<set>
#include<cassert>
using namespace std;
 
 
// Najpierw przeczytaj funkcję main, a potem przyjrzyj się definicji funkcji print
 
void print(set<int> &Z) // funkcja wypisuje elemtnu zbioru Z oddzielajac je przecinkami
{
	set<int>::iterator i; // i - jest iteratorem, którym będziemy przeglądać cały zbiór Z
 
	i = Z.begin(); // i - wskazuje na początek zbioru
	while ( i != Z.end() ) // Z.end() - jest wskaźnikiem na koniec zbioru (to nie jest ostatni element, lecz następny za nim)
	{
		int x = *i;  // *i - to jest wartość int-a, którą wskazuje iterator, a więc 'x' jest elementem zbioru
		printf("%d , ", x);
		i++; // iteratory można inkrementować, tj. zwiększać o jeden
	}
	printf("\n");
}
 
int main(void)
{
	set<int> A; // A - zbiór intów
 
	A.clear(); // czyści zbiór
 
	// Funkcja assert dziala nastepujaco
	// assert(bool w) :  jesli w jest falszem, to program konczy dzialanie z pewnym błędem (informacje są wypisywane na ekran)
	assert( A.empty() );
 
	if ( A.empty() ) // czy zbiór jest pusty
		printf("Zbior A jest pusty.\n");
 
	A.insert(1); // operacja dodawania do zbioru dziala bardzo szybko : czas O( log(n) )
	A.insert(5); A.insert(2); A.insert(9); A.insert(15); A.insert(75);
 
	int n = A.size(); // metoda size() zwraca liczbe elementow w zbiorze
 
	printf("Zbior A ma %d elementow.\n", A.size()); // Zbior A ma 6 elementow
	A.insert(2); // UWAGA : to jest zbior, a poniewaz elelement 2 jest juz w zbiorze, wiec ta operacja nic nie wstawi do zbioru
 
 
	assert( A.size()==6 );
	printf("Zbior A ma %d elementow.\n", A.size()); // Zbior A ma 6 elementow
	print(A); // teraz przeczytaj definicję funkcji print(set<int> Z);
 
	A.erase(2);
	printf("Zbior A ma %d elementow.\n", A.size()); // Zbior A ma 5 elementow
	print(A);
 
 
	set<int>::iterator it; // it jest zmienną typu   iterator w set'cie intów :-)
 
	// Można sprawdzić czy 'x' jest w zbiorze A
	it = A.find(100); // funkcja find zwraca iterator
	if ( it == A.end() ) printf("100 nie nalezy do zbioru A.\n");
 
	if ( A.find(15) != A.end() ) printf("15 nalezy do zbioru A.\n");
 
 
	// A teraz binarne wyszukiwanie :-)
	it = A.lower_bound(10); // znajduje pierwszy element w zbiorze, który jest >= 10
	while( it != A.end() )
	{
		printf("%d , ", *it);
		it++;
	}
	printf("\n");
 
	it = A.upper_bound(10); // znajduje pierwszy element, który jest > 10 
	while( it != A.end() )
	{
		printf("%d , ", *it);
		it++;
	}
	printf("\n");
 
 
 
	// Przykład
	A.clear();
	for (int i=1; i<=100; i++) A.insert(i);
	A.erase(17);
 
	printf("Elementy x spelniajace   15 <= x <= 20\n");
 
	set<int>::iterator start, end;
	start = A.lower_bound(15);
	end   = A.upper_bound(20);
 
	it = start;
	while (it != end)
	{
		printf("%d , ", *it);
		it++;
	}
	printf("\n");
 
	// Można utworzyć zbiór, który skonstruujemy z dwóch iteratorów
	set<int> B(start, end);
	print(B);
 
	return 0;
}
Źródło: "http://www.rafalnowak.pl/wiki/index.php?title=Set"