Besseres set gesucht?

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.

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.