Allocator für STL-Container: ein paar Fragen

[dooooomi]

Hallo,

ich versuche gerade, mir einen eigenen Allocator für std::list zu schreiben, bzw. erstmal zu verstehen, wie so ein Allocator überhaupt funktioniert. Einige Dinge sind mir da noch etwas unklar...

Wofür sind diese beiden Templates da?

template <class T> class allocator {
    ...
    template <class U> struct rebind { typedef allocator<U> other; };
    ...
    template <class U> allocator(const allocator<U>&) { }
    ...
};

Angenommen, ich habe eine std::list<Foo, MyAlloc<Foo> >. Dann muß MyAlloc<Foo> doch nie etwas anderes als Foo-Objekte allokieren, oder? Muß ich da noch irgendwas berücksichtigen, oder reicht es, wenn ich den Konstruktor und rebind einfach so wie oben schreibe, und mich nicht weiter darum kümmere?

Und noch eine andere Frage: Angenommen, der Speicher, den der Allocator zur Verfügung hat, ist begrenzt. Was wäre dann der richtige Weg damit umzugehen, wenn kein Speicher mehr frei ist? Sollte MyAlloc::allocate() dann einfach bad_alloc werfen?

[Besserwisser]

Stimmt alles was du sagst.

[Shade Of Mine]

dooooomi schrieb:

Angenommen, ich habe eine std::list<Foo, MyAlloc<Foo> >. Dann muß MyAlloc<Foo> doch nie etwas anderes als Foo-Objekte allokieren, oder? Muß ich da noch irgendwas berücksichtigen, oder reicht es, wenn ich den Konstruktor und rebind einfach so wie oben schreibe, und mich nicht weiter darum kümmere?

Gerade eine liste allokiert keine Foo Objekte sondern allokiert Knoten (die Foo Objekte enthalten). Ein Knoten muss ja einen prev und next zeiger haben...

aber ein allocator<T> allokiert nur T objekte - wenn ich U objekte will, muss ich allocator<T>::rebind<U>::other machen und habe einen allocator<U> bekommen...

Fuer soetwas gibt es rebind. die list holt sich ueber rebind einen allokator fuer die knoten objekte.

Und noch eine andere Frage: Angenommen, der Speicher, den der Allocator zur Verfügung hat, ist begrenzt. Was wäre dann der richtige Weg damit umzugehen, wenn kein Speicher mehr frei ist? Sollte MyAlloc::allocate() dann einfach bad_alloc werfen?

ja, du musst bad_alloc werfen.
aber warum hast du nur begrenzten speicher...?

aber bedenke:
ein allocator darf keinen per-object state haben. es gilt immer, dass alle allokatoren vom selben typ jederzeit voellig aequivalent sind.

[nachtrag]
daraus ergibt sich auch der leere kopierkonstruktor - da ein objekt ja keinen status haben darf kann auch nichts kopiert werden
[/nachtrag]

ich wollte mal einen artikel ueber allokatoren schreiben - aber die sind designtechnisch so richtig furchtbar

[dooooomi]

Shade Of Mine schrieb:

Gerade eine liste allokiert keine Foo Objekte sondern allokiert Knoten (die Foo Objekte enthalten). Ein Knoten muss ja einen prev und next zeiger haben...

Hoppla, das ist natürlich richtig. Hab ich gar nicht dran gedacht.

Shade Of Mine schrieb:

ja, du musst bad_alloc werfen.
aber warum hast du nur begrenzten speicher...?

Naja, letztlich weil ich zu faul bin, den Memory Pool bei Bedarf zu vergrößern ;). Aber der Allocator ist eh für einen sehr speziellen Anwendungszweck, wo das kein Problem darstellt. Wollte nur wissen, was im Fall der Fälle passieren sollte.

Shade Of Mine schrieb:

aber bedenke:
ein allocator darf keinen per-object state haben. es gilt immer, dass alle allokatoren vom selben typ jederzeit voellig aequivalent sind.

