C++ STL Vektoriterator vs. Indexzugriff und Thread-Sicherheit

Question

Ich durchlaufe einen STL-Vektor und lese Werte daraus. Es gibt einen anderen Thread, der Änderungen an diesem Vektor vornehmen kann. Wenn der andere Thread ein Element in den Vektor einfügt oder entfernt, wird der Iterator ungültig. Es werden keine Sperren verwendet. Macht es meine Wahl, auf den Container durch Indizes zuzugreifen (Ansatz 1) anstelle von Iteratoren (Ansatz 2), threadsicher? Wie steht es um die Leistung?

struct A{int i; int j;};

Ansatz 1:

   size_t s = v.size();//v enthält Zeiger auf Objekte vom Typ A
    for(size_t i = 0; i < s; ++i)
    {
         A* ptr = v[i];
         ptr->i++;
    }

Ansatz 2:

std::vector::iterator begin =  v.begin();
std::vector::iterator end =  v.end();
for(std::vector::iterator it = begin; it != end; ++it)
{
     A* ptr = *it;
     ptr->i++: 
}

Answer 1

Die Thread-Sicherheitsgarantien für Standard-Containerbibliotheken sind sehr einfach (diese Regeln wurden in C++ 2011 hinzugefügt, aber im Wesentlichen entsprechen alle aktuellen Bibliotheksimplementierungen diesen Anforderungen und setzen die entsprechenden Einschränkungen um):

1. Es ist in Ordnug, mehrere gleichzeitige Leser zu haben
2. Wenn ein Thread einen Container modifiziert, darf kein anderer Thread darauf zugreifen (lesen oder schreiben)
3. Die Anforderungen gelten pro Containerobjekt

Dies bedeutet effektiv, dass Sie einen Mechanismus extern zum Container verwenden müssen, um sicherzustellen, dass ein Container, der von mehreren Threads zugegriffen wird, korrekt behandelt wird. Zum Beispiel können Sie ein Mutex oder ein Lese-Schreib-Schloss verwenden. Natürlich werden Container in den meisten Fällen nur von einem Thread zugegriffen und funktionieren auch ohne jegliche Sperre einwandfrei.

Ohne die Verwendung expliziter Sperren verursachen Sie Datenkonflikte und das Verhalten ist undefiniert, unabhängig davon, ob Sie Indizes oder Iteratoren verwenden.

Answer 2

Nein. STL-Behälter sind nicht thread-sicher.

Sie sollten jedem Thread exklusiven Zugriff gewähren (demjenigen, der entfernt/demjenigen, der hinzufügt), während sie auf den Vektor zugreifen. Selbst bei Verwendung von Indizes können Sie das i-te Element entfernen, wodurch der von Ihnen abgerufene Zeiger ungültig wird.

Answer 3

OP "Macht meine Wahl, auf den Container über Indizes zuzugreifen (Ansatz 1) anstelle von Iteratoren (Ansatz 2), ihn threadsicher?"

Nein, keiner der Ansätze ist threadsicher, sobald Sie mit dem Schreiben in Ihre Datenstruktur beginnen.

Sie müssen also den Zugriff auf Ihre Datenstruktur serialisieren.

Um Ihnen viel Zeit und Frustration zu ersparen, gibt es viele vorgefertigte Lösungen, z.B.

Intel Threading Building Blocks (TBB), die threadsichere Container wie concurrent_vector mitbringen.

http://threadingbuildingblocks.org/

Ein concurrent_vector ist ein Container mit folgenden Merkmalen:

• Zugriff per Index. Der Index des ersten Elements ist null.
• Mehrere Threads können den Container erweitern und gleichzeitig neue Elemente hinzufügen.
• Das Erweitern des Containers macht bestehende Iteratoren oder Indizes nicht ungültig.*

OP "Was ist mit der Leistung?"

Nicht vorhersehbar. Unterschiedliche Leistung auf verschiedenen Systemen mit unterschiedlichen Compilern, aber nicht bekannt, dass sie groß genug ist, um Ihre Entscheidungen zu beeinflussen.

Answer 4

Könnte Ihr Algorithmus mit einem Array fester Größe arbeiten?

Der Grund, warum ich frage, ist, dass der einzige logische Weg, um mehrere Threads (die meisten Arten von) Container auf eine thread-sichere, sperrenfreie Weise zu modifizieren, darin besteht, den Container selbst invariant zu machen. Das bedeutet, dass der CONTAINER innerhalb der Threads niemals geändert wird, sondern nur die Elemente darin. Denken Sie an den Unterschied zwischen dem Herumspielen mit den Innenräumen von Güterwaggons eines Zuges und dem tatsächlichen Hinzufügen und Entfernen ganzer Güterwaggons von diesem Zug, während er auf den Gleisen fährt. Selbst das Manipulieren der Elemente ist nur dann sicher, wenn Ihre Operationen auf diese Daten bestimmte Einschränkungen beachten.

Gute Nachrichten sind, dass Sperren nicht immer das Ende der Welt bedeuten. Wenn mehrere Ausführungskontexte (Threads, Programme usw.) gleichzeitig auf dasselbe Objekt treffen können, sind sie oft sowieso die einzige Lösung.