Besseres set gesucht?

Eisflamme

Hi,

ich hätte gerne ein set, bei dem man etwas ändern kann. Die Frage hatte ich so ähnlich schon Mal gestellt, aber ich will auch Komfort und ein vector mit binary_search ist für mich erstmal keiner, da würde ich wohl einen anderen Container rumschreiben.

"Set, bei dem man etwas ändern kann? Das ergibt keinen Sinn."
Doch, weil nicht alle Teile der set-struct Schlüsselelemente sind und ich will Nicht-Schlüssel-Elemente ändern können. Dennoch will ich die Sortierung und den Aufbau des Sets gegeben haben.

struct Element
{
    int key1;
    int key2;

    int nonKey1;
    int nonKey2;

    Element(int key1, int key2); // nonKey1/2 set with dummy value or not set
    Element(int key1, int key2, int nonKey1, int nonKey2);

    bool operator<(const Element& rhs); // entsprechend key1/2
};

tollesSet<Element> xy;

xy.insert(Element(1, 2, 3, 4));

xy.find(Element(1, 2))->nonKey1 = 10;

Warum mich erase nebst insert stört? Weil der beim find/erase und beim insert den Baum durchlaufen muss.

Über map hört man nur schlechtes, da sei ja nichts cachelokal, zu viele Indirektionen und was-weiß-ich. Ich wollte ja auch Mal eine map nehmen für genau das und meinte, dass eine map logisch doch ein set mit eben dieser Unterscheidung sei, aber das war wohl nicht korrekt.

Vielleicht muss ich Mal in die STL debuggen, um den ganzen Overhead hinter den Containern zu verstehen.

Gibt es das, was ich will? Oder würdet ihr euch einen eigenen Container-Wrapper um vector schreiben? So was wie sorted_vector? Jeder insert, lookup setzt dann voraus, dass das Ding sortiert ist. Natürlich geht Einfügegeschwindigkeit weg, das wäre aber nicht schlimm (wenn ein Ändern eben nicht aus Löschen + Einfügen besteht ).

Ethon

Map und Set sind in der Implementierung fast identisch. Bevor du ein Set mit Schlüsseln in den Elementen nutzt, auf jeden Fall eine Map verwenden.

Eisflamme

Ich meine aber echt, dass mir ein set Mal empfohlen wurde, von einer map im gleichen Atemzug aber abgeraten wurde. Solche Aussagen verstehe ich dann nicht.

Hm, und eigentlich würde ich meine struct schon ungern auseinanderreißen. Zwar ist ein Teil schlüssel-relevant, der andere nicht, dennoch ist es im Grunde eine struct. Diverse Funktionen erwarten eben diese struct und brauchen auch beide Teile. Aber für die Sortierung ist eben nicht alles wichtig. Doppelte Einträge gibt es trotzdem nicht, da die Schlüssel eindeutig sind. Die Nicht-Schlüssel-Attribute drücken aber einen Zustand aus, der sich ändern kann.

Eigentlich wäre ein änderbares set einfach genau richtig. Ich würde fast gerne die Änderung einfach mit irgendwelchen bösen casts machen, denn was soll schon passieren, wenn ich Nicht-Schlüsselwerte ändere? Aber das sieht dann auch wieder blöd aus.

Skym0sh0

Quelle?

Bis zum Beweis gilt die Unschuld, würde ich erstmal sagen...

Eisflamme

Wenn es hier um Schuldzuweisungen ginge, ja. Darum geht's aber nicht. Wenn jetzt hier alle wie ein Mann sagen, dass map == set mit getrenntem Schlüssel/Wert-Bereich, dann gut.

Aber ich find die map eh nicht mehr so schön, weil ich es nicht so gerne auseinanderreißen möchte. Dann muss ich jeder Funktion, die eigentlich nur diese struct will, das map::value_type übergeben und das ist doch ekelhaft. Die Struktur soll sich nicht auseinanderreißen, sondern brav nach meinen eigenen Kriterien einsortiert werden... aber einfach dennoch änderbar sein. Das ist doch keine zweifelhafte Anforderung?

Mein Code oben ab Zeile 15 soll einfach klappen mit tolles_set = gesuchter Container (der kein set sein muss).