Ok, das hatte ich bisher auch so verstanden. Was mir aber noch nicht klar ist: Wofür hat der Konstruktor von std::list einen Allocator als Parameter? Warum kann ich da anscheinend ein konkretes Allocator-Objekt übergeben, wenn doch der Typ schon durch die Template-Parameter des Listen-Objekts vorgegeben ist, und eh alle Allokatoren gleich(wertig) sind?

Shade Of Mine schrieb:

ich wollte mal einen artikel ueber allokatoren schreiben - aber die sind designtechnisch so richtig furchtbar

Sehe ich auch so. Aber gerade deswegen wäre doch ein verständlicher Artikel mal eine feine Sache

[Shade Of Mine]

dooooomi schrieb:

Ok, das hatte ich bisher auch so verstanden. Was mir aber noch nicht klar ist: Wofür hat der Konstruktor von std::list einen Allocator als Parameter? Warum kann ich da anscheinend ein konkretes Allocator-Objekt übergeben, wenn doch der Typ schon durch die Template-Parameter des Listen-Objekts vorgegeben ist, und eh alle Allokatoren gleich(wertig) sind?

Wenn du das raus gefunden hast, dann sags mir bitte. Es ist mir ein absolutes raetsel. Genauso wie warum man ein konkretes allocator objekt braucht um allokationen machen zu koennen - da haette es ein static interface imho besser getan.

ich vermute es liegt daran, dass zu einem frueheren zeitpunkt allocatoren state haben durften. um genau zu sein gibt es nur einen grund warum ihnen state verboten wurde: list-splice operationen.

splicing ist natuerlich nur moeglich wenn man garantieren kann dass 2 allokatoren identisch sind... aber imho ist es sehr hart nur um konstantes splicen zu ermoeglichen das interface so zu verunstalten. ein operator== haette es imho auch getan - und splicing nur dann in konstanter zeit wenn die allocatoren gleich sind. aber das wollte man dann wohl auch wieder nicht haben.

was ich aber als riesen designfehler ansehe ist, dass es keinen weg gibt den speicher inplace zu vergroessern. was zumindest ein bisschen etwas gebracht haette waere, wenn der allokatoren mitteilen koennte wie gross der chunk ist den er allokiert hat. denn wenn ich 10 bytes will, bekomme ich idR ja 16 bytes geliefert, weil sie mit festen groessen schneller allokieren laesst. das bedeutet aber dass 6 bytes verschwendet sind und wenn ich dann von 10 auf 16 bytes wachse - muss ich reallokieren und umkopieren, obwohl das komplett unnoetig war.

was dafuer schoen ist, ist der locality pointer bei allokationen. die frage ist nur ob die allokatoren den auch nutzen

PS:
bei bad_alloc solltest du aufpassen - da diese exception in der realitaet nie fliegt, kann es natuerlich sein dass code falsch darauf reagiert.

[camper]

ISO 14882 schrieb:

20.1.5

4 Implementations of containers described in this International Standard are permitted to assume that their
Allocator template parameter meets the following two additional requirements beyond those in Table 32.
— All instances of a given allocator type are required to be interchangeable and always compare equal to
each other.
— The typedef members pointer, const_pointer, size_type, and difference_type are
required to be T*,T const*, size_t, and ptrdiff_t, respectively.
5 Implementors are encouraged to supply libraries that can accept allocators that encapsulate more general
memory models and that support non-equal instances. In such implementations, any requirements imposed
on allocators by containers beyond those requirements that appear in Table 32, and the semantics of containers
and algorithms when allocator instances compare non-equal, are implementation-defined.

Dass Objekte des gleichen Allokatortyps gleich sein müssen, ist nicht vorgeschrieben (abgesehen vom default-Allokator).

[Shade Of Mine]

camper schrieb:

Dass Objekte des gleichen Allokatortyps gleich sein müssen, ist nicht vorgeschrieben (abgesehen vom default-Allokator).

und was heisst der von dir zitierte teil dann?

