FOLLY: small_vector.h

FOLLY: small_vector.h

folly::small_vector<T,Int=1,...> is a sequence container that implements small buffer optimization.

It behaves similarly to std::vector except that it does not use the heap until a certain number of elements have been allocated.

Like a standard vector, contiguous memory is guaranteed to be used. (So ​​after it's spilled onto the heap, all 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 one of the following cases:

• Short-lived stack vectors with few elements (or perhaps a usually known number of elements) if you want to avoid malloc.

• If the vectors are usually below a known size and lookups are very common, you save yourself another cache miss in the common case of keeping data in-place.

• You have billions of these vectors and don't want to waste space tracking std::vector capacity. This vector allows malloc to keep track of our allocation capacity. (Note that this slows down the embedding/redistribution paths significantly; if you need them to be fast, you should use fbvector.)

The last two cases were the main motivation for the implementation.

There are also several flags you can pass to this class template to customize its behavior. After counting on the spot, you can provide them in any order. They are all in the small_vector_policy namespace.

• NoHeap - Avoid the heap altogether. (Throws a std::length_error if you spilled from the in-place allocation.)

• <Any Integral Type> – adjusts the amount of space we spend tracking the size of the vector.