Ich habe ein Std :: Set von Std :: String. Ich brauche den "Index" oder die "Position" jedes Strings in der Menge, ist das ein sinnvolles Konzept im Kontext?Index oder Position in Std :: Set
Ich denke, find() wird einen Iterator an die Zeichenfolge zurückgeben, so dass meine Frage besser formuliert werden könnte als: "Wie konvertiere ich einen Iterator in eine Zahl?".
std::distance ist, was Sie brauchen. Sie werden wollen, ich denke, std::distance(set.begin(), find_result)
Bemerkung: 'std :: distance' ist O (n) seit' set' Iteratoren sind Modelle von 'BidirectionalIterator' und nicht' RandomAccessIterator' –
Std :: Abstand ist O (N) gibt es irgendwelche Möglichkeit, die Auftragsstatistik in O (log (n)) zu erhalten? –
Es gibt keinen guten Weg.Die Berechnung der Entfernung ist in O (logN) für jede anständige Struktur mit geeigneter Buchführung möglich, aber sie wird vom Standard nicht benötigt und es gibt keine STL-Bibliothek, die ich kenne. Sie müssen otfind oder schreiben Sie eine maßgeschneiderte Struktur. – RichardPlunkett
Ich denke nicht, dass es sinnvoll ist - Set's sind "selbst eingegeben" und so sortiert der "Index" würde ungültig werden, wenn das Set geändert wird.
Natürlich hängt es davon ab, wie Sie den Index verwenden möchten und ob der Satz im Wesentlichen statisch ist (etwa ein Wörterbuch).
Ich denke, solange ein Container bestellt ist, hat die Position seiner Elemente eine semantische Bedeutung. Insbesondere kann die tatsächliche Position wichtig sein, abhängig davon, was Sie gerade tun (z. B. Daten mit Zeitstempel). Ändert sich die Menge, so gilt dies natürlich auch für die Position einiger Elemente. – laura
Trotz was andere hier geschrieben haben, glaube ich nicht, dass "Index" oder "Position" Bedeutung in Bezug auf eine Menge hat. In mathematischen Begriffen legt ein Satz nur seine Mitglieder und vielleicht seine Kardinalität offen. Die einzigen sinnvollen Operationen umfassen das Testen, ob ein Element ein Mitglied der Menge ist, und das Kombinieren oder Subtrahieren von Mengen, um neue Mengen zu erhalten.
Einige Leute sprechen über Sätze als Datenstrukturen in loserer Begriffen, durch Facetten der "bestellt" oder "ungeordnet", und ob sie Duplikate erlauben oder Eindeutigkeit erzwingen. Die erstgenannte Facette unterscheidet ein Array mit einem Einfügungsschutz, bei dem ein Versuch, ein Objekt einzufügen, zuerst die vorhandenen Mitglieder scannt, um zu sehen, ob das neue Objekt existiert, und falls nicht, das neue Objekt am Ende einzufügen, und eine Hash-Tabelle, die könnte behalten solche Reihenfolge nur innerhalb einer Eimer Kette. Ein Baum wie der rot-schwarze Baum, der von std::set verwendet wird, liegt irgendwo dazwischen; seine Durchlaufreihenfolge ist in Bezug auf das strict weak order, das durch das Komparatorprädikat vorgegeben wird, deterministisch, aber im Gegensatz zu dem oben skizzierten Array behält es die Einfügereihenfolge nicht bei.
Die andere Facette - ob der Satz doppelte Elemente erlaubt - ist in der Mathematik bedeutungslos und wird genauer als Tasche beschrieben. Eine solche Struktur erkennt den Unterschied zwischen Identität und wertebasierter "Gleichheit" an.
Ihr Problem kann sich auf einige Positionen beziehen; Es ist nicht klar, was diese Position bedeutet, aber ich nehme an, dass Sie eine Datenstruktur benötigen, die von std::set getrennt ist, um dies richtig zu modellieren. Vielleicht würde eine std::map Zuordnung von Ihrem Satz von Elementen zu jeder Position tun. Das würde nicht garantieren, dass die Positionen einzigartig sind.
Es kann auch helfen, das Problem zu klären, zu denken, wie Sie es als Relationen modellieren würden, wie in einer relationalen Datenbank. Was beinhaltet den Schlüssel? Welche Teile der Entitäten können unabhängig voneinander variieren?
Ich baue eine "Menge" von eindeutigen Strings aus einer Datenbank auf, dann müssen diese Strings als Zahlen dargestellt werden. Die Funktion distance() ist ausreichend. Es ist möglich (wahrscheinlich?), Dass das Set keine gute Wahl ist, ich habe es gemacht, weil es ein effizienter Weg schien, die Einzigartigkeit der Saiten zu garantieren. Die STL ist Neuland für mich. –
Wenn Sie ein Design gefunden haben, das Ihr Problem löst, ist alles in Ordnung. Wenn Sie sich für die STL-Konzepte erwärmen, können Sie das Buch * Elements of Programming * von Stepanov und McJones (http://www.elementsofprogramming.com/) genießen. – seh
http://stackoverflow.com/questions/1796503/index-or-position-in-stdset/1810416#1810416 @seh wenn wir semantisch sehen, was auch immer Sie gesagt haben, ist korrekt Aber die Sätze sind geordnet. Sie werden normalerweise mit einer Art ausgewogener Bäume wie einem roten schwarzen Baum implementiert und verwenden eine strenge schwache Ordnung, um die Elemente in der Menge zu ordnen. Ich weiß nicht, ob Standard diese Bestellung vorschreibt oder nicht. Aber das ist, wie es ist –