Unikalne i uporządkowane pojemniki w C ++

6, 10, 2, 8, 4 to zestaw; 2, 4, 6, 8, 10 to zestaw tych samych liczb całkowitych, ułożony w kolejności rosnącej. W matematyce zestaw ma unikalne elementy (odrębne elementy) i to znaczy żaden element nie występuje więcej niż raz. Ponadto multiset to zestaw, w którym każdy element może wystąpić więcej niż raz. 6, 6, 10, 2, 2, 8, 4, 4, 4 to multiset. 2, 2, 4, 4, 4, 6, 6, 8, 10 to ten sam multiset, ale z elementami ułożonymi w kolejności rosnącej. Ten artykuł nie dotyczy Multiset. Zajmuje się zwaną strukturą danych C ++, zestaw.

Mapa w oprogramowaniu jest jak tablica, ale jest tablicą z dwiema kolumnami zamiast jednej. Pierwsza kolumna ma klucze, a druga kolumna ma wartości. Każdy wiersz to jedna para, tworząc parę klucza/wartości. Klucz jest bezpośrednio związany z jego wartością.

Przykładem mapy jest 'c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10. Pierwsza para klucza/wartości wstawiona tutaj, to „c”, 3, gdzie „c” jest kluczem, a 30 to wartość. Ta mapa nie jest zamówiona przez klucze. Zamawianie tej mapy według klawiszy produkuje 'a', 10, 'b', 20, 'c', 30, 'd', 30, 'e', 40. Zauważ, że mogą być zduplikowane wartości, ale nie zduplikowane klucze. Uporządkowana mapa to mapa uporządkowana przez klucze.

Multiset jest do zestawu, ponieważ multimap jest na mapie. Oznacza to, że istnieją mapy z zduplikowanymi klawiszami. Przykładem multimap jest 'a', 10, 'b', 20, 'b', 20, 'c', 30, 'c', 30, 'd ', 30, ' e ', 40. I jak wspomniano powyżej, ten artykuł nie dotyczy MultImap, raczej dotyczy struktury danych C ++, mapy.

W C ++ struktura danych jest strukturą o właściwościach (członkach danych) i metodach (funkcje członka). Dane struktury są listą; Zestaw jest listą; Mapa to lista par kluczy/wartości.

W tym artykule omówiono podstawy zestawów i map w C ++, a aby lepiej zrozumieć ten artykuł, czytelnik powinien był mieć podstawową wiedzę na temat C++.

Treść artykułu:

• Klasa i jej obiekty
• Tworzenie zestawu lub mapy
• Podstawy iteratora
• Dostęp do elementów do zestawu i mapy
• Kolejność elementów w zestawie lub mapie
• Inne powszechnie używane funkcje członków
• Wniosek

Klasa i jej obiekty:

W C ++ zestaw, mapa i inne podobne struktury nazywane są pojemnikami. Klasa jest uogólnioną jednostką z elementami danych, które są zmiennymi, i powiązanymi funkcjami członkowskimi. Gdy członkowie danych otrzymają wartości, obiekt powstaje. Jednak obiekt powstaje w procesie o nazwie, tworzenie instancji. Ponieważ klasa może prowadzić do różnych wartości dla tych samych zmiennych elementów danych, różne obiekty można następnie utworzyć z tej samej klasy.

W C ++ zestaw bezużytecznych jest klasą, a także bezużyteczną mapą. Gdy obiekt jest utworzony z zestawu bezużytecznego lub mapy bezużytecznej, obiekt staje się prawdziwą strukturą danych. W przypadku struktur danych zestawu i mapy główny element danych jest listą. Cóż, zestaw i mapa tworzą grupę pojemników o nazwie, zamówione kontenery asocjacyjne. Zestaw nie uporządkowany i mapa nieopisana również istnieją, ale niestety nie są one adresowane w tym artykule.

Tworzenie zestawu lub mapy:

Instantowanie zestawu z klasy zestawu jest tworzenie zestawu; Instanowanie mapy z klasy mapy to tworzenie mapy. Tak utworzony obiekt otrzymuje nazwę wyboru programisty.

