C++ Programmier Interview: Wie wuerdet ihr einen Stack implementieren?
-
Wo wir grad beim Thema Adapter sind:
std::map und set wären auch prima Adapter.
Man hat dann Container wie binary_tree, hash_table und sorted_vector (ggf. als sorted_container und ebenfalls ein Adapter) und kann schön die Implementierung austauschen.
Ich bin ehrlich gesagt enttäuscht, dass die für Hashsupport neue Klassen eingebaut haben.
-
Nathan schrieb:
Ich bin ehrlich gesagt enttäuscht, dass die für Hashsupport neue Klassen eingebaut haben.
Das lässt sich wohl im Nachhinein kaum mehr ändern. Im alten Standard war fest vorgeschrieben, wie set und map sich genau zu verhalten haben. Das kann man im Nachhinein nicht einfach ändern. Dazu gehört vor allem keine komplette Umgestaltung der Templateparameter.
-
SeppJ schrieb:
Nathan schrieb:
Ich bin ehrlich gesagt enttäuscht, dass die für Hashsupport neue Klassen eingebaut haben.
Das lässt sich wohl im Nachhinein kaum mehr ändern. Im alten Standard war fest vorgeschrieben, wie set und map sich genau zu verhalten haben. Das kann man im Nachhinein nicht einfach ändern. Dazu gehört vor allem keine komplette Umgestaltung der Templateparameter.
Die immer mit ihrer Kompatibilität.
-
Nexus schrieb:
Man verdeutlicht mit den Container-Adaptern die Verwendung und muss sich beim Anschauen des Codes keine Fragen wie "wie werden die Elemente jetzt eingefügt und gelöscht" stellen. Kleinere Schnittstellen sind einfacher und schneller zu verstehen.
Gut, das ist ein Argument. Stellt sich immer noch warum das uneinheltiche Interface.
Gerade
std::queuekonnte ich schon einige Male einsetzen.std::stackhabe ich bisher primär benutzt, um eine rekursive Implementierung in eine iterative umzubauen.std::priority_queueso gut wie nie.Der Punkt ist, dass du auch einfach std::deque hättest verwenden können. (Gilt natürlich nicht für priority_queue, die brauche ich regelmässig)
SeppJ schrieb:
Das (also push, pop, peek) ist doch die einheitliche Schnittstelle!
Aber wenn man einen std::stack vorliegen hat, dann weiß man genau, welche Schnittstelle er hat und braucht nicht zu wissen, was dahinter steht (und kann es somit später auch ändern, ohne Gefahr, dass man irgendwo mal inkompatible Schnittstellen haben könnte)
Das ist das gleiche Argument wie von Nexus.
Find ich aber überhaupt nicht tragisch. Wenn ich meine lokale Variable vom Typ std::vector<T> "stack" nenne, dann ändere ich die ggf. auf std::list ohne auch nur zu überlegen, ob da irgendwo ein at vorkam. Der Compiler teilts mir schon mit, wenn das doch nicht stimmen sollte. Und in dem Fall wäre ich mit std::stack ohnehin aufgeschmissen gewesen.
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.
-
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==undstd::hash).
-
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==undstd::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.)
-
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==undstd::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
...
-
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.
-
Nathan schrieb:
Das ist mir bewusst.
Aber bspw. eine map ist eine Abstraktion!Du kannst ja immer noch einen Adapter
abstract_mapschreiben, 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.
-
Nexus schrieb:
Nathan schrieb:
Das ist mir bewusst.
Aber bspw. eine map ist eine Abstraktion!Du kannst ja immer noch einen Adapter
abstract_mapschreiben, 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.
-
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.
-
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++.
-
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:
`SerializableCloneable
Iterable<E>
Collection<E>
List<E>
RandomAccess`
-
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.
-
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.)
