Wie compare korrekt implementieren?

icarus2

Wieso willst du auf unterschiedliche Laengen reagieren? Bei einem lexikographischen Vergleich spielt die Laenge keine Rolle (ausser der eine String ist Praefix des anderen).
Oder was fuer einen Vergleich moechtest du implementieren?

Ethon

http://www.cplusplus.com/reference/string/string/compare/

Es gibt eine Compare-Funktion die von beiden Strings die Länge nimmt.

http://www.cplusplus.com/reference/string/char_traits/

Die compare()-Funktion der char_traits hingegen nimmt nur 1 Länge an.

Was ist für eine korrekte Implementierung zu tun? Die kürze Länge der Beiden zu nehmen?

icarus2

Ethon schrieb:

Was ist für eine korrekte Implementierung zu tun? Die kürze Länge der Beiden zu nehmen?

Du kannst nicht einfach die kuerzere nehmen. Dann wird z.B. "xx" vor "abc" aufgefuehrt - ich nehme nicht an, dass du das moechtest:

Ich nehme an du moechtest einen lexikographischen Vergleich - also so wie die Woerter in einem Lexikon aufgefuehrt werden. Dann gilt zum Beispiel:
- "abc" < "xx"
- "Deadlock" < "DeadlockStarvation"
- "D" > "C"
(Wie man Woerter bzw. Strings halt normalerweise vergleicht zum sortieren).

Ich habe kurz in C++ etwas Code geschrieben, der zwei Strings s1 und s2 vergleicht. Ich habe ihn nicht ausfuehrlich getestet und wahrscheinlich kann man das noch etwas schoener machen. Wenn s1 > s2, dann wird -1 zurueckgegeben. Wenn s1 = s2, dann wird 0 zurueckgegeben. 1 sonst.

int compare(string & s1, string & s2)
{
	size_t smaller_max_index = std::min( s1.size(), s2.size() );

	for ( size_t i = 0; i < smaller_max_index; i++ )
	{
		if ( s1[i] < s2[i] )
			return 1;
		if ( s1[i] > s2[i] )
			return -1;
	}

	if ( s1.size() == s2.size() )
		return 0;
	else if ( s1.size() < s2.size() )
		return 1;
	else
		return -1;
}

Der Algorithmus speichert zuerst die Laenge des kuerzeren Strings.
Dann werden die Strings zeichenweise verglichen an den Positionen i, fuer 0 <= i <= smaller_max_index. Falls s1[i] > s2[i] oder s1[i] < s2[i] wird entsprechend 1 oder -1 zurueckgegeben.

Wenn die einzelnen Zeichen fuer die Positionen 0 <= i <= smaller_max_index alle gleich sind, dann wird die Laenge verglichen. Ist die Laenge gleich, muessen auch die Strings gleich sein. Ansonsten wird entsprechend -1 oder 1 zurueckgegeben.

Shade Of Mine

Zur Info:
Man muss nicht 1 und -1 returnen sondern groesser 0 bzw. kleiner 0.

Das bedeutet statt

if ( s1.size() == s2.size() )
        return 0;
    else if ( s1.size() < s2.size() )
        return 1;
    else
        return -1;

kann man einfach

return s1.size()-s2.size();

Selbes gilt auch fuer die Schleife wo man einfach

if(s1[i] != s2[i])
   return s1[i]-s2[i];

schreiben kann.

krümelkacker

Shade Of Mine schrieb:

kann man einfach
return s1.size()-s2.size();

Auf unsigned/signed bitte aufpassen. Das hier erzeugt ggf undefiniertes Verhalten.

std::string::compare schreibt eine lexikalische Sortierung vor. Wenn Du (Ethon) hier bei unterschiedlicher Länge die Zeichen gar nicht mehr anfasst, kann das nicht funktionieren, da bei einer lexikalischen Orndung
"abc" < "xx"
"ab" < "xxx"
gilt. Wie man sieht, ist in den 2 Fällen die Länge gar nicht ausschlaggebend.

