Sollte "Set" eine Get-Methode haben?

Lassen Sie uns diese C # -Klasse haben (in Java wäre es fast dasselbe)

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}

   public override bool Equals(object obj) {
        var item = obj as MyClass;

        if (item == null || this.A == null || item.A == null)
        {
            return false;
        }
        return this.A.equals(item.A);
   }

   public override int GetHashCode() {
        return A != null ? A.GetHashCode() : 0;
   }
}

Wie Sie sehen können, ist die Gleichheit von zwei Instanzen von MyClass hängt dieA nur ab. Es kann also zwei Instanzen geben, die gleich sind, aber unterschiedliche Informationen in ihrer BEigenschaft enthalten.

In einer Standardsammlungsbibliothek mit vielen Sprachen (einschließlich C # und natürlich Java) gibt es eine Set ( HashSetin C #), eine Sammlung, die höchstens ein Element aus jedem Satz gleicher Instanzen enthalten kann.

Man kann Gegenstände hinzufügen, Gegenstände entfernen und prüfen, ob das Set einen Gegenstand enthält. Aber warum ist es unmöglich, einen bestimmten Gegenstand aus dem Set zu bekommen?

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

//I can do this
if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) {
    //something
}

//But I cannot do this, because Get does not exist!!!
MyClass item = mset.Get(new MyClass {A = "Hello", B = "See you"});
Console.WriteLine(item.B); //should print Bye

Die einzige Möglichkeit, meinen Artikel abzurufen, besteht darin, die gesamte Sammlung zu durchlaufen und alle Artikel auf Gleichheit zu prüfen. Dies dauert jedochO(n) Zeit statt O(1)!

Ich habe noch keine Sprache gefunden, die unterstützt wird. Alle "gebräuchlichen" Sprachen, die ich kenne (Java, C #, Python, Scala, Haskell ...), scheinen auf dieselbe Weise gestaltet zu sein: Sie können Elemente hinzufügen, aber nicht abrufen. Gibt es einen guten Grund, warum all diese Sprachen etwas nicht unterstützen, das so einfach und offensichtlich nützlich ist? Sie können nicht einfach alle falsch sein, oder? Gibt es Sprachen, die dies unterstützen? Vielleicht ist es falsch, einen bestimmten Gegenstand aus einem Set zurückzuerhalten, aber warum?

Es gibt einige verwandte SO-Fragen:

/programming/7283338/getting-an-element-from-a-set

/programming/7760364/how-to-retrieve-actual-item-from-hashsett

Das Problem dabei ist nicht, dass HashSeteine GetMethode fehlt , sondern dass Ihr Code aus der Sicht des HashSetTyps keinen Sinn ergibt .

Diese GetMethode lautet effektiv "Hol mir diesen Wert, bitte", worauf die .NET Framework-Leute vernünftigerweise antworten würden: "Wie? Sie haben diesen Wert bereits <confused face />".

Wenn Sie Elemente speichern und sie dann abrufen möchten, Dictionary<String, MyClass>indem Sie einen anderen, geringfügig anderen Wert angeben, verwenden Sie Folgendes:

var mset = new Dictionary<String, MyClass>();
mset.Add("Hello", new MyClass {A = "Hello", B = "Bye"});

var item = mset["Hello"];
Console.WriteLine(item.B); // will print Bye

Die Gleichheitsinformation tritt aus der gekapselten Klasse aus. Wenn ich den Satz der beteiligten Eigenschaften ändern wollte Equals, müsste ich den Code außerhalb ändern MyClass...

Na ja, aber das liegt daran, dass MyClassAmok mit dem Prinzip des geringsten Erstaunens (POLA) läuft. Wenn diese Gleichheitsfunktionalität gekapselt ist, ist es völlig vernünftig anzunehmen, dass der folgende Code gültig ist:

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) 
{
    // this code is unreachable.
}

