Problem mit Anzahl Elementen in einer Map

schmidm6

Hallo zusammen

Ich habe kürzlich ein komisches Verhalten bei einem von mir verwendeten Map festgestellt:

Hier mal der Code:

#include <ctime>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int main()
{
	typedef unsigned long int uli;

	uli n=259;

	// initialize random seed:
	srand ( time(NULL) );

	// init the map
	std::map<uli,uli> randPermMap;
	std::map<uli,uli>::iterator iter;

	for (uli i=1; i<=n; i++)
		randPermMap[rand()] = i;

	uli j = 0;
	for(iter = randPermMap.begin(); iter != randPermMap.end(); iter++)
	{
		std::cout << j << " map output 1: " << iter->first << " second: " << iter->second << "\n";
		j++	;
	}

	return 0;
}

Solange n <=256 ist, funktioniert alles wunderbar, sobald n grösser wird, kann es vorkommen, dass nicht mehr alle Elemente in der MAP richtig definiert werden und es kommt zu einem Programm absturz.
Weiss jemand, wieso dass so ist?

Gruss und besten Dank

Michael

MFK

Kann ich nicht reproduzeren.

schmidm6 schrieb:

Solange n <=256 ist, funktioniert alles wunderbar, sobald n grösser wird, kann es vorkommen, dass nicht mehr alle Elemente in der MAP richtig definiert werden und es kommt zu einem Programm absturz.

Was heißt denn "nicht richtig definiert"? Was für ein Absturz? Was sagt der Debugger?

schmidm6

Funktioniert bei dir der Code, den ich gepostet habe?

Ich verwende MinGW auf WinXP
setze für n mal den Wert 628! Also z.B. n=628

es sollte nicht 627 zeilen ausgegeben werden, bei mir sind es jedes mal weniger als 620 ....!
Das wäre falsch

Gruss und danke für deine Bemühungen
Michael

unskilled

Vll weil rand() auch mal die gleichen Werte liefert?
Somit werden diese Werte in der map überschrieben und nicht hinzugefügt..

bb

Dravere

Ehm, könnte es daran liegen?

for (uli i=1; i<=n; i++) 
  randPermMap[rand()] = i;

Und du meintest eher:

for (uli i=1; i<=n; i++) 
 randPermMap[i] = rand();

Edit: Mist, unskilled war schneller

Grüssli

schmidm6

Der Fehler liegt in der Logik.

Der Sinn dieses Codes liegt im erstellen einer Funktion, die einen Vektor mit zufällig angeordneten Integern zurück gibt. Die Integer sind im Bereich von 1:n!
Die zufällige Reihenfolge erzeuge ich, in dem im Map der Key mit einem Zufallswert gefüllt wird. Sobald das Map fertig erstellt ist, liegt dieses ja nach dem "Key" sortiert vor, also sind die Integer in einer mehr oder weniger
zufälligen reihenfolge. Nur je grösser der Vektor wird, also n, umso eher wird es wahrscheinlich, dass zweimal dieselbe zufallszahl generiert wird. Diese werden im map jedoch nicht zugelassen. Daher sollte ich wohl eher multimap verwenden. Damit funktionierts auf jeden Fall.

Der Code:

#include <ctime>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int main()
{
    typedef unsigned long int uli;

    uli n=1024;

    // initialize random seed:
    srand ( time(NULL) );

    // init the map
    std::multimap<uli,uli> randPermMap;
    std::multimap<uli,uli>::iterator iter;

    for (uli i=1; i<=n; i++)
        randPermMap.insert(pair<uli,uli>(rand(),i));

    uli j = 0;
    for(iter = randPermMap.begin(); iter != randPermMap.end(); iter++)
    {
        std::cout << j << " map output 1: " << iter->first << " second: " << iter->second << "\n";
        j++    ;
    }

    return 0;
}

Besten Dank für die Hilfe

Michael

asc

schmidm6 schrieb:

es sollte nicht 627 zeilen ausgegeben werden, bei mir sind es jedes mal weniger als 620 ....!
Das wäre falsch

Dann erklär mir mal was du hiermit tun willst:

randPermMap[rand()] = i;

Du willst also eine laufende Nummer mit einen Zufälligen Key setzen. Das rand() auch gleiche Ziffern ausspucken kann, ist dir hoffentlich auch klar.

