[gelöst] Listen in C/C++, STL ?

[abgdf]

Hallo,

in Python und Perl "arbeite" ich ständig mit Listen von Strings, aber auch Zahlen usw., z.B.

Python:

#!/usr/bin/python

list = ["Apfel", "Birne"]

for i in list:
    print i

list.append("Pfirsich")

print

for i in list:
    print i

Perl:

#!/usr/bin/perl -w
use strict;

my @list = ("Apfel", "Birne");

foreach (@list)
{
    print $_."\n";
}

print "\n";

push @list, "Pfirsich";

foreach (@list)
{
    print $_."\n";
}

Die sind sehr praktisch: Sie sind dynamisch erweiterbar, man kann da alles reinschmeißen, ihre Größe bestimmen, auf einzelne Elemente zugreifen, sie an Funktionen übergeben und aus diesen zurückerhalten (wenn auch in Perl "glattgebügelt").

Wäre doch schön, wenn man sowas auch in C++ hätte.

In C mit einem Array von Zeigern zu arbeiten, ist doch sehr qualvoll, vor allem, wenn man sie zur Laufzeit ändern will.

Ich verstehe mein C++-Buch so, daß "verkettete Listen" möglicherweise sowas Ähnliches leisten könnten. Da ist auch eine Implementierung beschrieben, die aber zu hoch für mich ist. Außerdem ist dort gesagt, es gebe eine Bibliothek, die STL, wohl z.B. auch in "/usr/include/c++/4.0.2/bits/stl_list.h", die sowas schon fertig bereitstelle.
Vielleicht ist es damit ja fast genauso leicht wie mit den Listen der Skriptsprachen.

Hätte jemand ein C++-Codebeispiel, wie man mit der STL umgeht, insbesondere C++-Strings darin speichert ?

Viele Grüße

 

[snaewe]

Also, Googlen nach "stl tutorial" kriegste wohl noch hin, oder ?

Ansonsten würde ich dir bei konkreten Fragen die News-Gruppe "de.comp.lang.iso-c++" empfehlen.

S.

 

[abgdf]

Also, Googlen nach "stl tutorial" kriegste wohl noch hin

Ähh, ja, schon .

Was ich meinte, ist: Ist es mit Zusatzbibliotheken wie z.B. C++/Tk, STL und anderen Sachen (welchen) möglich, C++-Programmierung fast so einfach wie Perl/Python-Programmierung zu machen ?

Offenbar gibt es da allerhand "Geheimtips" ...

Viele Grüße

 

[Cauchykriterium]

Könnte C++ alles, was Perl kann bzw. umgekehrt, dann wäre doch eine Sprache überflüssig. Leider muß ich Dir sagen, daß wenn Du so wie in Perl/Python programmieren möchtest, dann solltest Du kein C++ machen. Entweder Du stellst Dich auf die Eigenheiten von C++ ein oder es wird einfach nur frustrierend. Ich selbst mag' Skriptsprachen genauso sehr wie C/C++ und Java - die Kunst ist, zu jedem Problem die passende Sprache auszusuchen ...

 

[abgdf]

Ja, ich glaube auch, daß Python und Perl für die kleinen Sachen, die ich als Einzelner so mache, besser geeignet sind. "Rapid Development" ist schon klasse .

Es könnte sowieso sein, daß man, wenn man umfangreichere Konstruktionen verwendet, nur um einfacher zu benutzende Datentypen zu erhalten, wieder an Geschwindigkeit verliert. Ich denke da an:

http://www.perl.com/pub/a/2001/06/27/ctoperl.html

Also gut ...

Viele Grüße

 

[abgdf]

Falls es noch jemanden interessiert: Hab noch das hier gefunden:

Zur STL:
http://www.c-plusplus.de/forum/viewtopic-var-t-is-143816.html
http://www.c-plusplus.de/forum/viewtopic-var-t-is-146604.html
http://www.c-plusplus.de/forum/viewtopic-var-t-is-150106.html

http://www.infosys.tuwien.ac.at/Research/Component/tutorial/prwmain.htm

Zu C++-Strings:
http://www.c-plusplus.de/forum/viewtopic-var-t-is-155739.html

Wenn ich

http://www.artima.com/intv/goldilocks.html

richtig lese, ist Bjarne Stroustrup der Meinung, daß man ruhig die STL, boost usw. einsetzen sollte und auch mit C++ ruhig etwas High-Level-Programmierung machen kann.

Viele Grüße

 

[jengelh]

Nur leider ist die STL-Implementation stdlibc++ (Linux) ziemlich langsam.

 

[abgdf]

Alles ist möglich :

#include <vector>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    vector<string> mylist;

    mylist.push_back("Apfel");
    mylist.push_back("Birne");

    for(int i=0; i < mylist.size(); i++)
    {
        cout << mylist[i] << endl; 
    }

    cout << endl;

    mylist.push_back("Pfirsich");

    for(int i=0; i < mylist.size(); i++)
    {
        cout << mylist[i] << endl; 
    }
}

("mylist" im Sinne von "Meine String-Liste"; technisch sollte es sonst wohl "myvector" heißen.)

