Co to są przezroczyste komparatory?

W C ++ 14 wydaje się, że kontenery asocjacyjne zmieniły się z C ++ 11 - [Associative.reqmts] / 13 mówi:

Szablony funkcji składowej find, count, lower_bound, upper_bound, i equal_rangenie powinien uczestniczyć w rozdzielczości przeciążenia chyba typ Compare::is_transparentistnieje.

Jaki jest cel uczynienia komparatora „przejrzystym”?

C ++ 14 udostępnia również szablony bibliotek, takie jak ten:

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

Tak na przykład, std::set<T, std::less<T>>by nie mieć przejrzysty porównawczy, ale std::set<T, std::less<>> będzie mieć.

Jaki problem to rozwiązuje i czy zmienia to działanie standardowych kontenerów? Na przykład, parametry szablonów std::setsą nadal Key, Compare = std::less<Key>, ..., więc nie domyślny zestaw stracić swoje find, countitd członków?

Jaki problem to rozwiązuje,

Zobacz odpowiedź Dietmar za i odpowiedź remyabel użytkownika .

i czy to zmienia sposób działania standardowych kontenerów?

Nie, nie domyślnie.

Nowe przeciążenia szablonów funkcji składowych finditp. Pozwalają na użycie typu, który jest porównywalny z kluczem kontenera, zamiast używania samego typu klucza. Aby zapoznać się z uzasadnieniem i szczegółową, starannie napisaną propozycją dodania tej funkcji, zobacz N3465 autorstwa Joaquína Mª Lópeza Muñoza.

Na spotkaniu w Bristolu LWG zgodziło się, że funkcja wyszukiwania heterogenicznego jest użyteczna i pożądana, ale nie mogliśmy być pewni, że propozycja Joaquína będzie bezpieczna we wszystkich przypadkach. Propozycja N3465 spowodowałaby poważne problemy w przypadku niektórych programów (patrz sekcja Wpływ na istniejący kod ). Joaquín przygotował zaktualizowaną wersję roboczą propozycji z kilkoma alternatywnymi wdrożeniami z różnymi kompromisami, co było bardzo przydatne, pomagając LWG zrozumieć zalety i wady, ale wszyscy ryzykowali zerwanie niektórych programów w jakiś sposób, więc nie było zgody co do dodania tej funkcji. Zdecydowaliśmy, że chociaż bezwarunkowe dodawanie tej funkcji nie byłoby bezpieczne, byłoby bezpieczne, gdyby była domyślnie wyłączona i tylko „włączono”.

Kluczową różnicą w propozycji N3657 (która była ostatnią poprawką przeze mnie i STL opartą na N3465 i późniejszą niepublikowaną wersją roboczą Joaquína) było dodanie is_transparenttypu jako protokołu, którego można użyć do włączenia nowej funkcjonalności.

Jeśli nie używasz „przezroczystego funktora” (tj. Takiego, który definiuje is_transparenttyp), wtedy kontenery zachowują się tak samo, jak zawsze i nadal jest to ustawienie domyślne.

Jeśli zdecydujesz się na użycie std::less<>(co jest nowością w C ++ 14) lub innego typu „przezroczystego funktora”, otrzymasz nową funkcjonalność.

Korzystanie std::less<>z szablonów aliasów jest łatwe:

template<typename T, typename Cmp = std::less<>, typename Alloc = std::allocator<T>>
  using set = std::set<T, Cmp, Alloc>;

