cpp

Wprowadzenie

W języku C sposobem na dostarczenie fragmentu kodu (np. ustalającego porządek między elementami) do wywołania przez jakiś inny fragment kodu (np. funkcję sortującą) jest dostarczenie wskaźnika na funkcję do wywołania. W C++ uogólnieniem wskaźnika na funkcję jest “coś”, co możemy wywołać, co z angielskiego jest nazywane callable. Wywołanie callable ma ustaloną składnię (czyli składnię wyrażenia wywołania) i określony interfejs, czyli jakiego typu są parametry i wynik callable.

Uogólnienie wyrażenia wywołania (z funkcji na callable) ma na celu:

Biblioteka standardowa używa (przekazuje, zapisuje jako pole składowe) callable przez wartość, więc kopiowanie callable powinno być szybkie. Callable przekazywane do standardowych algorytmów, np. std::sort, i standardowych kontenerów, np. std::priority_queue, powinno się szybko kopiować. To oznacza, że callable nie powinno posiadać dużo danych do skopiowania.

Callable używamy najczęściej przez wartość, tak jak robi to biblioteka standardowa, ale można też używać callable przez referencję albo wskaźnik.

Motywacja

W poniższym sortowaniu porównywane są liczby całkowite, dla których jest ustalony porządek (liniowy) z użyciem operatora <:

#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 niżej sortujemy obiekty typu klasowego. Żeby kompilacja powiodła się, musimy zdefiniować porządek z użyciem operatora porównania, czyli operatora <. Jest kilka operatorów porównania, które mogą być zdefiniowane dla typu klasowego: ==, !=, <, <=, >, =>, <=>, ale dla ustalenia porządku miedzy elementami najważniejszy jest operator mniejszy od, czyli <.

Operator < zdefiniowaliśmy jako funkcję składową, dla której pierwszym operandem jest obiekt *this, a drugim jest parametr składowej. Składowy operator porównania powinien być stały (bo nie powinien zmieniać pierwszego operandu) i powinien pobierać drugi operand przez referenceję stałą (bo nie powinien zmieniać drugiego operandu).

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

using namespace std;

struct A
{
  int id;
  A(int id): id(id)
  {
  }

  bool
  operator < (const A &a) const
  {
    return this->id < a.id;
  }
};

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

Funkcja std::sort używa operatora <, jeżeli nie przakażemy jej callable porównania jako ostatni argument wywołania. Tak naprawdę funkcja std::sort używa obiektu typu std::less, która to z kolei używa operatora <. Dla porównania sortowanych elementów, implementacja funkcji std::sort nie używa bezpośrednio <, bo to ograniczałoby możliwość adaptacji sortowania przez programistę. Zamiast tego używa callable.

Możemy uzyskać identyczny efekt jak w przykładzie wyżej, jeżeli przekażemy jako callable obiekt struktury std::less<A>. Jeżeli tego nie zrobimy, zostanie on domyślnie użyty.

#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;

struct A
{
  int id;
  A(int id): id(id)
  {
  }

  bool
  operator < (const A &a) const
  {
    return this->id < a.id;
  }
};

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

Funkcja std::sort nie musi zawsze używać operatora <. Możemy użyć dowolnego callable. Możemy sortować w kolejności rosnącej, jeżeli użyjemy obiektu struktury std::greater. Ten typ używa operatora >, więc musimy go zdefiniować, zamiast operatora <.

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

using namespace std;

struct A
{
  int id;
  A(int id): id(id)
  {
  }

  bool
  operator > (const A &a) const
  {
    return this->id > a.id;
  }
};

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

Callable może być przekazywany nie tylko funkcji, ale też konstruktorowi, który może przechować callable w polu składowym. Tak robi, na przykład, kolejka priorytetowa biblioteki standardowej (std::priority_queue). Poniżej jest nasz roboczy przykład z kolejką priorytetową, który będziemy dalej zmieniać.

#include <iostream>
#include <queue>

using namespace std;

