 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Helmut Zeisel
Guest
|
 Posted: Fri Apr 02, 2004 6:13 am Post subject: Re: Alphabetisch sortieren |
 |
|
Georg Maaß <georg (AT) bioshop (DOT) de> wrote
| Quote: | Fütter die Strings als Keys in eine Map und zähle im Value die Häufigkeit.
|
Wieso nicht std::multiset?
Helmut
--
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 |
|
 |
Georg Maaß
Guest
|
| Posted: Fri Apr 02, 2004 8:58 pm Post subject: Re: Alphabetisch sortieren |
|
|
Helmut Zeisel wrote:
| Quote: | Georg Maaß <georg (AT) bioshop (DOT) de> wrote
Fütter die Strings als Keys in eine Map und zähle im Value die Häufigkeit.
Wieso nicht std::multiset?
|
Weil ich das noch nicht benutzt habe und ich in 17.4.4 Muliset von
Stroustrup nicht erkennen kann, was das Multiset genau macht bzw. welche
Methoden und Operatoren es besitzt. Aus 17.1.2 geht hervor, daß es wohl
die Listen-Operationen unterstützt, nicht aber den Index-Operator, den
die Map hat. Für den gewünschten Zweck ist der aber auch nicht nötig.
Wenn ich dem Multiset die Häufigkeit eines Key nicht entnehmen kann,
dann ist es nicht geeignet. Wenn garantiert ist, daß keine Duplikate
vorkommen, dann genügt eventuell auch ein set. Die Map ist auf jeden
Fall sparsamer im Speichervebrauch, wenn Duplikate vorkommen, weil sie
die Duplikate nicht mehrfach abspeichert, sondern nur zählt.
--
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 |
|
|
helmut zeisel
Guest
|
| Posted: Sat Apr 03, 2004 4:59 am Post subject: Re: Alphabetisch sortieren |
|
|
Georg Maaß wrote:
| Quote: | Helmut Zeisel wrote:
Wieso nicht std::multiset?
Aus 17.1.2 geht hervor, daß es wohl
die Listen-Operationen unterstützt, nicht aber den Index-Operator, den
die Map hat. Für den gewünschten Zweck ist der aber auch nicht nötig.
|
Genau.
| Quote: | Wenn ich dem Multiset die Häufigkeit eines Key nicht entnehmen kann,
dann ist es nicht geeignet.
|
Kannst Du aber (z.B. mit dem Algorithmus std::count): ein Element taucht
beim Iterieren ueber ein Multiset so oft auf, wie es eingefuegt worden ist.
| Quote: | Wenn garantiert ist, daß keine Duplikate
vorkommen, dann genügt eventuell auch ein set.
|
Wenn aber Duplikate vorkommen, dann genügt ein multiset.
| Quote: | Die Map ist auf jeden
Fall sparsamer im Speichervebrauch, wenn Duplikate vorkommen, weil sie
die Duplikate nicht mehrfach abspeichert, sondern nur zählt.
|
Kommt drauf an, wie viele Duplikate vorkommen. Wenn wenig Duplikate
dabei sind, ist multiset sparsamer, da Du keinen Zaehler speichern
musst; ab einer gewissen Zahl von Duplikaten wird das Map aber
tatsaechlich sparsamer.
Wenn man es so programmiert, wie Du es vorgeschlagen hat, wird das
Programm mit multiset einfacher (zumindest der Ausagbeteil) - ich finde
es jedenfalls interessant, wie viele verschiedene Zugaenge man zu so
einem auf den ersten Blick simplen Problem haben kann.
Helmut
--
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 |
|
|
Rolf Magnus
Guest
|
| Posted: Sat Apr 03, 2004 9:24 am Post subject: Re: Alphabetisch sortieren |
|
|
Georg Maaß wrote:
| Quote: | Helmut Zeisel wrote:
Georg Maaß <georg (AT) bioshop (DOT) de> wrote in message
news:<c4694c$2f8a2f$3 (AT) ID-3551 (DOT) news.uni-berlin.de>...
Fütter die Strings als Keys in eine Map und zähle im Value die
Häufigkeit.
Wieso nicht std::multiset?
Weil ich das noch nicht benutzt habe und ich in 17.4.4 Muliset von
Stroustrup nicht erkennen kann, was das Multiset genau macht bzw.
welche Methoden und Operatoren es besitzt.
|
Es verwaltet die Werte in sortierter Reihenfolge und kann auch mehrere
gleiche Werte enthalten. Es ist wie eine multimap, nur daß es keinen
value gibt bzw. key und value eins sind.
| Quote: | Aus 17.1.2 geht hervor, daß es wohl die Listen-Operationen
unterstützt, nicht aber den Index-Operator, den die Map hat.
|
Was sollte der denn auch tun?
| Quote: | Für den gewünschten Zweck ist der aber auch nicht nötig. Wenn ich dem
Multiset die Häufigkeit eines Key nicht entnehmen kann, dann ist es
nicht geeignet.
|
Wieso die Häufigkeit? Der OP hat mit keinem Wort geschrieben, daß er die
Häufigkeit bestimmter Namen will. Er will sie nur sortiert ausgeben,
und dazu kann er sie einfach in ein Multiset schreiben und dann zum
Auslesen wieder darüber iterieren. Einfacher geht's doch nicht. Er
könnte die Namen sogar direkt per std::copy und einen ostream_iterator
nach cout ausgeben. Du mußt bei der Map erst die Anzahl auslesen und
dann in einer Schleife den Namen entsprechend oft ausgeben.
| Quote: | Wenn garantiert ist, daß keine Duplikate vorkommen, dann genügt
eventuell auch ein set.
|
Und wenn nicht, dann eben ein multiset.
| Quote: | Die Map ist auf jeden Fall sparsamer im Speichervebrauch, wenn
Duplikate vorkommen, weil sie die Duplikate nicht mehrfach
abspeichert, sondern nur zählt.
|
Das dürfte für die Aufgabe des OP nicht relevant sein. Außerdem kommt's
für den Speicherverbrauch immer noch darauf an, wie häufig Duplikate
überhaupt vorkommen. Wenn die selten sind, ist das Multiset sparsamer,
weil man nicht für jeden Namen noch einen zusätzlichen Integer
abspeichern muß.
--
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 |
|
|
Rolf Magnus
Guest
|
| Posted: Sat Apr 03, 2004 12:46 pm Post subject: Re: Alphabetisch sortieren |
|
|
helmut zeisel wrote:
| Quote: | ich finde es jedenfalls interessant, wie viele verschiedene Zugaenge
man zu so einem auf den ersten Blick simplen Problem haben kann.
|
Ich würde erwarten, daß viele Anfänger vermutlich weder die map noch das
set als naheliegendste Möglichkeit ansehen, sondern eher einen vector,
den man nach dem Füllen mit std::sort sortiert und dann ausgibt.
--
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 |
|
|
Georg Maaß
Guest
|
| Posted: Sat Apr 03, 2004 1:16 pm Post subject: Re: Alphabetisch sortieren |
|
|
Rolf Magnus wrote:
| Quote: | Wieso die Häufigkeit? Der OP hat mit keinem Wort geschrieben, daß er die
|
damit er weiß, wie oft er die mehrfachen Einträge ausgeben muß, denn
sonst wäre ja die Ausgabe nicht eine sortierte Lister der Eingabe,
sondern eine sortierte und um Multiplikate gekürzte Liste.
| Quote: | Außerdem kommt's
für den Speicherverbrauch immer noch darauf an, wie häufig Duplikate
überhaupt vorkommen. Wenn die selten sind, ist das Multiset sparsamer,
weil man nicht für jeden Namen noch einen zusätzlichen Integer
abspeichern muß.
|
Wenn das Multiset als eine Multimap implementiert ist, bei welcher der
Key sowohl als Key wie auch als Value abgespeichert ist und dafür das
Interface leicht beschnitten, dann ist das Set bzw. Multiset immer
teuerer hinsichtlich Speicherplatz als eine Map bzw. Multimap.
--
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 |
|
|
Georg Maaß
Guest
|
| Posted: Sat Apr 03, 2004 1:19 pm Post subject: Re: Alphabetisch sortieren |
|
|
Rolf Magnus wrote:
| Quote: | Ich würde erwarten, daß viele Anfänger vermutlich weder die map noch das
set als naheliegendste Möglichkeit ansehen, sondern eher einen vector,
den man nach dem Füllen mit std::sort sortiert und dann ausgibt.
|
Für kleine Vektoren und insbesondere bei nicht gleichmäßiger
Häufigkeitsverteilung der Keys über das Spektum möglicher Keys könnte
das sogar performanter sein als die Map/Set-Geschichten.
--
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: Sat Apr 03, 2004 1:50 pm Post subject: Re: Alphabetisch sortieren |
|
|
"Rolf Magnus" <ramagnus (AT) t-online (DOT) de> schrieb:
| Quote: | Ich würde erwarten, daß viele Anfänger vermutlich weder die map noch das
set als naheliegendste Möglichkeit ansehen, sondern eher einen vector,
den man nach dem Füllen mit std::sort sortiert und dann ausgibt.
|
Womit sie intuitiv die (oft) beste Wahl getroffen hätten:
--->>>------>>>--- sort_set.cpp --->>>------>>>---
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <iostream>
#include <ostream>
class timer {
std::clock_t start;
public:
void reset() { start = std::clock(); }
timer() { reset(); }
double sec_elapsed() const {
return double( std::clock() - start ) / CLOCKS_PER_SEC;
}
};
void test_set()
{
std::multiset<int> s;
for( unsigned c = 1000000; --c; s.insert( std::rand() ) );
}
int main()
{
std::srand(0);
for( unsigned c = 10; --c; test_set() );
timer t;
for( unsigned c = 10; --c; test_set() );
std::cout << t.sec_elapsed() << " sn";
}
---<<<------<<<--------------->>>------>>>---
| Quote: | g++ -W -Wall -ansi -pedantic -O2 sort_set.cpp -o sort_set.exe
Exit code: 0
sort_set.exe
40.953 s
Exit code: 0
---<<<------<<<---------------<<<------<<<--- |
--->>>------>>>--- sort_vector.cpp --->>>------>>>---
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
#include <ostream>
class timer {
std::clock_t start;
public:
void reset() { start = std::clock(); }
timer() { reset(); }
double sec_elapsed() const {
return double( std::clock() - start ) / CLOCKS_PER_SEC;
}
};
void test_vector_1()
{
std::vector<int> v(1000000);
std::generate( v.begin(), v.end(), std::rand );
std::sort( v.begin(), v.end() );
}
void test_vector_2()
{
std::vector<int> v;
for( unsigned c = 1000000; --c; v.push_back( std::rand() ) );
std::sort( v.begin(), v.end() );
}
int main()
{
std::srand(0);
for( unsigned c = 10; --c; test_vector_1() );
timer t;
for( unsigned c = 10; --c; test_vector_1() );
std::cout << t.sec_elapsed() << " sn";
std::srand(0);
for( unsigned c = 10; --c; test_vector_2() );
t.reset();
for( unsigned c = 10; --c; test_vector_2() );
std::cout << t.sec_elapsed() << " sn";
}
---<<<------<<<--------------->>>------>>>---
| Quote: | g++ -W -Wall -ansi -pedantic -O2 sort_vector.cpp -o sort_vector.exe
Exit code: 0
sort_vector.exe
2.688 s |
2.812 s
| Quote: | Exit code: 0
---<<<------<<<---------------<<<------<<<--- |
--
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 |
|
|
Rolf Magnus
Guest
|
| Posted: Sat Apr 03, 2004 2:53 pm Post subject: Re: Alphabetisch sortieren |
|
|
Georg Maaß wrote:
| Quote: | Rolf Magnus wrote:
Wieso die Häufigkeit? Der OP hat mit keinem Wort geschrieben, daß er
die
damit er weiß, wie oft er die mehrfachen Einträge ausgeben muß, denn
sonst wäre ja die Ausgabe nicht eine sortierte Lister der Eingabe,
sondern eine sortierte und um Multiplikate gekürzte Liste.
|
Ja, schon. Aber du schriebst:
| Quote: | Wenn ich dem Multiset die Häufigkeit eines Key nicht entnehmen kann,
dann ist es nicht geeignet.
|
Bei der Variante mit dem Multiset mußt du die Häufigkeit aber gar nicht
wissen, und daher ist deine Behauptung, es sei nicht geeignet, flscah.
| Quote: | Wenn das Multiset als eine Multimap implementiert ist, bei welcher der
Key sowohl als Key wie auch als Value abgespeichert ist und dafür das
Interface leicht beschnitten, dann ist das Set bzw. Multiset immer
teuerer hinsichtlich Speicherplatz als eine Map bzw. Multimap.
|
Falls der Wert doppelt abgespeichert würde, dann wäre es tatsächlich
meistens (theoretisch nicht immer, je nach länge des Strings und Größe
des Zählers) teurer. Aber ich wüßte nicht, wozu man den Container so
implementieren sollte, daß er alles doppelt speichert.
--
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 |
|
|
helmut zeisel
Guest
|
| Posted: Sat Apr 03, 2004 4:22 pm Post subject: Re: Alphabetisch sortieren |
|
|
Georg Maaß wrote:
| Quote: | Wenn das Multiset als eine Multimap implementiert ist, bei welcher der
Key sowohl als Key wie auch als Value abgespeichert ist und dafür das
Interface leicht beschnitten, dann ist das Set bzw. Multiset immer
teuerer hinsichtlich Speicherplatz als eine Map bzw. Multimap.
|
Es ist aber ueblicherweise umgekehrt: eine (Multi)Map ist ein (Multi)Set
von Paaren, bei denen zum Vergleichen nur der erste Teil des Paares
herangezogen wird.
Helmut
--
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 |
|
|
helmut zeisel
Guest
|
| Posted: Sat Apr 03, 2004 5:48 pm Post subject: Re: Alphabetisch sortieren |
|
|
Rolf Magnus wrote:
| Quote: | Falls der Wert doppelt abgespeichert würde, dann wäre es tatsächlich
meistens (theoretisch nicht immer, je nach länge des Strings und Größe
des Zählers) teurer. Aber ich wüßte nicht, wozu man den Container so
implementieren sollte, daß er alles doppelt speichert.
|
Die Standardcontainer muessen gleiche Werte mehrfach speichern: was
"gleich" bedeutet, definiert der Anwender; gleiche Werte brauchen aber
nicht die selben sein, daher muessen sie mehrfach gespeichert werden -
siehe Codebeispiel.
Helmut
#include <set>
#include <string>
#include <iostream>
struct A
{
A(std::string s, int i): first(s), second(i) {}
struct Cmp
{
bool operator()(const A& a1, const A& a2) const
{
return a1.first < a2.first;
}
};
std::string first;
int second;
};
int main()
{
using namespace std;
typedef multiset
S s;
s.insert(A("Key",1));
s.insert(A("Key",2));
cout << "Key is contained " << s.count(A("Key",3)) << " times" << endl;
for(S::const_iterator i=s.begin(); i!= s.end(); i++)
{
cout << i->second << endl;
}
return 0;
}
--
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 |
|
|
Georg Maaß
Guest
|
| Posted: Sun Apr 04, 2004 5:11 pm Post subject: Re: Alphabetisch sortieren |
|
|
helmut zeisel wrote:
| Quote: | Es ist aber ueblicherweise umgekehrt: eine (Multi)Map ist ein (Multi)Set
von Paaren, bei denen zum Vergleichen nur der erste Teil des Paares
herangezogen wird.
|
Ob das so üblich ist, kann ich nicht beurteilen, weil ich dazu ja
mehrere Implementierungen untersuchen müßte. Die Ausführungen im
Stroustrup legen jedoch nahe, daß die Sets als kastrierte Maps
implementiert werden, bei denen Key und Value gleich sind. Vielleicht
habe ich das Gelesene aber auch nur falsch interpretiert.
--
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 |
|
|
Rolf Magnus
Guest
|
| Posted: Sun Apr 04, 2004 6:25 pm Post subject: Re: Alphabetisch sortieren |
|
|
Georg Maaß wrote:
| Quote: | helmut zeisel wrote:
Es ist aber ueblicherweise umgekehrt: eine (Multi)Map ist ein
(Multi)Set von Paaren, bei denen zum Vergleichen nur der erste Teil
des Paares herangezogen wird.
Ob das so üblich ist, kann ich nicht beurteilen, weil ich dazu ja
mehrere Implementierungen untersuchen müßte. Die Ausführungen im
Stroustrup legen jedoch nahe, daß die Sets als kastrierte Maps
implementiert werden, bei denen Key und Value gleich sind.
|
Daraus lese ich eher, daß ein Set fast wie eine Map ist, nur ohne value.
Es klingt auch wirklich nicht besonders sinnvoll, zweimal denselben
Wert als Key und Value zu speichern. Man hätte dann intern eine Kopie
des Wertes, die erstens eh immer gleich dem Key sein muß und auf die
man zweitens sowieso nicht zugreifen 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 |
|
|
Georg Maaß
Guest
|
| Posted: Sun Apr 04, 2004 6:37 pm Post subject: Re: Alphabetisch sortieren |
|
|
Rolf Magnus wrote:
| Quote: | Daraus lese ich eher, daß ein Set fast wie eine Map ist, nur ohne value.
Es klingt auch wirklich nicht besonders sinnvoll, zweimal denselben
Wert als Key und Value zu speichern. Man hätte dann intern eine Kopie
des Wertes, die erstens eh immer gleich dem Key sein muß und auf die
man zweitens sowieso nicht zugreifen kann.
|
So lesen eben verschiedene Leute aus der selben Quelle ganz
unterschiedliches ...
Deshalb ist es wichtig zu diskutieren, damit man solche und vorallem
gravierendere Verständnisunterschiede bemerkt und aufklärt.
--
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 |
|
|
Helmut Zeisel
Guest
|
| Posted: Mon Apr 05, 2004 8:35 am Post subject: Implementierung von std::map/std::set, war Re: Alphabetisch |
|
|
Georg Maaß <georg (AT) bioshop (DOT) de> wrote
| Quote: | Rolf Magnus wrote:
Daraus lese ich eher, daß ein Set fast wie eine Map ist, nur ohne value.
Es klingt auch wirklich nicht besonders sinnvoll, zweimal denselben
Wert als Key und Value zu speichern. Man hätte dann intern eine Kopie
des Wertes, die erstens eh immer gleich dem Key sein muß und auf die
man zweitens sowieso nicht zugreifen kann.
So lesen eben verschiedene Leute aus der selben Quelle ganz
unterschiedliches ...
Deshalb ist es wichtig zu diskutieren, damit man solche und vorallem
gravierendere Verständnisunterschiede bemerkt und aufklärt.
|
Ich habe ein weinig nachgelesen; meine Aussage war primär durch einen
NIHCL Abkömmling inspieriert: in der NIHCL ist Dictionary (das
entspricht std::map, genauer einer hash_map) von Set abgeleitet und
als Set von Assoc (das entpricht std::pair) implementiert (Gorlen et
al., S 177f).
Bei der STL liegt die Sache ein wenig adrs: es ist ja weder std::set
von std::map abgeleitet, noch umgekehrt. Es finden sich aber folgende
Definitionen (Stroustrup 3e, 17.4.3)
template<class Key, class Cmp, class A> class std::set
{
typedef Key value_type;
...
}
und (Stroustrup 3e, 17.4.1.1)
template<class Key, class T, class Cmp, class A> class std::map
{
typedef pair<const Key, T> value_type;
...
}
Das deutet darauf hin, dass std:set keinen unnötigen Speicher
beanspruchen muss - zumindest erlaubt der Standard so eine
Implementierung.
Helmut
--
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