Aby utworzyć zestaw, program powinien zacząć od:

#włączać
#włączać
za pomocą przestrzeni nazw Std;

Zwróć uwagę na dyrektywę „#Include”, która zawiera bibliotekę zestawu, z której set klasa, z której ustawione są struktury danych.

Aby utworzyć mapę, program powinien zacząć od:

#włączać
#włączać
za pomocą przestrzeni nazw Std;

Zwróć uwagę na dyrektywę „#Include”, która zawiera bibliotekę map, która ma klasę map, z której struktury danych mapy zostaną utworzone.

Składnia do utworzenia pustego zestawu to:

ustawić nazwa obiektu

Przykład:

ustawić setObj;

Przykładem utworzenia zestawu z treścią jest:

ustawić setOBJ (6, 10, 2, 8, 4);

Składnia do utworzenia pustej mapy to:

mapa nazwa obiektu

Przykład:

mapa Mapobj;

Przykładem utworzenia mapy z treścią jest:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Podstawy iteratora:

Iterator jest opracowanym wskaźnikiem, którego można użyć do przecinania listy struktury danych od początku do końca.

Funkcja członka start ()

Funkcja członka stear () zwraca iterator, który wskazuje na pierwszy element listy. Poniższy przykład ilustruje to dla zestawu:

ustawić setOBJ (6, 10, 2, 8, 4);
ustawić:: iterator iter = setOBJ.zaczynać();
Cout << *iter << '\n';

Zwróć uwagę na sposób, w jaki początek () został użyty z setOBJ i operatorem kropkowym. ITER to zwrócony obiekt iterator. Zwróć też uwagę na sposób, w jaki został zadeklarowany. * jest operatorem pośredniego. Zgodnie z ITER, zwraca pierwszy element zestawu; Pierwszy element to 2 zamiast 6 - patrz wyjaśnienie poniżej.

Poniższy przykład ilustruje użycie funkcji początkowej () dla mapy:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: iterator iter = mapobj.zaczynać();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Zwróć uwagę na sposób, w jaki początek () był używany z MAPOBJ i operatorem kropkowym. ITER to zwrócony obiekt iterator. Zwróć też uwagę na sposób, w jaki został zadeklarowany. „Po pierwsze”, jak tu używane, odnosi się do klucza. „Drugi” odnosi się do wartości odpowiadającej kluczowi. Obserwuj, w jaki sposób zostały użyte z ITER do uzyskania elementów początkowego listy. Pierwszy element to a, 10 zamiast c, 30 - patrz wyjaśnienie poniżej.

Funkcja członka „begin () const”

Funkcja członka „begin () const” zwraca iterator, który wskazuje na pierwszy element listy, gdy deklaracja zestawu zaczyna się od const (dla stałej). W tym stanie wartość na liście, o której mowa, zwrócona iterator, nie może zostać zmieniona przez iterator. Poniższy przykład ilustruje jego zastosowanie dla zestawu:

Const Set setOBJ (6, 10, 2, 8, 4);
ustawić:: const_iterator iter = setOBJ.zaczynać();
Cout << *iter << '\n';

Zwróć uwagę na sposób, w jaki początek () został użyty z setOBJ i operatorem kropkowym. Żadna „const” nie została wpisana tuż po początku (). Jednak „const” poprzedziło deklarację. ITER jest tutaj zwracany stały obiekt iterator, który różni się od normalnego iteratora. Zwróć też uwagę na sposób, w jaki został zadeklarowany. * jest operatorem pośredniego; Zgodnie z ITER, zwraca pierwszy element zestawu. Pierwszy element to 2 zamiast 6 - patrz wyjaśnienie poniżej.

Poniższy przykład ilustruje użycie funkcji „start () const” dla mapy:

