folly::small_vector<T,Int=1,...> is a sequence container that
implements small buffer optimization. It behaves similarly to
std::vector, except until a certain number of elements are reserved it
does not use the heap.
Like standard vector, it is guaranteed to use contiguous memory. (So, after it spills to the heap all the elements live in the heap buffer.)
Simple usage example:
small_vector<int,2> vec; vec.push_back(0); // Stored in-place on stack vec.push_back(1); // Still on the stack vec.push_back(2); // Switches to heap buffer.
This class is useful in either of following cases:
Short-lived stack vectors with few elements (or maybe with a usually-known number of elements), if you want to avoid malloc.
If the vector(s) are usually under a known size and lookups are very common, you'll save an extra cache miss in the common case when the data is kept in-place.
You have billions of these vectors and don't want to waste space on
std::vector's capacity tracking. This vector lets
malloctrack our allocation capacity. (Note that this slows down the insertion/reallocation code paths significantly; if you need those to be fast you should use
The last two cases were the main motivation for implementing it.
There are also a couple of flags you can pass into this class
template to customize its behavior. You can provide them in any
order after the in-place count. They are all in the
NoHeap- Avoid the heap entirely. (Throws
std::length_errorif you would've spilled out of the in-place allocation.)
OneBitMutex- On x64 platforms, this spends one bit of the
size_typeto provide a spin lock that you can use for whatever you want.
<Any integral type>- customizes the amount of space we spend on tracking the size of the vector.
A couple more examples:
// With space for 32 in situ unique pointers, and only using a // 4-byte size_type. small_vector<std::unique_ptr<int>, 32, uint32_t> v; // A inline vector of up to 256 ints which will not use the // heap and comes with a spin lock. small_vector<int, 256, NoHeap, OneBitMutex> v; // Same as the above, but making the size_type smaller too. small_vector<int, 256, NoHeap, uint16_t, OneBitMutex> v;