Wstecz: 24. Biblioteka standardowa W górę: 24. Biblioteka standardowa Dalej: 24.2 Algorytmy i obiekty funkcyjne

---

• 24.1.1 Wektory
• 24.1.2 Iteratory
• 24.1.3 Operacje na kolekcjach

24.1 Kolekcje i iteratory

Podstawowym udogodnieniem dostarczanym przez bibliotekę standardową są kolekcje. Kolekcja jest strukturą danych złożoną z danych pewnego typu i wyposażoną w zestaw operacji, jakie na tych danych można wykonywać. Może to być dodawanie elementów, ich usuwanie, wyszukiwanie, porównywanie, kopiowanie, porządkowanie itd. W bibliotece standardowej zaimplementowano takie podstawowe struktury danych, jak listy, stos, kolejki, kopce, tablice asocjacyjne (słowniki), zbiory; korzystając z nich użytkownik może łatwo i efektywnie tworzyć własne, bardziej złożone struktury, jak choćby różnego typu drzewa czy grafy.

24.1.1 Wektory

Najprostsza kolekcja opisywana jest szablonem vector dołączanym poprzez włączenie nagłówka vector. Modelem wektora jest tablica elementów tego samego typu, ale o nieokreślonej zawczasu pojemności. Elementy są umieszczane w dobrze zdefiniowanym porządku i mamy do nich dostęp swobodny, to znaczy znając pozycję (indeks) elementu możemy pobrać jego wartość lub go zmienić czy usunąć bez konieczności przeglądania wszystkich elementów wektora. Elementy możemy dodawać na dowolnej pozycji, choć najefektywniejsze (w stałym, niezależnym od rozmiaru wektora, czasie) jest dodawanie na koniec. W miarę jak elementów przybywa, wektorowi przydzielana jest automatycznie większa pamięć — programista nie musi się już martwić zarządzaniem pamięcią, jej przydzielaniem i zwalnianiem. Ponieważ vector jest szablonem klasy, a nie klasą, obiekty-wektory możemy tworzyć konkretyzując wzorzec dla pewnego typu — może to być również typ wbudowany, jak int czy double. Domyślny konstruktor tworzy wektor pusty (są też inne konstruktory). Do utworzonego wektora dodajemy elementy (takiego typu, jak ten dla którego wzorzec został skonkretyzowany) za pomocą metody push_back, która dodaje kopię obiektu na końcu wektora. Kopię, a zatem trzeba zadbać, aby obiekt był dobrze „kopiowalny”, a więc na przykład miał prawidłowo zdefiniowany konstruktor kopiujący.

Elementy można pobierać na różne sposoby. Najprościej to zrobić za pomocą indeksowania: robimy to dokładnie tak jak dla normalnej tablicy (pierwszy element ma, jak zwykle, indeks zero). Taki sposób jest bardzo efektywny, ale nie jest sprawdzane, czy użyty indeks jest legalny (tak jak nie jest to sprawdzane w przypadku normalnych tablic). Jeśli chcemy, aby zostało sprawdzone, czy indeks mieści się w dozwolonym zakresie, czyli od zera do liczby o jeden mniejszej niż aktualny rozmiar wektora, to można użyć metody at podając indeks jako argument. Przy tej metodzie dostępu zgłaszany jest wyjątek out_of_range (z nagłówka stdexcept), gdy indeks jest nielegalny. Wyjątek ten możemy obsłużyć:

      1.  #include <vector>
      2.  #include <stdexcept>
      3.  #include <iostream>
      4.  #include <string>
      5.  using namespace std;
      6.  
      7.  int main() {
      8.      vector<string> vs;
      9.  
     10.      vs.push_back("Ola");
     11.      vs.push_back("Ula");
     12.      vs.push_back("Ela");
     13.      vs.push_back("Ala");
     14.  
     15.      try {
     16.          for ( int i = 0; i < 5 /* BLAD */; i++ )
     17.              cout << vs.at(i) << " " ;
     18.      } catch(out_of_range) {
     19.          cout << "\n*** Zly indeks! *** "
     20.               << " wektor ma tylko " << vs.size()
     21.               << " elementy!" << endl;
     22.      }
     23.      cout << endl;
     24.  
     25.      cout << "Pierwszy element: " << vs.front() << endl;
     26.      cout << "Ostatni  element: " << vs.back()  << endl;
     27.  
     28.      vs.pop_back();
     29.  
     30.      cout << "Po pop_back: ";
     31.      int size = (int)vs.size();
     32.      for ( int i = 0; i < size; i++)
     33.          cout << vs[i] << " " ;
     34.      cout << endl;
     35.  }

    Ola Ula Ela Ala
    *** Zly indeks! ***  wektor ma tylko 4 elementy!

    Pierwszy element: Ola
    Ostatni  element: Ala
    Po pop_back: Ola Ula Ela

