Verständnisfragen SFINAE

DocShoe

Hallo zusammen,

ich habe auf stackoverflow einen Codeschnipsel gefunden, der für alle Containertypen der STL eine erase_if optimal implementiert:

   // https://stackoverflow.com/a/46159781
template<std::size_t I>	struct chooser : chooser<I-1> {};
template<> 	 	struct chooser<0> {};

// (1) Implementierung für std::list
template<typename Container, typename Predicate>
static auto erase_if( Container& container, Predicate&& predicate, chooser<3> )
       -> decltype( void( container.remove_if( std::forward<Predicate>( predicate ) ) ) )
{
   container.remove_if( std::forward<Predicate>( predicate ) );
}

// Implementierung für sets, multisets, maps und multimaps
template<typename Container, typename Predicate>
static auto erase_if( Container& container, Predicate&& predicate, chooser<2> )
       -> decltype( void( container.find( std::declval<typename Container::key_type const&>() ) ) )
{
   for( auto it = std::begin( container ), end = std::end( container ); it != end; )
   {
      if( predicate( *it ) ) it = container.erase( it );
      else                   ++it;
   }
}

template<typename Container, typename Predicate>
static void erase_if( Container& container, Predicate&& predicate, chooser<1> )
{
   container.erase( std::remove_if( std::begin( container ), std::end( container ), std::forward<Predicate>( predicate ) ),
                                    std::end( container ) );
}

template<typename Container, typename Predicate>
static void erase_if( Container& container, Predicate&& predicate )
{
   return erase_if( container, std::forward<Predicate>( predicate ), chooser<10>() );
}

Im Großen und Ganzen habe ich das verstanden:

std::list
Das template hat auto als Rückgabetyp damit der Rückgabetyp über decltype(...) bestimmt werden kann. Da nur std::list den member remove_if besitzt kann das Template nur für std::list instanziiert werden und für keinen anderen Containertypen, daher wird dieses template nur für std::list implementiert und aufgerufen.
alle map/set Containertypen:
Analog zu 1), allerdings mit set/map member find.
bewährtes erase-remove idiom

Und jetzt die Fragen

