Container mit Stack und dynamische Zuordnung

Gibt es einen Container, der einen lokalen Puffer für eine kleine Anzahl von Elementen verwendet und eine Heap-Zuweisung nur dann verwendet, wenn die Anzahl der Elemente eine bestimmte Grenze überschreitet? Ähnlich wie die meisten std::string Implementierungen tun.Container mit Stack und dynamische Zuordnung

Hintergrund

Der Behälter wird in der folgenden (vereinfacht) Kontext verwendet:

Foo foo;      // some data 
vector<HandlerPtr> tagged; // receives "tagged" items 

// first pass: over all items in someList 
for each(HandlerPtr h in someList) 
{ 
    h->HandleFoo(foo);   // foo may become tagged or untagged here 
    if (foo.Tagged()) 
    tagged.push_back(h); 
} 
for(auto itr=tagged.rbegin(); itr!=tagged.end(); ++itr) 
{ 
    // ... 
}

Dieser Codeteil hat eine hohe Aufruffrequenz, sondern ein Element Tagging ist eher selten, Zahl von Artikeln in someContainer ist in der Regel niedrig, aber ungebunden. Ich kann einen vorab zugewiesenen "globaleren" Puffer nicht einfach verwenden. Ziel ist es, die häufige Zuordnung zu vermeiden.

Anruffrequenz

Häufig: kein Element markiert wird. std :: vector is fine
Häufig: Nur eines der wenigen Elemente wird markiert. verursacht hohe Frequenzzuweisung I
Sehr selten, aber muß unterstützt werden, um vermeiden will: someList wächst während ersten Durchgangs Anzahl der Elemente nicht vorhersehbar, aber immer noch niedrig

Quelle

2010-12-10 peterchen

Möchten Sie statische oder Stapelzuordnungen verwenden? Für Stack-Zuordnung siehe http://stackoverflow.com/questions/354442/looking-for-c-stl-like-vector-class-but-using-stack-storage – nimrodm

@nimrodn: Stack-Zuweisung ist wahrscheinlich eine bessere Beschreibung von was Ich möchte (fester Titel). eine begrenzte Anzahl von Elementen, die in der Containerinstanz gespeichert werden können (ohne zusätzliche Zuweisung) und die Verwendung der Heap-Zuweisung, wenn dies nicht ausreichend ist. – peterchen

'std :: vector' reserviert keinen Speicher bevor mindestens ein Element eingefügt wurde. –

Es gibt keine Standard-Container, der garantiert, diese Art von Verhalten . Wenn Sie jedoch dazu in der Lage sind, können Sie eine benutzerdefinierte STL-kompatible Zuordnungsklasse erstellen, die aus einem kleinen Stapelpuffer für kleine Zuordnungen zieht und nur dann eine Heapzuweisung durchführt, wenn die angeforderte Zuordnungsgröße die Größe des Stapelpuffers überschreitet. Sie können Ihre benutzerdefinierte Zuordnungsklasse als zweiten Vorlagenparameter für std::vector<T, Alloc> einbinden.

Weitere Informationen zum Erstellen eines benutzerdefinierten Zuordners finden Sie unter this article.

Quelle

2010-12-10 07:37:04

Sie könnten auch versuchen, eine Menge an Speicherplatz in dem Vektor zu reservieren, der klein, aber "genug" die meiste Zeit ist. Dadurch werden Neuzuweisungen möglicherweise vermieden, wenn die Vektorrichtlinie mit einer Größe von 1 beginnen und unabhängig von der aktuellen Größe dieselbe Größenänderungsrichtlinie verwenden soll. –

@Karl: Ein häufiges Szenario ist, dass der Container leer bleibt. Das Reservieren ist dafür schlecht, da es immer dynamischen Speicher zuweist. – visitor

in C++ 0x, das ist sicherlich die Lösung, aber wenn ich mich richtig erinnere, C++ 03 Allocators sollten nicht beibehalten Zustand, der nicht zwischen allen Instanzen der Allocators geteilt wird (dh jeder andere Zuordner des gleichen Typs könnte gefragt werden zerstören/freigeben, auch wenn die beiden Instanzen völlig unabhängig sind). In der Praxis sollte es meiner Meinung nach funktionieren :) –

Obwohl dies nicht garantiert, die meisten std::string die Small String Optimization implementieren, die nur ist, dass (mit VC++ 10 bis zu 8 oder 16 Zeichen thusly gespeichert werden)

ich nicht vectors tun es gesehen haben, und immer gefragt, warum, aber der kommende C++ - Standard wird dies mit std::aligned_storage und alignof erleichtern. Auf diese Weise werden wir in der Lage sein, richtig ausgerichteten Rohspeicher zu erhalten und Container mit einer Standardanzahl von "Stapelspeicher" zu erstellen.

Quelle

2010-12-10 08:35:33

Die Größe eines Vektors ist normalerweise nicht größer als die Größe von drei Zeigern. Wie viele Daten würden in diesen Bereich passen, da Sie auch einige Verwaltungsdaten speichern müssen? – visitor

@visitor: Ich denke, es kommt darauf an, wenn Sie die höheren Bits der Zeiger verwenden, um solche Daten zu behalten :) Aber ich wäre persönlich bereit, eine Buffier-Vektorklasse zu haben. Die Kosten des Kopierens des "Vektors" unterscheiden sich erheblich von den Kosten des Kopierens von 3 Zeigern, da es eine dynamische Zuweisung (also einen Aufruf von "Zuweisen") und die tiefe Kopie von existierenden Daten beinhaltet. Daher war mein Standpunkt, dass es billiger wäre, einfach etwas mehr Platz zu reservieren. 'Vektor ' zum Beispiel. Allerdings kenne ich keinen solchen Container, aber ich werde es wahrscheinlich zu Hause versuchen, obwohl es immer schwierig ist, die STL-Effizienz zu erreichen. –

@ Mattieu: * schwer zu erfüllen * - genau, vor allem die Effizienz + Flexibilität Kombination. Es ist leicht, etwas für meinen speziellen Fall herauszuholen, aber das würde mit so vielen Einschränkungen kommen, dass es nicht lustig wäre. – peterchen

Container mit Stack und dynamische Zuordnung

Antwort

Verwandte Themen