[Gelöst] strdup mit built in language features only

HarteWare

Hallo zusammen,

könnte mir jemand erklären wie man folgendes machen würde:

Write a function, char* strdup(const char*), that copies a C-style string into memory it allocates on the free store. Do not use any standard library functions.

Mir ist klar, dass ich sowas nie machen wollen würde, aber iss halt so ne Übungsaufgabe, die ich nicht hinbekomme.

Mein Problem ist auch, dass 'str' ja eigentlich const sein sollte, also weiß ich nicht, wie ich den Speicher allozieren soll und den Inhalt kopieren.

Da man ja immer Code zeigen muss, mein Ansatz:

char* my_strdup(const char* str)
{
    if (!str) return "";
    size_t count = 1;  // space for '\0'
    for ( ; *str != '\0'; ++str)
        ++count;
    char* s = new char[count];
    while (*str != '\0') {
        *s = *str;
        ++s;
        ++str;
    }
    *s = *str;  // '\0'
    return s;
}

Folgender Test gibt keinen Output:

int main()
{
    char s[] = "Hello World!";
    char* str = my_strdup(s);
    while (*str != '\0') cout << *str;
    cout << '\n';
}

Hoffe jemand ist so nett und zeigt mir, wie das richtig geht.

LG

Warum sollte str const sein?
Was ist dein Problem mit dem gezeigten Code?

Du solltest einen Zeiger auf den Anfang behalten und diesen zurückgeben.

HarteWare

Also so:

char* my_strdup(char* str)
{
    if (!str) return "";
    size_t count = 1;  // space for '\0'
    for ( ; *str != '\0'; ++str)
        ++count;
    char* s = new char[count];
    char* res = s;  // Zeiger auf Anfang
    while (*str != '\0') {
        *s = *str;
        ++s;
        ++str;
    }
    *s = *str;  // '\0'
    return res;
}

str const ist Aufgabentechnisch vorgegeben. Problem kenne ich nicht, ich erhalte keinen Output, wenn ich das Ergebnis der Funktion mit beschriebener Methode ausgebe.

Auf welche Stelle zeigt str, wenn das Programm in Zeile 7 angekommen ist?

HarteWare

Auf das terminierende '\0'. *facepalm*. Danke
Habe es etwas angepasst. Zwar ist die Lösung trotzdem ohne den string const zu übergeben (was meiner Ansicht nach schlechtes Design ist, weil die Funktion eigentlich nicht ihr Argument verändern sollte), aber es "funktioniert":

#include <iostream>

using namespace std;

char* my_strdup(char* str)
{
    if (!str) return "";
    size_t count = 1;  // space for '\0'

    // Zeichen zählen und entsprechend neues char-array allozieren
    for (char* s = str; *s != '\0'; ++s) ++count;
    char* s = new char[count];

    // kopieren aller Zeichen von str nach s
    for (size_t i = 0; i < count; ++i)
        s[i] = str[i];

    return s;
}

int main()
{
    char s[] = "Hello World!";
    char* str = my_strdup(s);
    while (*str != '\0') {
        cout << *str;
        ++str;  // whoops, ohne diese Zeile lacht einen der PC aus
    }
    cout << '\n';
}

Danke schonmal. Falls jemand weiß, wie ich einen const pointer irgendwie kopieren kann oder wie ich das halt löse, dass mein Argument const char* sein kann, ich bin offen für Vorschläge.

LG

Const char* zeigt auf etwas konstantes. Der Pointer ist nicht konstant. Wo ist das Problem?

DAs mit dem const sollte doch jetzt klappen.
Du veränderst in der Funktion strdup ja str nicht mehr.
Du kannst auch beliebig viele andere char-Pointer in deiner Funktion einsetzen. Z.B. beim kopieren.

Zu einem new gehört auch ein delete .
In diesem Fall in main.
Wie sieht das aber aus, wenn die Funktion das "" aus Zeile 7 zurück gibt?

Finnegan

HarteWare schrieb:

Danke schonmal. Falls jemand weiß, wie ich einen const pointer irgendwie kopieren kann oder wie ich das halt löse, dass mein Argument const char* sein kann, ich bin offen für Vorschläge.

Wenn ich nichts übersehen habe, dann ist diese Zeile hier der Grund, weshalb kein const char* als Paranmeter akzeptiert wird:

for (char* s = str; *s != '\0'; ++s) ++count;

Man kann nicht einfach so einen Zeiger auf konstante Typen ein einen Zeiger auf nicht-konstante Typen kopieren. Die einfache Lösung ist, hier s ebenafalls als als const zu deklarieren:

for (const char* s = str; *s != '\0'; ++s) ++count;

Das macht auch insofern Sinn, dass die char in der Schleife ohnehin nicht verändert werden, sondern lediglich der Pointer auf die char .
const char* bedeutet schließlich nicht-konstanter Zeiger auf konstante char.

Gruss,
Finnegan

HarteWare

@manni66
Ich persönlich sehe da auch kein Problem, aber VC++ schon:

error C2440: 'initializing' : cannot convert from 'const char *' to 'char *'

@DirkB:
Ich denke die Lösung ist ganz einfach, dass ich anstatt den Pointer zu bewegen einfach subscripting verwende, um die Zeichen zu zählen:

for (size_t i = 0; str[i] != '\0'; ++i) ++count;

edit: Hab grad den Beitrag von Finnegan gesehen: Mir war schlicht und ergreifend die Bedeutung des const in diesem Fall nicht ganz klar. Hat sich geklärt.

Hab das delete angefügt. Jetzt knallts. Irgend ne Debug Assertion macht Schluss:

_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)

