C++/Set

Z Wikibooks, biblioteki wolnych podręczników.

Spis treści 1 Opis 2 Parametry 3 Prosty Przykład 4 Składniki

[edytuj] Opis

Zbiory są jednym z kontenerów biblioteki STL, których struktura oparta jest na drzewach. Elementy które są w nich przechowywane są posortowane, według pewnego klucza. Zarówno typ wartosci tych elementów jak i typ wartości klucza są takie same. Drzewiasta struktura zapewnia szybkie wyszukiwanie, jednak są z tym związane także pewne mankamenty, mianowicie modyfikacja elementu jest możliwa tylko w taki sposób, że kasujemy stary element, a następnie wstawiamy w to miejsce nowy. Korzystając z terminologii STL-a zbiory sa tzw. kontenerami asocjacyjnymi (o zmiennej długości, pozwalającymi na operowanie elementami przy użyciu kluczy):

	Rodzaj kontenera	Opis
1	prostymi	key_type i value_type są tego samego typu
2	posortowanymi	rosnąco względem klucza
3	unikalnymi	w danym zbiorze nie mogą wsytępowac dwa elementy o tym samym kluczu

[edytuj] Parametry

Parametr	Opis
Key	Klucz zbioru ten sam co typ wartości. Zdefiniowane także jako: set::key_type i set::value_type
Compare	Funkcja porównująca klucze, według słabo rosnącego porządku którego argumenty są typu key_type; zwraca true jeśli pierwszy argument jest wcześniejszy od drugiego, w przeciwnym razie zwraca false. Zdefiniowana także jako: set::key_compare i set::value_compare.
Alloc	Alokator zbioru, używany do wewnętrznego zarządzania pamięcią.

[edytuj] Prosty Przykład

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main()
{
  set<string> mapa;  //deklaracja zbioru mapa
  mapa.insert("lublin");
  mapa.insert("lodz");
  mapa.insert("warszawa");
  mapa.insert("krakow"); //dodawanie elem
  set<string>::iterator marker = mapa.find("warszawa"); //szuka elementu "warszawa"
  if (marker!=mapa.end())
  {
    cout<<"znalazlem! "<<*marker<<endl;
  }
  for (marker=mapa.begin(); marker!=mapa.end(); marker++)
  cout << *marker << endl;
  system("pause");
  return 0;
}

[edytuj] Składniki

Składnik	Opis działania
value_type	Typ obiektu, T, przechowywany w zbiorze(secie).
key_type	Typ klucza zbioru, powiązany z value_type.
key_compare	Funkcjonał porównujący dwa klucze w celu uporządkowania.
value_compare	Funkcjonał porównujący dwie wartości w celu uporządkowania.
pointer	Wskaźnik na T.
reference	Referencja do T.
const_reference	Stała referencja do T.
size_type	Integralny typ bez znaku.
difference_type	Integralny typ ze znaku.
iterator	Iterator używany do 'chodzenia' po zbiorze.
const_iterator	Stały iterator używany do 'chodzenia'(iteracji) po zbiorze(tego samego typu co zwykły iterator).
reverse_iterator	Iterator używany do 'chodzenia do tyłu'(iteracji wstecznej) po zbiorze.
const_reverse_iterator	Stały iterator używany do 'chodzenia do tyłu'(iteracji wstecznej) po zbiorze.
iterator begin()	Zwraca iterator wskazujący na początek zbioru.
iterator end()	Zwraca iterator wskazujący na koniec zbioru.
reverse_iterator rbegin()	Zwraca reverse_iterator wskazujący na początek odwróconego zbioru.
reverse_iterator rend()	Zwraca reverse_iterator wskazujący na koniec odwróconego zbioru.
size_type size()	Zwraca rozmiar zbioru.
size_type max_size()	Zwraca największy możliwy rozmiar zbioru.
bool empty()	Zwraca true gdy rozmiar zbioru wynosi 0.
key_compare key_comp()	Zwraca key_compare obiektu używanego przez zbiór.
value_compare value_comp()	Zwraca value_compare obiektu używanego przez zbiór.
set()	Tworzy pusty zbiór.
set(const key_compare& comp)	Tworzy pusty zbiór, używając comp jako key_compare obiektu(klucza porównującego).
template <class InputIterator> set(InputIterator f, InputIterator l)	Tworzy zbiór zawierający kopie zakresu.
template <class InputIterator> set(InputIterator f, InputIterator l, const key_compare& comp)	Tworzy zbiór zawierający kopie zakresu, używając comp jako key_compare obiektu.
set(const set&)	Konstruktor kopiujący.
set& operator=(const set&)	Operator przypisania.
void swap(set&)	Zamienia zawartość dwóch zbiorów.
pair<iterator, bool> insert(const value_type& x)	Wstawia do zbioru element x.
iterator insert(iterator pos, const value_type& x)	Wstawia do zbioru element x. Używa pos do wskazania miejsca, w którym ma być wstawiony.
template <class InputIterator> void insert(InputIterator, InputIterator)	Wstawia do zbioru zakres.
void erase(iterator pos)	Kasuje element wskazywany przez pos.
size_type erase(const key_type& k)	Kasuje element którego kluczem jest k.
void erase(iterator first, iterator last)	Kasuje wszystkie elementy z danego zakresu.
void clear()	Kasuje wszystkie elementy zbioru.
iterator find(const key_type& k) const	Znajduje element, którego klucz wynosi k.
size_type count(const key_type& k) const	Zwraca liczbę elementów, których klucz wynosi k.
iterator lower_bound(const key_type& k) const	Znajduje pierwszy element, którego klucz jest nie mniejszy od k.
iterator upper_bound(const key_type& k) const	Znajduje pierwszy element, którego klucz jest większy od k.
pair<iterator, iterator> equal_range(const key_type& k) const	Znajduje zakres zawierający wszystkie elementy o kluczu k.
bool operator==(const set&, const set&)	Sprawdza dwa zbiory pod względem równości. Jest to funkcja globalna, nie składnikowa.
bool operator<(const set&,const set&)	Porównanie leksykograficzne. Jest to funkcja globalna, nie składnikowa.