C++ Programmier Interview: Wie wuerdet ihr einen Stack implementieren?

Nexus schrieb:

Nathan, das ist zwar eine interessante Idee, aber die API von Hash-Containern unterscheidet sich doch etwas. Hier enthalten die Abschnitte "Bucket interface", "Hash policy" und "Observers" alles spezifische Methoden. Dazu kommt, dass die Anforderungen an den Typen unterschiedlich sind ( operator< vs. operator== und std::hash ).

Das ginge rein theoretisch. std::set_relationstd::less bzw. std::set_relation<std::is_equal, std::hash> als Vergleich, mymap.get_backend().bucket_size() und mymap.get_backend().rehash(). Macht auch Sinn da, weil das sind low-level-operationen.

lower_bound tut schon mehr weh.

Ich seh aber den Punkt nicht, in einer Sprache mit Templates ist der Klassenname völlig egal. Und abgesehen davon, sind map<A> und map<B> sowieso zwei völlig unterschiedliche Typen. Ein Problem gibt es nur dann, wenn das Interface nicht mehr einheitlich ist (push vs push_back etc.)

Nathan

Nexus schrieb:

Nathan, das ist zwar eine interessante Idee, aber die API von Hash-Containern unterscheidet sich doch etwas. Hier enthalten die Abschnitte "Bucket interface", "Hash policy" und "Observers" alles spezifische Methoden. Dazu kommt, dass die Anforderungen an den Typen unterschiedlich sind ( operator< vs. operator== und std::hash ).

Das ist mir bewusst.
Aber bspw. eine map ist eine Abstraktion!
Eine map ist ein Container in dem man Werte nicht anhand Indices sondern anhand beliebigen Keys auffindet.
Implementierungen sind binärer Baum oder Hashtable. Die Implementierung selber ist - genauso wie bei stack/queue - für das Konzept einer map irrelevant.
Die map als Abstraktion stellt auch keine Anforderungen an Typen. Nur die Implementierung. Und der der die Implementierung festlegt ist konzeptuell auf einer anderen Eben als eine simple map und kann dann auch Anforderungen an die Typen stellen.

fröhlicher wanderer schrieb:

Nathan schrieb:

Ich bin ehrlich gesagt enttäuscht, dass die für Hashsupport neue Klassen eingebaut haben.

Erklär mir mal, wie man so Dinge wie lower/upper_bound handhaben würde. std::unordered_map vs std::[ordered_]map bezeichnen ganz unterschiedliche Dinge, die gehören schon in unterschiedliche Klassen.

Meinst du lower_bound Member?
Die können dann natürlich nicht merh drin sein. Eine map bestimmt keine Ordnung der einzelnen Elemente.
Wohl aber der darunterliegende binary_tree, den man natürlich auch standalone verwenden kann.
Und std::map vs unordered_map sind nur deswegen unterschiedliche Dinge, weil das Interface sehr von der Implementierung geprägt wird.
Mein Adapter hätte nur die generellen insert/erase Funktionen (ggf. ohne Iterator, weil Hint Implementierungsabhängig), den operator[] und size()/empty().

Nathan schrieb:

Eine map ist ein Container in dem man Werte nicht anhand Indices sondern anhand beliebigen Keys auffindet.

Hey, wozu überhaupt Container?

std::list = std::map mit std::front und std::back als Keys.
std::vector = std::deque = std::map mit ints als Keys
std::stack = std::map mit std::special_back als Key
std::queue = std::map mit std::special_back, std::special_front als Keys
...

Nathan

ad absurdum schrieb:

Nathan schrieb:

Eine map ist ein Container in dem man Werte nicht anhand Indices sondern anhand beliebigen Keys auffindet.

Hey, wozu überhaupt Container?

std::list = std::map mit std::front und std::back als Keys.
std::vector = std::deque = std::map mit ints als Keys
std::stack = std::map mit std::special_back als Key
std::queue = std::map mit std::special_back, std::special_front als Keys
...

Nein, ich meine das umgekehrt.
map ist die Abstraktion und die vector und Co die Implementierung.

Nexus

Nathan schrieb:

Das ist mir bewusst.
Aber bspw. eine map ist eine Abstraktion!

Du kannst ja immer noch einen Adapter abstract_map schreiben, der im Hintergrund verschiedene Implementierungen zulässt. Finde ich persönlich sauberer als direkt nur einen Container anzubieten und das API auf Biegen und Brechen zusammenzuwürgen.

ad absurdum schrieb:

Hey, wozu überhaupt Container?

Die Idee ist gar nicht so abwegig. Wie mächtig assoziative Arrays/Maps/Tabellen sind, zeigt Lua z.B. sehr schön.

Nathan

Nexus schrieb:

Nathan schrieb:

Das ist mir bewusst.
Aber bspw. eine map ist eine Abstraktion!