Kolekcja jest zatem kolekcją elementów, z których każdy jest obiektem klasy string. Metoda size, użyta w linii 31 zwraca, jak łatwo się domyślić, rozmiar kolekcji (nie tylko wektorów). Typem zwracanym jest pewien typ całowity bez znaku, którego aliasem jest nazwa vector::size_type — dlatego użyliśmy rzutowania — można tu było użyć zwykłego int'a, ale narazilibyśmy się na ostrzeżenia kompilatora. Metoda pop_back (linia 28) usuwa ostatni element kolekcji, ale go nie zwraca. Metody front i  back (linie 25 i 26) zwracają, przez referencję, pierwszy i ostatni element kolekcji bez ich usuwania.

24.1.2 Iteratory

Podstawowym narzędziem do wykonywania operacji na kolekcjach są iteratory. Pozwalają one poruszać się po elementach kolekcji w sposób niezależny od ich rzeczywistego typu. Są swego rodzaju uogólnieniem wskaźników. Ich typ jest zdefiniowany w definicji wzorca szablonu kolekcji za pomocą instrukcji typedef i ma postać kol<Typ>::iterator, gdzie kol jest nazwą szablonu kolekcji, a  Typ jest typem użytym do skonkretyzowania tego szablonu. Użytkownik nie musi wiedzieć, jaki naprawdę ten typ jest. Na przykład nazwą (aliasem) typu iteratora związanego z wektorem liczb typu int jest vector<int>::iterator. Kolekcja może być kolekcją elementów niemodyfikowalnych; dla każdej kolekcji zatem jest też zdefiniowany osobny typ const_iterator (na przykład vector<int>::const_iterator).

Iteratory mają semantykę wskaźników do elementów tablicy, to znaczy, jeśli it jest iteratorem wskazującym na pewien element kolekcji, to *it jest l-wartością wskazywanego elementu, a it->sklad jest nazwą składowej sklad wskazywanego przez iterator obiektu (jeśli taka składowa istnieje). Podobnie, po ' ++it' iterator it wskazuje na następny element kolekcji.

Istnieją w klasach kolekcyjnych dwie ważne bezargumentowe metody zwracające iteratory: metoda begin i  end. Metoda begin zwraca iterator wskazujący na pierwszy element kolekcji. Nieco bardziej skomplikowany jest wynik metody end. Nie jest to iterator wskazujący na ostatni element kolekcji, jak by się mogło wydawać, ale na nieistniejący element „tuż za ostatnim”. Jeśli przebiegamy kolekcję za pomocą iteratora, to osiągnięcie przez niego wartości zwracanej przez end oznacza, że przebiegliśmy już całą kolekcję. Zamiast więc sprawdzać, jak zwykle w pętlach przebiegających tablice, czy indeks jest mniejszy od wymiaru tablicy, sprawdzamy, czy iterator wciąż nie jest równy iteratorowi zwracanemu przez metodę end; jeśli jest, to pętlę należy przerwać, bo iterator wskazuje na element nieistniejący:

      1.  #include <vector>
      2.  #include <iostream>
      3.  #include <string>
      4.  using namespace std;
      5.  
      6.  int main() {
      7.      vector<string> vs;
      8.  
      9.      vs.push_back("Ola");
     10.      vs.push_back("Ula");
     11.      vs.push_back("Ela");
     12.      vs.push_back("Ala");
     13.  
     14.      for ( vector<string>::iterator ite = vs.begin();
     15.                                     ite!= vs.end(); ++ite)
     16.          cout << *ite << " ";
     17.      cout << endl;
     18.  
     19.      // albo
     20.  
     21.      vector<string>::iterator it, kon = vs.end();
     22.  
     23.      for ( it = vs.begin(); it != kon; ++it )
     24.          cout << *it << " ";
     25.      cout << endl;
     26.  
     27.      // albo
     28.  
     29.      typedef vector<string>::iterator SIT;
     30.  
     31.      SIT iter, koniec = vs.end();
     32.  
     33.      for ( iter = vs.begin(); iter != koniec; ++iter )
     34.          cout << *iter << " ";
     35.      cout << endl;
     36.  }

