3. 2 Fragen zur std::map

2 Fragen zur std::map

  • ?

    Hallo!
    Ich habe mir gerade http://www.cplusplus.com/reference/stl/map/ durchgelesen, aber noch ein Paar fragen.

    1.) Welche Laufzeit zum finden eines keys hat eine map?

    2.) Brauche ich eine compare-Funktion schreiben wenn ich als key std::String verwende? Oder reicht die default variante?

    3.) Eignet sich die Map um Resourcen zu verwalten? (Key=Dateiname, T=Bilder)
    :xmas1:

    0
  • C

    JJ schrieb:

    1.) Welche Laufzeit zum finden eines keys hat eine map?

    Das asymptotische Verhalten steht bei den Funktionen beschrieben. Was das exakt für Laufzeiten sind ist implementierungs- / computerabhängig, das kannst du nur testen.

    JJ schrieb:

    2.) Brauche ich eine compare-Funktion schreiben wenn ich als key std::String verwende? Oder reicht die default variante?

    Default reicht.

    JJ schrieb:

    3.) Eignet sich die Map um Resourcen zu verwalten? (Key=Dateiname, T=Bilder)

    Ja. Falls du noch mehr Performance rauskitzeln willst, nutzt du nicht std::string sondern ranges die direkt in den Dateipuffer zeigen (der dann natürlich dauerhaft im Speicher bleiben muss), und sortierst erst nach Länge und dann alphabetisch.

    PS:
    Das waren 3 Fragen. 😉

    0
  • ?

    Danke für die schnelle Antwort.

    Den Kommentar zu 3.) hab ich nicht verstanden...
    Ich möchte doch mit einem key Dateien laden und dann darauf verweisen bzw. nur auf den Speicher verweisen, falls die Datei schonmal geladen wurde.

    0
  • C

    "Ressourcen" klingt für mich so, als würdest du diese aus einer Datei bekommen.
    Also in etwa so:

    Texture xyz.tga