mapa const mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: const_iterator iter = mapobj.zaczynać();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Zwróć uwagę na sposób, w jaki początek () był używany z MAPOBJ i operatorem kropkowym. Żadna „const” nie została wpisana tuż po początku (). Jednak „const” poprzedziło deklarację. ITER jest tutaj zwracany stały obiekt iterator, który różni się od normalnego iteratora. Zwróć też uwagę na sposób, w jaki został zadeklarowany. „Po pierwsze”, jak tu używane, odnosi się do klucza; „Drugi”, jak tu używany, odnosi się do wartości odpowiadającej kluczowi. Obserwuj, w jaki sposób zostały użyte z ITER do uzyskania elementów początkowego listy. Pierwszy element to a, 10 zamiast c, 30 - patrz wyjaśnienie poniżej.

Funkcja elementu end ()

Funkcja członka end () zwraca iterator, który wskazuje tuż po zakończeniu listy. Poniższy przykład ilustruje to dla zestawu:

ustawić setOBJ (6, 10, 2, 8, 4);
ustawić:: iterator iter = setOBJ.koniec();
Cout << *iter << '\n';

Zwróć uwagę na sposób, w jaki end () był używany z setOBJ i operatorem kropkowym. ITER to zwrócony obiekt iterator. Zwróć też uwagę na sposób, w jaki został zadeklarowany. * jest operatorem pośredniego; Zgodnie z ITER, zwraca ostatni element+1 zestawu. Na komputerze autora ten ostatni element+1 to 5, którego nie ma na liście. Uważaj więc, aby nie używać tego elementu.

Poniższy przykład ilustruje użycie funkcji end () dla mapy:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: iterator iter = mapobj.koniec();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Zwróć uwagę na sposób, w jaki end () został użyty z MAPOBJ i operatorem kropkowym. ITER to zwrócony obiekt iterator. Zwróć też uwagę na sposób, w jaki został zadeklarowany. * jest operatorem pośredniego; Zgodnie z ITER, zwraca ostatni element+1 mapy. Na komputerze autora ten ostatni element+1 to , 0, którego nie ma na liście. Uważaj więc, aby nie używać tego elementu.

Funkcja członka „end () const”

Funkcja członka „end () const” zwraca iterator, który wskazuje tuż po zakończeniu listy, gdy deklaracja zestawu zaczyna się od const (dla stałej). W tym stanie wartość na liście, o której mowa, zwrócona iterator, nie może zostać zmieniona przez iterator. Poniższy przykład ilustruje jego zastosowanie dla zestawu:

Const Set setOBJ (6, 10, 2, 8, 4);
ustawić:: const_iterator iter = setOBJ.koniec();
Cout << *iter << '\n';

Zwróć uwagę na sposób, w jaki end () był używany z setOBJ i operatorem kropkowym. Żadna „const” nie została wpisana tuż po zakończeniu (). Jednak „const” poprzedziło deklarację. ITER to zwrócony obiekt iterator. Zwróć też uwagę na sposób, w jaki został zadeklarowany. * jest operatorem pośredniego; Zgodnie z ITER, zwraca ostatni element+1 zestawu.

Poniższy przykład ilustruje użycie funkcji „end () const” dla mapy:

mapa const mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: const_iterator iter = mapobj.koniec();
Cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Zwróć uwagę na sposób, w jaki end () został użyty z MAPOBJ i operatorem kropkowym. Żadna „const” nie została wpisana tuż po zakończeniu (). Jednak „const” poprzedziło deklarację. ITER to zwrócony stały obiekt iterator, który różni się od normalnego iteratora. Ponadto uważnie obserwuj sposób, w jaki został zadeklarowany.

Dostęp do elementów do zestawu i mapy:

Ustawić

Z zestawem element jest odczytywany za pomocą operatora pośredniego. Pierwsze dwa elementy zestawu są odczytywane w poniższym przykładzie:

ustawić setOBJ (6, 10, 2, 8, 4);
ustawić:: iterator iter = setOBJ.zaczynać();
Cout << *iter << '\n';
++iter;
Cout << *iter << '\n';

Wyjście to 2, a następnie 4 - patrz wyjaśnienie poniżej. Aby wskazać następny element listy, iterator jest zwiększany.

UWAGA: Elementu nie można zmienić za pomocą operatora pośredniego dla zestawu. Na przykład „*iter = 9;” nie jest możliwe.

mapa

