====== Kolekcje i algorytmy  ======

===== STL - Standard Template Library  =====

  * [[http://www.sgi.com/tech/stl/|Standard Template Library Programmer's Guide]]
  * [[http://www.cplusplus.com/reference/stl/|STL Containers]]
  * [[http://www.cplusplus.com/reference/algorithm/|STL Algorithms]]

==== Przykład: vector i losowanie lotto ====

<code C++>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
   vector<int> w;
   vector<int>::iterator it;

   for(int i=1;i<=49;i++) w.push_back(i); 

   cout << "Zawartosc wektora\n";
   for(it=w.begin();it!=w.end();it++) cout << *it << " ";
   cout << endl;

   cout << "Size=" << w.size() << " Capacity=" << w.capacity() << endl;

   srand(time(NULL));

   cout << "Random shuffle (numery lotto)\n";

   random_shuffle(w.begin(),w.end());
   for(it=w.begin();it!=w.begin()+6;it++) cout << *it << " ";
   cout << endl;
}
</code>

==== Przykład: map i liczenie słów (słownik) ====

<code C++>
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
       string w;

       map<string,int> slownik;
       map<string,int>::iterator it;
       
       while(cin >> w) slownik[w]++;

       for(it=slownik.begin(); it!=slownik.end(); it++)
          cout << (*it).first << " " <<  (*it).second << endl;
}
</code>


===== Collections  =====

  * [[http://msdn.microsoft.com/en-us/library/system.collections%28v=vs.110%29|System.Collections]] 
    * [[http://msdn.microsoft.com/en-us/library/system.collections.arraylist%28v=vs.110%29.aspx|ArrayList]]
    * [[http://msdn.microsoft.com/en-us/library/system.array%28v=vs.110%29.aspx|Array]] - algorytmy do manipulacji tablicami
  * [[http://msdn.microsoft.com/en-us/library/system.collections.generic%28v=vs.110%29.aspx|System.Collections.Generic]], m.in.:
    * [[http://msdn.microsoft.com/en-us/library/6sh2ey19%28v=vs.110%29.aspx|List]]
    * [[http://msdn.microsoft.com/en-us/library/xfhwa508%28v=vs.110%29.aspx|Dictionary]]
    * [[http://msdn.microsoft.com/en-us/library/f7fta44c%28v=vs.110%29.aspx|SortedDictionary]]

==== Przykład: Lista - losowanie Lotto ====

<code C#>
using System;
using System.Collections.Generic;

namespace Lotto
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> lista = new List<int>();
            for (int i = 1; i <= 49; i++) lista.Add(i);
            Console.WriteLine("Zawartośc kolekcji");
            foreach (int i in lista) Console.Write("{0} ", i);
            
            Console.WriteLine("\n\nSize={0} Capacity={1}", lista.Count, lista.Capacity);

            Console.Write("Losowanie Lotto: ");
            Shuffle<int>(lista);

            for (int i = 0; i < 6; i++) Console.Write("{0} ", lista[i]);
            Console.WriteLine();

            lista.Sort();
        }

        public static void Shuffle<T>(List<T> sequence)
        {            
            Random random = new Random();
            for (int i = 0; i < sequence.Count; i += 1)
            {
                int swapIndex = random.Next(sequence.Count);
                if (swapIndex != i)
                {
                    T tmp = sequence[i];
                    sequence[i] = sequence[swapIndex];
                    sequence[swapIndex] = tmp;
                }
            }
        }
    }
}
</code>

==== Przykład: Dictionary (słownik) ====

<code C#>
using System;
using System.Collections.Generic;

namespace Dictionary
{
    class Program
    {
        static void Main(string[] args)
        {
            string line;
            SortedDictionary<string, int> slownik = new SortedDictionary<string, int>();

            while ((line = Console.ReadLine()) != null)
            {
                if (!slownik.ContainsKey(line)) slownik.Add(line,1);
                else slownik[line]++;
            }

            foreach (KeyValuePair<string, int> kvp in slownik)
                Console.WriteLine("{0} {1}", kvp.Key, kvp.Value);
        }
    }
}

</code>


====== Ćwiczenia ======

===== Algorytmy STL =====

Do wykonania tego zadania szablon klasy Wektor powinien posiadać zaimplementowany iterator o swobodnym dostępie oraz metody begin i end() zgodnie z [[csharp_dziedziczenie#Iterator|treścią jednego z poprzednich zadań]].

[[http://www.cplusplus.com/reference/algorithm/|Algorytmy STL]]\\

Przetestuj działanie algorytmów **sort()**, **reverse()**, **fill()**, **rotate()**, **replace()**, **random_shuffle**, **min_element()** na kolekcji **Wektor**.
  - utwórz wektor i wypełnij go liczbami całkowitymi od 1 do 100
  - wymieszaj zawartość całego wektora za pomocą algorytmu **random_shuffle** i wyświetl rezultat
  - posortuj elementy wektora i wyświetl rezultat
  - odwróć kolejność pierwszej połowy elementów wektora
  - wypełnij 20 ostatnich wartości zawartych w wektorze wartością -1 za pomocą algorytmu ''**fill**''
  - przesuń cyklicznie wszystkie elementy wektora o jedną pozycję w tył tak aby drugi element był pierwszym, trzeci drugim itd.
  - znajdź najmniejszy element
  - znajdź liczbę wszystkich liczb parzystych w wektorze za pomocą algorytmu ''**count_if**''. Warunek do sprawdzenia przekaż jako wskaźnik do odpowiedniej funkcji.
  - zamień wszystkie elementy wektora mniejsze od 50 na wartość 0 za pomocą algorytmu ''**replace_if**''. Warunek do sprawdzania przekaż za pomoca obiektu funkcyjnego (obiektu przeciążającego operator()).


===== Klasa Wyraz =====

Zaimplementuj klasę ''**Wyraz**'' służącą do obsługi łańcuchów znaków składających się wyłącznie z liter. \\
Klasa ''**Wyraz**'':
  * dziedziczy po klasie ''**Wektor<char>**''
  * przeciąża operator << wrzucający przechowywany wyraz do strumienia wyjściowego
  * przeciąża operator >> czytający ze strumienia wejściowego dokładnie jeden wyraz lub zwraca pusty łańcuch jeśli nastąpił błąd odczytu (np. koniec pliku). Pamiętaj, że wyrazy mogą być oddzielone od siebie dowolną ilością znaków nie będących literami. Przy wczytywaniu napisu należy zignorowac więc wszystkie znaki aż do momentu pojawienia się litery zaczynającej wyraz. 
  * przeciąża operator < porównujący dwa wyrazy. Przy porównywaniu małe i duże litery traktujemy równoważne, wiec wyraz "Ala", "ala" i "ALA" są identyczne.
  * konstruktor domyślny tworzy pusty łańcuch znakowy
  * konstruktor kopiujący 

Przykład działania:

<code c++>

Wyraz w;
while(!cin.eof())
{
   cin >> w;
   cout << w << endl;
}

</code>


Przydatne funkcje:
  * z biblioteki C ''string.h'' : ''isapha'', ''tolower'', ''toupper'', ''strcmp''
  * z ''iostream.h'' : ''get(char z)'', ''put(char z)'', ''eof()''

===== Słownik (kolekcja Map) =====

Wykorzystaj kolekcję **Map** oraz klasę **Wyraz** do stworzenia słownika zgodnie z treścią [[csharp_dziedziczenie#Słownik|zadania z pierwszych zajęć]].