was genau ist der Typ von decltype( void( container.remove_if( std::forward<Predicate>( predicate ) )?
wozu wird das declval in decltype( void( container.find( std::declval<typename Container::key_type const&>() ) ) ) benötigt, reicht da nicht auch decltype( void( container.find( typename Container::key_type const&>() )) ) aus?
wozu wird chooser benötigt, steuert er nur die Reihenfolge der Instanziierungsversuche für das template? Angenommen ich habe

struct A {};
struct B : A {};
struct C : B, A {};

void f( A obj ) {} // f1
void f( B obj ) {} // f2

int main()
{
   c anC;
   f( anC ); 
}

f2 wird aufgerufen, weil C besser auf B (f2) matcht als auf A (f1)?

hustbaer

Der Typ ist void. Das Konstrukt filtert per SFINAE alles raus wo der Ausdruck container.remove_if( std::forward<Predicate>( predicate ) nicht kompilieren würde.
typename Container::key_type const&>() ist Quatsch. typename Container::key_type() macht nen Fehler wenn Container::key_type nicht default-konstruierbar ist. declval geht dagegen immer.
chooser steuert welche Funktion bei der Overload-Resolution ausgewählt wird. Ohne chooser wären die Signaturen der instanzierten Templates exakt gleich und die Overloads daher ambiguous.

DocShoe

Hallo Hustbär,

danke für die Antworten. Punkt zwei war natürlich Quatsch, habe beim Rauslöschen ein Klammerpärchen übersehen.
Ich verstehe die decltype-Anweisungen nicht, zb. decltype( void(container.remove_if(std::forward<Predicate>(predicate)))). Was für ein Konstrukt ist denn der void(container.remove_if(std::forward<Predicate>(predicate))) Teil? Angenommen ich hätte nur decltype(container.remove_if(std::forward<Predicate>(predicate)), dann bezeichnet decltype den Rückgabetyp des remove_if-Aufrufs. Aber wenn das noch in void(...) eingepackt wird verstehe ich das nicht mehr.
Hast du da vllt iwo nen Artikel, der das für Idioten erklärt?

Columbo

void(...) ist ein functional-style cast. Also einfach ein Ausdruck, der den Operanden (hier als Ellipse dargestellt) zu void konvertiert, damit der Typ, den decltype(void(...)) bezeichnet, void ist. Das ist dieselbe Klasse von Ausdruck wie string("asdf") oder vector{1, 2, 3}. Der einzige Anlass für diesen void Cast ist die Tatsache, dass der Rückgabewert der Funktion selbst void sein muss.

Um das ganze mal etwas kohärenter zu erklären: Wir haben eine Reihe von Methoden, um Elemente aus einem Container zu entfernen. chooser ist ein bekanntes Idiom, in welchem eine einfache Vererbungshierarchie (chooser<0> → chooser<1> → ...) eingesetzt wird, um eine Rangfolge in der overload resolution aufzuerlegen. Die optimale Methode wird vom Argument des Typen chooser<10> die minimale Anzahl an Vererbungsebenen hinaufsteigen (7) um zu chooser<3> zu konvertieren.

Allerdings ist die Instanz dieses (und der anderen spezialisierten) Funktionstemplates nur dann ein Kandidat, wenn der Ausdruck im decltype(void(...)) wohlgeformt ist. Als erstes scheiden also alle Funktionstemplates aus, deren Deduktion aufgrund des Ausdrucks fehlerhaft ist. Dann wird (dank Symmetrie) die Funktion ausgewaehlt, deren Parameter die tiefste Vererbungsebene von choose hat.

In C++17 koennte man das etwas eleganter schreiben, naemlich mittels if constexpr und is_detected.

DocShoe

Aaaaah, danke!
Den function-style cast kannte ich noch nicht, jetzt ergibt das alles Sinn.

Swordfish

@DocShoe T(...) ist im Prinzip das selbe wie ((T)...)

HarteWare

Die ganzen vereinfachten Funktionen für den vollen Container, also sort(vec) anstatt sort(vec.begin(), vec.end()) etc. sollten im Standard festgelegt sein, damit nicht jeder den Mist selbst definieren muss... Sind wir mal ehrlich, wie oft musstet ihr schon Mal nur einen Teil eines Containers sortieren?

wob

@HarteWare sagte in Verständnisfragen SFINAE:

Die ganzen vereinfachten Funktionen für den vollen Container, also sort(vec) anstatt sort(vec.begin(), vec.end()) etc. sollten im Standard festgelegt sein

Muss du halt eine ranges-Bibliothek wie range-v3 einbinden oder auf C++20 warten.

Swordfish

@wob sagte in Verständnisfragen SFINAE:

oder auf C++20 warten.

kommt das in C++20?

HarteWare

Ja ich freue mich auf C++20, GCC hat noch nicht mal C++17 ganz implementiert...

Unterfliege

@HarteWare tatsächlich? Ich dachte eigentlich, dass inzwischen alle (GCC, Clang und MSVC) vollständigen C++17 support haben. Welche Features fehlen denn beim GCC?

It0101

@Unterfliege
laut der Liste ist nicht nur GCC noch nicht "fertig".
https://en.cppreference.com/w/cpp/compiler_support

It0101

@HarteWare sagte in Verständnisfragen SFINAE:

Die ganzen vereinfachten Funktionen für den vollen Container, also sort(vec) anstatt sort(vec.begin(), vec.end()) etc. sollten im Standard festgelegt sein, damit nicht jeder den Mist selbst definieren muss... Sind wir mal ehrlich, wie oft musstet ihr schon Mal nur einen Teil eines Containers sortieren?

der Aufruf von std::sort mit den Iteratoren ist jetzt aber auch nicht soooo der Zeitfresser... Da wäre mir eine socket-bibliothek im C++Standard wichtiger, als eine Sort-Funktion die statt 3 Parametern nur 2 braucht...

wob

@It0101 sagte in Verständnisfragen SFINAE:

der Aufruf von std::sort mit den Iteratoren ist jetzt aber auch nicht soooo der Zeitfresser...

Es ist ja nicht nur sort. In den meisten Fällen operiere ich mit einem kompletten std::vector. Auch bei accumulate. Gut, bei lower_bound hat man öfter mal andere Grenzen. Aber sehr oft operiere ich doch auf dem ganzen Ding. Es ist auch nicht sooo der Zeitfresser, vector<int>::const_iterator in einer for-Loop zu schreiben. Dennoch ist auto wesentlich angenehmer. So auch hier. Von daher:

Ich weiß nicht, was genau von range-v3 im Standard gelandet ist, aber ich fand auch Projections ziemlich gut.

HarteWare

@Unterfliege Naja das ist halt ein Rant von mir, weil ich mal gerne std::from_chars verwendet hätte und dann mein Compiler mich angemault hat.

Was mich auch etwas nervt: Sachen wie std::fstream etc. haben keinen c-tor für std::string_view...