 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Hubert Schmid
Guest
|
 Posted: Sun Oct 03, 2004 11:30 am Post subject: swap und Standard-Algorithmen |
 |
|
Hallo,
mir ist aufgefallen, dass einige Standard-Algorithmen (bei gcc-3.4)
Kopieroperationen an Stellen verwenden, an denen ich zunächst
swap-Aufrufe erwartet hätte. Beispiele: std::remove, std::unique
Ich habe testweise mal unique mit swap implementiert, und die
swap-Variante war bei Nicht-POD-Typen erwartungsgemäß auch deutlich
schneller.
Nach einer kurzen Suche im Standard bin ich jetzt allerdings der
Meinung, dass eine Implementierung mit (unqualifiziertem) swap nicht
konform ist, da der Standard keine Aussage darüber macht, wie sich ein
"überladenes" swap zu Verhalten hat.
namespace foo {
struct bar { int value; };
swap(bar& lhs, bar& rhs) { }
}
std::vector<foo::bar> v(...);
std::unique(v.begin(), v.end());
In dem Beispielcode verhält sich std::unique mit swap nicht so, wie es
der Standard verlangt.
Ist das nicht ein Defekt im Standard? IMHO sollte der Standard
fordern, wie sich "Überladungen" von swap zu Verhalten haben, damit
einige Algorithmen alternativ auch mit swap implementiert werden
können. Insbesondere auch Algorithmen aus Dritt-Bibliotheken.
Gruß, Hubert
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
 |