Jeśli kolekcja jest niemodyfikowalna, to nie tylko możemy, ale musimy użyć iteratora typu const_iterator. Z taką sytuacją spotykamy się bardzo często, gdy przesyłamy kolekcję jako argument funkcji, która z założenia nie powinna elementów tej kolekcji zmieniać, a wobec tego jej parametr jest typu ustalonego:

      1.  #include <vector>
      2.  #include <iostream>
      3.  using namespace std;
      4.  
      5.  struct Person {
      6.      char name[20];
      7.      int  year;
      8.      void print() const {
      9.          cout << name << "-" << year << endl;
     10.      }
     11.  } john = {"John",25}, mary = {"Mary",18}, sue = {"Sue",9};
     12.  
     13.  
     14.  void printPerson(const vector<const Person*>& list) {
     15.      typedef vector<const Person*>::const_iterator IT;
     16.      IT itend = list.end();
     17.      for ( IT it = list.begin(); it != itend; it++ )
     18.          (*it)->print();
     19.  }
     20.  
     21.  int main() {
     22.      vector<const Person*> list;
     23.  
     24.      list.push_back(&john);
     25.      list.push_back(&mary);
     26.      list.push_back(&sue);
     27.  
     28.      printPerson(list);
     29.  }

       vector<const Person*>

Zauważmy jeszcze, że parametr funkcji printPerson jest typu referencyjnego. Jest to zwykle pożądane przy przesyłaniu do funkcji kolekcji — w przeciwnym przypadku kopiowane byłyby całe kolekcje, wraz ze wszystkimi elementami. Tego problemu nie było przy przesyłaniu tablic, kiedy tak naprawdę przesyłany był tylko wskaźnik do pierwszego elementu.

Prócz iteratorów iterator i  const_iterator istnieje typ iteratora odwrotnego reverse_iterator, za pomocą którego można przebiegać kolekcje w odwrotnym kierunku; na przykład program

      1.  #include <vector>
      2.  #include <iostream>
      3.  #include <string>
      4.  using namespace std;
      5.  
      6.  int main() {
      7.      vector<string> vs;
      8.  
      9.      vs.push_back("Ola");
     10.      vs.push_back("Ula");
     11.      vs.push_back("Ela");
     12.      vs.push_back("Ala");
     13.  
     14.      typedef vector<string>::iterator         DO_PRZODU;
     15.      typedef vector<string>::reverse_iterator DO_TYLU;
     16.  
     17.      DO_PRZODU piter, pkoniec = vs.end();
     18.      DO_TYLU   titer, tkoniec = vs.rend();
     19.  
     20.      for ( piter = vs.begin(); piter != pkoniec; piter++ )
     21.          cout << *piter << " ";
     22.      cout << endl;
     23.  
     24.      for ( titer = vs.rbegin(); titer != tkoniec; titer++ )
     25.          cout << *titer << " ";
     26.      cout << endl;
     27.  }

    Ola Ula Ela Ala
    Ala Ela Ula Ola

Ze względu na swoją funkcjonalność iteratory dzielą się na kilka kategorii. Z różnymi kolekcjami związane są różne kategorie iteratorów.

Na przykład iterator związany z wektorem (vector) pozwala nie tylko na przesuwanie się w obu kierunkach za pomocą operatorów zwiększania i zmniejszania, ale na stosowanie arytmetyki wskaźników, to znaczy np. dodanie liczby 3 do takiego iteratora daje iterator przesunięty o trzy elementy do przodu względem wyjściowego. Podobnie, po

       vector<string> vs;
       // ...
       vector<string>::iterator it = vs.begin() + vs.size()/2;

Drugim typem iteratora jest iterator dwukierunkowy (ang. bidirectional iterator). Pozwala na poruszanie się po kolekcji w obu kierunkach za pomocą operatorów zwiększania i zmniejszania ('++' i '- -'), ale nie wspiera arytmetyki wskaźników, na przykład dodawania liczb całkowitych do iteratora. Takie itertory można porównywać za pomocą ' ==' i ' !=', ale nie za pomocą ' <' i ' >'. Są one związane na przykład z kolekcjami listowymi (list, z nagłówka list).

Jeszcze bardziej ograniczona jest funkcjonalność iteratorów jednokierunkowych (ang. forward iterator). Są one podobne do dwukierunkowych, ale pozwalają na poruszanie się tylko w jednym kierunku: do przodu.

W końcu najbardziej ograniczone są możliwości iteratorów wejściowych i wyjściowych (ang. input i output iterator). Pozwalają one tylko na jednokrotny przebieg (ang. single pass) kolekcji w kierunku do przodu. Iteratory wejściowe pozwalają tylko na odczyt elementu wskazywanego, a wyjściowe tylko na przypisanie im wartości, ale nie odczyt. Takie iteratory związane są zwykle ze strumieniami (wejściowymi i wyjściowymi).

Iteratory są podstawowym elementem stosowanym w algorytmach i funkcjach operujących na kolekcjach. Pełnią one rolę łącznika między algorytmami i funkcjami a strukturami danych, jakimi są kolekcje.

