cpp

Wprowadzenie

Alexander Stepanov, jeden z twórców programowania uogólnionego, napisał w swojej książce “From Mathematics to Generic Programming”:

Generic programming is an approach to programming that focuses on designing algorithms and data structures so that they work in the most general setting without the loss of efficiency.

Kluczowe są:

Najbardziej ogólny przypadek

Programowanie uogólnione jest wspierane przez język C++ z użyciem szablonów i przeciążeń, przy użyciu których zaimplementowane są:

Przykład niżej pokazuje w jaki sposób możemy używać kontenerów i algorytmów biblioteki standardowej. Przykład wymaga kompilatora C++17.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int
main()
{
  vector v{3, 1, 2};
  sort(v.begin(), v.end());
  for(const auto &e: v)
    cout << e << endl;
}

W przykładzie wyżej możemy zmienić typ sortowanych liczb z int na double: wystarczy zmienić type vector na vector<double> (czyli podać argument double szablonu typu vector). Możemy też zmienić typ z vector na array czy deque. Podczas kompilacji szablon funkcji sort jest konkretyzowany (kompilowany “na miarę”) dla użytej struktury danych i typów elementów struktury.

Programowanie uogólnione może też działać na danych, które nie są obiektowe, na przykład na tablicach z języka C, przez co jest bardziej ogólne niż programowanie obiektowe, które działa wyłącznie na typach obiektowych. Możemy przerobić przykład wyżej, żeby działał nie tylko na kontenerach (które są obiektowe), ale też na tablicy z języka C: zamieniamy wywołania funkcji składowych begin i end, na wywołania funkcji nieskładowych std::begin i std::end:

#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

int
main()
{
  int a[] = {3, 1, 2};
  sort(begin(a), end(a));
  for(const auto &e: a)
    cout << e << endl;
}

Ale przykład nie działa ze strukturą list. Kompilator zwraca masę błędów, z których trudno się zorientować, gdzie jest problem. A problem w tym, że iterator struktury list nie jest iteratorem swobodnego dostępu (ang. random access operator), czyli nie możemy zmniejszyć albo zwiększyć iteratora o dowolną liczbę elementów, np. list{3, 2, 1}.end() + 2 nie kompiluje się. Iterator jest swobodnego dostępu, jeżeli struktura posiada operator swobodnego dostępu operator [], a list go nie ma.

Problemem przede wszystkim jest obecna słaba diagnostyka. Powinniśmy otrzymać komunikat, że funkcja sort wymaga iteratora swobodnego dostępu. C++20 wprowadza koncepty, które pozwolą na klarowną diagnostykę błędów, ale to wymaga zmian (użycia konceptów) w implementacji biblioteki standardowej (np., GCC).

Bez utraty wydajności

Dla komitetu standaryzacyjnego C++, priorytetem jest wydajność kodu wynikowego, a dopiero potem łatwość użycia języka. Tak więc program napisany z użyciem mechanizmów uogólnienia (np. szablonów) ma działać szybko (tak szybko, jak to możliwe, czyli jak gdybyśmy “wyrzeźbili” kod ręcznie), chociaż sam kod źródłowy może być trudny do napisania.

Z użyciem prostych przykładów niżej sprawdzimy, jaki narzut wydajnościowy wprowadzają mechanizmy uogólnienia. Każdy z tych programów wypisuje na standardowe wyjście liczby 1 i 2. Interesuje nas kod wynikowy (asembler) programów.

To jest kod bazowy test_baseline.cc:

#include <iostream>

int
main()
{
  std::cout << 1 << 2;
}

To jest kod z użyciem szablonu funkcji test_template.cc:

#include <iostream>

template <typename T>
void
foo(T a, T b)
{
  std::cout << a << b;
}

int
main()
{
  foo(1, 2);
}

Kompilujemy oba przykłady do asemblera (możemy też użyć Compiler Explorer) i patrzymy na różnice (możemy też użyć c++filt):

g++ -O2 -std=c++17 -S test_baseline.cc test_template.cc
meld test_baseline.s test_template.s

Różnic nie ma. Użycie funkcji szablonowej nie wprowadza żadnego narzutu wydajnościowego, a kod jest tak szybki, jak bez wywołania funkcji.

W tym przykładzie, jak pokazuje kod wynikowy, parametry funkcji szablonowej nie są inicjalizowane (kopiowane) na podstawie argumentów wywołania, mimo że są przekazywane przez wartość. W języku C, funkcja przyjmująca argumenty przez wartość (a nie przez wskaźnik, czy referencję, bo referencji w C nie ma), zawsze ma parametry inicjalizowane na podstawie argumentów wywołania, co wprowadza narzut wydajnościowy.

Zwykła funkcja też może być wkompilowana, co można sprawdzić na tym przykładzie:

#include <iostream>

void
foo(int a, int b)
{
  std::cout << a << b;
}