PS:
oder wird das jetzt so eine diskussion wo jedes wort im standard versucht wird genau auszulegen?

fakt ist: wenn du einen portablen general-purpose allokator haben willst, darf er keinen state haben. zumindest keinen relevanten.

[camper]

Shade Of Mine schrieb:

camper schrieb:

Dass Objekte des gleichen Allokatortyps gleich sein müssen, ist nicht vorgeschrieben (abgesehen vom default-Allokator).

und was heisst der von dir zitierte teil dann?

Dass das Bestehen dieser Beschränkung implementation-defined ist?
Wäre es anders, gäbe es keinen plausiblen Grund, diese zusätzlichen Vorgaben nicht von vornherein in die Allocator requirements hineinzunehmen.
Betrachte etwa

a1 == a2 bool returns true iff storage allocated
from each can be deallocated via the other

Wozu den Operator so definieren, wenn die Bedingung immer zu gelten hat?

[Shade Of Mine]

camper schrieb:

Dass das Bestehen dieser Beschränkung implementation-defined ist?
Wäre es anders, gäbe es keinen plausiblen Grund, diese zusätzlichen Vorgaben nicht von vornherein in die Allocator requirements hineinzunehmen.

und somit ist es nicht moeglich portable general-purpose allokatoren zu haben die state besitzen.

es ist wie template template parametern mit container klassen oder funktionszeiger auf standard library funktionen...

[camper]

Shade Of Mine schrieb:

camper schrieb:

Dass das Bestehen dieser Beschränkung implementation-defined ist?
Wäre es anders, gäbe es keinen plausiblen Grund, diese zusätzlichen Vorgaben nicht von vornherein in die Allocator requirements hineinzunehmen.

und somit ist es nicht moeglich portable general-purpose allokatoren zu haben die state besitzen.

Das trifft sicher zu. Anderseits ist absolute Portabilität sowieso illusorisch, insbesondere halte ich es für wahrscheinlich, dass jeder nicht-triviale Allokator, der state hat, noch aus anderen Gründen nicht völlig portabel sein wird (aus den gleichen Gründen, die es praktisch unmöglich machen, eine portable Allokationsfunktion zu schreiben). Ich stimme zu, dass die Situation hier nicht ideal ist, andererseits ist es durchaus ein brauchbarer Kompromiss. Die Problematik geht schließlich weit über splice hinaus - das ist lediglich ein schönes Beispiel. Es ist ja auch nicht zweifelhaft, dass auch zustandslose Allokatoren möglich sind. Es ist aber außerordentlich schwierig, einerseits Allokatoren, die state haben, zuzulassen ohne dass dies andererseits auf Kosten der Effizienz im stateless Fall geht (das wäre wohl anders, wenn man das bereits beim Compilieren sicher feststellen könnte; dass der Allokator ein leeres Objekt ist - was man feststellen könnte - ist leider weder notwendig noch hinreichend); hier würde ich ansetzen, wenn ich das Interface von Allokatoren verändern dürfte.
Im Kern mag das darin liegen, dass die zugrunde liegende Annahme, dass die Allokationsstrategie sauber vom Container trennbar ist, in dieser Allgemeinheit nicht zutrifft.
Wir wissen,das bei allen auf Knoten basierenden Containern, der Allokator, der tatsächlich benutzt wird, in der Regel nicht derjenige ist, der als Templateparameter angegeben wird. Haben unsere Allokatoren aber state, heißt dass, dass etwa unsere Liste zwei Allokator-Objekte mit sich herumschleppen muss, obwohl nur eins benutzt wird. Irgendwie müssten wir auch spezifizieren, wie der benutzte interne Allokator mit dem öffentlichen zusammenhängt.
Schließlich trifft die Annahme, der angegebene Allokator wäre der, der auch benutzt wird, nicht einmal für die anderen Container zwingend zu. Bei deque ist das noch einigermaßen deutlich (auch dort müssen wir noch etwas zusätzliche Information speichern), aber selbst bei vector könnte dies zutreffen, wenn bestimmte Optimierungstechniken verwendet werden: vector<T*,A> basierend auf vector<void*,A> (oder allgemeiner für PODs: vector<T,A> basierend auf vector_impl<sizeof(T),A>).