Google sagt mir, dass dies kein seltener Fehler ist, aber ich kann aus den Antworten anderer Probleme nicht rauslesen, was ich da falsch mache.

Wenn ich nur "" zurückgebe, keine Ahnung was da los ist. Vielleicht terminiert meine while Schleife nie? Finde das ganze mit dem '\0' etwas kompliziert, weiß nicht wo das überall implizit angefügt wird und wo nicht.

Da merk ich langsam erst, wie wundervoll std::string ist.

Momentaner Code:

#include <iostream>

using namespace std;

char* my_strdup(const char* str)
{
    if (!str) return "";
    size_t count = 1;  // space for '\0'

    // Zeichen zählen und entsprechend neues char-array allozieren
    for (const char* s = str; *s != '\0'; ++s) ++count;
    char* s = new char[count];

    // kopieren aller Zeichen von str nach s
    for (size_t i = 0; i < count; ++i)
        s[i] = str[i];

    return s;
}

int main()
{
    char s[] = "Hello World!";
    char* str = my_strdup(s);
    while (*str != '\0') {
        cout << *str;
        ++str;  // whoops, ohne diese Zeile lacht einen der PC aus
    }
    cout << '\n';
    delete[] str;
}

Swordfish

HarteWare schrieb:

Hab das delete angefügt. Jetzt knallts. Irgend ne Debug Assertion macht Schluss:
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
[...]

Wenn ich nur "" zurückgebe, keine Ahnung was da los ist. [...]

Wenn Du "" zurückgibst, gibst du einen Zeiger auf einen Zeichenkettenliteral zurück. Einen solchen darfst du nicht an delete geben.

Gib doch immer fehlerfall einfach nullptr zurück.

btw, meine Variante:

char * strdup( char const * src )
{
	if( !src )
		return nullptr;

	char const * p = src;
	while( *p++ );

	char *dst = new char [ p - src ];

	p = src;
	while( *dst++ = *p++ );

	return dst - ( p - src );
}

Dein Programm stürzt ab, weil du immer den gleichen Fehler machst: du schiebst einen Pointer über das Array bis zum Rnde und verwendest ihn dann, als würede er noch auf den Anfang zeigen.

Swordfish

oh, stimmt, die main() hab' ich mir garnicht angesehen.

SeppJ

HarteWare schrieb:

edit: Hab grad den Beitrag von Finnegan gesehen: Mir war schlicht und ergreifend die Bedeutung des const in diesem Fall nicht ganz klar. Hat sich geklärt.

Solche Ausdrücke kann man grob von rechts nach links lesen. Auf Englisch funktioniert es mit der Grammatik des Satzbaus einfacher, daher mal auf Englisch:

char *p;
p      p is a
*      p is a pointer to
char   p is a pointer to char

char * const p;
p      p is a
const  p is a constant
*      p is a constant pointer to
char   p is a constant pointer to char

char const * p;
p      p is a
*      p is a pointer to
const  p is a pointer to a constant
char   p is a pointer to a constant char

const char * p;
p      p is a
*      p is a pointer to
char   p is a pointer to char
const  p is a pointer to a char constant

(wobei eine char constant und ein constant char das gleiche sind)

const char * const p;
p      p is a
const  p is a constant
*      p is a constant pointer to
char   p is a constant pointer to char
const  p is a constant pointer to char constant

char const * const p;
p      p is a
const  p is a constant
*      p is a constant pointer to
const  p is a constant pointer to a constant
char   p is a constant pointer to a constant char

const char const * const p;
p      p is a
const  p is a constant
*      p is a constant pointer to
const  p is a constant pointer to a constant
char   p is a constant pointer to a constant char
const  p is a constant pointer to a constant char constant

Eine constant char constant? Doppelt gemoppelt; das geht nicht mehr; der Ausdruck ist falsch.

So wird auch klar, dass eventuelle Leerzeichen oder nicht vorhandene Leerzeichen überhaupt nichts an der Bedeutung ändern. Wird manchmal nämlich fälschlicherweise angenommen.

HarteWare

Hallo zusammen,

@Swordfish:
mmh, deine Variante ist eigentlich in meinen Augen recht elegant, wenn man halt dan weiß, dass if(char) false ergibt, falls da ein '\0' drin steckt.
Auch das Zählen der Zeichen finde ich da besser gelöst.

@manni66:
Ich kann nur hoffen, dass mir dieser Fehler nie wieder passiert.

@SeppJ:
supi Erklärung, echt verständlich!

Vielen Dank nochmals an alle, die geholfen haben. Ist echt genial das Forum hier

LG

HarteWare schrieb:

..., wenn man halt dan weiß, dass if(char) false ergibt, falls da ein '\0' drin steckt.

Das sind Grundlagen. Die muss man wissen.
Aber du kannst es auch in lang schreiben: if(char != '\0')

HarteWare schrieb:

Auch das Zählen der Zeichen finde ich da besser gelöst.

Aber für den Rückgabewert hätte man eine Kopie von dst nehmen können. Das erspart die Rechnerei am Ende.

p = dst; // src brauch man danach nicht mehr, kann daher verändert werden.
    while( *dst++ = *src+ );

    return p;

Swordfish

DirkB schrieb:

HarteWare schrieb:

Auch das Zählen der Zeichen finde ich da besser gelöst.

Aber für den Rückgabewert hätte man eine Kopie von dst nehmen können. Das erspart die Rechnerei am Ende.
p = dst; // src brauch man danach nicht mehr, kann daher verändert werden.
    while( *dst++ = *src+ );
 
    return p;

Nicht mit p . p ist char const * . Dafür hätt's eine weitere Variable gebraucht, oder einen const_cast< char * >( p ) beim return .