Hallo Zusammen,
ich habe eine Frage zu verketteten Listen.
Unter C++ lese ich oft bei Klassen folgende Definition:
list<CKlasse*> Klasse1
In C lese ich zum Thema verkettete Listen bzw. dynamische
Datenstrukturen z.B.
struct ....{
...
...
struct Struktur1 *next
}
gibt es da Unterschiede zwischen Verkettete Listen/Dynamische
Datenstrukturen und verkettete Listen in C++ mit "<list>"?
Michael schrieb: > gibt es da Unterschiede zwischen Verkettete Listen/Dynamische > Datenstrukturen und verkettete Listen in C++ mit "<list>"? ja. (Typsicherheit, Verwendung, Interface)
Die grundlegende Funktionsweise ist praktisch gleich. In C++ wird dir lediglich mit std::list eine fertige Implementation geboten, bei der du dich nicht um die Details kümmern musst. Mithilfe von templates ist die dann auch typsicher. Bei der Eigenimplementation einer verketteten Liste gibts halt so diverse Fallstricke. Der einzige wirkliche Unterschied besteht darin, dass wenn du z.B. eine std::list<int> hast, und einen Pointer auf ein Element holst - also ein "int*" - du anhand dieses Pointers nicht auf das nächste/vorherige Element schließen kannst. Bei diesen typischen C-Listen ist das anders - da sind die Listenelemente die "Struktur1" (in deinem Beispiel), und mit einem Pointer auf eine Struktur1 Instanz kannst du halt über ->next durchaus das nächste Element bekommen. Verkettete Listen sind aber gar nicht so sinnvoll wie einem der Informatikunterricht glauben machen möchte - weil sie über den ganzen Speicher verteilt sind nutzen sie den Cache nicht gut und sind daher eher langsam. Oft sind array-artige Container wie std::vector sinnvoller.
Dr. Sommer schrieb: > Verkettete Listen sind aber gar nicht so sinnvoll wie einem der > Informatikunterricht glauben machen möchte - weil sie über den ganzen > Speicher verteilt sind nutzen sie den Cache nicht gut und sind daher > eher langsam. Oft sind array-artige Container wie std::vector > sinnvoller. Diese Begründung bezweifele ich. Algorithmen, die auf Listen operieren, haben Laufzeitprobleme. Suchen in Listen kostet O(n), Baumstrukturen eher O(log(n)). Listen versteht jeder, Baumoperationen strengen die grauen Zellen an. Welche Algorithmen sind denn explizit "cache-freundlich"?
Peter M. schrieb: > Algorithmen, die auf Listen operieren, haben Laufzeitprobleme. > Suchen in Listen kostet O(n), Baumstrukturen eher O(log(n)). Jaja, mit den Landau-Symbolen kann man alle Effizienz-Probleme erschlagen und dabei alle technischen Gegebenheiten ignorieren, ein Traum für Mathematiker. Die Iteration durch Listen ist zwar O(n), aber der konstante Faktor kann groß sein. Die Iteration durch einen Vektor ist auch O(n) aber typischerweise mit geringerem konstanten Faktor. Bei der Argumentation ist natürlich vorausgesetzt dass eine "lineare" Datenstruktur schon die richtige ist. Nicht alles lässt sich als Baum darstellen. Aber auch Bäume können schneller sein, wenn sie "flach" in einen Vektor gepackt sind. Peter M. schrieb: > Welche Algorithmen sind denn explizit "cache-freundlich"? Solche die hintereinander auf nah benachbarte Speicherstellen zugreifen.
Der große Vorteil von verketteten Listen gegenüber von Arrays/std::vector sind doch die billigen Verschiebe, Einfüge... -Operationen. Bei Listen müssen nur die Zeiger manipuliert werden, bei Arrays hingegen viel hin und her kopiert werden. D.h. wenn sich dein Array häufig im Programmverlauf ändert, ist wahrscheinlich eine Liste die bessere Wahl. Wobei man da mit Speicherallokationen aufpassen muss, also am besten das Ganze so konstruieren, dass für die Liste nie neuer Speicher reserviert werden muss, aber das gilt für Arrays/std::vector genauso.
Richtig, und daher muss man sich überlegen welche Operation man häufiger braucht. Wenn man 10000x pro Sekunde iteriert, aber nur 1x pro Sekunde neue Elemente einfügt, ist der vector vermutlich schneller. Wenn man gleich oft einfügt und iteriert sieht's schon anders aus. Ganz schlau ist dann auszuprobieren was schneller ist indem man den Container-Typ wechselt. Bei entsprechender Programmierung unter Ausnutzung der Fähigkeiten von C++ muss man dabei keinerlei Code anpassen außer der Deklaration der Variable.
Dr. Sommer schrieb: > Peter M. schrieb: >> Algorithmen, die auf Listen operieren, haben Laufzeitprobleme. >> Suchen in Listen kostet O(n), Baumstrukturen eher O(log(n)). > Jaja, mit den Landau-Symbolen kann man alle Effizienz-Probleme > erschlagen und dabei alle technischen Gegebenheiten ignorieren, ein > Traum für Mathematiker. > Die Iteration durch Listen ist zwar O(n), aber der konstante Faktor kann > groß sein. Die Iteration durch einen Vektor ist auch O(n) aber > typischerweise mit geringerem konstanten Faktor. > > Bei der Argumentation ist natürlich vorausgesetzt dass eine "lineare" > Datenstruktur schon die richtige ist. Nicht alles lässt sich als Baum > darstellen. Aber auch Bäume können schneller sein, wenn sie "flach" in > einen Vektor gepackt sind. > Ja, ich erinnere aus meiner LISP Zeit, dass es da ganze Doktorarbeiten gab über die Vor-und Nachteile der Organisation (da gab es so etwas wie CAR-CDRing, wenn ich es richtig erinnere, das versuchte die Listen so gepackt wie möglich zu halten). Allerdings ist der Knackpunkt halt, dass verkettete Listen grundsätzlich keine hardcodierte Maximalanzahl von Elementen haben, Arrays aber per Definition schon. In Embedded geht es halt immer um effiziente Ressourcennutzung, und da musst Du halt überlegen, ob Du einen worst case annimmst (also ein Array mit hardcodiert Max möglichen Anzahl Elemente falls bestimmbar, auch auf die Gefahr hin, zu 90% der Laufzeit viel vom Speicher brach liegen zu haben) oder den Speicher dynamisch zu nutzen (mit den bekannten Problemen). Sehr Vieles was man macht ist ja immer eine Abwägung zwischen Vor- und Nachteilen zweier oder mehr Lösungen für eine gegebene Aufgabenstellung, aber Universal richtige "beste" Lösungen gibt es eigentlich nie.
Also std::vector hat keine fixe Maximalanzahl, funktioniert aber wie ein Arrays. Dann gibt es noch std::deque, ein Hybrid (ohne feste Max.-Anzahl). Bei Embedded sieht das natürlich anders aus, auch weil MCU's selten Caches haben. Aber da brauchts auch eher selten dynamische Datenstrukturen: Ruediger A. schrieb: > also ein Array mit hardcodiert Max möglichen Anzahl > Elemente falls bestimmbar, auch auf die Gefahr hin, zu 90% der Laufzeit > viel vom Speicher brach liegen zu haben) Na und? Sofern man den Speicher nicht gerade für etwas anderes nutzen kann, ist das völlig egal.
Dr. Sommer schrieb: > > Ruediger A. schrieb: >> also ein Array mit hardcodiert Max möglichen Anzahl >> Elemente falls bestimmbar, auch auf die Gefahr hin, zu 90% der Laufzeit >> viel vom Speicher brach liegen zu haben) > Na und? Sofern man den Speicher nicht gerade für etwas anderes nutzen > kann, ist das völlig egal. Schreiben wir aneinander vorbei? Mein Punkt ist doch gerade, dass man in Embedded oftmals sehr wohl mit Ressourcen schwäbeln muss, d.h. "sofern man den Speicher nicht gerade für etwas anderes nutzen kann" ist hier genau der Knackpunkt! Klar, wenn ich mehr RAM On Board habe als ich zur Laufzeit jemals benutzen werde, kann ich Alles statisch mit Reserven anlegen. Genau das geht aber oftmals nicht. Speicher, der statisch weg ist, ist weg und eben nicht mehr verwendbar, weder "gerade" noch "irgendwann später mal." Da aber Embedded Architekturen normalerweise auf eine bestimmte Anwendung zurechtgeschnitten sind, hat man eben so viel Speicher zur Verfügung, dass man damit den Normalbetrieb durchsteht, aber nicht mehr. Damit passiert es also eher selten, dass "man den Speicher nicht gerade für etwas anderes nutzn kann." Das wollte ich damit ausdrücken, mehr eigentlich nicht. Ausserdem gibt es auch Fälle, in denen ein Maximum an Einträgen nicht bestimmbar ist oder im worst case temporär soviel Speicher in Aspruch nehmen kann, dass damit der Rest des Systemes dauerhaft nicht auskommen kann.
Dr. Sommer schrieb: > Peter M. schrieb: >> Welche Algorithmen sind denn explizit "cache-freundlich"? > Solche die hintereinander auf nah benachbarte Speicherstellen zugreifen. Das setzt voraus, große Speicherbereiche zu reservieren und selbst zu verwalten.
Ok, vielen Dank. ich bin etwas verwirrt, da zwischen C und C++ doch
viele Unterschiede sind.
Beispiel:
Unter C hat man eine Struktur struct adressen {};
Mit struct adressen ADDR1 erzeugt man sich die erste Instanz. Unter C++
fällt das Wort struct eben weg --> adressen ADDR1
Unter C kann man das auch, müsste aber eben mit typedef arbeiten.
Der Unterschied zwischen C und C++ ist in etwa der zwischen einem Werkzeugkasten und einem Baukasten wie zB von LEGO. In C lernst du deine relativ wenigen Werkzeuge kennen und bastelst dir dann damit die Funktionen und Strukturen, die du brauchst für deine Programme. In C++ hast du eine riesige Menge von fertigen Bausteinen, die du einfach zusammensetzen kannst. Du verbringst weniger Zeit mit dem Programmieren, aber dafür umso mehr mit dem Suchen von geeigneten Bausteinen und dem Studieren von Features und Blibliotheksreferenzen. Um auf die verketteten Listen zurück zu kommen, ich habe bisher nur zwei verschiedene gebraucht. Eine mit einem void *pointer und einem Integer zum Einsortieren pro Knoten sowie eine mit einem String (char *)statt dem int. Damit können beliebige Elemente in beliebiger Reihenfolge eingelesen und sortiert behandelt oder ausgegeben werden.
Jobst Q. schrieb: > ich habe bisher nur zwei > verschiedene gebraucht. Eine mit einem void *pointer und einem Integer > zum Einsortieren pro Knoten sowie eine mit einem String (char *)statt > dem int. Mir ist nicht ganz klar was du sagen willst, aber das klingt nach einem vermurksten Design... Allein schon weil man std::string und nicht char* für Strings nimmt. Jobst Q. schrieb: > In C++ hast du eine riesige Menge von fertigen Bausteinen, die du > einfach zusammensetzen kannst. Du verbringst weniger Zeit mit dem > Programmieren, aber dafür umso mehr mit dem Suchen von geeigneten > Bausteinen und dem Studieren von Features und Blibliotheksreferenzen. Das klingt mehr nach Java...
Angehängte Dateien:
-
forgetting.png
20 KB
Dr. Sommer schrieb: > Also std::vector hat keine fixe Maximalanzahl, funktioniert aber wie ein > Arrays. Dann gibt es noch std::deque, ein Hybrid (ohne feste > Max.-Anzahl). du verwechselst std::vector und std::array. das Array hat die fixe größe, der vektor kann wachsen. Aber am Vektor kann man nur hinten in (amortisierter) konstanter Zeit Elemente anfügen/entfernen. (push/pop) bei der deque (Double Ended Queue) geht das an beiden Enden, deshalb bietet sie sich oft als schneller Ersatz für std::list in FIFO-Anwendungen an...
Εrnst B. schrieb: > du verwechselst std::vector und std::array. > > das Array hat die fixe größe, der vektor kann wachsen. Ja das hab ich doch gesagt. "Funktioniert wie ein Array" sollte heißen dass keine Verkettung existiert.
Dr. Sommer schrieb: > Εrnst B. schrieb: >> du verwechselst std::vector und std::array. >> >> das Array hat die fixe größe, der vektor kann wachsen. > > Ja das hab ich doch gesagt. "Funktioniert wie ein Array" sollte heißen > dass keine Verkettung existiert. Ups, sorry.. hab ich nicht exakt genug gelesen. Zum Thema: Ob man besser eine std::list oder einen std::vector nimmt, hängt auch von der Art/Größe der zu speichernden Objekte ab. Die Liste braucht für jedes Element Verwaltungsinformationen, (prev/next Pointer), eine list<int> ist also sehr verschwenderisch. Der Vektor hingegen braucht nur einmal seinen Satz Verwaltungsinfos, unabhängig vom Füllstand. Andersherum kann der Vektor nur "kopierbare" Sachen speichern, und kopiert die auch öfters mal. Klassen mit teurem Copy-Constructor packt mal also besser in eine Liste. Aber, das ist das schöne an der stl: man die Container sind alle mehr oder weniger Kompatibel, man kann ohne großen Aufwand verschiedene mit realem Workload gegeneinander profilen.
Dr. Sommer schrieb: > Jobst Q. schrieb: >> ich habe bisher nur zwei >> verschiedene gebraucht. Eine mit einem void *pointer und einem Integer >> zum Einsortieren pro Knoten sowie eine mit einem String (char *)statt >> dem int. > > Mir ist nicht ganz klar was du sagen willst, Dass man nicht eine lange Latte von unterschiedlichen Listen braucht,sondern mit wenigen universell einsetzbaren auskommt, wenn sie gut konzipiert sind. > aber das klingt nach einem > vermurksten Design... Allein schon weil man std::string und nicht char* > für Strings nimmt. Man nimmt std::string, wenn man wenig von Stringbearbeitung versteht und gelegentlich mal einen einsetzen muss. Wenn man keine Angst vor Pointern hat und sich damit auskennt, ist es mit char* wesentlich effizienter.
Jobst Q. schrieb: > Man nimmt std::string, wenn man wenig von Stringbearbeitung versteht und > gelegentlich mal einen einsetzen muss. Wenn man keine Angst vor Pointern > hat und sich damit auskennt, ist es mit char* wesentlich effizienter. Der war gut. Du hast die Ironie Tags vergessen
Wenn ich eine Klasse HansPeter auflisten will nehm ich eine std::list<HansPeter>. Gleiches gilt für alle möglichen anderen Klassen. Keine Ahnung was du da mit void* und int willst. Das sind im Endeffekt alles die gleichen Listen mit typsicherem angepasstem Interface. C++ aber char* verwenden? Ist klaro. std::string ist äußerst schlau programmiert, das sollte bei den meisten Programmen praktisch keinen Unterschied machen. Dafür dass man dadurch eine Menge Komfort und Sicherheit gewinnt (im Gegensatz du den ganzen beliebten Buffer Overflows bei C String Verarbeitung mit char*)...
nicht"Gast" schrieb: > Jobst Q. schrieb: >> Man nimmt std::string, wenn man wenig von Stringbearbeitung versteht und >> gelegentlich mal einen einsetzen muss. Wenn man keine Angst vor Pointern >> hat und sich damit auskennt, ist es mit char* wesentlich effizienter. > > Der war gut. Du hast die Ironie Tags vergessen Nein, das ist mein voller Ernst. In std::string ist jeder String ein Objekt, das um ein vielfaches größer ist als ein Pointer.Dafür muss Speicher alloziiert werden, selbst wenn der String leer ist. Ein Array von mehreren tausend Strings, was wird das für ein Monster? Wenn ein String vergrößert wird, muss er realloziert werden und oft auch umkopiert werden. Bei jeder Änderung müssen Membervariablen aktualisiert werden. Wie soll das effizient sein? In C arbeitet man mit Puffern, die man statisch oder zu Beginn einer Funktion auf dem Stack anlegt. Ein Puffer kann mehrere Strings in Form von einfachen Pointern enthalten. So kann man eine Zeile aus einer Datei in den Puffer lesen und dann in einzelne Strings zerlegen, indem man Trennzeichen durch das Nullzeichen ersetzt. Beim Zusammensetzen von Strings kann man beliebige Strings und Zeichen aneinanderkopieren, solange noch Platz im Puffer ist. Dr. Sommer schrieb: > im Gegensatz du den ganzen beliebten Buffer > Overflows bei C String Verarbeitung mit char*). Mit geeigneten Funktionen sind Buffer Overflows kein Problem. Fürs Kopieren habe ich eine Funktion char * stpcpylim(char *t,const char *s, const char *lim).Dabei ist lim ein Zeiger auf das erste Byte, dass nicht beschrieben werden darf. Man muss es je Puffer nur einmal zuweisen: lim = buf +sizeof(buf); Näheres siehe Beitrag "Re: String-Array und malloc"
:
Bearbeitet durch User
Jobst Q. schrieb: > das um ein vielfaches größer > ist als ein Pointer. Korrekt. Es wird noch die Länge gespeichert, das musst du bei deinem Pointer ja auch, um Buffer Overflows zu vermeiden (oder rufst du jedes mal strlen auf - super effizient). Außerdem nutzen manche std::string Implementationen einen lokalen Buffer, d.h. sehr kurze strings werden direkt in std::string gespeichert. Dadurch wird der Zugriff deutlich schneller - ist also sogar effizienter als die Arbeit mit Pointern. Insbesondere, wenn ein Array von sehr vielen kurzen Strings hast... Jobst Q. schrieb: > Ein Array von mehreren tausend Strings, was wird > das für ein Monster? ... Ist das mit std::string viel schneller! Jobst Q. schrieb: > Wenn ein String vergrößert wird, muss er > realloziert werden und oft auch umkopiert werden Und bei char* etwa nicht? Jobst Q. schrieb: > Bei jeder Änderung > müssen Membervariablen aktualisiert werden. Nur beim Reallokieren. Und da musst du bei char* deine explizit gespeicherte Größe auch aktualisieren. Jobst Q. schrieb: > Wie soll das effizient sein? Wie gesagt, schlaue Implementierung. Anstatt zu spekulieren, kannst du es ja ausprobieren. Jobst Q. schrieb: > die man statisch oder zu Beginn einer > Funktion auf dem Stack anlegt D.h. du hast nur sehr wenige, kleine strings (der Stack ist ja typischerweise klein). Damit sind deine Argumente sowieso hinfällig, weil die Laufzeitunterschiede (falls vorhanden) dann ohnehin verschwinden. Wie gesagt nutzt std::string für kleine Strings auch lokalen Speicher. Und wie genau vergrößerst du solche statisch allokierten Strings? Jobst Q. schrieb: > indem man > Trennzeichen durch das Nullzeichen ersetzt. Das geht bei std::string auch. Nur dass man bei std::string die tatsächliche Länge noch behält (während strlen ja dann nicht mehr funktioniert). Jobst Q. schrieb: > Beim Zusammensetzen von Strings kann man beliebige Strings und Zeichen > aneinanderkopieren, solange noch Platz im Puffer ist. Ja, bei std::string auch. Der kann ja auch über-allokieren. Jobst Q. schrieb: > Mit geeigneten Funktionen sind Buffer Overflows kein Problem Klar. Die muss man aber präzise und immer korrekt nutzen. Dass das viele Leute nicht schaffen sieht man daran, dass das Ursache Nr. 1 von Sicherheitslücken ist. Wenn du so ein Genie bist der das nie falsch macht ist das schön für dich, aber das sollte man nicht als musterhaftes Vorgehen verbreiten... In vielen Anwendungen hat man viele verschiedene Strings, hauptsächlich für die GUI. Die sind aber absolut nicht Performance-kritisch. Daher ist es sehr angenehm, wenn man das super einfache und sichere std::string API dafür nutzen kann, anstatt bei jedem einzelnen mit der C-String-Verarbeitung rumzubasteln und ständig auf Overflows zu achten. Und selbst wenn es Performance-Kritisch wird (sehr viele/große Strings) ist keineswegs gesetzt dass std::string langsamer sei - das sollte man lieber ausprobieren anstatt wild zu spekulieren! In diesem seltenen Fall kann man bei std::string mit expliziter Allokierung und std::string_view arbeiten.
Εrnst B. schrieb: > Zum Thema: Ob man besser eine std::list oder einen std::vector nimmt, > hängt auch von der Art/Größe der zu speichernden Objekte ab. > > Die Liste braucht für jedes Element Verwaltungsinformationen, (prev/next > Pointer), eine list<int> ist also sehr verschwenderisch. Der Vektor > hingegen braucht nur einmal seinen Satz Verwaltungsinfos, unabhängig vom > Füllstand. Das schon. Dafür reserviert der Vektor in der Regel mehr Speicher als aktuell benötigt, um nicht bei jedem einzelnen Anhängen eines neuen Wertes komplett reallokieren zu müssen. Und wenn er reallokieren muss, braucht er temporär die bisher benötige Menge Speicher plus die neue Menge. Da kann also auch einiges an Overhead anfallen. Jobst Q. schrieb: > Man nimmt std::string, wenn man wenig von Stringbearbeitung versteht und > gelegentlich mal einen einsetzen muss. Wenn man keine Angst vor Pointern > hat und sich damit auskennt, ist es mit char* wesentlich effizienter. Wer tut sich denn heute noch freiwillig String-Verarbeitung im C-Stil an? Von der Laufzeit her mag das effizienter sein, aber die umständliche, hakelige und fehlerträchtige Programmierung tue ich mir nur an, wenn's nicht anders geht. Εrnst B. schrieb: > Andersherum kann der Vektor nur "kopierbare" Sachen speichern, und > kopiert die auch öfters mal. Klassen mit teurem Copy-Constructor packt > mal also besser in eine Liste. Auch eine std::list kann nur kopierbare Sachen speichern. Jobst Q. schrieb: > In std::string ist jeder String ein Objekt, das um ein vielfaches größer > ist als ein Pointer. Ja, man braucht einen Zeiger auf den Text und die Größe. > Dafür muss Speicher alloziiert werden, selbst wenn der String leer ist. Warum? > Ein Array von mehreren tausend Strings, was wird das für ein Monster? Hatte bisher kein Problem damit. > Wenn ein String vergrößert wird, muss er realloziert werden und oft auch > umkopiert werden. Und bei einem char* ist das auf magische Weise nicht nötig? Oder schlimmer noch, bei deinen unten angegebenen Puffern, die gar nicht dynamisch allokiert sind. Da kannst du nicht reallokieren und hast halt einfach Pech gehabt, wenn mehr benötigt wird. > Bei jeder Änderung müssen Membervariablen aktualisiert werden. Was soll da groß aktualisiert werden? Die Größe eben. > In C arbeitet man mit Puffern, die man statisch oder zu Beginn einer > Funktion auf dem Stack anlegt. So lange, bis dein Stack ohne Vorwarnung und ohne Erkennungsmöglichkeit überläuft. > Ein Puffer kann mehrere Strings in Form von einfachen Pointern enthalten. > So kann man eine Zeile aus einer Datei in den Puffer lesen und dann in > einzelne Strings zerlegen, indem man Trennzeichen durch das Nullzeichen > ersetzt. Und wenn der Puffer zu klein ist? Wenn du beim Programmieren nicht gut aufgepast hast, ist dein Programm dann ein Sicherheitsleck. Wenn du gut aufgepasst hast, musst du halt einen Fehler melden a la: "Zeile zu lang. Ich hätt nicht gedacht, dass jemand eine so lange Zeile einlesen will. Da die maximale Größe hartkodiert ist, kann diese Datei leider nicht geöffnet werden. Viel Spaß bei der Suche nach einem flexibleren Programm." Ja, dynamische Allokation ist langsamer. Aber gerade auf einem PC wirst du den Unterschied nur in sehr extremen Fällen merken. Da überwiegen für Standard-Anwendungen die Vorteile eines std::string einfach bei weitem. > Beim Zusammensetzen von Strings kann man beliebige Strings und Zeichen > aneinanderkopieren, solange noch Platz im Puffer ist. Das kann man bei std::string auch. Und wenn kein Platz mehr ist, wird automatisch reallokiert. Man kann übrigens auch schon bei der Erzeugung des Strings angeben, wieviel Platz reserviert werden soll. Wenn man also vorher die Größe schon kennt, kann man ihn so anlegen, dass Reallokationen nicht gemacht werden.
Rolf M. schrieb: > > Auch eine std::list kann nur kopierbare Sachen speichern. Nein, es geht auch nur verschiebbar (nicht-kopierbar). Und das gilt auch für std::vector (und die anderen Container).
:
Bearbeitet durch User
Dr. Sommer schrieb: > Jobst Q. schrieb: >> das um ein vielfaches größer >> ist als ein Pointer. > Korrekt. Es wird noch die Länge gespeichert, das musst du bei deinem > Pointer ja auch, um Buffer Overflows zu vermeiden (oder rufst du jedes > mal strlen auf - super effizient). Damit zeigst du nur, wie wenig du von Stringbearbeitung und Pointern verstehst. Die Länge eines Strings braucht man höchst selten, und wenn, kann man sie meist durch eine simple Subtraktion der Anfangsadresse vom Endpointer berechnen. Um Buffer Overflows zu vermeiden, braucht man nicht die Länge der Strings, sondern nur die Länge des Puffers oder besser einen Pointer auf das Ende des Puffers. Man braucht aber weit weniger Puffer als Pointer. Der Puffer ist das Spielfeld der Stringbearbeitung, die Pointer sind die Spieler, die sich darauf bewegen (können). Bei Strings als Objekte braucht jeder Spieler sein eigenes Spielfeld, das macht es so ineffizient. > Außerdem nutzen manche std::string > Implementationen einen lokalen Buffer, d.h. sehr kurze strings werden > direkt in std::string gespeichert. Dadurch wird der Zugriff deutlich > schneller - ist also sogar effizienter als die Arbeit mit Pointern. Die Derefenzierung eines Pointers braucht maximal 2 CPU-Befehle, wenn er als Register implementiert wird sogar nur einen. Effizienter geht es nicht. > Jobst Q. schrieb: >> Wenn ein String vergrößert wird, muss er >> realloziert werden und oft auch umkopiert werden > Und bei char* etwa nicht? Nicht, wenn man den Puffer groß genug wählt. Und die Trennung zwischen Puffer und Pointer ist bei der Pointermethode viel klarer. > > Jobst Q. schrieb: >> Bei jeder Änderung >> müssen Membervariablen aktualisiert werden. > Nur beim Reallokieren. Und da musst du bei char* deine explizit > gespeicherte Größe auch aktualisieren. Siehe oben. > Jobst Q. schrieb: >> die man statisch oder zu Beginn einer >> Funktion auf dem Stack anlegt > D.h. du hast nur sehr wenige, kleine strings (der Stack ist ja > typischerweise klein). Nein, ich verarbeite sehr viele Strings, da spielt die Effizienz schon eine Rolle. Meist sind es lange Strings aus Textdateien, die zerlegt werden in kurze Strings und evt wieder zu langen Strings zusammengesetzt werden. Wenn der Stack typischerweise klein wäre, dürfte man auch keine rekursiven Funktionen wie qsort verwenden. Auf PC's hatte ich noch nie Stackprobleme. Auf Mikrokontrollern mag das anders sein. > Damit sind deine Argumente sowieso hinfällig, > weil die Laufzeitunterschiede (falls vorhanden) dann ohnehin > verschwinden. Wie gesagt nutzt std::string für kleine Strings auch > lokalen Speicher. Und wie genau vergrößerst du solche statisch > allokierten Strings? Ich alloziere eben keine Strings, sondern Puffer. Und die eben groß genug für die jeweilige Anwendung. Den Unterschied zwischen String, Puffer und Pointer solltest du dir mal klarmachen, wenn du hier über Stringbearbeitung diskutieren willst. > > Jobst Q. schrieb: >> indem man >> Trennzeichen durch das Nullzeichen ersetzt. > Das geht bei std::string auch. Nur dass man bei std::string die > tatsächliche Länge noch behält (während strlen ja dann nicht mehr > funktioniert). > > Jobst Q. schrieb: >> Beim Zusammensetzen von Strings kann man beliebige Strings und Zeichen >> aneinanderkopieren, solange noch Platz im Puffer ist. > Ja, bei std::string auch. Der kann ja auch über-allokieren. > > Jobst Q. schrieb: >> Mit geeigneten Funktionen sind Buffer Overflows kein Problem > Klar. Die muss man aber präzise und immer korrekt nutzen. Dass das viele > Leute nicht schaffen sieht man daran, dass das Ursache Nr. 1 von > Sicherheitslücken ist. Wenn du so ein Genie bist der das nie falsch > macht ist das schön für dich, aber das sollte man nicht als musterhaftes > Vorgehen verbreiten... Was ist denn sonst musterhaftes Vorgehen? Sich blind auf vorgefertigte Funtionen und Objekte zu verlassen, ist es jedenfalls nicht. Dass es soviele Buffer Overflows gibt, liegt an dem Fehldesign früher C-Standardfunktionen wie strcpy oder strncpy. Besonders heimtückisch ist strncpy, da es ein begrenztes Kopieren suggeriert, aber im Begrenzungsfall keine Endnull schreibt und damit den String nicht abschließt. Wenn der so produzierte String ausgegeben wird, ist alles danach mit drin bis zur zufälligen nächsten Null. Es gibt eine ganz einfache Regel, um Buffer Overflows zu verhindern: Jede schreibende Funktion braucht einen Parameter, in dem die Grenze des zu beschreibenden Puffers übergeben werden kann.
Jobst Q. schrieb: > Damit zeigst du nur, wie wenig du von Stringbearbeitung und Pointern > verstehst. Sind hier eigentlich letztens alle bescheuert? Überall wird man mit Halbwahrheiten bombardiert, und wenn man versucht diese auszurotten wird man nur noch beleidigt. Und das nicht nur am Freitag. An deinem Beitrag ist so viel falsch, ich hab gar keine Lust darauf einzeln einzugehen. Ist auch schlecht für den Blutdruck. Ich kann dir nur raten mal über den Tellerrand zu blicken und zu schauen, wie std::string tatsächlich funktioniert.
Dr. Sommer schrieb: > Jobst Q. schrieb: >> Damit zeigst du nur, wie wenig du von Stringbearbeitung und Pointern >> verstehst. > > Sind hier eigentlich letztens alle bescheuert? Überall wird man mit > Halbwahrheiten bombardiert, und wenn man versucht diese auszurotten wird > man nur noch beleidigt. Und das nicht nur am Freitag. Bescheuert sind sicherlich nicht alle ... Aber es ist schon bemerkenswert, wie in diesem (!) Forum sofort bei einigen der Blutdruck hoch und das Niveau herunter geht. Das kenne ich von nirgendwo anders. Scheint irgendwie auch ein bisschen typisch deutsch zu sein, diese Schulmeisterhaftigkeit! Wenn man es nicht ganz ernst nicht, ist es eigentlich auch wieder lustig ;-)
Dr. Sommer schrieb: > Sind hier eigentlich letztens alle bescheuert? Nicht alle, hauptsächlich Jobst Quis. ;-)
Rolf M. schrieb: > Das schon. Dafür reserviert der Vektor in der Regel mehr Speicher als > aktuell benötigt, um nicht bei jedem einzelnen Anhängen eines neuen > Wertes komplett reallokieren zu müssen. Und wenn er reallokieren muss, > braucht er temporär die bisher benötige Menge Speicher plus die neue > Menge. > Da kann also auch einiges an Overhead anfallen. Ja, das ist ein Nachteil von std::vector, der oft übersehen wird. Er führt dazu, dass ein std::vector selbst bei nichtfragmentiertem Speicher schlimmstenfalls nur etwa ein Drittel desselben nutzen kann. Das liegt daran, dass mit jeder Reallokation die Kapazität des Vektors verdoppelt wird. Folgendes Beispiel zeigt dies:
1 | #include <iostream> |
2 | #include <vector> |
3 | #include <list> |
4 | |
5 | struct elem_t { |
6 | char a[10000]; // stellvertretend für einen etwas größere Datensatz, |
7 | // hier vereinfscht als Array dargestellt
|
8 | };
|
9 | |
10 | #ifdef USE_LIST
|
11 | std::list<elem_t> data; |
12 | #else
|
13 | std::vector<elem_t> data; |
14 | #endif
|
15 | |
16 | int main() { |
17 | elem_t elem; |
18 | |
19 | for(int i=0;; i++) { |
20 | try { |
21 | data.push_back(elem); |
22 | }
|
23 | catch (std::bad_alloc) |
24 | {
|
25 | std::cout << i << " sucessful push_backs\n"; |
26 | break; |
27 | }
|
28 | }
|
29 | }
|
Lässt man das Programm in seinen beiden Varienten auf einem 64-Bit-PC mit GCC und einem mit ulimit -d 1920000 auf 1920000 kiB begrenzten Datensegment laufen, liefert es folgende Ergebnisse: Variante mit std::vector
1 | 65536 sucessful push_backs |
Variante mit std::list
1 | 195963 sucessful push_backs |
Bei fragmentiertem Speicher wird der Unterschied u.U. noch viel größer. In dem von Dumdi Dum verlinkten Video von Stroustrup könnte der Eindruck enstehen, dass std::list grundsätzlich schlecht ist. Die richtige Wahl des Datentyps hängt aber, wie so oft, vom konkreten Anwendungsfall ab. Für kleinere Datenmengen hat Stroustrup sicher recht, bei größeren sollte man erst einmal die jeweiligen Vor- und Nachteile gegeneinander abwägen. Oft ist bei großen Datenmengen auch eine Kombination aus beiden, nämlich eine Liste von Vektoren oder Arrays, die beste Lösung. IMHO benutzen die meisten Textverarbeitungsprogramme eine solche Struktur für die interne Textrepräsentation.
Kleine Ergänzung: Yalu X. schrieb: > Das liegt daran, dass mit jeder Reallokation die Kapazität des Vektors > verdoppelt wird. Ist implementationsabhängig. Wobei das keine Schikane der Bibliotheksschreiber ist, sondern dem Standard geschuldet (die vorgeschriebene "amortized constant time" bei push_back wäre sonst nicht möglich, glaube ich - darum gibt es hier keinen großen Spielraum). https://stackoverflow.com/a/5232342
Yalu X. schrieb: > Bei fragmentiertem Speicher wird der Unterschied u.U. noch viel größer. Schönes Beispiel, danke. Ist das eigentlich Zufall, dass es genau 65536=2^16 Mal bei vector geht?
Yalu X. schrieb: > Lässt man das Programm in seinen beiden Varienten auf einem 64-Bit-PC > mit GCC und einem mit > > ulimit -d 1920000 > > auf 1920000 kiB begrenzten Datensegment laufen, liefert es folgende > Ergebnisse: > > Variante mit std::vector > >
1 | > 65536 sucessful push_backs |
2 | > |
> > Variante mit std::list > >
1 | > 195963 sucessful push_backs |
2 | > |
Wer Mist misst Mist ;-) Auch das ist eigentlich nur die halbe Wahrheit. Denn z.B. std::string ist selbst recht klein (SSO), die Daten liegen auf dem Heap. Etwa so wie diese Klasse:
1 | template<size_t Size = 10000> |
2 | class A { |
3 | public:
|
4 | A() = default; |
5 | A(const A&) = delete; |
6 | A(A&&) = default; |
7 | void swap(A& o) { |
8 | using std::swap; |
9 | swap(mData, o.mData); |
10 | }
|
11 | private:
|
12 | std::unique_ptr<uint8_t[]> mData = std::make_unique<uint8_t[]>(Size); |
13 | };
|
Solche Monster-Klassen wie Deine elem_t wird man (meistens) PImpl'n, so wie bei A. Dann ist das Vertauschen (s.o.swap()) billig und das Sortieren wird dadurch schnell. Was bei elem_t nicht gegen ist. Damit ergibt sich:
1 | 196063 sucessful push_backs |
Yalu X. schrieb: > In dem von Dumdi Dum verlinkten Video von Stroustrup könnte der Eindruck > enstehen, dass std::list grundsätzlich schlecht ist. Eben. Der Typ behauptet allen Ernstes, daß die lineare Suche durch statistisch die halbe Elementanzahl laufzeitbestimmend wäre, und vernachlässigt, daß das Verschieben der Elemente beim insert ins Array ebenfalls statistisch die halbe Elementanzahl betrifft und weil es neben der Lese- auch eine Schreiboperation benötigt deutlich aufwändiger ist, zudem muss man die Stelle erst finden, eine binäre Suche läuft also auch nebem dem (tatsächlich vernachlässigbaren) realloc noch.
Irgendein Benutzer schrieb: > Wobei das keine Schikane der Bibliotheksschreiber ist, sondern dem > Standard geschuldet (die vorgeschriebene "amortized constant time" bei > push_back wäre sonst nicht möglich, glaube ich - darum gibt es hier > keinen großen Spielraum). Statt um den Faktor 2 kann man die Kapazität auch jedesmal um einen anderen konstanten Faktor >1 vergrößerrn. Ein großer Faktor ermöglicht ein im Mittel schnelleres push_back, hat dafür aber einer schlechtere Speichernutzung zur Folge. Der Faktor 2 scheint sich hier als guter Kompromiss herausgebildet zu haben. Das ändert aber nichts an der Tatsache, dass der Speicher-Overhead bei std::vector proportional zur Gesamtgröße des Vektors, bei std::list aber proportional zur Anzahl der Elemente ist. Der Speicher-Overhead pro Element wächst also bei std::vector linear mit der Elementgtöße, während er bei std::list konstant ist. Dumdi D. schrieb: > Schönes Beispiel, danke. Ist das eigentlich Zufall, dass es genau > 65536=2^16 Mal bei vector geht? Die Zahl hängt von der Speicher- und Elementgröße ab, ist aber immer bei einem Reallokationsfaktor von 2 immer eine Zweierpotenz. Nach der Befüllung von 32768 Elementen wird die Kapazität auf 65536 erhöht und so lange weitergepusht, bis sie erneut erschöpft ist. Als nächstes würde die Kapazität auf 2**17=131072 erhöht werden. Dazu müsste aber temporär Platz für 65536+131072=196608 Elemente vorhanden sein. Da ich das Speicherlimit aber genau auf diesen Wert eingestellt habe und der Vektor ja auch noch einige Bytes Verwaltungsinformation belegt, klappt diese Erhöhung nicht mehr. Wilhelm M. schrieb: > Wer Mist misst Mist ;-) > > Auch das ist eigentlich nur die halbe Wahrheit. Denn z.B. std::string > ist selbst recht klein (SSO), die Daten liegen auf dem Heap. Etwa so wie > diese Klasse: Klar kann man das so machen. Dann ist aber der Geschwindigkeitsvorteil durch den Cache und die eingesparten Dereferenzierungen wieder dahin, da die Daten (in diesem Fall die String-Daten) nicht mehr zusammenhängend im Speicher liegen.
Yalu X. schrieb: > Klar kann man das so machen. Dann ist aber der Geschwindigkeitsvorteil > durch den Cache und die eingesparten Dereferenzierungen wieder dahin, da > die Daten (in diesem Fall die String-Daten) nicht mehr zusammenhängend > im Speicher liegen. Was bei std::list dann auch der Fall ist ... Man kann so eben keine pauschale Aussage treffen.
Wilhelm M. schrieb: > Man kann so eben keine pauschale Aussage treffen. Da sind wir ja einer Meinung, denn Yalu X. schrieb: > Die richtige Wahl des Datentyps hängt aber, wie so oft, vom konkreten > Anwendungsfall ab. Ich will ja keineswegs die Vektoren verteufeln. Ganz im Gegenteil: Der Vektor ist auch für mich der primäre Datentyp, um eine variable Anzahl von Elements gleichen Typs in einer Variablen zusammenzufassen. Aber ich möchte auch nicht, dass die armen Listen niedergemacht werden, denn auch sie haben ihre Daseinsberechtigung.
Rolf M. schrieb: > Jobst Q. schrieb: >> Man nimmt std::string, wenn man wenig von Stringbearbeitung versteht und >> gelegentlich mal einen einsetzen muss. Wenn man keine Angst vor Pointern >> hat und sich damit auskennt, ist es mit char* wesentlich effizienter. > > Wer tut sich denn heute noch freiwillig String-Verarbeitung im C-Stil > an? Von der Laufzeit her mag das effizienter sein, aber die > umständliche, hakelige und fehlerträchtige Programmierung tue ich mir > nur an, wenn's nicht anders geht. Für jeden ist das einfach, was er kann und das schwierig, was er nicht kann. Ich tu mir die Objektstrings nur dann an, wenn es nicht anders geht, zB weil eine GUI-Bibliothek das so verlangt. Das sind meist aber ziemlich triviale Aufgaben wie das Verketten von Strings. Für das Zerlegen und Analysieren von Strings bietet std::string trotz der Vielfalt von Methoden, Members und Operatoren fast nichts, was mit Pointern nicht viel einfacher geht. Für meine Programme wie Compiler, Interpreter, Übersetzer und ähnliche bringt std::string keine Vorteile. Ich hab nichts gegen Objektorientierung oder C++, aber Strings zu Objekten zu machen, ist kontraproduktiv. Ähnlichen Murks kenn ich noch aus meinen Anfängen im Programmieren von GWBASIC, wo Strings auch Variablen waren, auf die man nur mit speziellen Befehlen zugreifen konnte.
Jobst Q. schrieb: > Rolf M. schrieb: >> Jobst Q. schrieb: >>> Man nimmt std::string, wenn man wenig von Stringbearbeitung versteht und >>> gelegentlich mal einen einsetzen muss. Wenn man keine Angst vor Pointern >>> hat und sich damit auskennt, ist es mit char* wesentlich effizienter. >> >> Wer tut sich denn heute noch freiwillig String-Verarbeitung im C-Stil >> an? Von der Laufzeit her mag das effizienter sein, aber die >> umständliche, hakelige und fehlerträchtige Programmierung tue ich mir >> nur an, wenn's nicht anders geht. > > Für jeden ist das einfach, was er kann und das schwierig, was er nicht > kann. Ich hab nicht geschrieben, es sei schwierig, nur umständlich, hakelig und fehlerträchtig. Wenn man es einmal verstanden hat, ist es nicht wirklich schwierig. Wobei es aber durchaus zu den größten Problemen gehört, die Anfänger mit der Sprache haben. Und mal ehrlich: Heutzutage sollte sowas grundlegendes wie der Umgang mit Strings eigentlich nicht mehr zu den größten Schwierigkeiten beim Erlernen einer Sprache gehören, zumindest nicht auf dem PC. > Ich tu mir die Objektstrings nur dann an, wenn es nicht anders geht, zB > weil eine GUI-Bibliothek das so verlangt. Das sind meist aber ziemlich > triviale Aufgaben wie das Verketten von Strings. Bei mir ist es genau umgekehrt: Sobald es über triviale Sachen hinausgeht, habe ich keine Lust, das mit C-Strings zu machen. Nicht weil ich es nicht verstehen würde, sondern weil es mir eben zu unkomfortabel ist. > Für das Zerlegen und Analysieren von Strings bietet std::string trotz > der Vielfalt von Methoden, Members und Operatoren fast nichts, was mit > Pointern nicht viel einfacher geht. Für meine Programme wie Compiler, > Interpreter, Übersetzer und ähnliche bringt std::string keine Vorteile. Es gibt sicher Spezialfälle, in denen Standard-String-Klassen nicht wirklich passen. Und da ist es auch gut, dass man sowas auch komplett selber für den Anwendungsfall passend machen kann. Dann würde ich mir aber eigene Klassen schreiben, die die "schmutzigen Details" hinter einem komfortablen Interface kapseln, so dass ich diese Teile nur einmal machen muss und nicht jedes Mal, wenn mir ein String über den Weg läuft.
Rolf M. schrieb: > Bei mir ist es genau umgekehrt: Sobald es über triviale Sachen > hinausgeht, habe ich keine Lust, das mit C-Strings zu machen. Nicht weil > ich es nicht verstehen würde, sondern weil es mir eben zu unkomfortabel > ist. > >> Für das Zerlegen und Analysieren von Strings bietet std::string trotz >> der Vielfalt von Methoden, Members und Operatoren fast nichts, was mit >> Pointern nicht viel einfacher geht. Für meine Programme wie Compiler, >> Interpreter, Übersetzer und ähnliche bringt std::string keine Vorteile. > > Es gibt sicher Spezialfälle, in denen Standard-String-Klassen nicht > wirklich passen. Und da ist es auch gut, dass man sowas auch komplett > selber für den Anwendungsfall passend machen kann. > Dann würde ich mir aber eigene Klassen schreiben, die die "schmutzigen > Details" hinter einem komfortablen Interface kapseln, so dass ich diese > Teile nur einmal machen muss und nicht jedes Mal, wenn mir ein String > über den Weg läuft. Der Komfort kommt durch geeignete Funktionen, die man sich eben selber schreiben muss, wenn sie nicht mitgeliefert werden. Das ist bei der Programmierung mit Pointern auch nicht anders. Um einen String zu zerlegen habe ich zB eine häufig gebrauchte Funktion char* split(char *s,char c). Sie ersetzt das Trennzeichen auf Null und gibt den Pointer auf den Reststring zurück. Wenn kein Trennzeichen vorhanden ist auf die Null, was gleichbedeutend mit einem Leerstring ist. Um zB einen String in zwei aufzuteilen, muss ich nur sr=split(s,';'); schreiben. Was ist daran umständlich? Das bekommst du mit Objektstrings und Klassen auch nicht einfacher hin.
:
Bearbeitet durch User
Jobst Q. schrieb: > Was ist daran umständlich? Das bekommst du mit Objektstrings > und Klassen auch nicht einfacher hin. Was ist denn eigentlich mit Unicode? Das wird dann nochmal unerfreulicher, sobald man nicht nur den Bytecount braucht, sondern auch die Zeichenzahl (Trivialbeispiel: Editor).
Nop schrieb: > Jobst Q. schrieb: > >> Was ist daran umständlich? Das bekommst du mit Objektstrings >> und Klassen auch nicht einfacher hin. > > Was ist denn eigentlich mit Unicode? Das wird dann nochmal > unerfreulicher, sobald man nicht nur den Bytecount braucht, sondern auch > die Zeichenzahl (Trivialbeispiel: Editor). Solange die Trennzeichen normale 1:1 Zeichen sind, spielt das keine Rolle. Wie ich schon weiter oben geschrieben habe, ist die Stringlänge (Bytecount) nicht so wichtig, dass sie ständig mitgeführt werden müsste. Der Unterschied zwischen Bytecount und Zeichenzahl ist nur in bestimmten Fällen der Darstellung von Bedeutung. Dann schreibt man eben dafür eine spezielle Funktion.
Dr. Sommer schrieb: > Verkettete Listen sind aber gar nicht so sinnvoll wie einem der > Informatikunterricht glauben machen möchte - weil sie über den ganzen > Speicher verteilt sind nutzen sie den Cache nicht gut und sind daher > eher langsam. Oft sind array-artige Container wie std::vector > sinnvoller. naja, eine schlaue Implementierung reservert nicht für jedes Element einzeln den Speicher, sondern holt sich immer gleich Speicher für mehrere Elemente. Damit sitzen dann mehrere Elemente dann auch cachegünstiger nebeneinander. Die zusätzliche Indirektion beim iterieren bleibt natürlich trotzdem.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.