ZWI #1: Jak wykryć kontenery asocjacyjne w czasie kompilacji

Tym postem rozpoczynam kolejną serię – ZWI (Zapytane w Internecie). W planach jest co najmniej jeden wpis ;​) Posty będą przedstawiały pytania, na które odpowiedziałem na różnej maści forach, które (lub których odpowiedzi) uznałem za godne uwagi.

Na pierwszy ogień idzie następujące pytanie z forum 4programmers:

Mam prostą funkcję

template <typename Container, typename Value>
bool contains(const Container& container, const Value& value)
{
    return std::find(std::begin(container), std::end(container), value) !=
           std::end(container);
}

Dla kontenerów asocjacyjnych (set, multiset, unordered_set, map itd.) można wykorzystać metodę find(), która jest szybsza niż globalne find(). Pytanie czy da się w prosty i elegancki sposób wykryć taką sytuację, żeby wywołać container.find(), bo nie uśmiecha mi się pisać specjalizacji dla każdego typu kontenera.

Dla niecierpliwych: tak, da się. Przedstawiłem dwie metody, różniące się trochę semantyką:

Jeśli jest metoda find() to jej użyj

Ta metoda jest trochę niezgodna z literą pytania, ponieważ funkcja zostanie wywołana także dla innych kontenerów, np. boost::set. Jest to jednak zgodne z duchem pytania, ponieważ pozwala na wykorzystanie wydajniejszej metody w dowolnym kontenerze.

Wersja z błędem

Moja pierwsza odpowiedź zawierała zdradliwy błąd, ale przytoczę ją, ponieważ pokazuje pułapkę w jaką mogą wpaść implementatorzy, oraz wystarczy dodać jeden prosty trick, aby uzyskać poprawną odpowiedź.

namespace detail
{
template<typename C, typename V>
auto contains(C&& c, V&& v) -> decltype(c.find(forward<V>(v)) == c.end()) {
    BARK;
    return c.find(forward<V>(v)) != c.end();
}
 
template <typename Container, typename Value>
bool contains(const Container& container, const Value& value)
{
    BARK;
    return std::find(std::begin(container), std::end(container), value) !=
           std::end(container);
}
 
}
 
template<typename C, typename V>
bool contains(C&& c, V&& v)
{
    return detail::contains(forward<C>(c), forward<V>(v));
}

Jak widać w przykładzie, wybrane zostają poprawne funkcje (pierwsza wartość to nr linii – zgodna z oczekiwaniem):

int main()
{
    set<int> s{1,2,3};
    map<int, int> m{{1,2}, {2,3}};
    vector<int> v{1,2,3,4};
    deque<int> d{1,2,3,4};
    contains(s, 1);
    contains(m, 1);
    contains(v, 1);
    contains(d, 1);
}
  55 decltype ((c.find(forward<V>(v)) == c.end())) detail::contains(C&&, V&&) [with C = std::set<int>&; V = int; decltype ((c.find(forward<V>(v)) == c.end())) = bool]
  55 decltype ((c.find(forward<V>(v)) == c.end())) detail::contains(C&&, V&&) [with C = std::map<int, int>&; V = int; decltype ((c.find(forward<V>(v)) == c.end())) = bool]
  62 bool detail::contains(const Container&, const Value&) [with Container = std::vector<int>; Value = int]
  62 bool detail::contains(const Container&, const Value&) [with Container = std::deque<int>; Value = int]

Ok, skoro działa poprawnie, to co jest źle? Do stwierdzenia tego musimy zrozumieć co tu się dzieje.

Jak to działa?

Rozwiązanie wykorzystuje expression SFINAE. SFINAE (Substitution Failure Is Not An Error) to zasada w C++ mówiąca o tym, że jeśli podczas dopasowania szablonu do wzorca, dopasowanie się nie uda, to nie powoduje to błędu kompilacji. W zamian dany szablon po prostu nie jest brany pod uwagę.

Weźmy pod uwagę pierwszy szablon funkcji:

template<typename C, typename V>
auto contains(C&& c, V&& v) -> decltype(c.find(forward<V>(v)) == c.end()) {
    BARK;
    return c.find(forward<V>(v)) != c.end();
}

Jeśli zostanie wywołany z pierwszym parametrem będącym obiektem konkretyzacji std::set, to wyrażenie c.find(…) będzie poprawne i wydedukuje poprawny typ zwracany. Jednak np. std::vector nie ma metody find() to kompilator po prostu nie weźmie tego szablonu pod uwagę.