... oder funktionszeiger auf standard library funktionen...

dort bestehen keine Probleme. Sonst wäre die Verwendung mit Standardalgorithmen auch nicht denkbar. Zusätzliche Templateparameter sind möglich, nicht aber zusätzliche Funktionsparameter.

[dooooomi]

Ok, für meine Zwecke scheinen zustandsbehaftete Allokatoren portabel genug zu sein.

Eine Frage hab ich dann aber noch:

Ich möchte einen Allokator für eine Liste schreiben, so daß alle Elemente der Liste in einem festen Speicherbereich angelegt werden, der beim Erzeugen der Liste (?) allokiert wird. Dabei soll die maximale Anzahl der Elemente, die in die Liste passen, vorher festgelegt sein.

Ich brauche also z.B. insgesamt Speicher für N Elemente vom type _List_node<Foo> (o.ä.). Ich möchte sowas hier machen können:

template <typename T, size_t N>
class MyAlloc
{
    ...
};

MyAlloc<Foo, N> alloc;
std::list<Foo, MyAlloc<Foo, N> >(alloc);

Jetzt kann aber der Konstruktor MyAlloc<T, N>::MyAlloc() den Speicher nicht allokieren, denn er wird ja nur einmal mit T = Foo aufgerufen, und weiß noch nichts von irgendwelchen Listenknoten. Aber wo sollte ich das sonst machen?

[Shade Of Mine]

camper schrieb:

Wir wissen,das bei allen auf Knoten basierenden Containern, der Allokator, der tatsächlich benutzt wird, in der Regel nicht derjenige ist, der als Templateparameter angegeben wird. Haben unsere Allokatoren aber state, heißt dass, dass etwa unsere Liste zwei Allokator-Objekte mit sich herumschleppen muss, obwohl nur eins benutzt wird.

Wieso? Es gibt Template Copy Ctors.

Auch die effizienz ist denke ich beim kopieren kein thema: denn wenn ein allokator stateless ist, dann kann der compiler ein
allocator = other.allocator;
auf ein noop optimieren.

ich sehe einfach, bis auf splice, keine probleme bei statefull-allokatoren. allokatoren generell waren eine gute idee, aber imho wurde das interface komplett vermasselt. viele allokationsstrategien sind einfach nicht portabel implementierbar. auch zB dass pointer immer T* sein muss.

ich sehe auch wirklich nur bei splice operationen probleme mit statefull allokatoren - denn ich gebe ausser beim splicing nie speicher her der mir gehoert. ich allokiere ihn, ich zerstoere ihn. was ich da zwischen speichere ist eigentlich egal - lediglich wenn ich den speicher share wird es kritisch. aber das mache ich nur bei splice operationen...

... oder funktionszeiger auf standard library funktionen...

dort bestehen keine Probleme. Sonst wäre die Verwendung mit Standardalgorithmen auch nicht denkbar. Zusätzliche Templateparameter sind möglich, nicht aber zusätzliche Funktionsparameter.

Ich habe den Standard da jetzt nicht nachgelesen, aber in Exception C++ Style gibt es ein Kapitel ueber mem_fun wo darauf eingegangen wird, dass es bei funktionen durchaus default parameter geben darf.

dooooomi schrieb:

Ok, für meine Zwecke scheinen zustandsbehaftete Allokatoren portabel genug zu sein.

du musst halt testen was beim kopieren der container passiert. es ist nicht garantiert dass die allokatoren ebenfalls kopiert werden.

Jetzt kann aber der Konstruktor MyAlloc<T, N>::MyAlloc() den Speicher nicht allokieren, denn er wird ja nur einmal mit T = Foo aufgerufen, und weiß noch nichts von irgendwelchen Listenknoten. Aber wo sollte ich das sonst machen?