Um dies zu verhindern, MyClassmuss eindeutig dokumentiert werden, welche Form der Gleichheit es gibt. Wenn Sie das getan haben, ist es nicht mehr gekapselt und eine Änderung der Funktionsweise dieser Gleichstellung würde das offene / geschlossene Prinzip brechen. Ergo sollte es sich nicht ändern und ist daher Dictionary<String, MyClass>eine gute Lösung für diese ungewöhnliche Anforderung.

Sie haben bereits das Element, das sich "in" der Gruppe befindet - Sie haben es als Schlüssel übergeben.

"Aber es ist nicht die Instanz, mit der ich Add aufgerufen habe" - Ja, aber Sie haben ausdrücklich behauptet, dass sie gleich sind.

A Setist auch ein Sonderfall von a Map|Dictionary, mit void als Werttyp (auch die nutzlosen Methoden sind nicht definiert, aber das spielt keine Rolle).

Die Datenstruktur, nach der Sie suchen, ist ein Ort, an Dictionary<X, MyClass>dem Xdas As irgendwie aus den MyClasses herauskommt.

Der C # -Wörterbuchtyp ist in dieser Hinsicht nützlich, da Sie einen IEqualityComparer für die Schlüssel bereitstellen können.

Für das gegebene Beispiel hätte ich folgendes:

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}
}

public class MyClassEquivalentAs : IEqualityComparer<MyClass>{
   public override bool Equals(MyClass left, MyClass right) {
        if (Object.ReferenceEquals(left, null) && Object.ReferenceEquals(right, null))
        {
            return true;
        }
        else if (Object.ReferenceEquals(left, null) || Object.ReferenceEquals(right, null))
        {
            return false;
        }
        return left.A == right.A;
   }

   public override int GetHashCode(MyClass obj) {
        return obj?.A != null ? obj.A.GetHashCode() : 0;
   }
}

So verwendet:

var mset = new Dictionary<MyClass, MyClass>(new MyClassEquivalentAs());
var bye = new MyClass {A = "Hello", B = "Bye"};
var seeyou = new MyClass {A = "Hello", B = "See you"};
mset.Add(bye);

if (mset.Contains(seeyou)) {
    //something
}

MyClass item = mset[seeyou];
Console.WriteLine(item.B); // prints Bye

Ihr Problem ist, dass Sie zwei widersprüchliche Konzepte der Gleichheit haben:

• tatsächliche Gleichheit, bei der alle Felder gleich sind
• Setze Mitgliedschaftsgleichheit, wobei nur A gleich ist

Wenn Sie die tatsächliche Gleichheitsrelation in Ihrem Set verwenden, tritt das Problem des Abrufens eines bestimmten Elements aus dem Set nicht auf. Um zu überprüfen, ob sich ein Objekt im Set befindet, haben Sie dieses Objekt bereits. Es ist daher nie erforderlich, eine bestimmte Instanz aus einer Menge abzurufen, vorausgesetzt, Sie verwenden die richtige Gleichheitsrelation.

Wir könnten auch argumentieren, dass eine Menge ein abstrakter Datentyp ist, der nur durch die Beziehung S contains xoder x is-element-of Sdefiniert wird („charakteristische Funktion“). Wenn Sie andere Operationen wünschen, suchen Sie nicht wirklich nach einem Satz.

Was ziemlich oft passiert - aber was keine Menge ist - ist, dass wir alle Objekte in verschiedene Äquivalenzklassen gruppieren . Die Objekte in jeder solchen Klasse oder Untermenge sind nur gleichwertig, nicht gleich. Wir können jede Äquivalenzklasse durch jedes Mitglied dieser Untergruppe darstellen, und es wird dann wünschenswert, dieses repräsentierende Element abzurufen. Dies wäre eine Abbildung von der Äquivalenzklasse auf das repräsentative Element.

