Kontener typu set - zbiór

Stronę tą wyświetlono już: 9642 razy

Wstęp

Klasa set dostępna po załączeniu pliku nagłówkowego set jest kontenerem umożliwiającym przechowywanie zbiorów, czyli danych, które nie mogą się powtarzać. Dodanie do takiego kontenera elementu, który już istnieje jest nie możliwe. Zbiory przydają się do określenia liczebności unikalnych elementów zawartych w jakiejś tablicy oraz określenia zbioru tych elementów. Dla przykładu niech istnieje sobie pewna tablica danych:

Listing 1

int table[] = {0, 100, 20, 20, 30, 40};

Dodanie ich do obiektu klasy set spowoduje, że następujące elementy w sposób posortowany będą w niej zawarte:

Listing 2

0, 20, 30, 40, 100

Wiedza o liczebności elementów zbioru danych umożliwia np. zastosowanie algorytmu sortowania przez zliczanie, który jest opłacalny w zastosowaniu, gdy liczebność zbioru jest mała a liczebność sortowanych danych bazujących na elementach zbioru jest duża.

Dodawanie elementów do obiektu klasy set jest spowolnione przez proces równoczesnego sortowania danych. Od standardu C++ 11 dostępna jest klasa unordered_set, która nie sortuje elementów zbioru podczas ich dodawania.

Konstruktory klasy set

Standardowo klasa set ma konstruktor bezparametrowy i kopiujący:

Listing 3

std::set<int> set1;
std::set<int> set2(set1);

Możliwe jest zdefiniowanie własnego typu obsługującego porównywanie elementów przechowywanych przez obiekt klasy set:

Listing 4

struct Compare{
bool operator () (const std::string &str1, const std::string &str2){
return str1.compare(str2) > 0;
}
};
std::string str[] = {"first", "second", "first"};
std::set<std::string, Compare> set(str, str + sizeof(str) / sizeof(std::string)); // konstruktor z własnym typem porównywania danych oraz przyjmujący zakres kopiowanych danych
for(std::set<std::string, Compare>::iterator i = set.begin(); i != set.end(); i++){
std::cout << *i << std::endl;
}

Wynik działania powyższego kodu:

second
first

Można również do sortowania elementów użyć funkcji:

Listing 5

bool compare(std::string str1, std::string str2){
return str1.compare(str2) > 0;
}
std::set<std::string, bool (*)(std::string, std::string)> set(compare);

Istnieje również konstruktor umożliwiający skopiowanie zakresu elementów zbioru:

Listing 6

int table[] = {0, 100, 20, 20, 30, 40};
std::set<int> set1(table, table + sizeof(table) / sizeof(int));
std::set<int> set2(set1.begin(), set1.end());

Iterowanie po elementach klasy set

Standardowo iterowanie odbywa się w następujący sposób:

Listing 7

int table[] = {0, 100, 20, 20, 30, 40};
std::set<int> set1(table, table + sizeof(table) / sizeof(int));
for(std::set<int>::iterator i = set2.begin(); i != set2.end(); i++){
std::cout << *i << std::endl;
}

Wynik działania:

Dodawanie i usuwanie elementów klasy set

Dodawanie kolejnych elementów można wykonywać za pomocą metody insert:

Listing 8

int table[] = {0, 100, 20, 20, 30, 40};
std::set<int> set;
set.insert(10);
set.insert(table, table + sizeof(table) / sizeof(int));
for(std::set<int>::iterator i = set.begin(); i != set.end(); i++){
std::cout << *i << std::endl;
}

natomiast do usunięcia elementu z obiektu klasy set konieczne jest metody erase:

Listing 9

int table[] = {0, 100, 20, 20, 25, 30, 40};
std::set<int> set(table, table + sizeof(table) / sizeof(int));
set.erase(100); // usunie element zawierający wartość 100
set.erase(set.begin()); // usunie pierwszy element
set.erase(set.find(25), set.end()); // usunie elementy większe lub równe 25
for(std::set<int>::iterator i = set.begin(); i != set.end(); i++){
std::cout << *i << std::endl;
}

Wynik działania powyższego kodu:

Możliwe jest również usunięcie wszystkich elementów obiektu klasy set za pomocą metody clear.

Zamiana elementów dwóch obiektów klasy set

Za pomocą metody swap elementy dwóch obiektów klasy set mogą zostać zamienione miejscami. Oto przykład:

Listing 10

int table[] = {0, 100, 20, 20, 30, 40};
std::set<int> set( table, table + sizeof(table) / sizeof(int));
std::set<int> set2(table, table + 3);
std::cout << "object set before swap operation:" << std::endl;
for(std::set<int>::iterator i = set.begin(); i != set.end(); i++){
std::cout << *i << std::endl;
}
std::cout << "object set2 before swap operation:" << std::endl;
for(std::set<int>::iterator i = set2.begin(); i != set2.end(); i++){
std::cout << *i << std::endl;
}
set.swap(set2);
std::cout << "object set after swap operation:" << std::endl;
for(std::set<int>::iterator i = set.begin(); i != set.end(); i++){
std::cout << *i << std::endl;
}
std::cout << "object set2 after swap operation:" << std::endl;
for(std::set<int>::iterator i = set2.begin(); i != set2.end(); i++){
std::cout << *i << std::endl;
}

Wynik działania powyższego kodu:

object set before swap operation:
0
20
30
40
100
object set2 before swap operation:
0
20
100
object set after swap operation:
0
20
100
object set2 after swap operation:
0
20
30
40
100

Znajdowanie wskaźnika na element zawarty w obiekcie klasy set oraz sprawdzanie, czy element istnieje

Za pomocą metody find można uzyskać wskaźnik na szukany element w obiekcie klasy set. Metoda ta zwraca wskaźnik na koniec gdy element nie zostanie odnaleziony. W celu sprawdzenia, czy element istnieje można posłużyć się również metodą count, która zwraca 1, gdy element istnieje a 0 w przeciwnym przypadku.

Liczba elementów zawartych w obiekcie klasy set oraz sprawdzanie, czy obiekt nie ma elementów

Liczebność elementów obiektu klasy set można uzyskać za pomocą metody size, natomiast metodą empty można uzyskać informację o tym, czy obiekt nie zawiera żadnych elementów.

Strony powiązane