int
main(void)
{
  priority_queue<int> q;

  q.push(2);
  q.push(1);
  q.push(3);

  while(!q.empty())
    {
      cout << q.top() << endl;
      q.pop();
    }
  
  return 0;
}

Typy callable

Callable może być:

Funkcja

Wyrażenie, które jest tylko nazwą funkcji (bez operatora wywołania) może być potraktowane jako adres tej funkcji, co nazywamy rozpadem funkcji na wskaźnik. Możemy pobrać adres funkcji z użyciem operatora adresowania, np. &foo. Te dwa sposoby pobrania adresu są równoważne, co jest trochę niespójne, bo powinien być tylko jeden sposób.

Używając tego adresu możemy wywołać funkcję. Jedyne operacje możliwe na wskaźniku do funkcji to: pobranie adresu funkcji i wywołanie funkcji.

W przykładzie niżej posługujemy się funkcją przez wskaźnik i referencję.

#include <iostream>

bool
foo(const int &a, const int &b)
{
  std::cout << "foo: a = " << a << ", b = " << b << '\n';
  return true;
}

int
main()
{
  // Equivalent ways to call a function.
  foo(10, 20); // Is foo decaying into a pointer that we call?
  (&foo)(10, 20);

  // I don't like the C syntax of the pointer to a function.
  bool (*f1a)(const int &, const int &) = foo;
  bool (*f1b)(const int &, const int &) = &foo;
  f1a(10, 20);
  (*f1a)(10, 20);
  f1b(10, 20);
  (*f1b)(10, 20);

  // A reference to a function.
  bool (&f2a)(const int &, const int &) = foo;
  // A reference cannot be initialized with a pointer.
  // bool (&f2b)(const int &, const int &) = &foo;
  f2a(10, 20);
  // The following is wierd, but it compiles. f2a is an alias for foo.
  // So f2a is replaced with foo, and foo decays into a pointer, which
  // we dereference to get a function to call.
  (*f2a)(10, 20);
  
  // The C++ syntax for a function type.
  using foo_type = bool(const int &a, const int &b);
  // Pointers to a function.
  foo_type *f3a = foo;
  foo_type *f3b = &foo;
  // A reference to a function.
  foo_type &f3c = foo;
  f3a(10, 20);
  (*f3a)(10, 20);
  f3b(10, 20);
  (*f3b)(10, 20);
  f3c(10, 20);
  (*f3c)(10, 20);
}

Tutaj sortujemy malejąco z użyciem wskaźnika na funkcję:

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

using namespace std;

bool
cmp(const int &a, const int &b)
{
  return a > b;
}

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

Domyślnie kolejka priorytetowa sortuje malejąco, czyli zwraca największe elementy. W przykładzie niżej przekazujemy wskaźnik na funkcję porównującą, żeby ustalić porządek rosnący w kolejce priorytetowej.

#include <functional>
#include <iostream>
#include <queue>

using namespace std;

bool
foo(const int &a, const int &b)
{
  return a > b;
}

int
main(void)
{
  priority_queue<int, vector<int>,
                 bool(*)(const int &, const int &)> q(foo);

  q.push(2);
  q.push(1);
  q.push(3);

  while(!q.empty())
    {
      cout << q.top() << endl;
      q.pop();
    }
  
  return 0;
}

Funktor

Funktor to obiekt, który ma zdefiniowany operator wywołania () (ang. call operator). Zaletą funktora, w porównaniu z funkcją, jest możliwość przekazania do konstruktora dodatkowych danych, które są przechowywane w polach składowych, a potem używane przez operator wywołania.

W przykładzie niżej definiujemy prosty typ funktora, tworzymy funktor i wywołujemy go. Funktor jest callable, bo możemy go wywołać. Ponieważ operator () został zdefiniowany jako stały, to możemy go wywołać także na rzecz obiektów stałych.

#include <iostream>

struct functor_type
{
  void operator()() const
  {
    std::cout << "Hello World from a functor!\n";
  }
};

int
main()
{
  const functor_type f;
  f();
}