Model blubb.obj
Texture lol.tga
...

    Und anstatt jetzt für "xyz.tga", "blubb.obj" und "lol.tga" jeweils einen neuen std::string anzulegen, hälst du den Dateiinhalt einfach im Speicher und baust dir eine Klasse mit begin/end Paaren, die dann auf die Keynamen zeigen. Und nutzt dann eine "std::map<Range, ..>".

    0
  • 3

    JJ schrieb:

    1.) Welche Laufzeit zum finden eines keys hat eine map?

    O(log(N))

    JJ schrieb:

    2.) Brauche ich eine compare-Funktion schreiben wenn ich als key std::String verwende? Oder reicht die default variante?

    std::lessstd::string sortiert alphabetisch. Wenn du z.B. Anti-alphabetisch (gibts dafür eigentlich ein Wort?) sortieren möchtest, kannst du std::greaterstd::string verwenden.

    JJ schrieb:

    3.) Eignet sich die Map um Resourcen zu verwalten? (Key=Dateiname, T=Bilder)
    :xmas1:

    Was meinst du genau mit "Resourcen verwalten"? Willst du besitzende Zeiger in die Map stecken?

    0
  • ?

    Wenn du eine Hashmap möchtest, gäbe es std::unordered_map, vorrausgesetzt deine Standardbibliothek implementiert das schon.

    0
  • B

    JJ schrieb:

    Ich möchte doch mit einem key Dateien laden und dann darauf verweisen bzw. nur auf den Speicher verweisen, falls die Datei schonmal geladen wurde.

    Eine Art Cache... Dafür kann man durchaus eine map<FileNameType, Resource> verwenden. Da vermutlich eine Sortierung nicht benötigt wird, kann man auch eine unordered_map<FileNameType, Resource> verwenden.

    0
  • ?

    Was meinst du genau mit "Resourcen verwalten"? Willst du besitzende Zeiger in die Map stecken?

    Ich möchte Bilder vom Typ sf::Image aus der SFML-Bibliothek in die map stecken und als key dafür ihren Dateinamen verwenden, damit ich bei mehrfachbenutzung eines sf::Image nicht nochmal laden muss, sondern einfach eine Referenz übergebe. Die Klasse die ich dafür schrieb sieht so aus:

    class CResources {
private:
	std::map<std::string, sf::Image> Images;
	const sf::Image& addImage(std::string Filename)  {
		sf::Image newImage;
		if (!newImage.LoadFromFile(Filename)) {
			//Error
		}

		return Images.insert(std::pair<std::string, sf::Image> (Filename, newImage)).first->second;
	}
public:
	const sf::Image& getImage(std::string Filename) {
		if(Images.find(Filename) != Images.end()) {
			return Images.find(Filename)->second;
		}
		else {
			return addImage(Filename);
		}
	}
};

    Bekomm ich damit Probleme? Kann es sein das die map intern neu verwaltet und mir meine referenzen auf Mapeinträge ungültig macht? So wie beim std::vector?

    0
  • B

    JJ schrieb:

    Bekomm ich damit Probleme? Kann es sein das die map intern neu verwaltet und mir meine referenzen auf Mapeinträge ungültig macht? So wie beim std::vector?

    Nein die bleiben gültig.

    0
  • N

    Aber du solltest schauen, dass du schwergewichtige Klassen wie sf::Image nicht unnötig kopierst.

    D.h. ich würde das Bild zuerst einfügen und dann laden. Ist zwar etwas mühsamer für Rollback-Semantik (zumal sf::Image kein Swap() hat), aber dafür verschwendest du im Normalfall keine Zeit mit Pixel Kopieren.

    0
  • C

    Oder du nimmst std::move. 😉

    0
  • N

    cooky451 schrieb:

    Oder du nimmst std::move. 😉

    Was nur was bringt, wenn sf::Image movable ist. Entweder durch selbst definierten Move-Konstruktor und -Zuweisungsoperator oder durch einen automatisch generierten, sofern der Compiler es unterstützt und die Big Three nicht definiert wurden.

    std::move() ist eine gute Sache, aber bis es konsequent eingesetzt werden kann, werden noch einige Jahre ins Land ziehen... :xmas2:

    0

  • Bei "schwergewichtigen" Klassen wie sf::Image kann man IMO bedenkenlos zu std::shared_ptr bzw. boost::shared_ptr greifen, wenn man sich das Leben damit leichter machen kann.
    Also std::map<std::string, std::shared_ptr<sf::image>> .
    Bzw. wenn man unbedingt will kann man auch std::unique_ptr verwenden.

    In dem Fall würde ich wohl eher std::shared_ptr wählen: wieso verbieten dass der "Client-Code" ein sf::Image weiterverwendet, nachdem das Manager-Objekt ( CResources ) bereits zerstört wurde?

    Dann kann man weiterhin das Bild erstmal vollständig laden, und erst danach in die map einfügen -> kein Rollback mehr nötig.
    Beim kopieren des shared_ptr (Einfügen in die Map) fallen dann 2-3 Interlocked Befehle an, was aber in diesem Fall kaum ins Gewicht fallen wird.

    0
  • ?

    Das mit dem shared_ptr hört sich gut an. Allerdings sag mir der Compiler das er std::shared_ptr nicht kennt. Was muss ich dafür installieren/einbinden?

    Was ist hier mit Rollback gemeint?
    Und was sind Interlocked Befehle?

    Und noch eine Frage:
    Wenn ich sowas schreiben würde:

    std::vector<CClass*> CClassVec;
   CClassVec.push_back(&CClass());

    wie lange lebt CClass im vector?

    0
  • C

    Damit gibst du einen Pointer auf ein temporäres Objekt zurück, das sofort nach dem Befehl zerstört wird. Keine gute Idee. 😉
    Für shared_ptr brauchst du <memory>. Ich würde allerdings unique_ptr empfehlen.

    0
  • 3

    JJ schrieb:

    Und was sind Interlocked Befehle?

    Ein shared_ptr hält intern einen (um genau zu sein zwei, aber das ist im Moment nebensächlich) Referenzzähler. Wenn ein shared_ptr kopiert wird, wird der Zähler inkrementiert. Wird ein shared_ptr zerstört, dann wird er dekrementiert. Sobald der Refernzzähler auf 0 geht, wird das Objekt zerstört. Dieses Inkrementieren und Dekrementieren wird über Funktionen gemacht, die threadsicher sind, damit die Referenzzähler immer "richtig" bleiben.

    JJ schrieb:

    Und noch eine Frage:
    Wenn ich sowas schreiben würde:

    std::vector<CClass*> CClassVec;
   CClassVec.push_back(&CClass());

    wie lange lebt CClass im vector?

    Ganz einfach: Du holst die Addresse eines temporären Objekts, somit wird das Objekt gleich wieder zerstört und du hast einen ungültigen Zeiger eingefügt.

    cooky451 schrieb:

    Ich würde allerdings unique_ptr empfehlen.

    Das hängt wirklich vom Anwendungsfall ab. Mir gefällt die Idee von hustbaer eigentlich ziemlich gut. Vor allem könnte man im Client-Code auch weak_ptr auf die Objekte halten, was mir auch nützlich erscheint.

    0
  • ?

    Hallo nochmal :xmas1: !

    Bin grad den Boost::shared_ptr am einbinden und bin dann nach etlichen Fehlermeldungen bei diesem compilierbaren Code gelandet:

    #pragma once