Du kannst ja immer noch einen Adapter abstract_map schreiben, der im Hintergrund verschiedene Implementierungen zulässt. Finde ich persönlich sauberer als direkt nur einen Container anzubieten und das API auf Biegen und Brechen zusammenzuwürgen.

Naja, wäre stack kein Adapter gäb es garantiert auch einen vector_stack mit reserve und Co und einen list_stack o.ä.
Höhere Abstraktion bedeutet eben auch anderes Interface.

BTW: Ich hab in meinem 1500 Beitrag schlecht über das Standardisierungskomitee geredet. Juchhu!

fröhlicher wanderer schrieb:

SeppJ schrieb:

Weil das eben kein Implementierungsdetails ist. Das ist die Schnittstelle und der ganze Sinn, warum es überhaupt ein Stack-Template gibt.

Im Gegenteil, es stellt sich die Frage, wozu es einen Adapter braucht, der einheitliche Schnitstellen (push_back, pop_back) in uneinheitliche (push, pop) wrappt und keinerlei Zugriff auf die darunterliegenden, wichtigen, Funktionen erlaubt (wenn man dann notgedrungen wechselt, regt einen dieses pop/push gleich doppelt auf).

std::stack kann man mit std::queue in die Tonne rühren, es würde sie niemand vermissen.

Als ich noch viel in C++ programmierte kam in mir auch öfter das Gefühl auf, dass die stl nur einen ziemlich experimentellen Status hat.

Ich programmiere auch C++ nur weil es die ultimative Herausforderung ist. Noch nie war es so schwer, auf so viele Sachen achten zu müssen. Für Kunden würde ich niemals in C++ ein neues Projekt anfangen. Wenn es wirklich mal bei einem Projekt auf extreme Geschwindigkeit ankommen würde, was noch nie bei mir der Fall war, so würde ich eher die Performancekritischen-Teile auslagern.

C++ ist ein nettes Hobby, aber freiwillig sollte man es beruflich nicht mehr verwenden. Ganz einfach deshalb, weil es bessere Werkzeuge gibt. Immer nur das Schweizer-Messer raus holen ist nicht professionell.

Da hast Du vollkommen Recht. Die Gui schreibe ich in letzter Zeit in PHP und das OS abstrahiere ich mit JAVA. So habe ich stärkste aus allen Welten.

Nexus

Z schrieb:

Als ich noch viel in C++ programmierte kam in mir auch öfter das Gefühl auf, dass die stl nur einen ziemlich experimentellen Status hat.

Die STL ist, gerade für ihre Zeit, wohl eine der am besten designten Container-Bibliotheken. Die Entkopplung von Containern, Algorithmen und Iteratoren ist bis heute extrem mächtig und nützlich. Bei der Entwicklung der STL wurden extrem viele Punkte berücksichtigt, um möglichst keine Einbussen an Generizität und Performance zu haben. Oft merkt man davon als Anwender nicht viel. Vergleich das z.B. mit den Java-Collections, wo du sehr tiefe Hierarchien hast, Stack von Vector erbt und massiv Code dupliziert wird...

Wenn dich die Hintergründe der STL tatsächlich interessieren, schau vielleicht mal Alexander Stepanovs "Notes On Programming" an.

Zeus

Nexus schrieb:

... Vergleich das z.B. mit den Java-Collections, wo du sehr tiefe Hierarchien hast, Stack von Vector erbt und massiv Code dupliziert wird...

Was bitte ist für dich sehr tief?

decimad schrieb:

Da hast Du vollkommen Recht. Die Gui schreibe ich in letzter Zeit in PHP und das OS abstrahiere ich mit JAVA. So habe ich stärkste aus allen Welten.

Ja genau, nur diese beiden Möglichkeiten gibt es. Entweder C++ oder Desktop-Anwendungen in PHP

Obwohl es heute fast mehr Webanwendungen wie Denktopanwendungen gibt, zusätzlich rücken die Apps immer mehr auf. Würde mich nicht wundern wenn in PHP und Java weit mehr Anwendungen geschrieben werden als in C++.

Nexus

Zeus schrieb:

Was bitte ist für dich sehr tief?

"Sehr" ist vielleicht übertrieben, aber der Punkt ist, dass Java-Collections mehrere Vererbungsebenen (durchschnittlich etwa 5) und implementierte Interfaces haben, während die STL-Container ganz ohne Basisklassen auskommen.

Beispiel Stack<E> :

Basisklassen:
`Vector<E>

AbstractList<E>

AbstractCollection<E>

Object`

Implementierte Interfaces:
`Serializable

Cloneable

Iterable<E>

Collection<E>

List<E>

RandomAccess`

-> Quelle

Marthog

asdfsdf schrieb:

Obwohl es heute fast mehr Webanwendungen wie Desktopanwendungen gibt, zusätzlich rücken die Apps immer mehr auf. Würde mich nicht wundern wenn in PHP und Java weit mehr Anwendungen geschrieben werden als in C++.

