String Vergleichfunktion

Hallo,
ich wollte mal bewusst auf die Vorgegebene strcmp Funktion verzichten und mir was eigenes basteln zu Lernzwecken. Ziel ist es eine Vergleichsfunktion für qsort zu schreiben, die mir ein CSTRING Array sortiert.

Hier die Funktion. Sie müsste Großbuchstaben als "kleiner" ansehen aber das ist erst einmal egal:

int scmp(const void* a, const void* b) {
	int length=0;
	const char* A=(const char*)a;
	const char* B=(const char*)b;
	if(strlen(A)>strlen(B)) {
		length=strlen(A);
	} else {
		length=strlen(B);
	}
	for(int i=0; i<length; ++i) {
		if(A[i]<B[i]) {
			return -1;
		} else if(A[i]>B[i]) {
			return 1;
		}
	}
	return 0;
}

Hier erst mal meine Funktion. Da sind bestimmt noch ein Haufen Anfängerfehler drinne. Deswegen wäre es gut, wenn da mal jemand drüber schaut.

Nun wenn ich der Funktion Manuell Stringliterale Übergebe funktioniert sie. Aber in Verbindung mit qsort irgendwie nicht. WO liegt da der Fehler?

Danke

fr33g

Oh mein Gott, vll bin ich ja zu blöd, aber diese Klammernsetzung raff ich mal gar net:D verwirrt mich total:-P

l'abra d'or

Gandalf123 schrieb:

Nun wenn ich der Funktion Manuell Stringliterale Übergebe funktioniert sie. Aber in Verbindung mit qsort irgendwie nicht. WO liegt da der Fehler?

Keine Ahnung. Du verrätst uns ja nicht in welchem Kontext deine Funktion eingesetzt wird, welche Daten sortiert werden sollen, und vor allem nicht welchen Fehler du bekommst.

Also bitte mehr Infos vor allem in Form von Code posten.

Und an der Einrückung gibts gar nichts auszusetzen. Ist halt etwas kompakter

Also das habe ich in der main:

const char *sfeld[]={"eins","zwei", "drei", "vier","fünf", "sechs", "sieben", "acht", "neun", "zehn" };
	int anzahl=sizeof(sfeld)/sizeof(char*);
	qsort(sfeld,anzahl,sizeof(char*),scmp);

Zurück kommt das gleiche Array, unsortiert.

Kóyaánasqatsi

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

int main()
{
	std::vector<std::string> Buffer;

	Buffer.push_back("C");
	Buffer.push_back("B");
	Buffer.push_back("A");

	std::sort(Buffer.begin(), Buffer.end());

	for(std::vector<std::string>::const_iterator it(Buffer.begin());
		it != Buffer.end();
		++it)
			std::cout<< *it <<std::endl;
}

Wie sort Funktioniert weiß ich. Mir geht es aber wie gesagt aus Lerngründen um CSTRINGS und qsort.

rüdiger

In C++ sollte man lieber std::sort und nicht qsort benutzen. qsort ist deutlich komplizierter von der API und auch deutlich langsamer, da die Vergleichsfunktion nicht geinlined werden kann, sondern immer indirekt über einen Pointer aufgerufen werden muss.

Ja ich weiß, dass man lieber sort verwenden sollte. Mich würde trotzdem interessieren, was ich falsch gemacht habe.

l'abra d'or

Da ich das jetzt auch lustig fand hab ich etwas daran rumgespielt.
Und mit ein wenig debug-Ausgaben kam ich dahinter

int scmp(const void* a, const void* b) {
    size_t length=0;

    const char* A = *(const char**)a;
    const char* B = *(const char**)b;

    size_t len_a = strlen(A);
    size_t len_b = strlen(B);
    cout << A << " " << len_a << "\n" << B << " " << len_b << endl;
    if(len_a > len_b) {
        length=len_b;
    } else {
        length=len_a;
    }
    for(int i=0; i<length; ++i) {
        if(A[i]<B[i]) {
            return -1;
        } else if(A[i]>B[i]) {
            return 1;
        }
    }
    return 0;
}

Du hattest da noch eine mögliche Quelle für nen undefined behaviour:

if(strlen(A)>strlen(B)) {
        length=strlen(A);
    } else {
        length=strlen(B);
    }

Du nimmst als Länge immer die größere der beiden. Das führt dazu, dass du bei dem kleineren string irgendwann auf ungültige Indizes zugreifst. Hab ich oben schon umgedreht.

Dravere

Gandalf123 schrieb:

Ja ich weiß, dass man lieber sort verwenden sollte. Mich würde trotzdem interessieren, was ich falsch gemacht habe.

1. Grundsätzlich hast du im falschen Forum gefragt, da dies nur C betrifft und nichts mit C++ zu tun hat.
2. Du hast einen Zeigerfehler gemacht.

Was übergibst du mit sfeld an qsort ? qsort erwartet ja als ersten Parameter einen void* . Wenn du sfeld übergibst, dann wird aus dem Array implizit einen Zeiger erzeugt. Dieser Zeiger ist vom Typ char const** . Also einen Zeiger auf einen Zeiger.