am besten du machst es beim ersten allocate() aufruf. du schaust: ist die liste der allokierten bloecke leer, dann allokiere N elemente.

der ctor ist die falsche stelle zum allokieren, da der ctor sinnlos oft aufgerufen werden kann (da wie du richtig erkennt hast ein MyAlloc<T> nie etwas allokieren wird). Du brauchst aber auch kein allocator objekt an die liste geben, wenn du N als template parameter definierst.

gerade bei einer liste denk aber an das splice problem.

[dooooomi]

Shade Of Mine schrieb:

Jetzt kann aber der Konstruktor MyAlloc<T, N>::MyAlloc() den Speicher nicht allokieren, denn er wird ja nur einmal mit T = Foo aufgerufen, und weiß noch nichts von irgendwelchen Listenknoten. Aber wo sollte ich das sonst machen?

am besten du machst es beim ersten allocate() aufruf. du schaust: ist die liste der allokierten bloecke leer, dann allokiere N elemente.

Dann wäre allerdings die nächste Frage, wo ich den Speicher denn dann freigebe. "Beim letzten deallocate()" wäre natürlich irgendwie naheliegend, aber da die Liste auch "zwischendurch" immer wieder mal leer werden kann, dürfte das etwas ineffizient sein.

gerade bei einer liste denk aber an das splice problem.

Fast hätte ich jetzt gesagt, "kein Problem, ich brauche kein Splice". Aber je mehr ich darüber nachdenke frage ich mich, ob ich überhaupt eine std::list mit eigenem Allocator benutzen sollte, oder vielleicht besser einen Container schreibe, der nur einen Teil des Listen-Interfaces implementiert. Denn eine std::list, die nicht wie eine std::list benutzbar ist, ist schließlich auch nicht das Wahre...

[Shade Of Mine]

dooooomi schrieb:

Dann wäre allerdings die nächste Frage, wo ich den Speicher denn dann freigebe. "Beim letzten deallocate()" wäre natürlich irgendwie naheliegend, aber da die Liste auch "zwischendurch" immer wieder mal leer werden kann, dürfte das etwas ineffizient sein.

im destruktor.

denn zerstoert wird das objekt ja nur einmal.

Fast hätte ich jetzt gesagt, "kein Problem, ich brauche kein Splice". Aber je mehr ich darüber nachdenke frage ich mich, ob ich überhaupt eine std::list mit eigenem Allocator benutzen sollte, oder vielleicht besser einen Container schreibe, der nur einen Teil des Listen-Interfaces implementiert. Denn eine std::list, die nicht wie eine std::list benutzbar ist, ist schließlich auch nicht das Wahre...

was genau willst du denn machen?

[dooooomi]

Shade Of Mine schrieb:

dooooomi schrieb:

Dann wäre allerdings die nächste Frage, wo ich den Speicher denn dann freigebe. "Beim letzten deallocate()" wäre natürlich irgendwie naheliegend, aber da die Liste auch "zwischendurch" immer wieder mal leer werden kann, dürfte das etwas ineffizient sein.

im destruktor.

denn zerstoert wird das objekt ja nur einmal.

Hmm, stimmt. Der Destruktor müßte dann wohl gucken, ob das selbe Objekt vorher Speicher allokiert hatte, aber das wäre ja kein Problem.

Shade Of Mine schrieb:

Fast hätte ich jetzt gesagt, "kein Problem, ich brauche kein Splice". Aber je mehr ich darüber nachdenke frage ich mich, ob ich überhaupt eine std::list mit eigenem Allocator benutzen sollte, oder vielleicht besser einen Container schreibe, der nur einen Teil des Listen-Interfaces implementiert. Denn eine std::list, die nicht wie eine std::list benutzbar ist, ist schließlich auch nicht das Wahre...

was genau willst du denn machen?

Naja, zunächst einmal muß ich einfach nur einzelne Elemente in die Liste einfügen bzw. löschen können. So Sachen wie splice(), swap(), sort() etc. brauche ich alle nicht.

