Co to są przezroczyste komparatory?


106

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?


Na przykład zobacz ten opis cppreference . A teraz czuję się głupio, bo zwracam uwagę na słowo „ szablon funkcji
składowej

5
Prawdopodobnie powiązane: stackoverflow.com/questions/18939882/ ...

cppreference ma również notkę na en.cppreference.com/w/cpp/utility/functional/less_void
Cubbi

Odpowiedzi:


60

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).


3
Hej, czy to ty byłeś tym, do którego STL powiedział: „Oczywiście, że możesz dokonać w swojej głowie domyślnej dedukcji argumentów” w przemówieniu, które łączy woolstar?
Kerrek SB

10
Nie, nie było mnie tam, ale są ludzie, którzy mają w głowach znacznie więcej zgodnych kompilatorów niż ja :)
Jonathan Wakely

Wydaje mi się, że „operator diamentu” odnosi się do <>powiązanej propozycji, ale ta propozycja nie wprowadziła <>- jest to istniejąca składnia dla pustej listy parametrów szablonu. „Diamentowe funktory operatorów” byłyby nieco mniej zagmatwane.
Qwertie

33

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.


Dzięki - zobacz mój komentarz do drugiego pytania: Czy domyślnie otrzymujesz przezroczyste zachowanie?
Kerrek SB

8
@KerrekSB: przezroczyste zachowanie jest włączone, gdy is_transparentjest zdefiniowane w obiekcie funkcji porównania zgodnie z 23.2.4 [Associative.reqmts] paragraf 13. Domyślne obiekty funkcji porównania są std::less<Key>zgodne z 23.4.2 [associative.map.syn] i 23.4. 3 [associative.set.syn]. Według 20.10.5 [Porównanie] pkt 4 ogólny szablon na std::less<...>nie nie określają typ zagnieżdżony is_transparentale std::less<void>specjalizacja robi. Oznacza to, że nie, domyślnie nie otrzymujesz przezroczystego operatora.
Dietmar Kühl

Masz jakiś pomysł na nazewnictwo? Mam na myśli dlaczego is_transparent?
plasmacel

Szukasz „konkretnego przykładu, w którym jest to przydatne”? Oto mój przypadek użycia
spraff

19

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 .


1
Czy std::set<std::string>faktycznie korzyści płyną z „przejścia char const *przez”, czy też trzeba to zrobić std::set<std::string, std::less<>>?
Kerrek SB

@Kerrek Myślę, że "przekazanie znaku const *" było problemem, którego próbowali uniknąć, jeśli się nie mylę. Spójrz na sformułowanie:With the change proposed by N3465 the std::set::find() function would be an unconstrained template which would pass the const char* through to the comparator function, std::less<std::string>, which would construct a std::string temporary for every comparison. The LWG considered this performance problem to be a serious issue.

Twój cytat i mój z paragrafu 13 mówią odwrotnie: „chyba że typ istnieje / nie istnieje” ...?!
Kerrek SB

4
@KerrekSB, to moja wina, N3657 miał powiedzieć „istnieje”, ale napisałem „nie istnieje”… to była spóźniona praca napisana w ostatniej chwili. Projekt normy jest poprawny.
Jonathan Wakely

3
Tak, to może być wyraźniejszy zacytować co mam na myśli , aby powiedzieć, co tak naprawdę nie powiedział w czasie :)
Jonathan Wakely

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.