Besseres set gesucht?

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.

Eisflamme

Ich arbeite gerade den ganzen Tag und hab dann immer Einfälle und die gebe ich hier zum Besten und suche nach Lösungen. Ich komme leider nicht immer direkt zum profilen oder dazu Dinge anders umzusetzen. Lernen und Entwicklung laufen etwas auseinander (aber fernab von disjunkt!).

Premature Optimization mache ich nicht, ich weiß genau, wo die Software zu langsam ist. Und premature ist da auch nichts, die Funktionalität steht schon in anderer Variante.

Nur ist es natürlicherweise unelegant, wenn ich Ändern durch Löschen + Einfügen bewerkstellige, das ist für mich einfach ein Konzeptfehler und den gedenke ich zu beheben, weil ich lieber elegant und sauber statt umständlich und dreckig code. Hältst Du das für nachvollziehbar?

Natürlich ist es nicht schön das ganze Objekt auszutauschen, nur um einen Member zu ändern, aber das spielt gerade keine Rolle.

Du meinst für Deine Vermutung oder für mich? Für mich spielt es nämlich in der Tat eine große Rolle!

Für die Vermutung meinte ich. Ich bin selbst auch kein Fan von der mutable Lösung, aber einen anderen Designvorschlag können wir auch nicht machen, da wir nicht wissen, was du modellieren möchtest. Das mit mutable ist jetzt halt nur eine programmatische Lösung, keine logische.

Vermutlich sind key1 und key2 aber die hole cards

hustbaer

Habt ihr mich alle auf Ignore?
Ich hab' gerade zwei andere Vorschläge abgeliefert die beide wunderbar funktionieren...

Eisflamme

hustbaer:
Nein, tut mir Leid, ich hatte nur noch nicht Gelegenheit da reinzuschauen, da ich mit MultiIndex keine Erfahrung habe und dafür erst den Kopf freikriegen muss. Aber das sieht interessant aus und ich werde mir das definitiv noch anschauen!

KasF & knivil:
Ich finde ehrlich gesagt nicht, dass es hier notwendig wäre das genaue Problem zu kennen. Shade of Mine und hustbaer haben das Problem gelöst, gute Wege aufgezeigt. Die mussten auch nicht wissen, was ich "genau" mache. Genau genug steht es imo im OP.

Und die key-Dinger sind ein 13-Bit-Element, das die zwei Holecards ver-und-ed anzeigt und ein bool, der sagt, ob die suited sind. Der Value-Teil ist eine Suits-Klasse: die besteht aus einem 16-Bit, der Suits anzeigt, wobei jedes Bit für eine Kombination von zwei Suits steht, der Information und welche Suit-Klasse das ist (off-suited, suited, pair), zudem auch noch einen 16-Bit-Typ, der sagt, wie viele Suits hier maximal gesetzt werden dürfen. Hat das jetzt weitergeholfen? Ich denke nicht, da ich jetzt noch mehr dazu erklären müsste, schätze ich. Dann habe ich aber irgendwann den ganzen Programmkomplex hier in Foren-Form abgebildet. Dann würde das Forum meine gesamte Arbeit erledigen. Hätte zwar auch was, aber ich glaube, Einzelfragen sind sinnvoller.

Dankeschön jedenfalls

Shade und hustbaer hätten das mit Sicherheit besserer und sauberer lösen können, wenn sie in der Problemstellung stecken würden. Das du absichtlich die Problemstellung hier verkompliziert darstellst, hilft auch keinem weiter.

Nun denn, du scheinst und warst noch nie an einem anderen Design interessiert. Du hattest ein C++ Problem und wolltest genau die Lösung dazu erhalten. Fur saubere Softwareentwicklung wie du es geschrieben hast, bist du resistent.

Michael E.

KasF: Ich verstehe ehrlich gesagt das Problem nicht. Eisflamme hat eine präzise Frage zur Umsetzung seines Designs gestellt. Die Informationen waren ausreichen, um ihm eine genaue Antwort zu geben. Gut, das mit dem "map ist pöse langsam" (BTW @Eisflamme: eine binäre Suche ist auch nicht gerade cachefreundlich ) war etwas wirr, stört aber nicht weiter. Wenn du hier eine Frage stellst, willst du doch bestimmt auch nicht zuerst dein gesamtes Design vorstellen und rechtfertigen.

Jester

Das ist doch nur das übliche Säbelrassel hier: dir fällt keine lösung ein? Dann gibt es zwei möglichkeiten a) postuliere, dass ohne die genaue problemstellung das nicht gelöst werden kann oder b) dass das schon vom design/modellierung her ganz falsch klingt... Möglicherweise nebst überleitung zu a).