Kolekcje i algorytmy

STL - Standard Template Library

• Standard Template Library Programmer's Guide
• STL Containers
• STL Algorithms

Przykład: vector i losowanie lotto

#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;
}

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

#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;
}

Collections

• System.Collections
  • ArrayList
  • Array - algorytmy do manipulacji tablicami
• System.Collections.Generic, m.in.:
  • List
  • Dictionary
  • SortedDictionary

Przykład: Lista - losowanie Lotto

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;
                }
            }
        }
    }
}

Przykład: Dictionary (słownik)

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);
        }
    }
}

Ć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 treścią jednego z poprzednich zadań.

Algorytmy STL

Przetestuj działanie algorytmów sort(), reverse(), fill(), rotate(), replace(), random_shuffle, min_element() na kolekcji Wektor.

1. utwórz wektor i wypełnij go liczbami całkowitymi od 1 do 100
2. wymieszaj zawartość całego wektora za pomocą algorytmu random_shuffle i wyświetl rezultat
3. posortuj elementy wektora i wyświetl rezultat
4. odwróć kolejność pierwszej połowy elementów wektora
5. wypełnij 20 ostatnich wartości zawartych w wektorze wartością -1 za pomocą algorytmu fill
6. przesuń cyklicznie wszystkie elementy wektora o jedną pozycję w tył tak aby drugi element był pierwszym, trzeci drugim itd.
7. znajdź najmniejszy element
8. znajdź liczbę wszystkich liczb parzystych w wektorze za pomocą algorytmu count_if. Warunek do sprawdzenia przekaż jako wskaźnik do odpowiedniej funkcji.
9. 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:

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

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ą zadania z pierwszych zajęć.