Thomas Maeder
Guest
|
| Posted: Sun Oct 03, 2004 1:04 pm Post subject: Re: swap und Standard-Algorithmen |
|
|
Hubert Schmid <h.schmid-usenet (AT) gmx (DOT) de> writes:
| Quote: | mir ist aufgefallen, dass einige Standard-Algorithmen (bei gcc-3.4)
Kopieroperationen an Stellen verwenden, an denen ich zunächst
swap-Aufrufe erwartet hätte. Beispiele: std::remove, std::unique
Ich habe testweise mal unique mit swap implementiert, und die
swap-Variante war bei Nicht-POD-Typen erwartungsgemäß auch deutlich
schneller.
|
Bei Typen, wo die Kopier-Zuweisung dynamische Ressourcen allozieren muss,
wird die swap-Variante schneller sein; bei anderen Typen wird die Variante
mit Kopier-Zuweisung schneller sein.
Was fehlt, ist eine standardisierte Operation, welche einem Objekt den Wert
eines anderen Objekts zuweist, wobei der Zustand dieses anderen Objekts
anschliessend egal ist (na ja, konsistent muss er noch sein).
Eine solche Operation könnte dann wahlweise mit Kopier-Zuweisung oder
"shallow copy" implementiert werden. Das ist beides schneller als swap()
und würde für Operationen wie std::remove() und std::unique() genügen.
| Quote: | Nach einer kurzen Suche im Standard bin ich jetzt allerdings der
Meinung, dass eine Implementierung mit (unqualifiziertem) swap nicht
konform ist, da der Standard keine Aussage darüber macht, wie sich ein
"überladenes" swap zu Verhalten hat.
namespace foo {
struct bar { int value; };
swap(bar& lhs, bar& rhs) { }
}
std::vector<foo::bar> v(...);
std::unique(v.begin(), v.end());
In dem Beispielcode verhält sich std::unique mit swap nicht so, wie es
der Standard verlangt.
Ist das nicht ein Defekt im Standard?
|
std::remove() ist ja exakt spezifiziert, und zwar, wie Du schreibst, auf eine
Weise, welche die Verwendung von swap() ausschliesst. Defekt liegt also wohl
keiner vor.
| Quote: | IMHO sollte der Standard
fordern, wie sich "Überladungen" von swap zu Verhalten haben, damit
einige Algorithmen alternativ auch mit swap implementiert werden
können. Insbesondere auch Algorithmen aus Dritt-Bibliotheken.
|
Meines Wissens sind entsprechende Vorschläge gemacht worden. Vielleicht wird
das Resultat davon in C++0x auftauchen.
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Markus Schaaf
Guest
|
| Posted: Sun Oct 03, 2004 3:39 pm Post subject: Re: swap und Standard-Algorithmen |
|
|
"Hubert Schmid" <h.schmid-usenet (AT) gmx (DOT) de> schrieb:
| Quote: | mir ist aufgefallen, dass einige Standard-Algorithmen (bei gcc-3.4)
Kopieroperationen an Stellen verwenden, an denen ich zunächst
swap-Aufrufe erwartet hätte. Beispiele: std::remove, std::unique
|
Quality-of-Implementation-Issue. Und ja, man hätte in den Standard mehr
Forderungen an die Implementierung schreiben sollen, aber das ist ein
generelles Problem.
| Quote: | Ich habe testweise mal unique mit swap implementiert, und die
swap-Variante war bei Nicht-POD-Typen erwartungsgemäß auch deutlich
schneller.
|
Mit POD hat das nicht direkt was zu tun, eher damit, ob der D'tor
nichttriviale Dinge tut.
| Quote: | Nach einer kurzen Suche im Standard bin ich jetzt allerdings der
Meinung, dass eine Implementierung mit (unqualifiziertem) swap nicht
konform ist, da der Standard keine Aussage darüber macht, wie sich ein
"überladenes" swap zu Verhalten hat.
|
Richtig. Wenn, dann muß »std::swap« verwendet werden. Aber ich denke,
das ist auch genau die Idee für diesen "Algorithmus".
| Quote: | Ist das nicht ein Defekt im Standard? IMHO sollte der Standard
fordern, wie sich "Überladungen" von swap zu Verhalten haben, damit
einige Algorithmen alternativ auch mit swap implementiert werden
können. Insbesondere auch Algorithmen aus Dritt-Bibliotheken.
|
Unsinn. Wenn Du die Arbeitsweise der Std-Algorithmen beeinflussen willst,
mußt Du »std::swap« spezialisieren.
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Hubert Schmid
Guest
|
| Posted: Mon Oct 04, 2004 6:33 pm Post subject: Re: swap und Standard-Algorithmen |
|
|
"Markus Schaaf" <markus (AT) sags-per-mail (DOT) de> writes:
| Quote: | "Hubert Schmid" <h.schmid-usenet (AT) gmx (DOT) de> schrieb:
Ist das nicht ein Defekt im Standard? IMHO sollte der Standard
fordern, wie sich "Überladungen" von swap zu Verhalten haben, damit
einige Algorithmen alternativ auch mit swap implementiert werden
können. Insbesondere auch Algorithmen aus Dritt-Bibliotheken.
Unsinn. Wenn Du die Arbeitsweise der Std-Algorithmen beeinflussen
willst, mußt Du »std::swap« spezialisieren.
|
Ich verstehe nicht, was du mir sagen willst. Ich kann std::swap nicht
spezialisieren, weil es eine Template-Funktion ist. Im Namespace "std"
darf ich swap IIRC auch nicht überladen.
So wie ich den Standard verstehe (beispielsweise 25.2.9), müssen die
Standard-Algorithmen "swap" statt "std::swap" verwenden. Nur auf diese
Weise kann ich die Standard-Algorithmen mit einer effizienten
swap-Methode für eigene Datentypen verwende.
Gruß, Hubert
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Hubert Schmid
Guest
|
| Posted: Mon Oct 04, 2004 6:40 pm Post subject: Re: swap und Standard-Algorithmen |
|
|
Thomas Maeder <nvgicmomjvlmaa (AT) mailinator (DOT) com> writes:
| Quote: | Hubert Schmid <h.schmid-usenet (AT) gmx (DOT) de> writes:
mir ist aufgefallen, dass einige Standard-Algorithmen (bei gcc-3.4)
Kopieroperationen an Stellen verwenden, an denen ich zunächst
swap-Aufrufe erwartet hätte. Beispiele: std::remove, std::unique
Ich habe testweise mal unique mit swap implementiert, und die
swap-Variante war bei Nicht-POD-Typen erwartungsgemäß auch deutlich
schneller.
Bei Typen, wo die Kopier-Zuweisung dynamische Ressourcen allozieren
muss, wird die swap-Variante schneller sein; bei anderen Typen wird
die Variante mit Kopier-Zuweisung schneller sein.
|
Das ist wahrscheinlich der Grund dafür, dass die Funktion std::unique
nicht mit swap definiert ist. Im Gegensatz zu std::reverse ist
std::unique bei manchen Typen mit swap eben langsamer.
| Quote: | Was fehlt, ist eine standardisierte Operation, welche einem Objekt
den Wert eines anderen Objekts zuweist, wobei der Zustand dieses
anderen Objekts anschliessend egal ist (na ja, konsistent muss er
noch sein).
Eine solche Operation könnte dann wahlweise mit Kopier-Zuweisung
oder "shallow copy" implementiert werden. Das ist beides schneller
als swap() und würde für Operationen wie std::remove() und
std::unique() genügen.
|
Eine solche Operation gibt es leider (noch) nicht. Aber im Prinzip
macht swap genau das, nur dass diese Funktion eben noch ein klein
wenig mehr macht (aber maximal das Dreifache).
Ich selbst verwende häufig swap für eine Move-Semantik.
Gruß, Hubert
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Markus Schaaf
Guest
|
| Posted: Mon Oct 04, 2004 7:51 pm Post subject: Re: swap und Standard-Algorithmen |
|
|
"Hubert Schmid" <h.schmid-usenet (AT) gmx (DOT) de> schrieb:
| Quote: | Wenn Du die Arbeitsweise der Std-Algorithmen beeinflussen
willst, mußt Du »std::swap« spezialisieren.
Ich verstehe nicht, was du mir sagen willst. Ich kann std::swap nicht
spezialisieren, weil es eine Template-Funktion ist. Im Namespace "std"
darf ich swap IIRC auch nicht überladen.
|
Du darfst AFAIK Templates spezialisieren. Es gibt zwar keine partiellen
Spezialisierungen von Funktionstemplates (kann man mit Überladung
"umgehen", die ist jedoch wohl nicht erlaubt), wohl aber (vollständige)
Spezialisierungen -- mehr braucht man für »std::swap« nicht.
| Quote: | So wie ich den Standard verstehe (beispielsweise 25.2.9), müssen die
Standard-Algorithmen "swap" statt "std::swap" verwenden.
|
Ich weiß nicht, wie Du das da rauslesen willst. (Der Standard benutzt
in seinen Beschreibungen IIRC nie qualifizierte Bezeichner. Ich lese
dort z.B. genau das Gegenteil.)
| Quote: | Nur auf diese
Weise kann ich die Standard-Algorithmen mit einer effizienten
swap-Methode für eigene Datentypen verwende.
|
Das ist falsch. §14.8/1, _erster_ Satz. (Natürlich unter der Annahme,
daß man spezialisieren darf, wovon ich fest überzeugt bin, jedoch ad
hoc keine Stelle zitieren kann.)
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Hubert Schmid
Guest
|
| Posted: Mon Oct 04, 2004 10:09 pm Post subject: Re: swap und Standard-Algorithmen |
|
|
"Markus Schaaf" <markus (AT) sags-per-mail (DOT) de> writes:
| Quote: | "Hubert Schmid" <h.schmid-usenet (AT) gmx (DOT) de> schrieb:
Wenn Du die Arbeitsweise der Std-Algorithmen beeinflussen willst,
mußt Du »std::swap« spezialisieren.
Ich verstehe nicht, was du mir sagen willst. Ich kann std::swap
nicht spezialisieren, weil es eine Template-Funktion ist. Im
Namespace "std" darf ich swap IIRC auch nicht überladen.
Du darfst AFAIK Templates spezialisieren. Es gibt zwar keine
partiellen Spezialisierungen von Funktionstemplates (kann man mit
Überladung "umgehen", die ist jedoch wohl nicht erlaubt), wohl aber
(vollständige) Spezialisierungen -- mehr braucht man für »std::swap«
nicht.
|
Das war mein Fehler. Ich habe angenommen, dass man Template-Funktionen
überhaupt nicht spezialisieren kann. In der Tat sind nur partielle
Spezialisierungen nicht erlaubt.
Dann stellt sich mir aber die Frage, ob ich nun std::swap für meine
eigenen Typen spezialisieren soll, oder besser swap im Namensraum der
eigenen Typen überladen soll. Bisher habe ich immer den zweiten Weg
gewählt, der mir sauberer erscheint, und mit dem ich bisher auch noch
keine Probleme hatte.
Mittlerweile bin ich aber noch aus einem anderen Grund verwirrt. Ich
habe gerade festgestellt, dass einige Standard-Algorithmen bei gcc-3.4
überhaupt nicht (std::)swap aufrufen (beispielsweise
std::reverse). Stattdessen rufen sie die Funktion std::iter_swap auf,
die die beiden Werte immer mit drei Kopien vertauscht.
Der folgende Code gibt beispielsweise nichts aus:
#include <algorithm>
#include <iostream>
class Foo { };
namespace std {
template <>
void swap<Foo>(Foo& lhs, Foo& rhs)
{
std::cout << "swap" << std::endl;
Foo temp = lhs;
lhs = rhs;
rhs = temp;
}
}
int main()
{
Foo bar[10];
std::reverse(bar, bar + 10);
}
Egal wie man den Standard interpretiert, konform ist das doch nicht
mehr? Oder habe ich wieder einen anderen Fehler gemacht?
Gruß, Hubert
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Markus Schaaf
Guest
|
| Posted: Tue Oct 05, 2004 3:56 pm Post subject: Re: swap und Standard-Algorithmen |
|
|
"Hubert Schmid" <h.schmid-usenet (AT) gmx (DOT) de> schrieb:
| Quote: | Mittlerweile bin ich aber noch aus einem anderen Grund verwirrt. Ich
habe gerade festgestellt, dass einige Standard-Algorithmen bei gcc-3.4
überhaupt nicht (std::)swap aufrufen (beispielsweise
std::reverse). Stattdessen rufen sie die Funktion std::iter_swap auf,
die die beiden Werte immer mit drei Kopien vertauscht.
|
Wenn man nur lange genug draufschaut, versteht man den Standard am
Ende noch. Ich meine, nicht juristisch nagelfest, aber im Sinne von
"wie er gemeint ist". Wenn bei "25.2.9 Reverse" steht: "... applies
/swap/ to all pairs of iterators ...", dann ist mit "swap" die
abstrakte Operation im Sinne des Abschnitts 25.2.2 gemeint, nicht
irgendeine spezielle Funktion. Welche davon besonders geeignet ist,
mag im Ermessen des Implementors liegen.
Ich würde es als Mangel der Library (der Implementierung) ansehen,
daß das unspezialisierte »iter_swap« nicht auf »swap« zurückfällt.
Wahrscheinlich fehlt im Std die Stelle, daß Algorithmen für ihre
internen Operationen immer die spezifischste Operation aus »std«,
die zur Verfügung steht, verwenden müssen. Vermutlich erschien
das den Autoren als Selbstverständlichkeit.
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