In C # kann ein Wörterbuch eine explizite Gleichheitsrelation verwenden, denke ich. Andernfalls kann eine solche Beziehung durch Schreiben einer Quick-Wrapper-Klasse implementiert werden. Pseudocode:

// The type you actually want to store
class MyClass { ... }

// A equivalence class of MyClass objects,
// with regards to a particular equivalence relation.
// This relation is implemented in EquivalenceClass.Equals()
class EquivalenceClass {
  public MyClass instance { get; }
  public override bool Equals(object o) { ... } // compare instance.A
  public override int GetHashCode() { ... } // hash instance.A
  public static EquivalenceClass of(MyClass o) { return new EquivalenceClass { instance = o }; }
}

// The set-like object mapping equivalence classes
// to a particular representing element.
class EquivalenceHashSet {
  private Dictionary<EquivalenceClass, MyClass> dict = ...;
  public void Add(MyClass o) { dict.Add(EquivalenceClass.of(o), o)}
  public bool Contains(MyClass o) { return dict.Contains(EquivalenceClass.of(o)); }
  public MyClass Get(MyClass o) { return dict.Get(EquivalenceClass.of(o)); }
}

Aber warum ist es unmöglich, einen bestimmten Gegenstand aus dem Set zu bekommen?

Denn dafür sind Sets nicht gedacht.

Lassen Sie mich das Beispiel umformulieren.

"Ich habe ein HashSet, in dem MyClass-Objekte gespeichert werden sollen, und ich möchte sie mithilfe der Eigenschaft A abrufen können, die der Eigenschaft A des Objekts entspricht."

Wenn "HashSet" durch "Collection", "objects" durch "Values" und "property A" durch "Key" ersetzt wird, lautet der Satz:

"Ich habe eine Sammlung, in der ich MyClass-Werte speichern möchte, und ich möchte sie mithilfe des Schlüssels abrufen können, der dem Schlüssel des Objekts entspricht."

Was beschrieben wird, ist ein Wörterbuch. Die eigentliche Frage lautet: "Warum kann ich HashSet nicht als Wörterbuch behandeln?"

Die Antwort ist, dass sie nicht für dasselbe verwendet werden. Der Grund für die Verwendung eines Sets besteht darin, die Eindeutigkeit der einzelnen Inhalte zu gewährleisten. Andernfalls können Sie nur eine Liste oder ein Array verwenden. Das in der Frage beschriebene Verhalten ist das, wofür ein Wörterbuch gedacht ist. Alle Sprachdesigner haben es nicht vermasselt. Sie bieten keine get-Methode, da sie äquivalent sind, wenn Sie das Objekt haben und es sich in der Menge befindet, was bedeutet, dass Sie ein äquivalentes Objekt "bekommen" würden. Das Argument, dass HashSet so implementiert werden sollte, dass Sie nicht-äquivalente Objekte "erhalten" können, die Sie als gleich definiert haben, ist ein Nichtstarter, wenn die Sprachen andere Datenstrukturen bereitstellen, mit denen Sie dies tun können.

Ein Hinweis auf die OOP und Gleichstellung Kommentare / Antworten. Es ist in Ordnung, wenn der Schlüssel des Mappings eine Eigenschaft / ein Mitglied des in einem Dictionary gespeicherten Werts ist. Zum Beispiel: Ein Guid als Schlüssel und auch die Eigenschaft, die für die equals-Methode verwendet wird, sind durchaus sinnvoll. Was nicht sinnvoll ist, sind unterschiedliche Werte für die restlichen Eigenschaften. Ich finde, wenn ich in diese Richtung gehe, muss ich wahrscheinlich meine Klassenstruktur überdenken.

Sobald Sie gleich überschreiben, sollten Sie den Hashcode besser überschreiben. Sobald Sie dies getan haben, sollte Ihre "Instanz" den internen Status nie wieder ändern.

