Matt,
Regarding your use of allocators in your implementation: a. Support the C++ allocator model 1. Either use a.allocate(size) or allocator_traits<A>::allocate(a, size, hint) if you want to supply a hint, but don't bother calling a.allocate(size, 0) - you alienate anyone who writes a C++11 allocator that may not provide an allocate(size, hint) member.
Right - this might be something that has to change for the boost submission, the original is designed to work with both C++0x and C++11, and the hints made a substantial difference to speed with std::allocator.
2. Use allocator_traits<A>::construct(a, ...) and allocator_traits<A>::destroy(a) instead of a.construct(...) and a.destroy(...)
Why, and is there a C++0x-friendly way of doing the same thing?
3. Use allocator_traits<A> to obtain the type members (pointer, rebind, etc.) (You could use boost::allocator_traits if you want to support pre-C++11)
What is the advantage of doing this?
b. Use a compressed_pair<> or the EBCO to reduce the storage for when stateless allocators are supplied (i.e. instead of the 1 + 1 bytes that would be used for the empty objects).
Empty base optimization is not something I understand at this point. I've read a bit about it but I am not sure in which particular area of the colony it would make a difference in?
c. Support element_type's whose constructor might throw: Do you catch, accordingly destroy any constructed elements, deallocate any allocated elements, before rethrowing?
I guess that makes sense in the limited scenario where memory is full. My general feeling is more in line with Mike Acton's in that if something throws, you've got a problem anyway - peaceably unrolling isn't really helping anyone. But I grant that in the context of boost, and in some scenarios, this is vital, and will look at adding it. Thank you, Matt