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

[Werner Salomon]

Warum schrieb:

Werner Salomon schrieb:

SeppJ schrieb:
Werner Salomon schrieb:

1.) mich fragt, was die genauen Anforderungen an die Stack-Implementierung sind (schneller push,pop-Wechsel -> array ) (wenig Speicherbedarf leerer Stacks -> einfach verkettete Liste)
Das hieße, er kennt die Technik nicht, mit der der STL-Stack beides hinbekommt. Ein Adaptor wäre mMn hier die beste Lösung. Das wäre auch die Lösung für das Problem des TE.

Es geht mir weniger darum, dass er/sei die Technik genau kennt (sollte er schon!).

Warum sollte ich ein internes Implementierungsdetail der Standard Bibliothek kennen?

Mit 'die Technik' war gemeint, dass der std::stack einen zweiten Container nutzt, um einen Stack zu realisieren. D.h. es geht gar nicht um ein Implementierungsdetail eines Containers im Standard, sondern lediglich um das Wissen, dass der std::stack ein sogenannter Container-Adapter ist.
Dieses Wissen kann man von jemanden der sagt, er sei versierter C++-Progger, verlangen. Wenn er es dann doch nicht weiß, so ist dass allein noch kein Problem.

Ich kann mich nur wiederholen: es geht mir primär darum, dass man sich intensiv mit den Anforderungen aus einander setzt. Auch eine Adapter-Lösung ist nicht zwangsläufig die 'beste' Lösung. Zusammen mit dem benötigten Container ist sie nämlich aufwendiger als z.B. eine reine einfach-verkettete-Liste-Lösung. Es ist in Summe schlicht mehr Code - wenn auch nicht komplexer.
Die beste Lösung ist die, die die Anforderungen erfüllt.

Gruß
Werner

[decimad]

@Werner: Ich habe Dich vor allem bezüglich Deiner Beiträge zu streams in Erinnerung. Wenn Du ein Prüfling nicht magst, nutzt Du dieses Gebiet um sie/ihn zu zerstören?

[Werner Salomon]

decimad schrieb:

@Werner: Ich habe Dich vor allem bezüglich Deiner Beiträge zu streams in Erinnerung. Wenn Du ein Prüfling nicht magst, nutzt Du dieses Gebiet um sie/ihn zu zerstören?

.. Äh! derartiges Verhalten ist mir fremd. Der arme Mensch hat mir ja zunächst mal nichts getan, auch wenn mir aus welchen Gründen auch immer seine Nase missfällt.

Aus welcher Motivation heraus stellst Du diese Frage?

Ich bemühe mich eher nach der Devise zu handeln:
Leben & leben lassen
Seid nett zueinander

Gruß
Werner

[decimad]

Ich möchte Dir, vor allem in Anbetracht Deiner Verhaltensweise hier, nicht unterstellen, Du seist ein Unmensch - sorry falls das so rüberkam Mir kam nur gerade amüsiert der Gedanke, wie ich da wohl zusammenbrechen würde, und das wahrscheinlich auch in 10 Jahren...

[hustbaer]

Ist es üblich unter "Stack" ganz abstrakt einfach abstrakte LIFO Queue zu verstehen? Für mich gehört da schon dazu dass das Ding als Array aufgebaut ist. Eben wegen cachefreundlich und so. Sonst könnte man ja gleich LIFO Queue sagen.

Und wenn ich Interviewer wäre, dann würde mich vermutlich am meisten interessieren ob der Bewerber es schafft seine Implementierung auch nur halbwegs fehlerfrei hinzubekommen. Stichwort Corner-Cases usw. Da hab ich nämlich schon einige Schauergeschichten erlebt.

[std__stack unwissender]

SeppJ schrieb:

Werner Salomon schrieb:

1.) mich fragt, was die genauen Anforderungen an die Stack-Implementierung sind (schneller push,pop-Wechsel -> array ) (wenig Speicherbedarf leerer Stacks -> einfach verkettete Liste)

Das hieße, er kennt die Technik nicht, mit der der STL-Stack beides hinbekommt. Ein Adaptor wäre mMn hier die beste Lösung. Das wäre auch die Lösung für das Problem des TE.

Welche Technik? Ich kenne sie nicht.

Ich würde einen Stack implementieren, wo ich ein Array dynamisch alloziiere. Wird das Array beim letzten pop gelöscht, ist der Speicherbedarf minimal. Allerdings ist der erste push dann langsamer. Es ist also meines Erachtens eine Abwägung, welches der Ziele wichtiger ist.

