CODEWITHSUNDEEP
c++optimizationstlcontainers
peterchen
peterchen

Reputation: 41126

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

Upvotes: 0

Views: 1637

Answers (2)

Charles Salvia
Charles Salvia

Reputation: 53339

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.

Upvotes: 3

Matthieu M.
Matthieu M.

Reputation: 300399

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.

Upvotes: 0

Related Questions