Was ich mit dem Allokator ausnutzen wollte ist die Tatsache, daß ich immer nur am Ende der Liste Elemente einfüge, und auch größtenteils am Ende der Liste wieder entferne. Irgendwann wird dann die komplette Liste in einem Rutsch geleert, und das ganze beginnt von vorne.
Hat also ein bißchen was von einem Stack, nur daß es auch möglich sein soll, mittendrin Elemente zu löschen.

[camper]

... oder funktionszeiger auf standard library funktionen...

dort bestehen keine Probleme. Sonst wäre die Verwendung mit Standardalgorithmen auch nicht denkbar. Zusätzliche Templateparameter sind möglich, nicht aber zusätzliche Funktionsparameter.

Ich habe den Standard da jetzt nicht nachgelesen, aber in Exception C++ Style gibt es ein Kapitel ueber mem_fun wo darauf eingegangen wird, dass es bei funktionen durchaus default parameter geben darf.

Stimmt, hatte ich auch vergessen. Ich nahm allerdings auch an, dass sich deine Formulierung auf normale Funktionen bezieht.

Shade Of Mine schrieb:

camper schrieb:

Wir wissen,das bei allen auf Knoten basierenden Containern, der Allokator, der tatsächlich benutzt wird, in der Regel nicht derjenige ist, der als Templateparameter angegeben wird. Haben unsere Allokatoren aber state, heißt dass, dass etwa unsere Liste zwei Allokator-Objekte mit sich herumschleppen muss, obwohl nur eins benutzt wird.

Wieso? Es gibt Template Copy Ctors.

Auch die effizienz ist denke ich beim kopieren kein thema: denn wenn ein allokator stateless ist, dann kann der compiler ein
allocator = other.allocator;
auf ein noop optimieren.

Diese Allokatoren nehmen aber immer noch Platz im Containerobjekt weg - und das lässt sich nicht so ohne Weiteres wegoptimieren. Haben wir es nur mit einem Allokatorobjekt zu tun, hilft EBO; bei zwei Objekten wird es dagegen schwierig (nicht unmöglich, aber ziemlich umständlich).

ich sehe einfach, bis auf splice, keine probleme bei statefull-allokatoren. allokatoren generell waren eine gute idee, aber imho wurde das interface komplett vermasselt. viele allokationsstrategien sind einfach nicht portabel implementierbar. auch zB dass pointer immer T* sein muss.

ich sehe auch wirklich nur bei splice operationen probleme mit statefull allokatoren - denn ich gebe ausser beim splicing nie speicher her der mir gehoert. ich allokiere ihn, ich zerstoere ihn. was ich da zwischen speichere ist eigentlich egal - lediglich wenn ich den speicher share wird es kritisch. aber das mache ich nur bei splice operationen...

Es gibt noch (wenigstens) einen weiteren Fall, bei dem Speicher zwar nicht im eigentlichen Sinne geteilt wird, aber doch von verschiedenen Allokatorobjekten verwaltet wird: swap. Da Allokatoren kein spezialisiertes swap haben (eine Designfehler in meinen Augen), werden nach dem swap die Elemente durch Kopien der ursprünglichen Allokatoren verwaltet. Das bedeutet aber, dass sich die Äquivalenz der Kopie eines Allokators (wg. CopyConstructible) auch auf den Vergleichsoperator erstreckt. Das wiederum bedeutet, das ein statefull allokator immer mit shared state arbeitet - damit ist der Vorteil eines solchen Allokators gegenüber einem, der von vornherein nur globalen state benutzt, deutlich verringert.

Was einen Templatekonstruktor betrifft: dort müssen wir dann präzise bestimmen, was das bedeuten soll. Allokatoren mit verschiedene Templateparametern können natürlich nicht äquivalent sein, aber wie ist das mit Allokatorobjekten, die aus der gleichen Vorlage heraus konvertiert wurden?

alloc<char> a;
alloc<int> a1(a);
alloc<int> a2(a);
a1==a2  // geht das im Allgemeinen überhaupt?