Ethon

Kannst ja etwas Redundanz walten lassen und aus

struct Foo
{
    int key;
    std::string value;
};

set<Foo> bar;

->

struct Foo
{
    int key;
    std::string value;
};

map<int, Foo> bar;

machen. Solange der Key nicht groß ist, juckt es ja nicht wirklich ...

daddy_felix

Eisflamme schrieb:

Die Struktur soll sich nicht auseinanderreißen, sondern brav nach meinen eigenen Kriterien einsortiert werden... aber einfach dennoch änderbar sein. Das ist doch keine zweifelhafte Anforderung?

und was spricht da jetzt gegen ein std::set<YourStruct>?

Skym0sh0

Eisflamme schrieb:

Wenn es hier um Schuldzuweisungen ginge, ja. Darum geht's aber nicht. Wenn jetzt hier alle wie ein Mann sagen, dass map == set mit getrenntem Schlüssel/Wert-Bereich, dann gut.

Nein, klar. Aber ich würde gerne wissen, woher du das Wissen beziehst, dass eine map doof sein soll.

Ich meine, der Standard gibt doch die Komplexitäten vor, der sagt dir wie lange das alles dauern soll.

Eisflamme

Skym0sh0:
Ja, aber Laufzeiten sind ja nicht der Weisheits letzter Schluss. Ich weiß noch, dass mit Cache-Lokalitäten, mehr Indirektionen usw. argumentiert wurde. Das wird von der O-Notation nicht abgedeckt.

Ethon:
Der Key besteht leider aus einem unsigned int und einem bool, also müsste ich schon eine struct für die map erstellen, unschön.

daddy_felix:
Dass ich keine Einträge ändern kann. Ändern heißt löschen + einfügen. 1. wird dann zwei Mal pro "Änderungs"-Operation der Baum durchlaufen und 2. kann ich nicht alle Elemente über eine Schleife ändern, was ich aber manchmal möchte (set::erase liefert ja void, selbst wenn nicht, wäre der iterator spätestens nach set::insert kaputt). Der Code ab Zeile15 mit tollesSet = set kompiliert nicht.

Wenn du wirklich nicht viel ändern willst und das so benutzen möchtest wie du es quasi schon hast, dann nimm std::set und mach deine non-keys mutable.

set::find liefer dir immer einen const_iterator. Die version mit non-const ist ebenfalls ein const_iterator, da set::iterator auch const ist! Siehe Standard.

Eisflamme

set::find liefer dir immer einen const_iterator. Die version mit non-const ist ebenfalls ein const_iterator, da set::iterator auch const ist! Siehe Standard.

weiß ich und:

dann nimm std::set und mach deine non-keys mutable.

Ja wie denn? Die einzige Variante, die ich sehe, ist ein const_cast.

struct Element 
{ 
    int key1; 
    int key2; 

    mutable int nonKey1; 
    mutable int nonKey2; 

    Element(int key1, int key2); // nonKey1/2 set with dummy value or not set 
    Element(int key1, int key2, int nonKey1, int nonKey2); 

    bool operator<(const Element& rhs); // entsprechend key1/2 
}; 

set<Element> xy; 

xy.insert(Element(1, 2, 3, 4)); 

xy.find(Element(1, 2))->nonKey1 = 10;

knivil

ich hätte gerne ein set, bei dem man etwas ändern kann.

Was willst du? Was willst du aendern?

Die Frage hatte ich so ähnlich schon Mal gestellt

Aeh ja? Daran soll sich jetzt jeder erinnern.

Ich meine aber echt, dass mir ein set Mal empfohlen wurde, von einer map im gleichen Atemzug aber abgeraten wurde. Solche Aussagen verstehe ich dann nicht.

Voellig irrelevant. Bestimmt war es M3gahack0r

Eisflamme

Öh, geil, das Schlüsselwort kannte ich noch gar nicht. Und das macht in diesem Kontext natürlich absolut Sinn.

Hat das denn auch Nachteile im Sinne von schlechtem Design? Ich finde nämlich, die gibt es hier nicht. Aber jetzt frage ich mich natürlich auch, was eigentlich der Zweck von mutable ist und ob es zB hierfür vorgesehen ist. Das passt ja wie die Faust aufs Auge!