#include <map>
#include <SFML/Graphics.hpp>
#include <Boost/shared_ptr.hpp>

class CResources {
private:
	std::map<std::string, boost::shared_ptr<sf::Image>> Images;
	const boost::shared_ptr<sf::Image> addImage(std::string Filename) {
		boost::shared_ptr<sf::Image> newImage(new sf::Image());

		#pragma region Errormessages
			if (!newImage.get()->LoadFromFile(Filename)) {
				std::cerr << "const CResources::addImage(std::string Filename)\n";
				std::cerr << "I/O error while reading file. File may not exist:\n \"" << Filename << "\"" << std::endl;
			}
		#pragma endregion

		std::pair<std::string,  boost::shared_ptr<sf::Image>> newInsert(Filename, newImage);
		return Images.insert(newInsert).first->second;
	}
public:
	const boost::shared_ptr<sf::Image> getImage(std::string Filename) {
		if(Images.find(Filename) != Images.end()) {
			return Images.find(Filename)->second;
		}
		else {
			return addImage(Filename);
		}
	}
};

    Ist das ok so? Verwende ich die Container sinngemäß? Sollte ich die namespaces weglassen? (also using namespace std etc. einfügen) ich finde das sieht einwenig unübersichtlich aus im moment. Für ein paar gute Codeschnipsel wäre ich dankbar :).

    Danke für eure Mühe!
    Bisher bin ich gut vorwärts gekommen...

    0
  • C

    Warum nutzt du nicht std::shared_ptr? (Oder unique_...^^)
    Ansonsten:
    - Hilft dir das #pragma region wirklich? Das sind doch nur 4 Zeilen.
    - Zeile 20: "auto NewInsert = std::make_pair(Filename, NewImage);" Oder gleich die Zeile weg und insert(std::make_pair(..));
    - Zeile 25: Warum durchsuchst du die map zwei mal? Das ist doch eine ziemliche Performanceverschwendung. Ich denke mal nicht, dass das optimiert wird. Wie wäre es mit:

    auto found = Images.find(Filename);
if (found != std::end(Images))
  ..
    0
  • ?

    Das #pragma region hab ich überall bei den Fehlermeldungen, dann steht da immer eine Zeile "Errormessages", statt eine fetter Block mit fehlerbehandlungsroutinen.

    Warum ich boost::shared_ptr statt std::shared_ptr verwende?
    Ich habe versucht <memory> zu includen ging dann immernoch nicht, dann hab ich mir einfach boost gezogen, das brauche ich wahrscheinlich sowieso in naher Zukunft :).

    auto frisst mein complier nicht.

    Error	1	error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
Error	2	error C2440: 'initializing' : cannot convert from 'std::_Tree<_Traits>::iterator' to 'int'
Error	3	error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
Error	4	error C2440: 'initializing' : cannot convert from 'std::_Tree<_Traits>::iterator' to 'int'

    Ich hab VS 2008, liegt das daran?
    Ich glaub deshalb habe ich auch das std::shared_ptr nicht...

    Hab stattdessen das ganze ausgeschrieben:

    std::map<std::string, boost::shared_ptr<sf::Image>>::iterator Found(Images.find(Filename));
		if(Found != Images.end()) {
    0

  • JJ schrieb:

    auto frisst mein complier nicht.
    [...]
    Ich hab VS 2008, liegt das daran?
    Ich glaub deshalb habe ich auch das std::shared_ptr nicht...

    Ja liegt daran und du glaubst richtig 🙂

    Wobei shared_ptr im "Feature Pack" für VS 2008 drinnen ist, bzw. genau so im SP1.
    Allerdings nur mit Visual Studio Versionen >= Standard (d.h. NICHT Express).

    Aber nimm ruhig Boost, dort ist shared_ptr gewachsen, und die funktionieren zu 99% gleich wie die in std::.

    0
Anmelden zum Antworten