314159265358979

std::lexicographical_compare

otze

Laut dem Standard (siehe hier: http://www.csci.csusb.edu/dick/c++std/cd2/lib-strings.html) muss sich das compare von char_traits wie folgt verhalten:

X::compare(p,q,n)

yields: 0 if for each i in [0,n) X::eq(p[i],q[i]) is true;
else, a negative value if, for some j in [0,n), X::lt(p[j],q[j]) is true and for each i in [0,j) X::eq(p[i],q[i]) is true;
else a positive value.

und compare von den Strings:

int compare(
  size_type pos1, size_type n1,
  const basic_string<charT,traits,Allocator>& str,
  size_type pos2, size_type n2
) const;

Returns:
basic_string<charT,traits,Allocator>(*this,pos1,n1).compare(
basic_string<charT,traits,Allocator>(str,pos2,n2)) .

und alle compare funktionen bilden am Ende auf eine Funktion ab, die sich wie folgt verhält:

int compare(const basic_string<charT,traits,Allocator>& str)

Effects:
Determines the effective length rlen of the strings to compare as
the smallest of size() and str.size(). The function then compares
the two strings by calling traits::compare(data(), str.data(),rlen).

Lernt man nicht schon in der ersten Klasse, wie man etwas alphabetisch sortiert?

ehrlich schrieb:

Lernt man nicht schon in der ersten Klasse, wie man etwas alphabetisch sortiert?

Lernt man nicht schon in der ersten Klasse, dass man einfach mal die Fresse halten sollte, wenn man nichts zu melden hat? Diese ganzen Dummschwätzer-unreg Kommentare gehen mir tierisch auf den Sack. Ich glaube ich muss mich bald mal registrieren, ansonsten halten die Leute mich noch für genauso dämlich. Und für den nächsten Volldeppen: Ich bin mir durchaus bewusst, dass ich nichts zum Thema beitrage, aber das musste einfach mal gesagt werden. Unglaublich ist das. Keine Ahnung von nichts, aber einfach mal dazwischenbrabbeln.

Ethon

314159265358979 schrieb:

std::lexicographical_compare

Wäre leider nicht korrekt, da man das Verhalten, das die Traits definieren, über den Haufen wirft.

Okay, danke für die Antworten. Dann gehe ich jetzt davon aus, dass

template<class Allocator>
        int compare(size_type pos1, size_type n1,
            std::basic_string<Char, Traits, Allocator> const& str,
            size_type pos2, size_type n2 ) const
        {
            return Traits::compare(data() + pos1, str.data() + pos2,
                std::min(n1, n2);
        }

ganz im Sinne des Standards ist.
Am Besten such ich mir Tests zu std::string, wirds sicher welche bei libstdc++ oder STLport oä. geben.

noch ehrlicher schrieb:

ehrlich schrieb:

Lernt man nicht schon in der ersten Klasse, wie man etwas alphabetisch sortiert?

Lernt man nicht schon in der ersten Klasse, dass man einfach mal die Fresse halten sollte, wenn man nichts zu melden hat? Diese ganzen Dummschwätzer-unreg Kommentare gehen mir tierisch auf den Sack. Ich glaube ich muss mich bald mal registrieren, ansonsten halten die Leute mich noch für genauso dämlich. Und für den nächsten Volldeppen: Ich bin mir durchaus bewusst, dass ich nichts zum Thema beitrage, aber das musste einfach mal gesagt werden. Unglaublich ist das. Keine Ahnung von nichts, aber einfach mal dazwischenbrabbeln.

Ich war sogar der erste der hier geantwortet hat, aber das anscheinend immer noch zu kompliziert und hat nochmal eine Seite Erklärungen gebraucht, da fragt man sich doch wie aufwendig man so simple Sachen erklären muss.