Mapa składa się z par kluczy/wartości. Wartość można odczytać za pomocą odpowiedniego klucza i zmienić za pomocą tego samego klucza. Poniższy segment kodu to ilustruje:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
Cout << mapObj['b'] << '\n';
mapobj ['b'] = 55;
Cout << mapObj['b'] << '\n';

Wyjście to:

20
55

Operator DOT nie był tutaj używany. Zamiast tego jest to operator Square Brackets, który przyjmuje klucz jako treść, która została użyta.

Kolejność elementów w zestawie lub mapie:

Elementy można wstawić do zestawu, w każdej kolejności. Jednak po włożeniu zestaw ustawia swoje elementy w kolejności rosnącej. Zamówienie rosnące to zamówienie domyślne. Jeśli potrzebne jest kolejność maleństwa, zestaw musi zostać zadeklarowany jak w poniższym przykładzie:

ustawić > setOBJ (6, 10, 2, 8, 4);

Tak więc po typu E.G., int, dla szablonu jest przecinek, a następnie „większy” w nawiasach kąta.

Elementy można włożyć do mapy w dowolnej kolejności. Jednak po włożeniu mapa zmienia swoje elementy w kolejności rosnącej według klucza (tylko), zachowując związek między każdym kluczem a jego wartością. Zamówienie rosnące jest zamówieniem domyślnym; Jeśli potrzebna jest kolejność maleństwa, mapa musi zostać zadeklarowana jak w poniższym przykładzie:

mapa > mapOBJ ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Więc po parach typu e.G., „Char, int”, dla szablonu jest przecinek, a następnie „większy” w nawiasach kątowych.

Przemierzanie zestawu

Pętla pobytu lub za pętla z iteratorem można użyć do przemierzania zestawu. Poniższy przykład używa pętli do przemierzania zestawu skonfigurowanego w kolejności malejącej:

ustawić > setOBJ (6, 10, 2, 8, 4);
dla (set:: iterator iter = setOBJ.zaczynać(); iter != setObj.koniec(); ++ ITER)

Cout << *iter << ";

Wyjście to:

10 8 6 4 2

Zwiększanie iteratora wskazuje go na następny element.

Przemierzanie mapy

While pętli lub na pętli z iteratorem można użyć do przemierzania mapy. Poniższy przykład wykorzystuje pętlę do przemierzania mapy skonfigurowanej w kolejności malejącej:

mapa > mapOBJ ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
dla (mapa:: iterator iter = mapobj.zaczynać(); iter != MapOBJ.koniec(); ++ ITER)

Cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

Wyjście to:

e, 40, d, 30, c, 30, b, 20, a, 10,

Zwiększanie iteratora wskazuje go na następny element. „Po pierwsze” w kodzie odnosi się do klucza, a „drugi” odnosi się do odpowiedniej wartości. Zwróć uwagę, w jaki sposób te wartości zostały uzyskane dla wyjścia.

Inne powszechnie używane funkcje członków:

Funkcja rozmiaru ()

Ta funkcja zwraca liczbę całkowitą, która jest liczbą elementów na liście. Zestaw przykład:

ustawić > setOBJ (6, 10, 2, 8, 4);
Cout << setObj.size() << '\n';

Wyjście to 5.

Przykład mapy:

mapa > mapOBJ ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
Cout << mapObj.size() << '\n';

Wyjście to 5.

Funkcja insert ()

ustawić

zestaw nie pozwala na duplikat. Tak więc każdy zduplikowany włożony jest cicho odrzucony. Z zestawem argumentem funkcji insert () jest wartość, którą należy wstawiać. Wartość jest zamontowana w pozycji, w której kolejność w zestawie pozostaje wznosząca się lub zstępuje. Przykład:

ustawić setOBJ (6, 10, 2, 8, 4);
setObj.wstaw (6);
setObj.wstaw (9);
setObj.wstaw (12);
dla (set:: iterator iter = setOBJ.zaczynać(); iter != setObj.koniec(); ++ ITER)

Cout << *iter << ";

Wyjście to:

2 4 6 8 9 10 12