Nazwa is_transparentpochodzi od języka STL N3421, który dodał „operatory diamentowe” do C ++ 14. „Przezroczysty funktor” to taki, który akceptuje dowolne typy argumentów (które nie muszą być takie same) i po prostu przekazuje te argumenty do innego operatora. Taki funktor jest dokładnie tym, czego potrzebujesz do wyszukiwania heterogenicznego w kontenerach asocjacyjnych, więc typ is_transparentzostał dodany do wszystkich operatorów rombu i użyty jako typ tagu, aby wskazać, że nowa funkcja powinna być włączona w kontenerach asocjacyjnych. Z technicznego punktu widzenia kontenery nie potrzebują „przezroczystego funktora”, tylko taki, który obsługuje wywoływanie go z typami heterogenicznymi (np. pointer_compTyp w https://stackoverflow.com/a/18940595/981959 nie jest przezroczysty zgodnie z definicją STL,pointer_comp::is_transparentpozwala na użycie go do rozwiązania problemu). Jeśli tylko kiedykolwiek odnośnika w twojej std::set<T, C>z klawiszami typu Ti intnastępnie Cmusi być wpłacone z argumentami typu tylko Ti int(w dowolnej kolejności), to nie musi być naprawdę przejrzyste. Użyliśmy tej nazwy częściowo dlatego, że nie mogliśmy wymyślić lepszej nazwy (wolałbym, is_polymorphicponieważ takie funktory używają statycznego polimorfizmu, ale istnieje już std::is_polymorphiccecha typu, która odnosi się do dynamicznego polimorfizmu).

W C ++ 11 nie są członkami szablony find(), lower_bound()itp Oznacza to, że nic nie jest stracone przez tę zmianę. Szablony członkowskie zostały wprowadzone wraz z n3657, aby umożliwić używanie heterogenicznych kluczy z kontenerami asocjacyjnymi. Nie widzę żadnego konkretnego przykładu, w którym byłoby to przydatne, z wyjątkiem przykładu, który jest dobry i zły!

is_transparentStosowanie ma na celu uniknięcie niepotrzebnych konwersji. Jeśli szablony elementów członkowskich byłyby nieograniczone, istniejący kod może bezpośrednio przechodzić przez obiekty, które zostałyby przekonwertowane bez szablonów elementów członkowskich. Przykładowy przypadek użycia z n3657 polega na zlokalizowaniu obiektu w a std::set<std::string>przy użyciu literału ciągu: w definicji C ++ 11 std::stringobiekt jest konstruowany podczas przekazywania literałów ciągu do odpowiedniej funkcji składowej . Dzięki zmianie możliwe jest bezpośrednie użycie literału ciągu. Jeśli bazowy obiekt funkcji porównania jest zaimplementowany wyłącznie w kategoriach std::string, jest to złe, ponieważ teraz std::stringzostanie utworzony dla każdego porównania. Z drugiej strony, jeśli podstawowy obiekt funkcji porównania może przyjmować rozszerzeniestd::string i literał łańcuchowy, który może uniknąć konstrukcji tymczasowego obiektu.

Zagnieżdżony is_transparenttyp w obiekcie funkcji porównania zapewnia sposób określenia, czy należy użyć funkcji składowej opartej na szablonie: jeśli obiekt funkcji porównania może obsługiwać heterogeniczne argumenty, definiuje ten typ, aby wskazać, że może efektywnie radzić sobie z różnymi argumentami. Na przykład nowe obiekty funkcji operatora po prostu delegują operator<()i twierdzą, że są przezroczyste. To przynajmniej działa, dla std::stringktórego przeciążono mniej niż operatorzy przyjmujący char const*jako argument. Ponieważ te obiekty funkcyjne są również nowe, nawet jeśli robią niewłaściwe rzeczy (tj. Wymagają konwersji dla jakiegoś typu), przynajmniej nie byłaby to cicha zmiana powodująca pogorszenie wydajności.

_{Poniżej znajduje się cała kopia makaronu z n3657 .}

P. Jaki jest cel uczynienia komparatora „przejrzystym”?

A. Asocjacyjne funkcje wyszukiwania kontenerów (find, lower_bound, upper_bound, equal_range) pobierają tylko argument typu key_type, wymagając od użytkowników skonstruowania (niejawnie lub jawnie) obiektu typu key_type w celu wykonania wyszukiwania. Może to być kosztowne, np. Skonstruowanie dużego obiektu do przeszukiwania w zbiorze, gdy funkcja komparatora patrzy tylko na jedno pole obiektu. Wśród użytkowników istnieje silne pragnienie, aby móc wyszukiwać przy użyciu innych typów, które są porównywalne z typem_klucza.

P. Jaki problem to rozwiązuje

A. LWG miała następujące obawy dotyczące kodu:

std::set<std::string> s = /* ... */;
s.find("key");

W C ++ 11 to skonstruuje pojedynczy tymczasowy std :: string, a następnie porówna go z elementami, aby znaleźć klucz.

Ze zmianą zaproponowaną przez N3465 funkcja std :: set :: find () byłaby nieograniczonym szablonem, który przekazywałby const char * do funkcji komparatora, std :: less, która tworzyłaby tymczasowy std :: string dla każde porównanie. LWG uznała ten problem z wydajnością za poważny. Funkcja szablonu find () zapobiegałaby również znalezieniu NULL w kontenerze wskaźników, co powoduje, że poprzednio prawidłowy kod nie jest już kompilowany, ale był to mniej poważny problem niż cicha regresja wydajności

P: Czy to zmienia sposób działania standardowych kontenerów

O. Ta propozycja modyfikuje asocjacyjne kontenery wi przez przeciążenie funkcji wyszukiwania elementów składowych szablonami funkcji składowych. Nie ma zmian językowych.

P: tak więc domyślny zestaw traci elementy znajdowania, liczenia itp

O. Prawie cały istniejący kod C ++ 11 pozostaje nienaruszony, ponieważ funkcje składowe nie są obecne, chyba że jako funkcje porównawcze zostaną użyte nowe funkcje biblioteki C ++ 14.

Cytując Yakka ,

W C ++ 14 std :: set :: find jest funkcją szablonu, jeśli istnieje Compare :: is_transparent. Typ, który przekazujesz, nie musi być kluczem, po prostu odpowiednikiem w twoim komparatorze.

i n3657,

Dodaj paragraf 13 w 23.2.4 [Associative.reqmts]: Szablony funkcji składowych find, lower_bound, upper_bound i equal_range nie biorą udziału w rozwiązywaniu przeciążenia, chyba że nie istnieje typ Compare :: is_transparent .

n3421 zawiera przykład „przezroczystych funktorów operatora” .

Pełny kod jest tutaj .

Stephan T Lavavej opowiada o problemach, w których kompilator tworzy elementy tymczasowe, oraz o tym, jak jego propozycja przezroczystych funktorów operatorowych rozwiąże to w języku c ++ 1y

GoingNative 2013 - nie pomagaj kompilatorowi (około godziny)