W takim razie sprawą oczywistą dlaczego drugi szablon jest wybierany w przypadku parametrów, które powodują odrzucenie pierwszego. Dlaczego jednak jest wybierany pierwszy? Musi być lepszy, ponieważ jeśli kompilator nie umie wybrać poprawniejszej funkcji, to musi zakończyć kompilację z błędem (ambiguous call).

Gdy to możliwe, pierwszy wybierany jest, ponieważ C&& i V&& to referencje znane pod nazwami uniwersalne (universal references) i forwarding references1. W pewnym uproszczeniu: w kontekście dopasowania szablonów prawie zawsze dają najlepszy możliwy typ, a więc i najlepszą możliwą funkcję dla swoich argumentów2.

No super, to co z tym błędem?

Stwierdzenie z poprzedniego akapitu jest w większości prawdziwe, ale jeśli wydedukowany typ argumentów będzie identyczny jak w innej, bardziej wyspecjalizowanej funkcji (a jeszcze lepiej jeśli będzie nieszablonowa), to zostanie wybrana ta bardziej wyspecjalizowana. Dlatego też, jeśli parametrami będą const set<int> oraz const int, tak jak w poniższym przypadku, czeka nas srogi zawód.

int main()
{
    const set<int> s{1,2,3};
    const int i = 1;
    map<int, int> m{{1,2}, {2,3}};
    vector<int> v{1,2,3,4};
    deque<int> d{1,2,3,4};
    contains(s, i); // wybierze "zły" overload
    contains(m, 1);
    contains(v, 1);
    contains(d, 1);
}
  62 bool detail::contains(const Container&, const Value&) [with Container = std::set<int>; Value = int]
  55 decltype ((c.find(forward<V>(v)) == c.end())) detail::contains(C&&, V&&) [with C = std::map<int, int>&; V = int; decltype ((c.find(forward<V>(v)) == c.end())) = bool]
  62 bool detail::contains(const Container&, const Value&) [with Container = std::vector<int>; Value = int]
  62 bool detail::contains(const Container&, const Value&) [with Container = std::deque<int>; Value = int]

Wersja poprawiona

Powyższy problem można rozwiązać wyraźnie mówiąc kompilatorowi, którą funkcję ma preferować – poprzez dodatkowy argument dla obu szablonów. Może to być coś równie prostego jak int i long.

namespace detail
{
template<typename C, typename V>
auto contains(C&& c, V&& v, int) -> decltype(c.find(forward<V>(v)) == c.end()) {
    BARK;
    return c.find(forward<V>(v)) != c.end();
}
 
template <typename Container, typename Value>
bool contains(const Container& container, const Value& value, long)
{
    BARK;
    return std::find(std::begin(container), std::end(container), value) !=
           std::end(container);
}
 
}
 
template<typename C, typename V>
bool contains(C&& c, V&& v)
{
    return detail::contains(forward<C>(c), forward<V>(v), 0);
}

Kompilator pierw spróbuje nie dokonywać konwersji 0 z int na long. Jednak jeśli pierwszy overload jest niemożliwy to zostanie to uczynione.

W finalnym kodzie jednak sugeruję użyć bardziej czytelnej selekcji przeładowania3:

template<int Priority> struct select_overload;
template<> struct select_overload<0>{};
template<int Priority> struct select_overload : select_overload<Priority-1>{};

To rozwiązanie pozwala na ustalenie bardzo wielu priorytetów dla wielu przeładowań. Teraz wystarczy to zrobić dla wybranych funkcji:

template<typename C, typename V>
auto contains(C&& c, V&& v, select_overload<1>)
    -> decltype(c.find(forward<V>(v)) == c.end()) {
    BARK;
    return c.find(forward<V>(v)) != c.end();
}
 
template <typename Container, typename Value>
bool contains(const Container& container, const Value& value, select_overload<0>)
{
    BARK;
    return std::find(std::begin(container), std::end(container), value) !=
           std::end(container);
}

Oraz ich wywołania:

template<typename C, typename V>
bool contains(C&& c, V&& v)
{
    return detail::contains(forward<C>(c), forward<V>(v), detail::select_overload<1>{});
}

Dla takiego samego testu:

int main()
{
    const set<int> s{1,2,3};
    const int i = 1;
    map<int, int> m{{1,2}, {2,3}};
    vector<int> v{1,2,3,4};
    deque<int> d{1,2,3,4};
    contains(s, i); // wybierze "dobry" overload
    contains(m, 1);
    contains(v, 1);
    contains(d, 1);
}

Wybrane zostaną dobre przeładowania: [link]

  61 decltype ((c.find(forward<V>(v)) == c.end())) detail::contains(C&&, V&&, detail::select_overload<1>) [with C = const std::set<int>&; V = const int&; decltype ((c.find(forward<V>(v)) == c.end())) = bool]
  61 decltype ((c.find(forward<V>(v)) == c.end())) detail::contains(C&&, V&&, detail::select_overload<1>) [with C = std::map<int, int>&; V = int; decltype ((c.find(forward<V>(v)) == c.end())) = bool]
  68 bool detail::contains(const Container&, const Value&, detail::select_overload<0>) [with Container = std::vector<int>; Value = int]
  68 bool detail::contains(const Container&, const Value&, detail::select_overload<0>) [with Container = std::deque<int>; Value = int]

Yay, udało się!

Specjalnie traktuj tylko wybrane szablony

A co jeśli autor faktycznie chce specjalnie traktować tylko wybrane szablony i nic innego? Na szczęście na to odpowiedź jest prosta: może napisać własny trait rozpoznający, czy jest to wybrany szablon:

template<typename T> struct is_special : false_type {};
template<typename... Ps> struct is_special<set<Ps...>> : true_type {};
template<typename... Ps> struct is_special<map<Ps...>> : true_type {};

Dla dowolnej mapy i setu, klasa is_special skonkretyzowana po niej będzie dziedziczyć po true_type. W przeciwnym wypadku dziedziczyć będzie po false_type. Dzięki temu można użyć tych typów jako wykluczających się parametrów szablonów:

template<typename C, typename V>
bool contains(C&& c, V&& v, true_type) {
    BARK;
    return c.find(forward<V>(v)) != c.end();
}
 
template <typename Container, typename Value>
bool contains(const Container& container, const Value& value, false_type)
{
    BARK;
    return std::find(std::begin(container), std::end(container), value) !=
           std::end(container);
}

Oraz wywołanie:

 
template<typename C, typename V>
bool contains(C&& c, V&& v)
{
    using decayed = typename decay<C>::type;
    using is_special = detail::is_special<decayed>;
    return detail::contains(forward<C>(c), forward<V>(v), is_special{});
}

is_special w funkcji będzie odpowiadało traitowi detail::is_special, czyli będzie typem dziedziczącym po true_type lub false_type w zależności od tego, czy nasz typ jest wybrany. Dla identycznej funkcji main():

int main()
{
    const set<int> s{1,2,3};
    const int i = 1;
    map<int, int> m{{1,2}, {2,3}};
    vector<int> v{1,2,3,4};
    deque<int> d{1,2,3,4};
    contains(s, i); // wybierze "dobry" overload
    contains(m, 1);
    contains(v, 1);
    contains(d, 1);
}

Ponownie wybrane zostaną dobre przeładowania: [link]

  59 bool detail::contains(C&&, V&&, std::true_type) [with C = const std::set<int>&; V = const int&; std::true_type = std::integral_constant<bool, true>]
  59 bool detail::contains(C&&, V&&, std::true_type) [with C = std::map<int, int>&; V = int; std::true_type = std::integral_constant<bool, true>]
  66 bool detail::contains(const Container&, const Value&, std::false_type) [with Container = std::vector<int>; Value = int; std::false_type = std::integral_constant<bool, false>]
  66 bool detail::contains(const Container&, const Value&, std::false_type) [with Container = std::deque<int>; Value = int; std::false_type = std::integral_constant<bool, false>]

I znów wygrało dobro (kq).

1Bardziej szczegółowy opis pojawi się w osobnym poście, gdy taki napiszę.
2Wybór przeładowań z uwzględnieniem szablonów w C++ to tak naprawdę materiał na dobrą pracę magisterską, a nie przypis w poście.
3Bardziej szczegółowy opis pojawi się w osobnym poście, gdy taki napiszę. Pomysł zaczerpnięty stąd.

One thought on “ZWI #1: Jak wykryć kontenery asocjacyjne w czasie kompilacji

Leave a Reply

Your email address will not be published.