Element aus verschachtelter Datenstruktur löschen.

[nielsp]

Hallo zusammen!

Ich will bestimmte Anwendungseinstellungen in einer Struktur speichern. Dabei soll es möglich sein, verschiedene Kategorien zu verwenden. Jede einzelne Einstellung beseht dabei aus einem Pair, wobei der Schlüssel vom Typ std::string ist und der Wert vom Typ boost::any ist. Mein Versuch sieht also folgendermaßen aus:

struct node 
{
	void append(const std::string& rhs, const boost::any& lhs)
	{
		content.insert(std::make_pair(rhs, lhs));
	}
	std::map<std::string, boost::any> content;
};

Jetzt will ich aber Extrafunktionen haben, die z.B. das Zugreifen oder das Löschen von Einstellungen vereinfachen. Um dabei den Pfad zu einer bestimmten Einstellung anzugeben, habe ich mir überlegt, ein Objekt AccessObject zu haben, dass lediglich dazu verwendet wird, den Pfad in einem Ausdruck angeben zu können:

class AccessObject
{
private:
	std::vector<std::string> path;

public:
	AccessObject& append(const std::string& rhs)
	{
		path.push_back(rhs);
	}

	std::vector<std::string> get()
	{
		return path;
	}
};

Man kann jetzt also einfach:

AccessObject().append("parent").append("child1").append("child2").append("name").get()

schreiben und erhält dadurch eine Liste der einzelnen Pfadelemente.
Für den Zugriff auf ein Objekt will ich nun schreiben können:

access<std::string>(root, AccessObject("child1").append("child2").append("name").get());

Daher habe ich die Funktion folgendermaßen implementiert:

template<typename T>
T access(const node& root, const std::vector<std::string>& path)
{
	node current = root;
	for(int i=0; i<path.size(); ++i)
	{
		try
		{
			current = boost::any_cast<node>(current.content[path[i]]);
		}
		catch(std::exception& e)
		{
			return boost::any_cast<T>(current.content[path[i]]);
		}
	}
	return T();
}

Das funktioniert so auch ganz wunderbar.
Was mir jetzt allerdings Schwirigkeiten bereitet, ist die Funktion zum Löschen einer bestimmten Einstellung. Mein Versuch dazu sieht so aus:

void remove(node& root, const std::vector<std::string>& path)
{
	node& current = root;
	for(int i=0; i<path.size()-1; ++i)
	{
		current = boost::any_cast<node&>(current.content[path[i]]); 
                // Wenn das letzte Element des nächste ist, dann lösche dieses nächste. 
		if(path[path.size()] == path[i+1])
			current.content.erase(current.content.find(path[i+1]));
	}
}

Das aber gibt mir einen Speicherzugriffsfehler . Ich sitze nun schon einen halben Tag daran, und versuche nur, diese verdammte remove()-Funktion zu schreiben, scheitere aber jedesmal kläglich.

Danke für die Hilfe,

Niels

[nielsp]

Weiß wirklich niemand irgendetwas?

[Dravere]

Habe grad nicht viel Zeit, aber nur so schnell auf die Schnelle:

current = boost::any_cast<node&>(current.content[path[i]]);

Kommt mir verdächtig vor. Sollte das nicht boost::any_cast<node> heissen?

Grüssli

[nielsp]

Endlich kam mir der Geistesblitz. Dazu habe ich allerdings jedem Knoten einen Zeiger auf sein Elternknoten hinzugefügt.

void remove(node& root, const std::vector<std::string>& path)
{
	node current = root;
	for(unsigned int i=0; i<path.size(); ++i)
	{
		try
		{
			current = boost::any_cast<node>(current.content.find(path[i])->second);
		}
		catch(boost::bad_any_cast& e)
		{
			std::cout << e.what() << std::endl;
		}

		if(i == path.size()-2)
		{
			for(std::map<std::string, boost::any>::iterator iter = current.content.begin(); iter != current.content.end(); ++iter)
				if(iter->first == path[i+1])
					current.content.erase(current.content.find(path[i+1]));

			for(int j=i; j>=0; --j)
			{
				(*current.parent).content[path[j]] = current;
				current = *current.parent;
				if(!current.parent)
				{
					root = current;
					return;
				}
			}
			return;
		}
	}
}

Allerdings kommt mir das immer noch seltsam kompliziert vor für eine eigentlich doch triviale Angelegenheit. Ich wäre wirklich sehr erfreut, wenn einer, der sich etwas besser mit C++ auskennt als ich, sich das angucken könnte.

Vielen Dank!

Niels.

[Jocker16]

Ich hoffe mal, ich habe dein Problem richtig verstanden, und hier mein lösungsansatz:

void remove(node& root, const std::vector<std::string>& path)
{

    node* current = &root;  // man beachte das "&"
    unsigned int i=0;
    for(i=0; i<path.size()-1; ++i)
    {
        try
        {
            current = &boost::any_cast<node>(current->content.find(path[i])->second);
        }
        catch(boost::bad_any_cast& e)
        {
            std::cout << e.what() << std::endl;
        }

    }
    current->content.erase( path[i] ); // i== path.size()-1, also das letzte element in path
}

