Ich habe zwei (sehr große) Arrays foo und bar vom selben Typ. Um in der Lage zu sein, etwas netten Code zu schreiben, möchte ich eine schreibgeschützte Scheibe, result , der Verkettung der zwei Felder erhalten. Diese Operation muss in O (1) Zeit und Raum ausgeführt werden.
Der Array-Zugriff für result muss auch in O (1) sein. Allgemeiner gesagt, wenn result die Verkettung von k -Array-Slices ist, sollte ein beliebiger Array-Zugriff für result in O ( k ) laufen.
Ich möchte keine Elemente von foo noch bar kopieren.
Dies scheint leicht in den Rust-Kern zu implementieren, aber keine Menge an Suche hat mir eine Lösung gebracht.
Es gibt keinen vordefinierten Typ, Sie können jedoch problemlos eigene erstellen, indem Sie das Merkmal Index für einen Typ implementieren, der beide Segmente enthält:
Allgemeiner, wenn
resultdie Verkettung vonk-Array-Slices ist, sollte ein beliebiger Array-Zugriff fürresultin O (k) laufen.
Sie können den Slice-Zugriff in O(log(k)) erhalten, wenn Ihre Slice-Verkettung O(k) ist, indem Sie ein Array erstellen, das die kumulativen Längen der Slices enthält und eine binäre Suche verwendet, um den tatsächlichen Slice zum Indizieren zu finden. p>
Dies würde ein Makro erfordern, da wir noch kein ausreichend gutes konstantes Auswertungsprogramm und keine generischen Werte haben.
Ich fürchte, das, was Sie fragen, ist ziemlich unmöglich, wenn Sie verlangen, dass das Ergebnis ein tatsächliches Stück ist. Ein Slice ist ein Blick in einen Speicherblock. Zusammenhängender Speicher Wenn Sie ein neues Slice wollen, indem Sie zwei andere Slices kombinieren, müssen Sie den Inhalt an einen neuen Speicherort kopieren, damit Sie einen neuen zusammenhängenden Speicherblock erhalten.
Wenn Sie zufrieden sind, verketten Sie einfach, indem Sie kopieren SliceConcatExt stellt die Methoden concat und join für Slices bereit, die in Slices von benutzerdefinierten Typen verwendet werden können, solange sie Clone :
Beachten Sie, dass obwohl SliceConcatExt instabil ist, die Methoden selbst stabil sind. Es gibt also keinen Grund, sie nicht zu benutzen, wenn das Kopieren in Ordnung ist. Wenn Sie nicht kopieren können, erhalten Sie kein Stück. In diesem Fall müssen Sie einen Wrapper-Typ erstellen, wie in die Antwort von ker erklärt.
Tags und Links rust