W funktorze możemy przechowywać dane:

#include <iostream>

struct functor_type
{
  int m_n;

  functor_type(int n): m_n(n)
  {
  }

  void operator()() const
  {
    for(int i = 0; i < m_n; ++i)
      std::cout << "Hello World from a functor!\n";
  }
};

int
main()
{
  functor_type f(10);
  f();
}

Funktor działa jak funkcja, kiedy nie przechowuje danych. Na przykład, typy std::less i std::greater zachowują się jak funkcje, bo nie przechowują danych. Takie typy funktora nie spowalniają programu: konstruktor i destruktor są puste, a operator porównania jest wkompilowywany w miejsce wywołania. Szybciej się nie da.

Domyślnie kolejka priorytetowa zwraca największy element, bo do porównania używa klasy funktora std::less. Poniżej użyjemy funktora klasy std::greater, żeby kolejka zwracała najmniejszy element.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int
main(void)
{
  // HERE'S THE DIFFERENCE!
  priority_queue<int, vector<int>, greater<int>> q;

  // I was hoping the third template argument would be deduced from
  // the constructor argument, but, alas, no.
  // priority_queue<int> q(std::greater<int>{});
  
  q.push(2);
  q.push(1);
  q.push(3);

  while(!q.empty())
    {
      cout << q.top() << endl;
      q.pop();
    }
  
  return 0;
}

Możemy także zdefiniować własny typ funktora, który działa jak funkcja:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct CMP
{
  bool
  operator()(const int &a, const int &b)
  {
    return a > b;
  }
};

int
main(void)
{
  // An object of CMP will be default-constructed by q.
  priority_queue<int, vector<int>, CMP> q;

  q.push(2);
  q.push(1);
  q.push(3);

  while(!q.empty())
    {
      cout << q.top() << endl;
      q.pop();
    }
  
  return 0;
}

W tym przykładzie w czasie uruchomienia przekazujemy konstruktorowi funktora argument (dodatkową daną do obliczeń), który mówi o porządku (rosnącym bądź malejącym):

#include <functional>
#include <iostream>
#include <queue>

using namespace std;

struct CMP
{
  bool m_order;

  CMP(bool order): m_order(order)
  {
  }

  bool
  operator()(const int &a, const int &b) const
  {
    return m_order ? a < b : a > b;
  }
};

int
main(void)
{
  bool order;

  cout << "Enter 0 or 1:";
  cin >> order;

  priority_queue<int, vector<int>, CMP> q(CMP{order});
  // The same as above.
  // priority_queue<int, vector<int>, CMP> q(order);

  q.push(2);
  q.push(1);
  q.push(3);

  while(!q.empty())
    {
      cout << q.top() << endl;
      q.pop();
    }

  return 0;
}

Domknięcie

Domknięcie jest funktorem, który jest wynikiem opracowania wyrażenia lambda. Lambda (w skrócie od wyrażenia lambda) jest syntaktycznym skrótem wygodnego tworzenia funktorów w porównaniu z pisaniem klasy funktora. Moglibyśmy się obejść bez lambd, bo tą samą funkcjonalność mają klasy funktora. Lambdy są po prostu wygodne.

Ponieważ domknięcie jest obiektem, to musi mieć typ, ale zwykle go nie potrzebujemy, więc możemy powiedzieć, że domknięcie jest typu anonimowego. Możemy pozyskać typ domknięcia z użyciem operatora decltype.

Składnia

Wyrażenia lambda mają wiele szczegółów, których nie omówimy. Jednak większość lambd ma taką składnię:

[lista przechwytywania](lista parametrów) mutable {ciało}

Listy przechwytywania i parametrów używają przecinków do oddzielenia pozycji. Jeżeli lista parametrów jest pusta, to () można pominąc. Nawet jeżeli lista przechwytywania i ciało są puste, to [] i {} nie mogą być pominięte.

Lista przechwytywania może zawierać:

Lista parametrów jest listą parametrów funkcji, tak jak dla zwykłej funkcji.