knivil:
Endlich Mal wieder jemand, der auch Mal etwas draufschlägt, ich hab mich hier schon viel zu wohl gefühlt.

Deine Frage wird im zweiten Absatz beantwortet, was natürlich voraussetzt, dass man diesen liest, mein Fehler vorauszusetzen, dass mein OP gelesen wird, sorry:

"Set, bei dem man etwas ändern kann? Das ergibt keinen Sinn."
Doch, weil nicht alle Teile der set-struct Schlüsselelemente sind und ich will Nicht-Schlüssel-Elemente ändern können.

Vielleicht willst Du aber noch mehr Details, von denen ich ausging, sie seien unwichtig. Dann brauche ich aber wohl eine präzisere Frage.

Skym0sh0

Wie Herb Sutter sagt: "const und mutable sind deine Freunde"
Mutable ist dafür da, dass du Interna, die aber nicht den zustand deines Objekts reflektieren, ändern kannst.

Ein blödes Beispiel wäre, wie oft die Funktionen einer Klasse aufgerufen werden:

class Foo
{
	mutable unsigned int m_functionCalls;
	int m_x;
	int m_y;
	// ...

public:
	Foo()
	 : /*...*/ m_functionCalls(0)
	{ }

	void foo1()
	{
		this->m_functionCalls++;
		// ...
	}

	void foo2()
	{
		this->m_functionCalls++;
		// ...
	}
	void foo3() const
	{
		this->m_functionCalls++;
		// ...
	}
	void foo4() const
	{
		this->m_functionCalls++;
		// ...
	}
	void foo5() const
	{
		this->m_functionCalls++;
		// ...
	}
};

Was mutable macht, kannst du ja überall nachlesen. Aber letztlich unterstützt (bzw. soll unterstützen) es die const-correctness.

Eisflamme

Die Funktionsweise von mutable ist ja erstmal einfach. Aber ich bin etwas unsicher, ob das für mein set gut ist. Also es erfüllt meinen Wunsch, daher finde ich es erstmal sehr gut!

Leider gehören diese Variablen sehr wohl zum Zustand, nicht aber zum Sortierzustand. Wenn ich const Element& einer Funktion übergebe, will ich eigentlich nicht, dass die die mutable-Elemente ändern kann. Also ist es unsauber die Attribute mutable zu machen (wobei erase/insert noch unsauberer ist und ich immer noch keinen passenden Container kenne; was haltet ihr denn von sorted_vector?)

Skym0sh0

Dann kapsel das ab:

struct MyStruct
{
	bool flag;
	int ding;
	double d;

	bool operator<(MyStruct const& other) const
	{
		return this->ding < other.ding;
	}
};

struct MyStructEncapsulation
{
	MyStruct ms;
	mutable int * ding;

	MyStructEncapsulation(MyStruct const& ms)
	 : ms(ms), ding(&ms.ding)
	{}
};

Irgendwie so.
Achtung, der Ansatz ist nicht zu Ende gedacht, da müsstest du eventuell ein wenig Energie reinstecken, kann auch sein, dass es sehr aufwändig wird.

Aber es geht halt drum, dein Element zu verstecken, den Zugriff darauf zu liefern, aber auch das const aushebeln zu können.

knivil

mutable ist nicht der geeignete Weg, da es nur eingesetzt wird, um ein Zusammenspiel mit std::set zu ermoeglichen, aber nichts mit der eignetlichen Klasse zu tun hat.

Wieviele Elemente steckst du in die set?

knivil

Ich sehe kein Problem:

#include <set>
#include <iostream>

struct value
{
    int key;
    int data;

    bool operator<(value const& e) const
    {
        return key < e.key;
    }
};

int main()
{
    std::set<value> values;
    value v1 = {0, 1};
    values.insert(v1);

    value& r = const_cast<value&>(*values.begin());
    r.data = 2;

    std::cerr << (*values.begin()).data << '\n';
}

Endlich Mal wieder jemand, der auch Mal etwas draufschlägt

Koenntest du mal genau erklaeren, warum ein const_cast deine Probleme nicht loest.