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