Wie speichern Sie Objekte ohne Kopie oder verschieben Sie Konstruktor in Std :: Vector?

Question

Um die Effizienz von std::vector<T> zu verbessern, ist es Array zugrunde liegen muss vorab zugeordnet werden und manchmal neu zugeteilt. Dies erfordert jedoch das Erzeugen und spätere Verschieben von Objekten vom Typ T mit einem copy ctor oder move ctor.

Das Problem, das ich habe ist, dass T kann nicht kopiert oder verschoben werden, da es Objekte enthält, die nicht oder bewegt (wie atomic und mutex) kopiert werden können. (Und ja, ich bin der Umsetzung eines einfachen Thread-Pool.)

Ich möchte mit Zeigern vermeiden, weil:

1. Ich habe keinen Dereferenzierungsebene brauchen und so will ich nicht ein.
2. (Pointers sind weniger effizient und die Komplexität erhöhen. Zeiger erhöht Speicherfragmentierung verwenden und Datenlokalität verringert, die können (aber nicht unbedingt müssen) eine spürbare Auswirkung auf die Leistung verursachen. Nicht so wichtig, aber immer noch eine Überlegung wert.)

Gibt es eine Möglichkeit, hier ein Maß an Indirektion zu vermeiden?

UPDATE: Ich habe einige falsche Annahmen korrigiert und die Frage neu formuliert, basierend auf Feedback in Kommentaren und Antworten.

Answer 1

Um zusammenzufassen, was bisher vorgeschlagen wurde:

1. Verwenden vector<unique_ptr<T>> - Fügt eine explizite Dereferenzierungsebene und war unerwünscht durch OP.
2. Verwenden Sie deque<T> - Ich versuchte zuerst deque, aber das Löschen von Objekten von ihm funktioniert auch nicht. See this discussion auf Unterschiede zwischen deque und list.

Die Lösung ist forward_list zu verwenden, die eine einfach verknüpfte Liste (oder Sie können list verwenden, wenn Sie eine doppelt verknüpfte Liste wollen). Wie @JanHudec darauf hingewiesen hat, erfordern vector (und viele seiner Freunde) eine Neuzuweisung beim Hinzufügen oder Entfernen von Elementen. Das passt nicht gut zu Objekten wie mutex und atomic, die nicht kopiert oder verschoben werden dürfen. forward_list und list erfordern dies nicht, da jede Zelle unabhängig zugewiesen wird (ich kann den Standard nicht angeben, aber die Indexierungsmethode führt zu dieser Annahme). Da sie tatsächlich verknüpfte Listen sind, unterstützen sie keine Indexierung mit wahlfreiem Zugriff. myList.begin() + i erhalten Sie einen Iterator der i 'th Element, aber es (am sichersten) wird durch alle vorherigen i Zellen zuerst durchlaufen müssen.

Ich habe die Versprechungen vom Standard nicht angeschaut, aber die Dinge funktionieren gut unter Windows (Visual Studio) und CompileOnline (g ++). Fühlen Sie sich frei mit dem folgenden Testfall zu spielen, um auf CompileOnline:

#include <forward_list> 
#include <iostream> 
#include <mutex> 
#include <algorithm> 

using namespace std; 

class X 
{ 
    /// Private copy constructor. 
    X(const X&); 
    /// Private assignment operator. 
    X& operator=(const X&); 

public: 
    /// Some integer value 
    int val; 
    /// An object that can be neither copied nor moved 
    mutex m; 

    X(int val) : val(val) { } 
}; 


int main() 
{ 
    // create list 
    forward_list<X> xList; 

    // add some items to list 
    for (int i = 0; i < 4; ++i) 
     xList.emplace_front(i); 

    // print items 
    for (auto& x : xList) 
     cout << x.val << endl; 

    // remove element with val == 1  
    // WARNING: Must not use remove here (see explanation below) 
    xList.remove_if([](const X& x) { return x.val == 1; }); 


    cout << endl << "Removed '1'..." << endl << endl; 

    for (auto& x : xList) 
     cout << x.val << endl; 

    return 0; 
} 

Ausgang:

Executing the program.... 
$demo 
3 
2 
1 
0 

Removed '1'... 

3 
2 
0 

ich dies erwarten, etwa die gleiche Leistung wie vector<unique_ptr<T>> haben (solange Sie nicht zufällig verwenden Zugriffsindizierung zu oft).

WARNUNG: Die Verwendung von forward_list::remove funktioniert derzeit nicht in VS 2012. Das liegt daran, dass das Element kopiert wird, bevor versucht wird, es zu entfernen. Die Header-Datei Microsoft Visual Studio 11.0\VC\include\forward_list (gleiches Problem in list) zeigt:

void remove(const _Ty& _Val_arg) 
{ // erase each element matching _Val 
    const _Ty _Val = _Val_arg; // in case it's removed along the way 

    // ... 
} 

So wird kopiert "falls es auf dem Weg entfernt ist".Dies bedeutet, dass list und forward_list nicht einmal die Speicherung von unique_ptr zulassen. Ich nehme an, dass dies ein Designfehler ist. Die Umgehung ist einfach: Sie müssen remove_if anstelle von remove verwenden, da die Implementierung dieser Funktion nichts kopiert.

Ein Großteil des Kredits geht auf die anderen Antworten. Da jedoch keine von ihnen eine vollständige Lösung ohne Zeiger war, beschloss ich, diese Antwort zu schreiben.

Answer 2

Für den Anfang kann std::mutex nicht kopiert oder verschoben werden, daher sind Sie gezwungen, eine Art von Indirektion zu verwenden.

Da Sie Mutex in einem Vektor speichern möchten, und kopieren Sie es nicht, würde ich std::unique_ptr verwenden.

vector<unique_ptr<T>> erlaubt es nicht, bestimmte Vektoroperationen (wie for_each)

Ich verstehe ich diesen Satz nicht sicher sind. Es ist durchaus möglich zu tun Bereich für:

std::vector< std::unique_ptr<int> > v; 
// fill in the vector 
for (auto & it : v) 
    std::cout << *it << std::endl; 

oder std Algorithmen zu verwenden:

#include <iostream> 
#include <typeinfo> 
#include <vector> 
#include <memory> 
#include <algorithm> 


int main() 
{ 
    std::vector< std::unique_ptr<int> > v; 
    v.emplace_back(new int(3)); 
    v.emplace_back(new int(5)); 
    std::for_each(v.begin(), v.end(), [](const std::unique_ptr<int> & it){ std::cout << *it << std::endl; }); 
} 

Answer 3

Das jedoch die Erstellung von Objekten des Typs T mit einer Kopie Ctor erfordert.

Das ist nicht ganz richtig, wie von C++ 11 ist, wenn Sie den Konstruktor von std::vector verwenden, die eine Anzahl von Elementen konstruieren wird standardmäßig, dann brauchen Sie nicht eine Kopie haben oder Konstruktor zu bewegen.

Als solcher, wenn keine Threads oder von Ihrem Pool gelöscht werden hinzugefügt haben, können Sie tun, nur:

int num = 23; 
std::vector<std::mutex> vec(num); 

Wenn Sie die Dinge dynamisch hinzufügen oder löschen möchten, dann müssen Sie eine Indirektion verwenden.

1. Verwenden std::vector + std::unique_ptr wie bereits vorgeschlagen
2. ein std::deque verwenden, die Sie ordentlich ermöglicht es für Schleifen oder std-Algorithmen mit einer Reichweite basiert verwenden und vermeidet alle Umwege. (Was nur Ergänzungen erlaubt)
3. Verwenden Sie eine std::list/forward_list diese Lösung ist ähnlich wie Nummer eins, aber es hat den zusätzlichen Vorteil der einfacheren Verwendung mit Bereich für und Algorithmen. Es ist wahrscheinlich das Beste, wenn Sie nur sequentiell auf die Elemente zugreifen, da kein Direktzugriff unterstützt wird.

So:

std::deque<std::mutex> deq; 
deq.emplace_back(); 
deq.emplace_back(); 

for(auto& m : deq) { 
    m.lock(); 
} 

Als abschließende Bemerkung, std::thread ist natürlich beweglich, so dass Sie std::vector + std::vector::emplace_back mit ihm nutzen kann.

Answer 4

Sie können Speicherelemente ohne Bewegung oder Kopierkonstruktoren in std::vector, aber man muss einfach Methoden vermeiden, die die Elemente erfordern Bewegung haben oder Konstrukteuren kopieren. Fast alles, was die Größe des Vektors ändert (z. B. push_back, resize(), usw.).

In der Praxis bedeutet dies, dass Sie zur Konstruktionszeit einen Vektor mit fester Größe zuweisen müssen, der den Standardkonstruktor Ihrer Objekte aufruft, den Sie mit Zuweisung ändern können. Dies könnte zumindest für std::atomic<> Objekte funktionieren, die zugewiesen werden können.

---

clear() ist das einzige Beispiel einer Größe ändernden Methode, die nicht kopieren/verschieben Bauer benötigt, da es nie irgendwelche Elemente verschieben oder kopieren muss (schließlich ist der Vektor leer nach diese Operation). Natürlich können Sie Ihren Vektor nie wieder vergrößern, nachdem Sie ihn aufgerufen haben!