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

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

[ad absurdum]

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!

[Gast]

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.