int
main()
{
  foo(1, 2);
}

Użycie krotki (std::tuple) też nie wprowadza narzutu. Krotka jest szablonowym typem klasowym, więc ma konstruktor i destruktor, jednak są one puste. Oto przykład dla testów:

#include <iostream>
#include <tuple>

using namespace std;

int
main()
{
  tuple t{1, 2};
  cout << get<0>(t) << get<1>(t);
}

Nawet iterowanie po elementach tablicy std::array nie wprowadza żadnego narzutu:

#include <array>
#include <iostream>

int
main()
{
  std::array a{1, 2};
  for(auto e: a)
    std::cout << e;
}

Konkretyzacja pozwala też na lepszą optymalizację kodu:

#include <iostream>

template <unsigned I>
int
divide(int t)
{
  return t / I;
}

int
divide(int t, int I)
{
  return t / I;
}

int
main()
{
  volatile int x = 2;
  // Super-fast division by bit shifting.
  std::cout << divide<2>(x) << std::endl;
  // Regular division, depending on optimizer.
  std::cout << divide(x, 2) << std::endl;
}

Programowanie uogólnione a obiektowe

Język C++ jest językiem wieloparadygmatowym, bo można w nim programować obiektowo, strukturalnie, proceduralnie, funkcyjnie i w sposób uogólniony. Programowanie uogólnione i obiektowe są komplementarne, nie wykluczają się.

Złożone typy danych implementujemy jako struktura, a operacje specyficzne dla tych typów implementujemy jako funkcje składowe (ang. member functions) – oto typowy przykład programowania obiektowego. Operacje (algorytmy) najlepiej implementować jako funkcje nieskładowe (ang. non-member functions, aka free-standing, global or namespace functions), żeby można było je przeciążać dla dowolnych typów, nie tylko obiektowych – a to typowy przykład programowania uogólnionego.

Częstym problemem programowania jest potrzeba dostarczenia różnych fragmentów kodu (operacji czy algorytmów) w zależności od typów danych, na których działamy. Programowanie uogólnione i obiektowe rozwiązują problem z użyciem polimorfizmu, ale różnego rodzaju:

Podsumowując, programowanie uogólnione jest super szybkie i może działać na danych dowolnego typu, a programowanie obiektowe jest wolniejsze i działa wyłącznie na typach klasowych (1.foo() nie przejdzie).

Przykład polimorfizmu statycznego

Przykład implementacji polimorfizmu statycznego z użyciem przeciążeń funkcji znajduje się niżej. Te przeciążenia mają kod wspólny (std::cout << "Function foo:"; i std::cout << std::endl) i kod zależny od typu parametru.

#include <iostream>

struct A
{
};

// B doesn't have to derive from a base class.
struct B
{
};

void foo(const int &i)
{
  std::cout << "Function foo: ";
  std::cout << i;
  std::cout << std::endl;
}

void foo(const A &)
{
  std::cout << "Function foo: ";
  std::cout << "A";
  std::cout << std::endl;
}

void foo(const B &)
{
  std::cout << "Function foo: ";
  std::cout << "B";
  std::cout << std::endl;
}

int
main()
{
  foo(1);
  foo(A());
  foo(B());
}

Niżej znajduje się rozwiązanie z użyciem szablonu, gdzie wspólny kod pojawia się tylko raz. Funkcja szablonowa korzysta z operatora <<, który jest przeciążony dla różnych typów. Ciągle korzystamy z przeciążania, jak w poprzednim przykładzie, ale już dla bardziej okrojonej funkcjonalności, czyli tylko operatora <<, który możemy użyć także gdzie indziej. Możemy powiedzieć, że uogólniliśmy kod funkcji foo.

#include <iostream>

struct A
{
};

std::ostream &
operator << (std::ostream &os, const A &)
{
  os << "A";
  return os;
}

// B doesn't have to derive from a base class.
struct B
{
};

std::ostream &
operator << (std::ostream &os, const B &)
{
  os << "B";
  return os;
}

template <typename T>
void foo(const T &t)
{
  std::cout << "Function foo: ";
  std::cout << t;
  std::cout << std::endl;
}

int
main()
{
  foo(1);
  foo(A());
  foo(B());
}

Przykład polimorfizmu dynamicznego

To samo zadanie możemy zaimplementować z użyciem polimorfizmu dynamicznego. Kod wynikowy funkcji main jest jednak znacznie bardziej skomplikowany.

#include <iostream>

struct A
{
  virtual void foo() const
  {
    std::cout << "A\n";
  }
};

// Type B must derive from the base class.
struct B: A
{
  void foo() const override
  {
    std::cout << "B\n";
  }
};

void
foo(const A &a)
{
  std::cout << "Function foo: ";
  a.foo();
  std::cout << std::endl;
}

int
main()
{
  // foo(1);
  foo(A());
  foo(B());
}

Podsumowanie

Programowanie uogólnione:

Quiz