0

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 frequency allocation I want to avoid
  • Very rare, but must be supported: someList grows during first pass, number of items not predictable but still low
peterchen
  • 40,917
  • 20
  • 104
  • 186
  • Do you want to use static or stack allocations? For stack allocation see http://stackoverflow.com/questions/354442/looking-for-c-stl-like-vector-class-but-using-stack-storage – nimrodm Dec 10 '10 at 07:20
  • @nimrodn: stack allocation is probably a better description of what I want (fixed title). i.e. a limited number of elements that can be stored within the container instance (without additional allocation), and using heap allocation if that's not sufficient. – peterchen Dec 10 '10 at 11:39
  • `std::vector` does not allocate any memory before at least one element is inserted. – Matthieu M. Dec 10 '10 at 16:14

2 Answers2

3

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.

Charles Salvia
  • 52,325
  • 13
  • 128
  • 140
  • 3
    You could also try .reserve()ing an amount of space in the vector that is small, but "enough" most of the time. That will potentially avoid reallocations if your vector's policy is to start at a size of 1 and use the same resizing policy regardless of current size. – Karl Knechtel Dec 10 '10 at 07:52
  • 1
    @Karl: A common scenario is that the container will remain empty. Reserving will be bad for this, since it will always allocate dynamic memory. – visitor Dec 10 '10 at 10:38
  • 1
    in C++0x that is certainly the solution, however if I recall correctly C++03 Allocators should not maintain state that is not shared between all instances of the Allocators (ie, any other allocator of the same type could be asked to destroy / deallocate, even if the two instances are completely unrelated). In practice, I think it should work :) – Matthieu M. Dec 10 '10 at 16:14
0

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.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • The sizeof a vector isn't normally more than the sizeof three pointers. How much data would fit into this space, given that you'll also need to store some housekeeping data? – visitor Dec 10 '10 at 10:40
  • 1
    @visitor: I guess it depends if you use the higher bits of the pointers to keep such data :) But I would personally be willing to have a buffier `vector` class. The cost of copying the `vector` is much different than the cost of copying 3 pointers, because it involves a dynamic allocation (thus a call to `allocate`) and the deep copy of existing data. Therefore my take was that it would be cheaper to simply reserve some extra space. `vector` for example. However I know of no such container, but I'll probably try it at home, though it's always hard to match the STL efficiency. – Matthieu M. Dec 10 '10 at 13:14
  • @Mattieu: *hard to match* - exactly, especially the efficiency+flexibility combination. It's easy to whip out something for my special case, but this would come with so many limitation it wouldn't be funny. – peterchen Dec 10 '10 at 14:04
  • @peterchen: that's true too, but even in pure efficiency, my code is often slower than the STL one even when I have the theoretical high-ground (like not allocating on the heap). That's where the "measure" comes into play I guess :D – Matthieu M. Dec 10 '10 at 16:24