Das ist doch schon seit längerem so. Allerdings werden große Anwendungen (Browser, Compiler, Interpreter, Textverarbeitungen, große 3d-Spiele) in C++ geschrieben und daran wird sich wohl auch in Zukunft nicht viel ändern, weil man die statische Programmstruktur und Geschwindigkeit braucht.

hustbaer

Wirklich grosse Anwendungen werden denke ich kaum welche (ausschliesslich oder grösstenteils) in C++ geschrieben.
Sondern in ABAP, X++ oder ähnlichen Verbrechen an der Menschheit.

Ausgenommen vielleicht Betriebssysteme. Wobei da auch ein riesen Teil C ist. (Die Linusche weigert sich ja auch weiterhin hartnäckig gegen C++, weil C++ Programmierer ja alle schlecht sind, *hust*, ja Linusch, wir sind alle schlecht.)

Mechanics

hustbaer schrieb:

Wirklich grosse Anwendungen werden denke ich kaum welche (ausschliesslich oder grösstenteils) in C++ geschrieben.

Ah ja, ich denk schon. Open Office ist C++ und ist schon sehr groß. Ich denke, viele CAD Systeme sind in C++ geschrieben (z.B. bei NX geh ich von C++ aus), sowas wie Photoshop, Premiere usw. wahrscheinlich auch. Unsere Software ist C++
Ich glaub jetzt nicht, dass einzelne ABAP Module so wirklich groß sind. Vielleicht die, die direkt von SAP kommen, aber das ist halt die Ausnahme. Sonst stell ich die mir nicht so wahnsinnig groß vor.

hustbaer

Ne, die einzelnen Module vermutlich nicht.
Ich dachte da eher an das gesamte SAP Paket
(Und da greift so viel ineinander, dass man das Ding mMn. schon als ein grosses Ganzes betrachten kann bzw. eher fast muss.)

Mechanics

Aber dann ist SAP nur ein Programm, auch wenn das jetzt sehr groß ist, würd ich nicht behaupten, dass die meisten großen Programme ABAP sind.

Übrigens, ist kann zwar beides nicht, aber ist X++ nicht doch um einiges "besser" als ABAP? ABAP zieht seit 40 Jahren alle Legacy Features mit, X++ ist relativ modern und die haben versucht, paar interessante Sprachkonstrukte aufzunehmen.

Nexus schrieb:

Z schrieb:

Als ich noch viel in C++ programmierte kam in mir auch öfter das Gefühl auf, dass die stl nur einen ziemlich experimentellen Status hat.

Die STL ist, gerade für ihre Zeit, wohl eine der am besten designten Container-Bibliotheken. Die Entkopplung von Containern, Algorithmen und Iteratoren ist bis heute extrem mächtig und nützlich. Bei der Entwicklung der STL wurden extrem viele Punkte berücksichtigt, um möglichst keine Einbussen an Generizität und Performance zu haben. Oft merkt man davon als Anwender nicht viel.

Es mögen ja die Designziele der STL gewesen sein, dass möglichst viele theoretische Informatiker sich vor Ehrfurcht niederwerfen und zu weinen anfangen. Ich war halt nur einfacher Anwender der sich nie großartig um Implementierungsdetails der STL gekümmert hat. Und in einigen Fällen zickte die STL ziemlich rum. Vermutlich hätte man es mit etwas Aufwand irgendwie hinbekommen, aber jedes Mal boten sich Alternativen an, die gleich reibungslos funktionierten, weshalb ich ständig den Eindruck hatte, dass sich die STL in einem frühen Beta-Stadium befindet.

Das ist aber nur mein persönlicher Eindruck. Wenn man auf die STL angewiesen ist und lernt ihre Macken zu umschiffen, lässt sich damit sicherlich einiges anstellen, dass ziemlich nerdish ist.

Ich finde jedoch dass bei Libraries eine intuitive, einfache und sichere Anwendung im Vordergrund stehen sollte. Wenn man erst tagelang testen, lernen und experimentieren muss, um eine bestimmte Library-Funktion in den Griff zu bekommen, kann man sie auch gleich selbst programmieren.

Nexus

Was meinst du konkret? Ich finde die STL relativ intuitiv zu bedienen. Man muss sich aber an die Philosophie gewöhnen, dass nicht jeder Container jede noch so ineffiziente Operation direkt anbietet, und dass für viele Probleme die STL-Algorithmen (statt Memberfunktionen) angeboten werden.

Natürlich kann mans auch übertreiben, ich bin auch kein Fan von ostream_iterator oder for_each() + Lambda. Was mich am meisten nervt, ist dass man dauernd begin() / end() -Paare angeben muss... Da gibts wenigstens Ranges als möglichen Ausweg.