Mal sehen, wie weit ich so komme (und wie schnell das dann wird) ...

Viele Grüße

 

[abgdf]

Hi,

bin gerade doch wieder bei C.

Neulich bemerkte jemand (ich glaube jengelh) in einem anderen Thread, daß man eine Textdatei wegen der '\n'-Zeichen auch in einem einzigen String speichern könnte.
Da ein String in C nur nacheinander im Speicher abgelegte Zeichen mit '\0' am Ende sind, spricht eigentlich nichts dagegen, für eine Liste einen sehr großen String anzulegen und die '\n'-Zeichen zur Trennung der (Pseudo-)Listenelemente zu verwenden.
Auf dieser Grundlage hab ich für mich zur Wiederverwendung in einer eigenen kleinen Bibliotheksdatei ein paar Funktionen geschrieben, die ich mal posten wollte. Insbesondere für "getLine()", die eine einzelne Zeile aus der Pseudoliste zurückgibt, hab ich ziemlich lange gebraucht (bin ja kein Informatiker). Hat aber trotzdem Spaß gemacht:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countLines(char *a);
char *getLine(char *a, int nr);
char *chomp(char *a);
char *readFile(const char *filename);

/* Some pseudo-list-functions by abgdf@gmx.net, 2007, LGPL. */

int main()
{
    char *pslist = (char *) malloc(200);
    strcpy(pslist, "Apfel\nBirne\nPfirsich\n");

    int numlist = countLines(pslist);

    puts("");

    printf("The list starts with %d elements:\n", numlist);
    printf("%s\n", pslist);

    strcat(pslist, "Melone\nKiwi\n");

    numlist = countLines(pslist);

    printf("The list has %d elements now.\n", numlist);

    puts("The single elements of the list are");

    int i = 0;

    for (i = 0; i < numlist; i++)
    {
        printf("%d. %s\n", i+1, chomp(getLine(pslist, i)));
    }

    puts("");
}


int countLines(char *a)
{
    int i;
    int count = 0;
    int stringlength = strlen(a);

    for (i = 0; i <= stringlength; i++)
    {
        if (*a == 10)
            count++;
        a++;

        /* You could get rid of variable "stringlength" by using a[i],
           but it would be A LOT less efficient. */
    }

    return count;
}


char *getLine(char *a, int nr)
{
    int i;
    int x = 0;
    int count = 0;
    int stringlength = strlen(a);
    int cc = 0; /* Counts movements of pointer c */

    char *c;
    if ((c = (char *) malloc(stringlength + 1)) == NULL)
    {
        puts("Error allocating memory.");
        exit(1);
    }

    for (i = 0; i <= stringlength; i++)
    {
        *c = *a;
 
        if (*a == '\n')
        {
            if (count == nr)
            {
                *(c + 1) = 0;
                c -= cc;
                x = 1;
                break;
            }

            else
            {
                count++;
                c -= cc;
                cc = 0;
            }
        }

        /* c mustn't move forward any more, if '\n' is found. */

        if (*a != '\n')
        {
            c++;
            cc++;
        }

        /* a must always move forward until '\n' of the right line is found. */

        a++;
    }

    if (x == 0)
    {
        puts ("List index out of range.");
        return NULL;
    }

    /* cc starts at zero, so it's "strlen(c) - 1" and there's the '\0' at
       the end. So you need "cc + 2" bytes of memory for the string. */

    if ((c = (char *) realloc(c, cc + 2 )) == NULL)
    {
        puts("Error reallocating memory.");
        exit(1);
    }

    return c;
}


char *chomp(char *a)
{
    /* Like Perl's "chomp()" or Python's "string.rstrip('\n')".
       Changes passed string itself.
       Use malloc and 'strcpy(string, "Text");' to create the string
       in the calling function. */

    char *b = (strchr(a, '\n')); 

    if (b == NULL)
    {
        return a;
    }

    *b = 0; 

    return a;
}


char *readFile(const char *filename)
{
    /* Open a text-file nearly regardless of its size,
       store it in memory and return a char-pointer pointing
       to the memory-adress. */

    FILE *fp;

    char buff[1000];
    buff[999] = 0;

    int i;

    int size = 0;

    char *a;

    if ((a = (char *) malloc(1000)) == NULL)
    {
        puts("Error allocating memory.");
        exit(1);
    }


    if ((fp = fopen(filename, "r")) == NULL)
    {
        puts("Error opening file.");
        return NULL;
    }

    while (!feof(fp))
    {
        for (i = 0; i < 999; i++)
        {
            buff[i] = fgetc(fp);
            size++;
            if (buff[i] == EOF)
            {
                buff[i] = '\0';
                break;
            }
        }

        size++;

        if ((a = (char *) realloc(a, size)) == NULL)
        {
            puts("Error reallocating memory.");
            exit(1);
        }

        strcat(a, buff);
    }

    fclose(fp);

    return a;
}

Viele Grüße

 

[jengelh]

Hat aber trotzdem Spaß gemacht:

