Gibt es eine lock-freie Vektorimplementierung?

Ich habe gerade nachgeschlagen, was ein Vektor ist, in der Wikipedia.

Ich denke (nur ein oder zwei Minuten des Denkens, Denkens) ist eine vollständig lock-freie Version ein bisschen problematisch.

Überlegen Sie; Sie erstellen das Array, greifen darauf wie gewohnt zu, etc. Dafür benötigen Sie keine Lock-Free. Das Problem kommt, wenn Sie die Größe ändern müssen. Der Thread, der hereinkommt und entdeckt, muss zu malloc. Dies ist eine wirklich einzigartige Operation - andere Threads an diesem Punkt müssen blockieren / drehen. Wenn sie versuchten zu helfen, z.B. Mach das Malloc selbst, du könntest viele Threads haben, die den Malloc ausgeben. Nun könnte es in der Praxis die Anzahl der Threads sein das ist so niedrig es ist okay - in diesem Fall haben Sie vielleicht eine Anzahl von Threads, die das Malloc ausführen, wobei der Gewinner das neue Gedächtnis atomar aktiviert und die Verlierer das sehen und dann frei ( ) ihre Erinnerung.

Um dann die Kopie auszuführen, wenn ein Thread auf ein Element zugreift, müssen wir alle der zugewiesenen Arrays in einer Liste verfolgen und auf sie über die Liste, älteste zuerst, bis wir das Element finden, das wir wollen, und wenn es nicht im neuesten Array ist, verschieben wir es und dann darauf zugreifen.

Wir brauchen dann auch einen Weg, damit ein Thread weiß, dass er das letzte Element verschoben hat und dieses Array freigeben kann, also müssen wir Elemente zählen; Daher besteht das Risiko potenziell unbegrenzter Allokationsanforderungen. Was mehr ist, die Datenstruktur (ich habe eine Liste gesagt, aber es könnten andere Dinge sein, obwohl sie nicht so gut, prolly sind) müssen atomar sein (da vielleicht Threads ein Array zur selben Zeit löschen könnten) und eine atomare Lock-Free-Liste war bis vor kurzem die Spitze der Lock-Free-Datenstrukturen, so komplex wie sie kamen und SMR und eine komplexe Implementierung benötigten.

(Ich sage bis vor kurzem - jemand hat vor kurzem einen Lock-Free-rot-schwarz-Baum erfunden, die ganze Sache hinzufügen und löschen!)

TBH, ich verstehe nicht, warum irgendjemand einen Vektor benutzen würde. Warum nicht einfach einen ausgewogenen Binärbaum oder einen Hash verwenden?