folly/docs/small_vector.md

   1 `folly/small_vector.h`
   2 ----------------------
   3
   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
   7 does not use the heap.
   8
   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.)
  11
  12 Simple usage example:
  13
  14 ``` Cpp
  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.
  19 ```
  20
  21 ### Details
  22 ***
  23
  24 This class is useful in either of following cases:
  25
  26 * Short-lived stack vectors with few elements (or maybe with a
  27   usually-known number of elements), if you want to avoid malloc.
  28
  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.
  32
  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`.)
  38
  39 The last two cases were the main motivation for implementing it.
  40
  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
  44 small_vector_policy`.
  45
  46 * `NoHeap` - Avoid the heap entirely.  (Throws `std::length_error` if
  47   you would've spilled out of the in-place allocation.)
  48
  49 * `<Any integral type>` - customizes the amount of space we spend on
  50   tracking the size of the vector.
  51
  52 A couple more examples:
  53
  54 ``` Cpp
  55     // With space for 32 in situ unique pointers, and only using a
  56     // 4-byte size_type.
  57     small_vector<std::unique_ptr<int>, 32, uint32_t> v;
  58
  59     // A inline vector of up to 256 ints which will not use the heap.
  60     small_vector<int, 256, NoHeap> v;
  61
  62     // Same as the above, but making the size_type smaller too.
  63     small_vector<int, 256, NoHeap, uint16_t> v;
  64 ```