Wenn du statt dessen:

randPermMap[i] = rand();

geschrieben hättest, würde auch deine gewünschte Anzahl herauskommen.

(Getestet habe ich das Programm unter VS2010 Beta, mit dem gleichen Ergebnis wie du auch erlebt hast: Der Zufallsgenerator hat einfach mehrmals gleiche Zahlen ausgespuckt).

unskilled

[offtopic]
VS2010 Beta

lohnt sich die beta schon oder sollte man besser bei der VS9 bleiben?
gibts die beta mittlerweile iwo legal zu dln? ^^
[/offtopic]

bb

asc

schmidm6 schrieb:

Der Sinn dieses Codes liegt im erstellen einer Funktion, die einen Vektor mit zufällig angeordneten Integern zurück gibt.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main()
{
    std::size_t count = 1000;
	std::vector<std::size_t> valueList;
	valueList.reserve(1000);

	for(std::size_t i=1; i<=count; ++i)
        valueList.push_back(i);
	std::random_shuffle(valueList.begin(), valueList.end());
	std::copy(valueList.begin(), valueList.end(), std::ostream_iterator<std::size_t>(std::cout, "\n"));

    return 0;
}

asc

unskilled schrieb:

[offtopic]
VS2010 Beta

lohnt sich die beta schon oder sollte man besser bei der VS9 bleiben?
gibts die beta mittlerweile iwo legal zu dln? ^^
[/offtopic]

bb

http://www.microsoft.com/visualstudio/en-us/products/2010/default.mspx
Microsoft Download-Seite (VS2010)

Meiner Meinung nach ist es aber zumindest im C++ Bereich ein Rückschritt (Zumindest empfinde ich die Fehlermeldungen im C++ Bereich teils als kryptischer als je zuvor). Achtung: Unter Umständen musst du einen Ordner im 4er Framework umkopieren (Wenn er Dateien nicht findet, einfach mal eine Ebene höher schauen wie der Ordner heißt).

Ansonsten ist mein Ersteindruck nicht schlecht.

schmidm6

Es tauchte zwischendurch nochmals die Frage auf, für was das sein Soll.

Also, Ziel ist es, am Ende einen Vektor zu haben (einen MTL4-Vektor, siehe
http://www.osl.iu.edu/research/mtl/mtl4/) mit Integer-Werten, die zufällig angeordnet sind und im Bereich 0 bis n liegen.
Darum habe ich den "Key" mit Zufallszahlen generiert und mit einem fortlaufenden Integer gefüllt. Das Map sortiert sich ja selber nach den "Keys", wodurch sich die Reihenfolge der Integer ändert.

Aber wie schon bemerkt, habe ich vergessen, dass rand auch mal die gleiche Zahl bringen kann. Daher habe ich den Code auf multimap geändert und damit scheints zu funktionieren.

Besten Dank noch für den hinzugefügten Code, den werde ich mir gerne heute Abend zu gemüte führen, um wirklich zu verstehen, was da geschieht.

Gruss und schönen Tag

Michael

asc

schmidm6 schrieb:

Besten Dank noch für den hinzugefügten Code, den werde ich mir gerne heute Abend zu gemüte führen, um wirklich zu verstehen, was da geschieht.

Wichtig an meinen Code ist im wesentlichen:

#include <algorithm>

Für die Algorithmen die, die Standardbibliothek von Haus aus mitbringt. Und dazu gehört auch ein Algorithmus der einen Container zufällig anordned, namens random_shuffle. Die Übergabe ist der Bereich, der durcheinander gewürfelt werden soll.

std::random_shuffle(valueList.begin(), valueList.end());

Und zwar wird der Bereich wie in den Algorithmen üblich mit dem Iterator auf das erste Element des Zielbereiches begonnen, und mit dem Element, das eins nach dem Ende des Zielbereiches liegt (end() liefert das Element HINTER dem Letzten Element) abgeschlossen.

Die sonstigen Zeilen dienen nur dem füllen des Containers mit Werten, und der Ausgabe (std::copy in Zusammenhang mit dem std::ostream_iterator). std::size_t ist ein typedef auf einen sehr großen unsigned-Typ.

cu André