Uwaga: Do wypełnienia pustego zestawu można użyć funkcji Insert ().

mapa

Mapa nie pozwala na duplikat według klucza. Tak więc każdy zduplikowany włożony jest cicho odrzucony. Z mapą argumentem funkcji insert () jest para klucza/wartości w aparat ortodontyczny. Element jest zamontowany w pozycji według klucza, w którym kolejność na mapie pozostaje wznosząca się lub zstępuje. Przykład:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
Mapobj.insert ('e', 80);
Mapobj.insert ('f', 50);
Mapobj.insert ('g', 60);
dla (mapa:: iterator iter = mapobj.zaczynać(); iter != MapOBJ.koniec(); ++ ITER)
Cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

Wyjście to:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

Uwaga: Funkcja elementu Insert () może być użyta do wypełnienia pustej mapy.

Funkcja pustej ()

Ta funkcja zwraca true, jeśli lista jest pusta i fałszywa, jeśli inaczej. Zestaw przykład:

ustawić setOBJ (6, 10, 2, 8, 4);
bool ret = setObj.pusty();
Cout << ret << '\n';

Wyjście to 0 dla fałszywych, co oznacza, że ​​zestaw tutaj nie jest pusty.

Przykład mapy:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
bool ret = mapobj.pusty();
Cout << ret << '\n';

Wyjście to 0 dla fałszywych, co oznacza, że ​​mapa tutaj nie jest pusta.

Funkcja Erase ()

ustawić

Rozważ następujący segment kodu:

ustawić setOBJ (10, 20, 30, 40, 50);
ustawić:: iterator iter = setOBJ.zaczynać();
ustawić:: iterator ITR = setOBJ.usunąć (itera);
Cout << "new size: " << setObj.size() << '\n';
Cout << "next value: " << *itr << '\n';
ITr = setObj.usunąć (ITR);
Cout << "new size: " << setObj.size() << '\n';
Cout << "next value: " << *itr << '\n';

Wyjście to:

Nowy rozmiar: 4
Następna wartość: 20
Nowy rozmiar: 3
Następna wartość: 30

Funkcja Erase () bierze iterator, który wskazuje na element jako argument. Po wymazaniu elementu funkcja Erase () zwraca iterator, który wskazuje następny element.

mapa

Rozważ następujący segment kodu:

mapa mapobj ('a', 10, 'b', 20, 'c', 30, 'd', 40, 'e', 50);
mapa:: iterator iter = mapobj.zaczynać();
mapa:: iterator ITR = mapobj.usunąć (itera);
Cout << "new size: " << mapObj.size() << '\n';
Cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
ITR = MAPOBJ.usunąć (ITR);
Cout << "new size: " << mapObj.size() << '\n';
Cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

Wyjście to:

Nowy rozmiar: 4
Następna para wartości: b, 20
Nowy rozmiar: 3
Następna para wartości: C, 30

Funkcja Erase () bierze iterator, który wskazuje na element jako argument. Po wymazaniu elementu funkcja Erase () zwraca iterator, który wskazuje następny element.

Funkcja Clear ()

Funkcja Clear () usuwa wszystkie elementy na liście. Zestaw przykład:

ustawić setOBJ (6, 10, 2, 8, 4);
setObj.jasne();
Cout << setObj.size() << '\n';

Wyjście to 0.

Przykład mapy:

mapa mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
Mapobj.jasne();
Cout << mapObj.size() << '\n';

Wyjście to 0.

Wniosek:

Ustawiona struktura danych w C ++ to struktura, w której lista elementów jest domyślnie przechowywana w kolejności rosnącej lub w kolejności malejącej według wyboru programisty. Wszystkie elementy zestawu są wyjątkowe. Struktura danych map w C ++ to struktura, w której lista jest skrótem par klucza/wartości, przechowywanej domyślnie w kolejności rosnącej lub w kolejności malejącej klawiszy według wyboru programisty. Klucze są również wyjątkowe i mogą być zduplikowane wartości. Głównym członkiem danych jednej ze struktur jest lista. Każda ze struktur ma funkcje członków, z których niektóre są powszechnie używane.