Wie funktioniert std::less

Wie ich schonmal in einem anderen Beitrag geschrieben habe, möchte ich selbst zur Übung einen AVL-Baum implementieren und scheitere aufgrund meiner mangelnden Kenntnisse in C++ schon beim Interface.

Das Hauptproblem ist für mich, wie ich der Klasse eine Funktion oder Klasse mitgeben kann, so dass auch Typen verglichen werden können, die an sich die Vergleichsoperatoren nicht mitbringen.

zB Möchte ich Komplexe Zahlen in meinem AVL-Baum speichern können, und dann komponenentenweise zunächst Realteil und dann Imaginärteil vergleichen.

Nun hat SeppJ mir schon den Tipp gegeben, mich an der STL zu orientieren und wenn ich es richtig sehe, wird dort

class Compare = less<T>

für solche Zwecke angegeben.

Allerdings verstehe ich nun nicht ganz wie das funktioniert.
Ich habe http://en.cppreference.com/w/cpp/utility/functional/less mal durchgelesen, aber klar wird mir dabei nichts.

Wie könnte ich jetzt zB meinen AVL-Baum aufbauen und verwenden, damit ich meine imaginäre Klasse Komplexe_Zahl einfügen kann?

Hier mal ein simples less (was nicht ganz äquivalent zu std::less) ist:

template <typename T>
struct less {
  bool operator()(const T& lhs, const T& rhs) const {
    return lhs < rhs;
  }
};

int main()
{
  int a=4, b=7;
  less<int> l;
  std::cout << a << "<" << b << ": " << std::boolalpha << l(a, b) << '\n';
  std::swap(a, b);
  std::cout << a << "<" << b << ": " << std::boolalpha << less<int>()(a, b) << '\n';
}

Ist damit klar, wie man less benutzt?

Ramanujan

template <class T, class Compare = std::less<T>>
class AVL  {
    // ...
}

typedef std::complex<double> Complex
struct cplxComp {
    bool operator()(const Complex& a, const Complex& b) {
        if (a.real == b.real)
            return a.real < b.real;
        else 
            return a.imag < b.imag;
    }
}

int main() {
    AVL<int> a;
    AVL<Complex, cplxComp> b;
}

alles ungetestet

Ramanujan schrieb:

bool operator()(const Complex& a, const Complex& b) {
        if (a.real == b.real)
            return a.real < b.real;
        else 
            return a.imag < b.imag;
    }
}

Bitte nicht die hardgecodeten Pair-Vergleiche weiterverbreiten. Das muss heutzutage so aussehen:

bool operator()(const Complex& a, const Complex& b) {
        return std::tie(a.real, a.imag) < std::tie(b.real, b.imag);
    }

SeppJ

shisha schrieb:

Wie könnte ich jetzt zB meinen AVL-Baum aufbauen und verwenden, damit ich meine imaginäre Klasse Komplexe_Zahl einfügen kann?

Das hat nichts mit std::less zu tun, sondern eher damit, wie du Vergleichsfunktionen übergeben kannst, oder? std::less ist nur ein simpler Wrapper um den Operator<.

Da du anscheinend nicht weißt, wie man die STL benutzt (keine gute Voraussetzung, wenn man selber Container programmieren will):

#include <set>
#include <functional>

bool bar(int a, int b)
{
  return a < b;
}

struct Functor
{
  bool operator()(int a, int b) const { return a < b; }
};

int main()
{
  std::set<int> set_int_mit_standardvergleichsfunktion;

  std::set<int, std::greater<int> > set_int_mit_std_greater;

  std::set<int, bool (*)(int, int)> set_int_mit_funktionszeiger(bar);
  // oder einfacher:
  std::set<int, decltype(&bar)> set_int_mit_funktionszeiger2(bar);

  auto lambda = [](int a, int b) {return a < b;};
  std::set<int, decltype(lambda)> set_int_mit_lambda(lambda);

  Functor func;
  std::set<int, Functor> set_int_mit_funktionsobjekt(func);
  // oder
  std::set<int, decltype(func)> set_int_mit_funktionsobjekt2(func);
  // oder mit default-konstruierter Instanz:
  std::set<int, Functor> set_int_mit_funktionsobjekt3(); 
}

Wie schafft std::set diese unglaubliche Flexibilität? Ziemlich trivial:

#include <iostream>
#include <functional>

template<typename T, class Comp = std::less<T> > bool foo(T a, T b, const Comp& comp = Comp() ) // Das ist auch schon das ganze Geheimnis
{
  return comp(a, b);
} 

bool bar(int a, int b)
{
  return a < b;
}

struct Functor
{
  bool operator()(int a, int b) const { return a < b; }
};

int main()
{
  Functor func;
  std::cout << "foo(1,2)  mit Standardvergleichsfunktion: " << foo(1, 2) << '\n'
            << "foo(1,2)  mit std::greater: " << foo(1, 2, std::greater<int>() ) << '\n'
            << "foo(1,2)  mit Funktionszeiger: " << foo(1, 2, bar) << '\n'
            << "foo(1,2)  mit lambda: " << foo(1, 2, [](int a, int b) {return a < b;} ) << '\n'
            << "foo(1,2)  mit Funktionsobjekt: " << foo(1, 2, func) << '\n';
}

Du hast immer noch nicht gesagt, warum du eine AVL-Baum implementieren möchtest, anstatt einfach std::set zu nutzen.

Hat er doch geschrieben, zur Übung.

SeppJ

deedbeef schrieb:

Hat er doch geschrieben, zur Übung.

Ahh, ok. Im letzten Thread klang das noch ganz anders.