Wenn Sie keine Gleichheit überschreiben, wird die Gleichheit mithilfe der Hashcode-VM-Objektidentität ermittelt. Wenn Sie dieses Objekt in ein Set einfügen, können Sie es wiederfinden.

Wenn Sie einen Wert eines Objekts ändern, der zur Bestimmung der Gleichheit verwendet wird, kann dieses Objekt in Hash-basierten Strukturen nicht mehr verfolgt werden.

Ein Setter auf A ist also gefährlich.

Jetzt haben Sie kein B, das nicht an der Gleichstellung beteiligt ist. Das Problem ist hier semantisch nicht technisch. Weil sich das technisch veränderte B neutral zur Gleichheit verhält. Semantisch muss B so etwas wie ein "Versions" -Flag sein.

Der Punkt ist:

Wenn Sie zwei Objekte haben, die gleich A, aber nicht B sind, gehen Sie davon aus, dass eines dieser Objekte neuer ist als das andere. Wenn B keine Versionsinformationen hat, ist diese Annahme in Ihrem Algorithmus verborgen, WENN Sie sich entscheiden, dieses Objekt in einem Set zu "überschreiben / aktualisieren". Dieser Quellcode-Speicherort, an dem dies geschieht, ist möglicherweise nicht eindeutig, sodass ein Entwickler Schwierigkeiten hat, die Beziehung zwischen Objekt X und Objekt Y zu identifizieren, die sich von X in B unterscheidet.

Wenn B über Versionsinformationen verfügt, legen Sie die Annahme offen, dass diese zuvor nur implizit aus dem Code abgeleitet werden konnten. Jetzt können Sie sehen, dass Objekt Y eine neuere Version von X ist.

Denken Sie an sich selbst: Ihre Identität bleibt Ihr ganzes Leben, vielleicht ändern sich einige Eigenschaften (zB die Farbe Ihrer Haare ;-)). Sicher können Sie davon ausgehen, dass Sie auf dem Foto mit braunen Haaren jünger sind, wenn Sie zwei Fotos haben, eines mit braunen Haaren und eines mit grauen Haaren. Aber vielleicht hast du dir die Haare gefärbt? Das Problem ist: SIE wissen vielleicht, dass Sie Ihre Haare gefärbt haben. Mögen andere? Um dies in einen gültigen Kontext zu stellen, müssen Sie das Eigenschaftsalter (Version) eingeben. Dann bist du semantisch explizit und eindeutig.

Um die versteckte Operation "Ersetzen eines alten durch ein neues Objekt" zu vermeiden, sollte ein Set keine get-Methode haben. Wenn Sie ein solches Verhalten wünschen, müssen Sie es explizit machen, indem Sie das alte Objekt entfernen und das neue Objekt hinzufügen.

BTW: Was soll es bedeuten, wenn Sie ein Objekt übergeben, das dem Objekt entspricht, das Sie erhalten möchten? Das macht keinen Sinn. Halten Sie Ihre Semantik sauber und tun Sie dies nicht, obwohl Sie technisch gesehen niemand daran hindern wird.

Speziell in Java HashSetwurde anfangs HashMapohnehin ein implementiert und der Wert einfach ignoriert. Das ursprüngliche Design sah also keinen Vorteil darin, eine Methode zum Abrufen von Daten bereitzustellen HashSet. Wenn Sie einen kanonischen Wert unter verschiedenen Objekten, die gleich sind, speichern und abrufen möchten, verwenden Sie einfach HashMapselbst einen.

Ich habe mit solchen Implementierungsdetails nicht auf dem neuesten Stand gehalten, daher kann ich nicht sagen, ob diese Argumentation in Java noch vollständig zutrifft, geschweige denn in C # usw. Aber selbst wenn HashSetsie erneut implementiert wurden, um weniger Speicher als HashMapin jedem Fall zu verwenden wäre eine bahnbrechende Änderung, um der SetSchnittstelle eine neue Methode hinzuzufügen . Es ist also eine Menge Schmerz für einen Gewinn, den nicht jeder für wert hält.