Genau dies bekommst du dann in deiner Vergleichsfunktion als Zeiger. Also der Zeiger, den du bekommst, ist ein Zeiger auf einen Zeiger ( char const** ). Also verändere in der Verlgeichsfunktion die Umwandlung wie folgt:

char const* A = *static_cast<char const* const*>(a);
    char const* B = *static_cast<char const* const*>(b);

Die zusätzlichen const wegen Const-Correctness und der static_cast weil wir hier im C++ Forum sind

Grüssli

Shade Of Mine

l'abra d'or schrieb:

Du nimmst als Länge immer die größere der beiden. Das führt dazu, dass du bei dem kleineren string irgendwann auf ungültige Indizes zugreifst.

nein das kann nicht passieren.
das ganze strlen zeugs ist dennoch unnoetig.

Ah vielen dank. Jetzt scheint es zu funktionieren.

Zu dem undefined behaviour ich hatte mir das so überlegt immer die Länge des kürzeren von beiden zu nehmen und hab mich dann vertippt. Danke!

So dann noch ein paar Fragen zu der casterei.

Also ich übergebe der compare Funktion ein Array von Zeigern auf char. Das zerfällt in einen Zeiger auf Zeiger auf void. Das muss ich jetzt umwandeln zu einem Zeiger auf Zeiger auf char und einmal dereferenzieren. Damit erhalte ich einen Zeiger auf char richtig?

Dann was macht in deiner Formulierung welches const?

Dravere

Gandalf123 schrieb:

Also ich übergebe der compare Funktion ein Array von Zeigern auf char.

An qsort, grundsätzlich ja.

Gandalf123 schrieb:

Das zerfällt in einen Zeiger auf Zeiger auf void.

Kann man nicht wirklich so stehen lassen.
1. Es zerfällt nicht, sondern wird implizit konvertiert.
2. Es wird darauf nicht ein Zeiger auf Zeiger auf void, sondern ein Zeiger auf Zeiger auf konstantes char. Ein Zeiger auf Zeiger ist schlussendlich nichts anderes als ein Zeiger. Der Zeiger verweist einfach auf die Speicherstelle, wo der Zeiger liegt. Ein Zeiger braucht schliesslich auch Speicher
Einem Zeiger auf void kann man grundsätzlich jeglicher Zeiger zuweisen. Das passiert dann im letzten Schritt. Also dem Zeiger auf void wird der Zeiger auf den Zeiger zugewiesen.

Gandalf123 schrieb:

Das muss ich jetzt umwandeln zu einem Zeiger auf Zeiger auf char und einmal dereferenzieren. Damit erhalte ich einen Zeiger auf char richtig?

Dieser Teil ist grundsätzlich wieder richtig.

Gandalf123 schrieb:

Dann was macht in deiner Formulierung welches const?

char const* A = *static_cast<char const* const*>(a);
//    (1)                          (2)    (3)

(1) Sollte klar sein, ist ein Zeiger auf einen konstanten char Wert. const char* und char const* bedeuten das Gleiche.
(2) Wie bei (1). Dies ist ja der Zieltyp.
(3) Hier wird ausgesagt, dass der Wert des Zeigers, auf welcher der Zeiger verweist, konstant ist. Dies ist daher nötig, weil a ein Zeiger auf konstant void ist. Du kannst dieses const mal weglassen und wirst sehen, dass der Kompiler einen Fehler ausgibt, da er die Umwandlung als ungültig erklärt, weil du ein const wegcasten willst. Nämlich eben das const in const void* .

Die zwei wichtigen Dinge, welche du hier merken und genau überlegen musst, sind:
1. Ein Zeiger belegt auch Speicher, daher kann man einen Zeiger auf diesen Speicherbereich haben (Zeiger auf Zeiger).
2. Da ein Zeiger auch Speicher belegt, kann man den Speicherbereich als konstant kennzeichnen.

Am besten, falls es dir weiterhin Mühe macht, skizziere dir mal die Speicherbereiche auf ein Blatt Papier auf. Mit Pfeilen zeigst du von den Speicherbereichen, wo die Zeiger liegen, auf die Speicherbereiche, zu welchen die Zeiger verweisen. Auch immer schön markieren, wie ein Zeiger den Speicherbereich kennzeichnet (also ob konstant oder nicht).

Grüssli

Dravere

Sorry für den Doppelpost, aber habe da noch schnell was fabriziert, vielleicht hilft es ja:
http://img535.imageshack.us/img535/8434/memoryexample.png

Zeiger mit gestrichelter Linie verweisen auf einen konstanten Speicherbereich.
Zeiger mit durchgezogener Linie verweisen auf einen veränderlichen Speicherbereich.

rhs == right hand side
lhs == left hand side

Jedes Rechteck ist ein Speicherbereich.

rhs und lhs Verweisen hier nur als Beispiel auf das erste und zweite Element von sfield . Auf welches Element sie verweisen, ist natürlich von qsort abhängig.

Ich hoffe, dass dies für das Verständnis hilfreich ist

Grüssli