Gegen Selbstversuche (lies: Versuche zum Erlenen) habe ich nichts, aber man sollte dann, wenn man es verstanden hat, doch nicht so oft das Rad neu entwickeln, insbesondere bei solch elementaren Datenstrukturen ;-)
Für's Casten bei malloc kriegst du aber erstmal einen :evil: -Antismiley.
Im folgenden das ganze aufgeräumt 8)

#include <stdio.h>
#include <libHX.h>

int main(void)
{
    struct HXdeque_node *nd;
    struct HXdeque *dq = HXdeque_init();
    hmc_t *ln = NULL;
    FILE *fp;

    fp = fopen("foobar.txt", "r");
    if (fp != NULL) {
        while (HX_getl(&ln, fp) != NULL) {
            HX_chomp(ln);
            HXdeque_push(dq, HX_strdup(ln));
        }
        fclose(fp);
    }

    /* Noch ein Paar Früchte dran */
    HXdeque_push(dq, "Apfel");
    HXdeque_push(dq, "Birne");
    printf("%u Elemente:\n", dq->items);

    for (nd = dq->first; nd != NULL; nd = nd->next)
        printf("%s\n", (const char *)nd->ptr);

    /* Noch mehr Früchtchen */
    HXdeque_push(dq, "Melone");
    printf("Nun sind's %u Elemente\n", dq->items);
    return 0;
}

Nur so als Beispiel. Auf fixe Längen wie 999 oder 1000 zu setzen ist bei Programmen, die später auch wirklich was leisten sollen, nicht empfehlenswert.

 

[abgdf]

Hallo,

@jengelh: Dein Beispiel habe ich ausprobiert und bin sehr beeindruckt von libHX !

Leider kann ich immer noch nicht genug C (vor allem im Hinblick auf "struct", verkettete Listen usw.), um Deine libHX wirklich einsetzen zu können.

Ich hab mit meinem Selbstversuch daher erstmal weitergemacht. Bin soweit ganz zufrieden (und hab dabei auch einiges über realloc() und Zeiger gelernt).
Was ich soweit gebaut hab, ist ein bißchen viel, um es hier zu posten. Meine Funktionen mit einem kompilierbaren und kommentierten Beispiel (example.c) hab ich mal hierhin gestellt:

http://www.angelfire.com/linux/tux25/liblist.zip

(Bitte ggf. mit "wget -c" runterladen, falls es mit dem Browser nicht so leicht gehen sollte).

Viele Grüße

 

[jengelh]

Evtl. hilft dir ja doc/deque.txt und der WP-Eintrag warum es "Deque" heißt (DE, EN). C++s std::vector<> ist soweit ich das sehen kann, darüberhinaus eine semistatische Datenstruktur (sollte meist mit realloc implementiert sein). Aber ich mag STL nicht so sehr, weil es alles #included statt gelinkt wird, das macht den Compilevorgang langsamer und lässt die Executables 30x bei McD essen. :roll:

 

[abgdf]

Ja, ich verstehe allmählich, daß mein Ansatz keine so gute Performance leistet, weil bei jeder Operation für den Speicher der ganzen Liste realloc() aufgerufen wird.
Deine Lösung ist da viel professioneller.

Wenn ich das alles noch besser verstehe, werde ich bestimmt libHX benutzen.

Ich hab das Problem übrigens noch hier angesprochen und dort auch libHX vorgestellt:

http://cboard.cprogramming.com/showthread.php?t=89682

Ich hoffe, das war Dir so recht ...

Viele Grüße

 

[jengelh]

Ja, ich verstehe allmählich, daß mein Ansatz keine so gute Performance leistet, weil bei jeder Operation für den Speicher der ganzen Liste realloc() aufgerufen wird.

Dass es realloc() verwendet ist nicht so sehr problematisch, aber dass es eben includet wird und somit zur Codegröße beiträgt.

Deine Lösung ist da viel professioneller.

Das lernt man doch in der Schule, dass man eine verkettete Liste "happenweise" bearbeitet

Ich hoffe, das war Dir so recht ...

Kann nie schaden... (außer die Interface-Changes die für 1.10 anstehen :roll: )

 

[abgdf]

Das lernt man doch in der Schule, dass man eine verkettete Liste "happenweise" bearbeitet.

Tja, zu meiner Zeit gab's noch nicht mal ein Schulfach "Informatik". Ach ja, die gute alte Zeit .

aber dass es eben includet wird und somit zur Codegröße beiträgt.

Inzwischen gibt es bei mir auch die Möglichkeit, eine dynamische Bibliothek (.so) zu erzeugen, gegen die man dann seine Programme linken kann, so daß nicht mehr alles mit "#include" eingebunden werden muß. Dazu die 2 Skripte im Unterverzeichnis "libscripts". Nach Ausführung von "mklib" muß man nach einem versteckten Unterverzeichnis ".libs" Ausschau halten.
In seiner eigenen .h-Datei kann man dann bestimmen, welche Funktionen man benötigt.

Meine Datei befindet sich jetzt übrigens unter

http://www.angelfire.com/linux/tux25/libpslist.zip

Zum Herunterladen bitte gegebenenfalls "wget" verwenden.

Viele Grüße