24.1.3 Operacje na kolekcjach

Na kolekcjach można wykonywać wiele operacji, choć należy pamiętać, że nie każdą z nich można wykonać na każdej kolekcji. Związane jest to z kwestią wydajności: niektóre kolekcje dopuszczają mniej operacji, ale za to są one wykonywane bardzo efektywnie. Na przykład, jak wspominaliśmy, różnica dwóch iteratorów odnoszących się do wektora daje liczbę elementów pomiędzy nimi — ponieważ w wektorze elementy są rozmieszczone w pamięci jeden przy drugim i rozmiar ich jest znany, jest to operacja bardzo szybka, sprowadzająca się do jednego odejmowania i jednego dzielenia. Dla listy (list) nie jest to takie proste, więc aby osiągnąć ten sam cel, należy użyć specjalnej funkcji distance o liniowym (a więc proporcjonalnym do rozmiaru listy) czasie działania:

      1.  #include <iostream>
      2.  #include <vector>
      3.  #include <string>
      4.  #include <list>
      5.  using namespace std;
      6.  
      7.  int main() {
      8.      vector<string> vec;
      9.  
     10.  #if   defined(__WIN32)
     11.      cout << "Lista slow (^Z konczy): ";
     12.  #elif defined(__linux)
     13.      cout << "Lista slow (^D konczy): ";
     14.  #else
     15.      #error Nieznany system
     16.  #endif
     17.  
     18.      string s;
     19.      while ( cin >> s ) vec.push_back(s);
     20.      cin.clear();
     21.  
     22.      list<string> lis(vec.begin(),vec.end());
     23.  
     24.      cout << "Slowo do znalezienia: ";
     25.      cin  >> s;
     26.  
     27.      vector<string>::iterator sit;
     28.      list<string>::iterator   lit;
     29.  
     30.        // wektor
     31.      for (sit = vec.begin(); sit != vec.end(); ++sit)
     32.          if ( *sit == s ) break;
     33.      if ( sit != vec.end() )
     34.          cout << "Slowo " << s << " na pozycji "
     35.               << sit - vec.begin() << endl;
     36.      else
     37.          cout << "Slowo " << s << " nie wystapilo" << endl;
     38.  
     39.        // lista
     40.      for (lit = lis.begin(); lit != lis.end(); ++lit)
     41.          if ( *lit == s ) break;
     42.      if ( lit != lis.end() )
     43.          cout << "Slowo " << s << " na pozycji "
     44.               << distance(lis.begin(),lit) << endl;
     45.      else
     46.          cout << "Slowo " << s << " nie wystapilo" << endl;
     47.  }

    Lista slow (^D konczy): Ala
    Ela
    Ola
    Ula
    ^D
    Slowo do znalezienia: Ola
    Slowo Ola na pozycji 2
    Slowo Ola na pozycji 2

Zwykła tablica może być traktowana jak kolekcja. Wskaźniki do elementów tablicy pełnią wtedy rolę iteratorów. Na przykład po

       int arr[] = {1,4,6,8,9};
       vector<int> v(arr+1,arr+4);

Jak wspomnieliśmy, kolekcją (znaków) jest obiekt klasy string. Kilka przykładów ilustrujących tę cechę napisów w stylu C++ podaliśmy już w rozdziale o napisach .

Inną, często stosowaną operacją jest usuwanie elementów kolekcji. Służy do tego metoda erase. Jej argumentem powinien być iterator wskazujący na usuwany element albo para iteratorów; w tym drugim przypadku usuwane są elementy od wskazywanego pierwszym iteratorem włącznie do wskazywanego drugim iteratorem wyłącznie. Na przykład po

       vector<Person> os;

       os.push_back(Person("Jenny"));
       os.push_back(Person("Jill"));
       os.push_back(Person("Jane"));
       os.push_back(Person("Janet"));

       os.erase(os.begin()+1, os.end());

Podobnie można do kolekcji dodawać nowe elementy za pomocą metody insert. Argumentem wskazującym, na której pozycji (a ściślej, przed którym elementem) nowe elementy powinny się pojawić, jest oczywiście iterator. Z kolei elementy do wstawienia mogą pochodzić z innej kolekcji; ich zakres wskazywany jest parą iteratorów:

       double tab[] = {2, 4, 6, 7, 8, 1.5, 5, 7};
       list<double> lis(5);
       lis.insert(lis.begin(),10.5);
       lis.insert(lis.begin(),tab+1,tab+3);

    4 6 10.5 0 0 0 0 0

---

Wstecz: 24. Biblioteka standardowa W górę: 24. Biblioteka standardowa Dalej: 24.2 Algorytmy i obiekty funkcyjne