Ohne diese Äquivalenzforderung ist es wiederum nicht möglich, ein konstantes splice zu garantieren. Geben wir diese Forderung aber auf, stellt sich die Frage, wozu dieser Parameter (bei der Konstruktion als Funktionsparameter) überhaupt existiert.

Ich denke immer noch, dass das Problem nicht einseitig beim Allokatordesign selbst zu suchen ist, sondern das schon theoretisch nur postuliert wird, dass Allokatoren und Container orthogonale Konzepte sind. Beschränkt man sich auf stateless Allokatoren, ist das aber möglicherweise machbar.

[Shade Of Mine]

camper schrieb:

Diese Allokatoren nehmen aber immer noch Platz im Containerobjekt weg - und das lässt sich nicht so ohne Weiteres wegoptimieren. Haben wir es nur mit einem Allokatorobjekt zu tun, hilft EBO; bei zwei Objekten wird es dagegen schwierig (nicht unmöglich, aber ziemlich umständlich).

wieso hast du bei stateful allokatoren mehr allokator objekte als mit stateless? Ich komme auf exakt ein allokator objekt per typ. und ein container der einen typ beinhalten kann, hat einen allokator.

Es gibt noch (wenigstens) einen weiteren Fall, bei dem Speicher zwar nicht im eigentlichen Sinne geteilt wird, aber doch von verschiedenen Allokatorobjekten verwaltet wird: swap. Da Allokatoren kein spezialisiertes swap haben (eine Designfehler in meinen Augen), werden nach dem swap die Elemente durch Kopien der ursprünglichen Allokatoren verwaltet.

Eben, designfehler. hätten sie ein swap, wäre es kein problem.

wie gesagt: statefull allokatoren sind aktuell nicht möglich aber ich sehe nicht warum sie generell nicht möglich sind (wenn man sie denn richtig designed hätte).

alloc<char> a;
alloc<int> a1(a);
alloc<int> a2(a);
a1==a2  // geht das im Allgemeinen überhaupt?

Ohne diese Äquivalenzforderung ist es wiederum nicht möglich, ein konstantes splice zu garantieren. Geben wir diese Forderung aber auf, stellt sich die Frage, wozu dieser Parameter (bei der Konstruktion als Funktionsparameter) überhaupt existiert.

ja, splice ist ein problem - aber _nur_ splice.

Und die frage ist, ist ein general purpose O(1) slice bei einem container wichtiger als das komplette allokator konzept? es lässt sich recht leicht für splice ein spezialfall erfinden - nämlich dass splice nur erlaubt ist, wenn beide allokatoren identisch sind, ansonsten fliegt eine bad_splice exception oder so.

wäre alles denkbar. aber general purpose O(1) splice ist mit statefull allokatoren wie gesagt nicht möglich.

Ich denke immer noch, dass das Problem nicht einseitig beim Allokatordesign selbst zu suchen ist, sondern das schon theoretisch nur postuliert wird, dass Allokatoren und Container orthogonale Konzepte sind. Beschränkt man sich auf stateless Allokatoren, ist das aber möglicherweise machbar.

ne, verstehe ich nicht.
alles was allokatoren sind, ist eine malloc().

wenn du (bis auf splice) ein wirkliches problem von statefull allokatoren siehst, nur her damit. aktuell ist es so, dass ich einfach nirgendwo ein problem erkennen kann. dazu wie gesagt eine grow() funktion und natürlich ein swap - und wir hätten sinnvolle allokatoren. dann noch die bedingung weg dass pointer immer ein T* sein muss (wobei ich mir da nicht 100% sicher bin) und sie wären richtig nice...

[camper]

Shade Of Mine schrieb:

camper schrieb:

Diese Allokatoren nehmen aber immer noch Platz im Containerobjekt weg - und das lässt sich nicht so ohne Weiteres wegoptimieren. Haben wir es nur mit einem Allokatorobjekt zu tun, hilft EBO; bei zwei Objekten wird es dagegen schwierig (nicht unmöglich, aber ziemlich umständlich).