Specyfikator mutable jest opcjonalny. Domyślnie składowa funkcja operatorowa () domknięcia jest stała, ale możemy ją zadeklarować jako niestałą z użyciem specyfikatora mutable.

Dlatego najprostszą lambdą jest []{}. Tutaj tworzymy domknięcie i wywołujemy je w jednym wyrażeniu:

int
main()
{
  // These two are equivalent.
  [](){};
  []{};

  // Here we also call the closure: notice the trailing ().
  []{}();
}

Wyrażenie []{}(), które tworzy i wywołuje domknięcie, jest równoważne temu kodowi:

int
main()
{
  // The block scope is here, so that object x behaves like a
  // temporary object.  Object x is of anonymous type.
  {
    struct
    {
      void
      operator()() const
      {
      }
    } x;
    x();
  }
}

Semantyka

Lambda tworzy typ funktora (strukturę albo klasę) i obiekt tej klasy. Podstawowe fakty:

Lista przechwytywania określa, jak w ciele funkcji zapewnić dostęp do wartości zmiennych z zakresu wyrażenia lambda. Zakres jest fragmentem kodu, w którym dostępne są zmienne. Zakres może być globalny, klasy, funkcji, czy bloku.

Lista przechwytywania może być pusta. W takim przypadku w ciele dostępne są jedynie parametry z listy parametrów. Oto przykład:

#include <iostream>

int
main()
{
  int x = 1;

  // Would not compile, because x is not captured, and the parameter
  // list is empty.
  // []{x = 10;}();

  [](int &x){x = 10;}(x);
  std::cout << "x = " << x << std::endl;
}

Powyższy kod jest równoważny poniższemu:

#include <iostream>

int
main()
{
  int x = 1;

  {
    struct
    {
      void
      operator()(int &x) const
      {
        x = 10;
      }
    } f;
    f(x);
  }

  std::cout << "x = " << x << std::endl;
}

Sposoby przechwytywania zmiennych

Zmienna może być przechwycona przez wartość albo referencję. Kiedy zmienna jest przechwycona przez wartość, domknięcie przechowuje w swoim polu składowym kopię wartości przechwyconej zmiennej, czyli pole składowe jest inicjalizowane przez skopiowanie wartości z przechwytywanej zmiennej. Żeby przechwycić zmienną przez wartość, należy podać nazwę zmiennej w liście przechwytywania.

Kiedy zmienna jest przechwycona przez referencję, domknięcie przechowuje jako swoje pole składowe referencję do przechwyconej zmiennej, czyli składowa referencja jest inicjalizowana z użyciem przechwytywanej zmiennej. Any przechwycić zmienną przez referencję, należy podać nazwę zmiennej w liście przechwytywania i poprzedzić ją deklaratorem &.

Na przykład:

#include <iostream>

int
main()
{
  int x = 1, y = 2;

  // Variable x is captured by value, y by reference.
  [x, &y]() mutable {x = 10, y = 20;}();

  std::cout << "x = " << x << ", y = " << y << std::endl;
}

Powyższy kod jest równoważny poniższemu:

#include <iostream>

int
main()
{
  int x = 1, y = 2;

  {
    struct F
    {
      int x;
      int &y;

      F(int x, int &y): x(x), y(y)
      {
      }

      void
      operator()()
      {
        x = 10;
        y = 20;
      }
    };

    F f(x, y);
    f();
  }

  std::cout << "x = " << x << ", y = " << y << std::endl;
}

Domyślna polityka przechwytywania

Możemy zażądać domyślnej polityki przechwytywania przez podanie na początku listy przechwytywania deklaratora polityki. Jeżeli domyślna polityka jest podana, to wszystkie zmienne użyte w ciele są przechwytywane i nie musimy ich podawać w liście.

Domyślnej polityki przechwytywania przez wartość żądamy z użyciem deklaratora =. Na przykład:

#include <iostream>