Gerade zur Übung fände ich es gut, das STL-Interface wirklich komplett durch zu ziehen. Was uns zum nächsten Schritt bringt: Allokatoren . Ich glaube, die habe ich selber erst so richtig verstanden, als ich mal einen STL-konformen Container programmiert habe.

Aber: Das schöne an all dem ist ja, dass man im Prinzip erst einmal alles mit int, < und new programmieren kann, falls man sich dabei wohler fühlt. Wenn der Code erst einmal steht, kann man dann durchgehen und nach und nach alles ersetzen. Erst int durch einen Templateparameter, dann alle Vorkommen von < durch eine allgemeine Vergleichsfunktion und am Ende alle new/delete durch die entsprechenden Allokatorfunktionen. Wobei letzteres wohl der komplizierteste Schritt ist, da new<->Allokator keine exakte 1:1 Korrespondenz ist.

SeppJ schrieb:

Was uns zum nächsten Schritt bringt: Allokatoren . Ich glaube, die habe ich selber erst so richtig verstanden, als ich mal einen STL-konformen Container programmiert habe.

Allokatoren sind eine schöne Idee, aber die Umsetzung in der STL ein grosses Fehldesign. Ich finde es besser, mal ein paar eigene Memory-Pools zu schreiben und sich dann zu überlegen, wie man diese allgemein in Containern nutzen könnte ohne sich von der STL fehlleiten zu lassen.

SeppJ

akkolator schrieb:

SeppJ schrieb:

Was uns zum nächsten Schritt bringt: Allokatoren . Ich glaube, die habe ich selber erst so richtig verstanden, als ich mal einen STL-konformen Container programmiert habe.

Allokatoren sind eine schöne Idee, aber die Umsetzung in der STL ein grosses Fehldesign. Ich finde es besser, mal ein paar eigene Memory-Pools zu schreiben und sich dann zu überlegen, wie man diese allgemein in Containern nutzen könnte ohne sich von der STL fehlleiten zu lassen.

Also nach meiner Uhr ist 2007 schon lange vorbei. Stell mal ein paar Jahre vor. Insbesondere wenn du an den Jahren 2011 und 2014 vorbei kommst, sollte der Wecker bimmeln.

SeppJ schrieb:

akkolator schrieb:

SeppJ schrieb:

Was uns zum nächsten Schritt bringt: Allokatoren . Ich glaube, die habe ich selber erst so richtig verstanden, als ich mal einen STL-konformen Container programmiert habe.

Allokatoren sind eine schöne Idee, aber die Umsetzung in der STL ein grosses Fehldesign. Ich finde es besser, mal ein paar eigene Memory-Pools zu schreiben und sich dann zu überlegen, wie man diese allgemein in Containern nutzen könnte ohne sich von der STL fehlleiten zu lassen.

Also nach meiner Uhr ist 2007 schon lange vorbei. Stell mal ein paar Jahre vor. Insbesondere wenn du an den Jahren 2011 und 2014 vorbei kommst, sollte der Wecker bimmeln.

Nur weil einige wenige Punkte repariert worden sind, heisst das nicht, dass das Dokument veraltet ist.

std STL allocators are painful to work with and lead to code bloat and sub-optimal performance.

Allocators are rebound by containers to one or more additional types -- types which the user cannot know in any portable way. Thus the author of an allocator cannot know what it will actually be asked to allocate and construct. [...]

Containers do not let you access their allocators; they only give you copies of their allocators. [Was u.A. heisst, dass ein Allokator nur aus einem Pointer zur eigentlichen Implementation bestehen darf und keine Value-Semantik sondern eher shared_ptr-Semantik haben soll.]

The STL puts an emphasis on correctness before practicality and performance. This is an understandable policy but in some cases (particularly std::allocator) it gets in the way of usability and optimized performance.

Kannst du

Einen std::vector mit SSO bauen?
Den Allokator aus einem Interface einfach type-erasen (z.B. in einer virtuellen Methode)?
Einen Allokator schreiben, der mehr Features unterstüzt, wie z.B. realloc oder aktives verschieben von Objekten?

SeppJ

Nein, das geht noch nicht, aber die dicksten Fehler wurden mittlerweile berichtigt. Das, was dir jetzt noch fehlt, ist zwar tatsächlich Schade, dass es (noch) nicht geht, aber gegenüber dem alten Allokatormodell sind das doch nur Kleinigkeiten.

Einen std::vector mit SSO bauen?

Das ist doch eine Sache von std::vector, nicht des Allokators. Ein vector, der SSO erlaubt, hätte eben andere Eigenschaften als einer ohne. Es ist kein Schwarz-Weiß, welche der Eigenschaften wünschenswerter ist. Da der C++98-vector diese Eigenschaften bereits vorgeschrieben hat und sich so einiger Code darauf verlässt, kann man sie auch nicht einfach ändern.

Skym0sh0

Sorry Jungs dass ich frage, aber was ist SSO?

Mir fällt da grad spontan nur Single-Sign On ein, aber das hat eigentlich ja nur was mit Anmelden an (Web-)Systemen zu tun?!

(Und das ist auch das, was man hauptsächlich per Google findet)

volkard

Skym0sh0 schrieb:

Sorry Jungs dass ich frage, aber was ist SSO?
Mir fällt da grad spontan nur Single-Sign On ein, aber das hat eigentlich ja nur was mit Anmelden an (Web-)Systemen zu tun?!
(Und das ist auch das, was man hauptsächlich per Google findet)

Wir alle haben manchmal google kaputt.

Probier mal

c++ sso

Skym0sh0

Aha Small String Optimization, das sagt mir wieder was

Ja, Google ist doch nicht so allwissend, wenn man nur dummes/unvollständiges Zeug eingibt. Oder einfach nicht gut genug sucht