wieso hast du bei stateful allokatoren mehr allokator objekte als mit stateless? Ich komme auf exakt ein allokator objekt per typ. und ein container der einen typ beinhalten kann, hat einen allokator.

Der Originalallokator (also den, der öffentlich ggf. beim Konstruieren übergeben wird) muss die ganze Zeit mitgeschleppt werden, denn z.B. get_allocator liefert eine Kopie dieses Arguments. Dass wir im stateful-Fall zusätzlich immer noch das eigentliche Allokatorobjekt, das benutzt wird, mit uns herumschleppen müssen, ist ja sowieso klar.

wie gesagt: statefull allokatoren sind aktuell nicht möglich aber ich sehe nicht warum sie generell nicht möglich sind (wenn man sie denn richtig designed hätte).

Das behaupte ich auch nicht. Ich sage nur, dass es eine ganze Reihe von Problemen gibt, die geklärt werden müssten. Selbst wenn es stimmt, dass im Moment nur splice betroffen ist, kann man das so nicht verallgemeinern. Schließlich ist das ganze Container/Algorithmus/Iterator-Konzept auf Erweiterbarkeit ausgelegt. Die jetzige status quo hat den Vorteil, dass die Komplexität einer Implementation überschaubar bleibt. Für eine Verallgemeinerung wäre erst einmal die Machbarkeit zu demonstrieren. Ich glaube nicht, dass die jetzigen Beschränkungen nur zufällig da sind, sondern das Ergebnis des Versuchs, ursprünglich in allgemeinerer Weise an die Sache heranzugehen.

Ich denke immer noch, dass das Problem nicht einseitig beim Allokatordesign selbst zu suchen ist, sondern das schon theoretisch nur postuliert wird, dass Allokatoren und Container orthogonale Konzepte sind. Beschränkt man sich auf stateless Allokatoren, ist das aber möglicherweise machbar.

ne, verstehe ich nicht.
alles was allokatoren sind, ist eine malloc().

malloc braucht nur globalen state. Träfe deine Behauptung zu, wäre das eigentlich ein Totschlagargument gegen stateful allocators.

Wie sieht es denn mit der Kapselung aus. Der tatsächlich benutzte Allokatortyp kann in ziemlich beliebiger Weise vom Templateargument des Containers abweichen, und zwar in Abhängigkeit der Implementation dieses Containers. Andererseits ist es durchaus beobachtbar, welcher Allokator tatsächlich benutzt wird (zumindest können wir uns einen eigenen Allokator schreiben, bei dem das sichtbar wird). Ich sehe hier ein prinzipielles Problem.
Vergessen wir aber den Typ, landen wir tatsächlich bei so etwas wie malloc - und dafür brauchen wir keinen state.

Hast du eine konkrete Vorstellung, wie ein gutes Allokatordesign aussehen müsste?

[maximAL]

*ausgrab*

Wenn Allokatoren keinen State haben dürfen, was genau kann man dann mit dem Allokator-Parameter bei den Container-CTors erreichen? Weiterbenutzen "darf" man die Instanz ja eigentlich nicht.
Ich hab mir mal die Implementierung vom g++ vector angesehen und dort wird, soweit ich das durchschaue, eine Allokator-Instanz als Member gehalten, die gegebenenfalls über den CTor initialisiert wird.

Meine Zielsetzung ist wohl ähnlich wie bei dooooomi einen per-Instanz Pool von Objekten zu haben, der Anfangs mit einer unveränderlichen Kapazität initialisiert wird.
Eben wegen diesen ganzen Problemen mit statusbehafteten Allokatoren (leider muss es sehr portabel sein), habe ich letztendlich den Weg gewählt, dass der Container den Allokator ganz einfach benutzt, um sich anfangs seinen Pool zu allokieren und den Rest dann selbst macht.

[maximAL]

*push*

Sind die Experten noch alle im Weihnachtsurlaub?