int
main()
{
  int x = 1, y = 2;

  // Capture every variable by value.
  [=]() mutable {x = 10; y = 20;}();

  std::cout << "x = " << x << ", y = " << y << std::endl;
}

Powyższy kod jest równoważny poniższemu:

#include <iostream>

int
main()
{
  int x = 1, y = 2;

  {
    struct F
    {
      int x;
      int y;

      F(int x, int y): x(x), y(y)
      {
      }

      void
      operator()()
      {
        x = 10;
        y = 20;
      }
    };

    F f(x, y);
    f();
  }

  std::cout << "x = " << x << ", y = " << y << std::endl;
}

Domyślnej polityki przechwytywania przez referencję żądamy z użyciem deklaratora &. W dwóch przykładach niżej, funkcja operatora () może być stała, bo nie zmieniamy referencji składowej, a jedynie zmienną, do której referencja się odnosi.

#include <iostream>

int
main()
{
  int x = 1, y = 2;

  // Capture every variable by reference.
  [&]{x = 10; y = 20;}();

  std::cout << "x = " << x << ", y = " << y << std::endl;
}

Powyższy kod jest równoważny poniższemu:

#include <iostream>

int
main()
{
  int x = 1, y = 2;

  {
    struct F
    {
      int &x;
      int &y;

      F(int &x, int &y): x(x), y(y)
      {
      }

      void
      operator()() const
      {
        x = 10;
        y = 20;
      }
    };

    F f(x, y);
    f();
  }

  std::cout << "x = " << x << ", y = " << y << std::endl;
}

Możemy zażądać domyślnej polityki, a następnie podać te zmienne, które powinny być przechwycone odwrotnie. Możemy także użyć innych nazw dla pól składowych, innych od nazw przechwytywanych zmiennych. Oto przykład:

#include <iostream>

using namespace std;

int
main()
{
  {
    int x = 1, y = 2;

    // Because of the default capture-by-value policy, x is captured
    // by value, while y is captured by reference.
    [=, &y]() mutable {x = 10, y = 20;}();
    cout << "x = " << x << ", y = " << y << endl;
  }

  {
    int x = 1, y = 2;

    // Because of the default capture-by-reference policy, x is
    // captured by reference, while y is captured by value.
    [&, y]() mutable {x = 10, y = 20;}();
    cout << "x = " << x << ", y = " << y << endl;
  }

  {
    int x = 1, y = 2;

    // We name the captured variables differently: a, b.
    [a = x, &b = y]() mutable {a = 10, b = 20;}();
    cout << "x = " << x << ", y = " << y << endl;
  }
}

Przykłady domknięć

Ponieważ domknięcie ma typ, który najczęściej nas nie interesuje, to możemy napisać:

auto c = wyrażenie lambda;

Przez użycie typu auto pozwalamy kompilatorowi na wywnioskowanie typu zmiennej c na podstawie wyrażenia lambda. Mimo że jest użyty znak =, to powyższa linia nie jest wyrażeniem przypisania, a inicjalizacją zmiennej: domknięcie nie jest kopiowane, a inicjalizowane bezpośrednio w miejscu zmiennej c z pominięciem konstruktora.

Tutaj jest przykład użycia lambdy z kolejką priorytetową:

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int
main(void)
{
  auto f = [](const int &a, const int &b){return a > b;};

  priority_queue<int, vector<int>, decltype(f)> q(f);

  q.push(2);
  q.push(1);
  q.push(3);

  while(!q.empty())
    {
      cout << q.top() << endl;
      q.pop();
    }
  
  return 0;
}

Tutaj przekazujemy argument do domknięcia:

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int
main(void)
{
  bool order;

  cout << "Enter 0 or 1: ";
  cin >> order;
  
  auto c = [order](const int &a, const int &b)
           {return order ? a < b : a > b;};

  priority_queue<int, vector<int>, decltype(c)> q(c);

  q.push(2);
  q.push(1);
  q.push(3);

  while(!q.empty())
    {
      cout << q.top() << endl;
      q.pop();
    }
  
  return 0;
}

Podsumowanie

Quiz