Es gibt eine Hauptsprache, deren Satz die gewünschte Eigenschaft hat.

In C ++ std::setist eine geordnete Menge. Es gibt eine .findMethode, die das Element basierend auf dem von Ihnen angegebenen Ordnungsoperator <oder der Binärfunktion sucht bool(T,T). Mit find können Sie die gewünschte get-Operation implementieren.

Wenn die von bool(T,T)Ihnen bereitgestellte Funktion ein bestimmtes Flag aufweist ( is_transparent), können Sie Objekte eines anderen Typs übergeben, für die die Funktion Überladungen aufweist. Das bedeutet, dass Sie das "Dummy" -Datenfeld nicht in das zweite Feld einfügen müssen, sondern lediglich sicherstellen müssen, dass der von Ihnen verwendete Bestellvorgang zwischen dem Lookup- und dem Set-Typ sortiert werden kann.

Dies ermöglicht eine effiziente:

std::set< std::string, my_string_compare > strings;
strings.find( 7 );

Dabei wird my_string_compareverstanden, wie man Ganzzahlen und Zeichenfolgen ordnet, ohne zuvor die Ganzzahl in eine Zeichenfolge umzuwandeln (mit potenziellen Kosten).

Für unordered_set(die Hash-Menge von C ++) gibt es (noch) kein äquivalentes transparentes Flag. Sie müssen eine Tan eine unordered_set<T>.findMethode übergeben. Es könnte hinzugefügt werden, aber Hashes erfordern ==einen Hasher, im Gegensatz zu geordneten Sätzen, die nur eine Bestellung erfordern.

Das allgemeine Muster ist, dass der Container die Suche durchführt und dann einen "Iterator" für dieses Element innerhalb des Containers ausgibt. An welcher Stelle können Sie das Element innerhalb des Satzes erhalten oder es löschen usw.

Kurz gesagt, nicht alle Standardcontainer der Sprachen weisen die von Ihnen beschriebenen Mängel auf. Die iteratorbasierten Container der C ++ - Standardbibliothek sind nicht vorhanden, und zumindest einige der Container waren vor den anderen von Ihnen beschriebenen Sprachen vorhanden, und die Möglichkeit, einen Abruf noch effizienter auszuführen, als Sie es beschrieben haben, wurde sogar hinzugefügt. Es ist nichts falsch an Ihrem Design oder dem Wunsch nach dieser Operation. Die Designer der von Ihnen verwendeten Sets haben diese Schnittstelle einfach nicht bereitgestellt.

C ++ - Standardcontainer wurden entwickelt, um die Low-Level-Vorgänge des entsprechenden handgerollten C-Codes sauber zu verpacken. Dieser Code wurde entwickelt, um zu berücksichtigen, wie Sie ihn effizient in Assemblys schreiben können. Seine Iteratoren sind eine Abstraktion von C-Zeigern. Die Sprachen, die Sie erwähnen, haben sich alle von Zeigern als Konzept entfernt, sodass sie die Iteratorabstraktion nicht verwendeten.

Es ist möglich, dass die Tatsache, dass C ++ diesen Fehler nicht aufweist, ein Designunfall ist. Der iteratorzentrierte Pfad bedeutet, dass Sie für die Interaktion mit einem Element in einem assoziativen Container zuerst einen Iterator für das Element erhalten und dann diesen Iterator verwenden, um über den Eintrag im Container zu sprechen.

Die Kosten bestehen darin, dass Sie Iterations-Invalidierungsregeln nachverfolgen müssen, und einige Vorgänge erfordern 2 Schritte anstelle von einem (was den Client-Code verrauscht). Der Vorteil ist, dass die robuste Abstraktion eine weitergehende Verwendung ermöglicht als die API-Designer ursprünglich gedacht hatten.