Allocator für STL-Container: ein paar Fragen

[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?

[unskilled]

der Anfangs mit einer unveränderlichen Kapazität initialisiert wird.

das ist kein problem...
so was hab ich so gar vor einiger zeit mal geschrieben gehabt:

#ifndef H_MY_ALLOCATOR_ALLOCATE_AT_STACK_INCLUDED_20091202221055
#define H_MY_ALLOCATOR_ALLOCATE_AT_STACK_INCLUDED_20091202221055

#include <cassert>
#include <cstddef>
#include <new>
#include <stdexcept>
#ifdef _MSC_VER
#	pragma warning(push)
#	pragma warning(disable: 4510) //default constructor could not be generated
#	pragma warning(disable: 4610) //can never be instantiated - user defined constructor required
#endif
#include <type_traits>
#ifdef _MSC_VER
#	pragma warning(pop)
#endif

#ifdef _MSC_VER
#	pragma warning(push)
#	pragma warning(disable: 4100) //http://msdn.microsoft.com/en-us/library/26kb9fy0.aspx "C4100 can also be issued when code calls a destructor on a otherwise unreferenced parameter of primitive type. This is a limitation of the Visual C++ compiler."
#endif

namespace MY_NAMESPACE_NAME
{

	template <typename T, std::size_t count>
	struct stack_allocator;

	template <std::size_t count>
	struct stack_allocator <void, count>
	{
	public:
		typedef void* pointer;
		typedef const void* const_pointer;

		typedef void value_type;

		template <typename U>
		struct rebind
		{
			typedef stack_allocator<U, count> other;
		};
	};

	template <typename T, std::size_t count>
	struct stack_allocator
	{
	public:
		enum
		{
			allocating_size = count,
			allocating_byte = allocating_size*sizeof(T)
		};

		typedef std::size_t size_type;
		typedef std::ptrdiff_t difference_type;

		typedef T value_type;
		typedef value_type* pointer;
		typedef const value_type* const_pointer;
		typedef value_type& reference;
		typedef const value_type& const_reference;

		template <typename U>
		struct rebind
		{
			typedef stack_allocator<U, count> other;
		};

		stack_allocator() throw()
		:	empty(true)
		{}

		stack_allocator(const stack_allocator&) throw()
		:	empty(true)
		{}

		template <typename U, std::size_t Ucount>
		stack_allocator(const stack_allocator<U, Ucount>&) throw()
		:	empty(true)
		{}

		~stack_allocator() throw()
		{
			assert(empty);
			empty; //we dont want a warning at release-mode
		}

		pointer address(reference x) const
		{
			return &x;
		}

		const_pointer address(const_reference x) const
		{
			return &x;
		}

		pointer allocate(size_type n, stack_allocator<void, 0>::const_pointer /*hint*/ = 0)
		{
			if(n > allocating_size)
				throw std::bad_alloc();

			if(!empty)
				throw std::bad_alloc();

			empty = false;
			return reinterpret_cast<pointer>( data.data );
		}

		void deallocate(pointer p, size_type /*n*/)
		{
			assert( p == reinterpret_cast<pointer>(data.data) );
			p; //we dont want a warning at release-mode
			empty = true;
		}

		size_type max_size() const throw()
		{
			return allocating_size;
		}

		void construct(pointer p, const_reference val)
		{
			new ( static_cast<void*>(p) ) T(val);
		}

		void destroy(pointer p)
		{
			p->~T();
		}

	private:
		bool empty;
		union
		{
			typename std::tr1::aligned_storage<sizeof(T), std::tr1::alignment_of<T>::value>::type alignment;
			char data[allocating_byte];
		} data;
	};

	template <typename T, std::size_t Tc, typename U, std::size_t Uc>
	bool operator== (const stack_allocator<T, Tc>& /*lhs*/, const stack_allocator<U, Uc>& /*rhs*/) throw()
	{
		return true;
	}

	template <typename T, std::size_t Tc, typename U, std::size_t Uc>
	bool operator!= (const stack_allocator<T, Tc>& /*lhs*/, const stack_allocator<U, Uc>& /*rhs*/) throw()
	{
		return false;
	}

}//namespace MY_NAMESPACE_NAME

#ifdef _MSC_VER
#	pragma warning(pop)
#endif

#endif //#ifndef H_MY_ALLOCATOR_ALLOCATE_AT_STACK_INCLUDED_20091202221055

der allokator wird nur nie mit einer liste funktionieren, sondern lediglich mit nem vektor... außerdem muss man dann manuell ein reserve am anfang machen, was ein wenig nervig ist - aber mir hat es damals so gereicht^^
das problem bei einem allokator, der auch mit listen etc geht, ist halt, dass man dort lookups (nach freiem speicher) braucht - und somit wird man auch wieder langsamer... listen reservieren ja speicher nur immer für einen knoten auf einmal - obwohl man erst mal versuchen könnte, mehrere knoten auf einmal zu allokieren und nur wenn das schief geht, einzeln allokieren könnte - aber naja, man kann ja nicht alles haben
was ich mir bei der zeile im dtor gedacht hatte ( empty; //we dont want a warning at release-mode ), kann ich dir nicht mehr sagen xD
das #ifdef-zeugs um #include <type_traits> ist leider notwendig, weil sonst nen haufen warnings kommen - zumindest beim MSVC9
ist ein wenig fail, aber kann man halt nix machen

was genau kann man dann mit dem Allokator-Parameter bei den Container-CTors erreichen

man kann erreichen, dass der copy-ctor aufgerufen wird... und man muss das template-argument nicht mitschreiben...

bb