[SeppJ]

std__stack unwissender schrieb:

SeppJ schrieb:

Werner Salomon schrieb:

1.) mich fragt, was die genauen Anforderungen an die Stack-Implementierung sind (schneller push,pop-Wechsel -> array ) (wenig Speicherbedarf leerer Stacks -> einfach verkettete Liste)

Das hieße, er kennt die Technik nicht, mit der der STL-Stack beides hinbekommt. Ein Adaptor wäre mMn hier die beste Lösung. Das wäre auch die Lösung für das Problem des TE.

Welche Technik? Ich kenne sie nicht.

Na, ein Adaptor! Dem Stacktemplate wird einfach gesagt, welche Datenstruktur es nehmen soll. Der Stack implementiert dann bloß die Schnittstelle (push, pop, top, size und ähnliches). Dafür verlangt er nur, dass die unterliegende Datenstruktur gewisse Funktionen bietet. Für den Stack der STL reichen push_back, pop_back und back. vector, deque und list aus der STL erfüllen bereits diese Anforderung (man kann natürlich auch eigene Container nehmen), daher kann man jeden davon wählen, was dann zu jeweils unterschiedlichen Eigenschaften des Stacks führt (welche, das hat Werner Salomon schon erklärt).

[Gast]

WasIstWas schrieb:

Hi,

in einem Programmier Interview sollte ich einen Stack implementieren. Ich habe damals eine Implementierung mit Zeigern gegeben.Inzwischen denke ich aber eine implementierung mit einem Array ist vielleicht effektiver. Wegen der Cache peformance.

Ob du ...
stack[stackptr++] = neues_element;
oder
*stackptr++ = neues_element;
benutzt, ist prinzipiell egal. Der erzeugte Maschinencode ist sehr oft identisch bzw. hängt davon ab wo sich der Stack-Speicher physikalisch befindet.

[SeppJ]

Z schrieb:

WasIstWas schrieb:

Hi,

in einem Programmier Interview sollte ich einen Stack implementieren. Ich habe damals eine Implementierung mit Zeigern gegeben.Inzwischen denke ich aber eine implementierung mit einem Array ist vielleicht effektiver. Wegen der Cache peformance.

Ob du ...
stack[stackptr++] = neues_element;
oder
*stackptr++ = neues_element;
benutzt, ist prinzipiell egal. Der erzeugte Maschinencode ist sehr oft identisch bzw. hängt davon ab wo sich der Stack-Speicher physikalisch befindet.

Ich glaube, er meint mit seiner Implementierung eine verkettete Liste.

[Gast]

SeppJ schrieb:

Ich glaube, er meint mit seiner Implementierung eine verkettete Liste.

Geht zwar auch, aber das ist dann das sprichwörtliche Schießen auf Spatzen mit Kanonen.

[fröhlicher wanderer]

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.

[Nexus]

fröhlicher wanderer schrieb:

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

Abstraktion? Du willst nur was auf den Stack oder in die Queue werfen und dich nicht um Reihenfolge o.Ä. kümmern. Wenn du beliebige Funktionen brauchst, nimmst du natürlich die vollwertigen Container. 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.

Aber ja, es gibt natürlich Situationen, in denen man plötzlich merkt, dass man doch mehr benötigt... Bei mir war das vor allem Iteration.

fröhlicher wanderer schrieb:

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

Gerade std::queue konnte ich schon einige Male einsetzen. std::stack habe ich bisher primär benutzt, um eine rekursive Implementierung in eine iterative umzubauen. std::priority_queue so gut wie nie.

[SeppJ]

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

Das (also push, pop, peek) ist doch die einheitliche Schnittstelle! Erstens ist es die übliche Bezeichnung der Funktionen beim Stack. Zweitens ist dies eine Vereinheitlichung der Schnittstelle von sehr unterschiedlichen Containern. list und vector haben eben kein einheitliches Interface. Ein vector hat kein eigenes sort, eine list kein at. 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)

[Nathan]

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.

[SeppJ]

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.

[Nathan]

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.

[fröhlicher wanderer]

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::queue konnte ich schon einige Male einsetzen. std::stack habe ich bisher primär benutzt, um eine rekursive Implementierung in eine iterative umzubauen. std::priority_queue so 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.

[Nexus]

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

[fröhlicher wanderer]

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