Besseres set gesucht?

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.

Eisflamme

Ich hab ja gesagt, const_cast geht. Aber const_cast ist eben ein const_cast, die damit implizierte Aussage ist für mich: set ist nicht der Container, den Du suchst.

Hat aber ansonsten nur Vorteile, eigentlich gefällt mir die Idee. Ich finde ja sowieso, dass der iterator durch find nicht const sein sollte. Er sollte eben nur die Sortierelemente schützen. Aber das kann man in C++ nicht abbilden.

Also würdet ihr tatsächlich einfach den iterator um sein const entreichern?

knivil

Ich hab ja gesagt, const_cast geht. Aber const_cast ist eben ein const_cast, die damit implizierte Aussage ist für mich: set ist nicht der Container, den Du suchst.

Haeh? Mach den Key private und niemand wird ihn aendern koennen. std::set wird sicherlich nicht direkt verwendet, d.h. es gibt ein Ding, dass std:;set benutzt mit entsprechenden Methoden. D.h. const_cast kann gekapselt werden.

Also würdet ihr tatsächlich einfach den iterator um sein const entreichern?

Nein, das zurueckgegebene Element. Und keine Ahnung von "ihr", ich wuerde das so machen, ohne dein eigentliches Problem zu kennen. Wuerde ich dein eigentliches Problem kennen, koennte ich es auch anders loesen.

Aber das kann man in C++ nicht abbilden.

Doch, es gibt viele Moeglichkeiten: const_cast und private key. Auch kannst du eine eigene set implementieren. Auch kannst du einfach nur eine Indexmenge/Keymenge in einen std::vector verwalten, ...

PS: Wahrscheinlich ist std::set trotzdem der falsche Container.

Kellerautomat

Das Problem ist, dass std::set scheisse designt ist. Es nimmt an, dass der volle Zustand eines Objekts zum Vergleichen gebraucht wird. Darum nimmt z.b. find() auch einen T, anstatt das, was fuer einen Vergleich benoetigt wird. std::set ist deshalb ziemlich nutzlos. Ich bilde mir ein, dass es dafuer schon einen Proposal gibt, aber ich finde ihn gerade nicht.

boost::multi_index_container kann sowas, auch wenn er moeglicherweise Overkill ist.

Eisflamme

Kellerautomat:
Das ist auch meine Auffassung, endlich Mal etwas Bestätigung.

Und ja, Overkill will ich eigentlich nicht.

Gut, also scheint man da wohl echt gerne const_cast zu verwenden, das erscheint mir gerade am sinnvollsten.

Shade Of Mine

Und was hat nochmal genau gegen map gesprochen?
Oder auch einen sorted vector?

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

lower_bound ist hier dein freund.

Eisflamme

Gegen map spricht für mich, dass ich meine struct auseinanderreißen muss, was ich nicht will, weil ich die häufiger an andere Funktionen übergeben muss, die beides brauchen. Und dann habe ich immer zwei statt einem Parameter, obwohl das Ding logisch eins ist. Ich verstümmel ungern meine struct, nur weil der Container das erfordert.

sorted_vector habe ich ja vorgeschlagen, den finde ich gut. Aber den gibt es noch nicht, also müsste man sich den selbst basteln, oder? (ja, dass das nicht schwer ist, weil es Algos wie binary_search gibt, weiß ich)

Shade Of Mine

sorted vector: http://www.c-plusplus.net/forum/p2304315#2304315

Ich würde die struct als ganzes lassen und zusätzlich die teile die für die sortierung wichtig sind in eine eigene struct auslagern und diese als key benutzen. ein eigenes make_pair erstellt dann aus deiner struct die key-struct.

nachteil ist doppelter speicherverbrauch für die teile der struct die für die sortierung relevant sind.

ansonsten gibt es auch noch die möglichkeit ein set zu verwenden und hier einen wrapper um deine struct zu schreiben:

struct DeineStruct {
  int data;
};

struct MyWrapper {
  DeineStruct mutable impl;
  bool operator<(MyWrapper const& other) const { return impl < other.impl; }

  operator DeineStruct&() const { return impl; }
};

So kann MyWrapper der Key für das Set sein aber du kannst per impl und operator DeineStruct& easy die Werte ändern.

Eisflamme

Das klingt nach ausgezeichneten Vorschlägen, vielen Dank.

hustbaer

Eisflamme schrieb:

"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.

Boost MultiIndex unterstützt allgemein das Ändern von Objekten in einem Set, selbst wenn sich dadurch die Position ändern sollte:
http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/reference/ord_indices.html#modify

Und mit Intrusive-Containern funktioniert es natürlich auch.

KasF schrieb:

Wieviele Elemente steckst du in die set?

Und hast du schon geprofiled? Ebenfalls musst du auch nicht bei find und co durch den ganzen Baum wandern, deswegen ist es ja auch ein Baum. Kann es sein, dass du irgendwo einen Flaschenhals vermutest, wo keiner ist. Wie sagt man so schön "Premature optimization is the root oft evil". Natürlich ist es nicht schön das ganze Objekt auszutauschen, nur um einen Member zu ändern, aber das spielt gerade keine Rolle.