Gibt es ein Äquivalent von vector :: reserve() für eine std :: list?

Question

Ich habe eine Klasse, die wie folgt aussieht:

typedef std::list<char*> PtrList; 
class Foo 
{ 
public: 
    void DoStuff(); 
private: 
    PtrList m_list; 
    PtrList::iterator m_it; 
}; 

Die Funktion DoStuff() grundsätzlich Elemente m_list hinzufügt oder löscht Elemente daraus, findet einen Iterator zu einem besonderen Element in sie und speichert sie in m_it. Es ist wichtig zu beachten, dass jeder Wert von m_it in jedem folgenden Anruf von DoStuff() verwendet wird.

Also, was ist das Problem? Alles funktioniert, außer dass die Profilerstellung zeigt, dass der Operator new wegen list::push_back() aufgerufen von DoStuff() zu viel aufgerufen wird.

Leistung erhöhen ich für Speicher wollen m_list in der Initialisierung von Foo vorzubelegen, wie ich tun würde, wenn es sich um eine std::vector waren. Das Problem ist, dass diese neue Probleme einführen würde, wie:

1. Weniger effiziente insert und erase von Elementen.
2. m_it wird ungültig, sobald der Vektor von einem Aufruf zu DoStuff() zum nächsten geändert wird. EDIT: Alan Stokes vorgeschlagen, einen Index anstelle eines Iterators zu verwenden, dieses Problem zu lösen.

Meine Lösung: die einfachste Lösung, die ich denken könnte, ist ein Pool von Objekten zu implementieren, die auch eine verknüpfte Liste Funktionalität. Auf diese Weise bekomme ich eine verkettete Liste und kann Speicher dafür vorbelegen.

Fehle ich etwas oder ist es wirklich die einfachste Lösung? Ich möchte das Rad nicht "neu erfinden" und stattdessen eine Standardlösung verwenden, falls diese existiert.

Alle Gedanken, Umgehungslösungen oder aufschlussreiche Kommentare würden uns freuen!

Answer 1

Ich denke, Sie verwenden den Container falsch.

Wenn Sie schnell zurück drücken möchten, dann nicht automatisch davon ausgehen, dass Sie eine verkettete Liste benötigen, eine verkettete Liste ist ein langsamer Container, es ist grundsätzlich für die Neuordnung geeignet.

Ein besserer Container ist ein Std :: Deque. Eine Deque ist im Grunde eine Anordnung von Arrays. Es reserviert einen Speicherblock und belegt es, wenn Sie zurück drücken, wenn es ausläuft, wird es einen anderen Block zuweisen. Dies bedeutet, dass es nur sehr selten zugewiesen wird und Sie die Größe des Containers nicht rechtzeitig für die Effizienz kennen müssen, wie beispielsweise std :: vector und reserver.

Answer 2

Könnte möglicherweise list::get_allocator().allocate() verwenden. Afaik, Standardverhalten wäre, Speicher zu erwerben als und aufgrund der nicht-zusammenhängenden Art von list s - daher das Fehlen von reserve() - aber keine wesentlichen Nachteile bei der Verwendung der allocator Methode treten mir sofort. Vorausgesetzt, Sie haben einen nicht kritischen Abschnitt in Ihrem Programm, am Anfang oder was auch immer, können Sie zumindest wählen, den Schaden an diesem Punkt zu nehmen.

Answer 3

Liste und Vektor unterscheiden sich vollständig in der Art, wie sie Objekte verwalten.

Vektor konstruiert Elemente in einem zugewiesenen Puffer einer gegebenen Kapazität. Neue Zuweisung erfolgt, wenn die Kapazität erschöpft ist. Listen Sie Elemente nacheinander in einem individuell zugewiesenen Bereich auf.

Vektorelemente verschieben sich, wenn etwas eingefügt/entfernt wird, daher sind Vektorindizes und Elementadressen nicht stabil. Listenelemente werden neu verknüpft, wenn etwas eingefügt/entfernt wird, daher sind Listeniteratoren und Elementadressen stabil.

Eine Möglichkeit, eine Liste so zu gestalten, dass sie sich ähnlich wie ein Vektor verhält, ist das Ersetzen des Standardzuordners (der das System bei jedem Aufruf zuweist) durch ein anderes, das Objekte in größeren Teilen zuordnet Liste, wenn es aufgerufen wird. Dies ist nichts, was die Standardbibliothek standardmäßig bietet.

Answer 4

Mein Rat ist der gleiche wie 111111 's, versuchen Sie, auf deque zu wechseln, bevor Sie einen signifikanten Code schreiben.

Um jedoch direkt Ihre Frage zu beantworten: Sie könnten std::list mit einem benutzerdefinierten Zuordner verwenden. Es ist ein wenig fummelig, und ich werde hier nicht alle Details durcharbeiten, aber der Kern davon ist, dass Sie eine Klasse schreiben, die die Speicherzuweisungsstrategie für Listenknoten darstellt. Die von list zugewiesenen Knoten sind eine kleine implementierungsdefinierte Menge größer als char*, aber alle haben die gleiche Größe, was bedeutet, dass Sie einen optimierten Zuordner nur für diese Größe schreiben können (einen Pool von Speicherblöcken und keinen Pool von Objekten)), und Sie können Funktionen hinzufügen, mit denen Sie jederzeit den gewünschten Speicherplatz im Zuordner reservieren können. Dann kann die Liste schnell freigeben/freigeben. Dies erspart Ihnen, die tatsächliche list Funktionalität neu zu implementieren. Wenn Sie (aus irgendeinem Grund) einen Pool von Objekten mit Listenfunktionalität implementieren, können Sie mit boost::intrusive beginnen. Das könnte auch nützlich sein, wenn Sie Ihren eigenen Zuordner schreiben, um Ihre Liste der freien Blöcke zu verfolgen.

Answer 5

Sie können die splice-Funktion in std::list verwenden, um einen Pool zu implementieren. Fügen Sie eine neue Mitgliedsvariable PtrList m_Pool hinzu. Wenn Sie ein neues Objekt hinzufügen möchten und der Pool nicht leer ist, weisen Sie den Wert dem ersten Element im Pool zu und fügen Sie ihn dann in die Liste ein. Um ein Element zu löschen, spleiß es aus der Liste in den Pool.

Aber wenn Sie sich nicht um die Reihenfolge der Elemente kümmern, dann kann ein deque viel schneller sein. Wenn Sie ein Element in der Mitte löschen möchten, kopieren Sie das letzte Element auf das Element, das Sie löschen möchten, und löschen Sie dann das letzte Element.