container with stack and dynamic allocation

Is there a container that uses a local buffer for a small number of elements, and uses a heap allocation only when the number of elements exceeds a certain limit? Similar to what most std::string implementations do.

Background

The container is used in the following (simplified) context:

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)
{
  // ...
}

This code part has high call frequency, but tagging an item is rather rare, number of items in someContainer is usually low but unbound. I can't use a preallocated "more global" buffer easily. The goal is to avoid the frequent allocation.

Call Frequency

• Common: no item becomes tagged. std::vector is fine
• Common: only one of a few items become tagged. causes high 开发者_StackOverflowfrequency allocation I want to avoid
• Very rare, but must be supported: someList grows during first pass, number of items not predictable but still low

There is no standard container which guarantees this sort of behavior. However, if you're up to it, you can create a custom STL-compatible allocator class that draws from a small stack buffer for small allocations, and only performs a heap allocation when the requested allocation size exceeds the size of the stack buffer. You can plug-in your custom allocator class as the second template parameter for std::vector<T, Alloc>.

For information on creating a custom allocator, you should read this article.

Though this is not guaranteed, most std::string will implement the Small String Optimization, which is just that (with VC++10 up to 8 or 16 characters are thusly stored)

I have not seen vectors do it, and always wondered why, but the upcoming C++ standard will facilitate this with std::aligned_storage and alignof. This way we'll be able to get properly aligned raw memory and build containers with some default number of "stack" memory.