was ich in deinem Code noch nicht so ganz verstehe ist, wieso du über die Elemente iterierst wenn i==path.size()-2 ist.
Bzw. ich verstehs schon, weil du wohl sicherstellen willst, ob es den key path[path.size()-1] überhaupt gibt, was viel schneller getan wäre mit

if ( current.content.find(path[i+1]) != current.content.end() )

Aber noch eleganter ist die variante oben, indem man einfach erase mit dem pfad aufruft, und erase löscht einfach nix, wenns das nicht gibt. Wenn dich auch noch interessiert, ob es das gegeben hat, dann liefert die erase funktion 1 zurück, wenn das element gefunden wurde, ansonsten 0 (aber lies dazu einfach mal bei einer beliebigen C++ referenz nach).

Was ich hauptsächlich geändert habe: current ist nicht vom Typen node, sondern vom Typen node*, d.h. du kopierst nicht blöd deine gesamten maps unnötig, und was du an current veränderst, veränderst du natürlich automatisch an der gesamten struktur...

[nielsp]

Danke für die Antwort!

Dein Lösungsvorschlag scheint ja recht ähnlich mit meinem ersten. So gibt nämlich sowohl deine als auch meine Implementierung einen Speicherzugriffsfehler. Ich glaube, das Problem liegt in der folgenden Anweisung:

current = &boost::any_cast<node>(current->content.find(path[i])->second);

Dadurch wird ja root auf current begrenzt, alle Elemente aus dem Baum davor gehen aber verloren. Ansonsten danke auch für den Hinweis für Erase. Jetzt sieht das ganze schon ein wenig weniger kompliziert aus :p

Niels.

[Jocker16]

Du glaubst, das problem liegt dort????
Dann probiers doch aus, und sag genau, bei welcher zeile es abstürzt...
Füge ein paar std::cout << __FILE__ << __LINE__ << std::endl in deine remove Funktion und sag, wann es genau abstürzt. Bei welchem i und bei welcher zeile...

Und nein, wir haben vermutlich nicht den gleichen Fehler, denn du hattest in deiner ersten variante sowas wie: path[path.size()], was eigentlich zu einem absturz führen sollte, da es nur path[path.size()-1] gibt, aber kein nächstes element mehr.

Du veränderst root eigentlich nicht, sondern du veränderst worauf die Variable current zeigt. Am Anfang zeigt sie auf root, und in der for-schleife ändert sich ständig worauf current gerade zeigt. Aber damit veränderst du nicht, die Variable root selbst.
Aber so wie du es am Anfang hattest hast du recht, du veränderst nämlich root selbst, da eine Referenz nur am anfang initialisiert werden kann. Danach sind alles zuweisungen, d.h. du veränderst ständig die root variable. Aber einen Pointer kannst du ständig neu "initialisieren".
hier vielleicht nochmal zum verständnis der unterschied:

int a=1;
int &b=a;
int c=2;
b=c;  // --> a bekommt automatisch den 2, da b und a den selben speicherbereich referenzieren, diese zeile heißt nicht, dass b und c jetzt den selben speicherbereich referenzieren...

int a=1;
int *b=&a;
int c=1;
b=&c;
*b=2;  // hier hat jetzt c den wert 2 bekommen, weil b auf den speicherbereich von c zeigt, aber a ist unverändert und hat noch immer den wert 1

[nielsp]

Ich glaube, verstanden zu haben, warum deine Implementierung fehlschlägt. Mit

&boost::any_cast<node>(current->content.find(path[i])->second);

verweist du nämlich auf eine temporäre Variable (das kam eigentlich schon in den Compilerwarnungen: warning: taking address of temporary ). Der Speicherzugriffsfehler kommt nämlich auch genau bei dieser Anweisung. Und nach Node* casten geht natürlich auch nicht, schließlich ist ja Node* nicht dasselbe wie Node (boost::bad_any_cast). Leider scheine ich nicht klug genug zu sein, herauszufinden, wie ich trotzdem auf current->content.find(path[i])->second richtig verweise. Ich hatte davor probiert: &(current->content.find(path[i])->second) , aber dann kommt: cannot convert node** to node* in assignment.

Ich wäre Für Hilfe sehr dankbar!

Niels

[Jocker16]

boost::any_cast<node*>( &(current->content.find(path[i])->second) );

klappt das?

[nielsp]

Nein, eben das klappt nicht. Genau das wollte ich eigentlich mit dem vorhergehenden Post sagen (war wohl ein wenig unglücklich formuliert). Es kommt:
cannot convert 'node**' to 'node*' in assignment

[Jocker16]

ok, wenn man die Doku von any_cast sich anguckt, dann ist hier die entscheidende Zeile:
template<typename ValueType> ValueType * any_cast(any * operand);

damit ist klar, dass es lauten muss:

boost::any_cast<node>( &(current->content.find(path[i])->second) );

Sieht komisch aus (da man zunächst erwartet, dass eine node rauskommt, und nicht node*), aber es sollte funktionieren.

Die Access funktion würde ich auch auf pointer umstellen, da du ansonsten immer alles kopierst bei der zuweisung

current = boost::any_cast.....

was bei einer tiefen Hierarchie schnell mal langsam werden kann.

So, ich hoffe, damit ist dir jetzt geholfen, und die lösch funktion geht so wie du es brauchst...

[nielsp]

Danke Jocker16! Jetzt haben sich alle Probleme in Luft aufgelöst.

Niels