SmallVector.hpp

A drop-in replacement for std::vector with optimization to handle small vector sizes without dynamic allocation. It contains some number of elements in-place, which allows it to avoid heap allocation when the actual number of elements is below that threshold. This allows normal “small” cases to be fast without losing generality for large inputs.

Note

Adapted from the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. See https://llvm.org/LICENSE.txt for license information. SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

Functions

template<typename T, unsigned N>
inline size_t capacity_in_bytes(const SmallVector<T, N> &X)
template<typename T, typename ...Ts>
struct AlignedCharArrayUnion
#include <SmallVector.hpp>

A suitably aligned and sized character array member which can hold elements of any type.

These types may be arrays, structs, or any other types. This exposes a buffer member which can be used as suitable storage for a placement new of any of these types.

Public Members

char buffer[sizeof(detail::SizerImpl<T, Ts...>)]
class SmallVectorBase
#include <SmallVector.hpp>

This is all the non-templated stuff common to all SmallVectors.

Subclassed by SmallVectorTemplateCommon< T, typename >

Public Functions

inline size_t size() const
inline size_t capacity() const
inline bool empty() const
inline void set_size(size_t N)

Set the array size to N, which the current array must have enough capacity for.

This does not construct or destroy any elements in the vector.

Clients can use this in conjunction with capacity() to write past the end of the buffer when they know that more elements are available, and only update the size later. This avoids the cost of value initializing elements which will only be overwritten.

Protected Functions

SmallVectorBase() = delete
inline SmallVectorBase(void *FirstEl, size_t TotalCapacity)
inline void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize)

This is an implementation of the grow() method which only works on POD-like data types and is out of line to reduce code duplication.

Protected Attributes

void *BeginX
unsigned Size = 0
unsigned Capacity
template<typename T, typename = void>
class SmallVectorTemplateCommon : public SmallVectorBase
#include <SmallVector.hpp>

This is the part of SmallVectorTemplateBase which does not depend on whether the type T is a POD. The extra dummy template argument is used by ArrayRef to avoid unnecessarily requiring T to be complete.

Subclassed by SmallVectorTemplateBase< T, bool >, SmallVectorTemplateBase< T, true >

Public Types

using size_type = size_t
using difference_type = ptrdiff_t
using value_type = T
using iterator = T*
using const_iterator = const T*
using const_reverse_iterator = std::reverse_iterator<const_iterator>
using reverse_iterator = std::reverse_iterator<iterator>
using reference = T&
using const_reference = const T&
using pointer = T*
using const_pointer = const T*

Public Functions

inline iterator begin()
inline const_iterator begin() const
inline iterator end()
inline const_iterator end() const
inline reverse_iterator rbegin()
inline const_reverse_iterator rbegin() const
inline reverse_iterator rend()
inline const_reverse_iterator rend() const
inline size_type size_in_bytes() const
inline size_type max_size() const
inline size_t capacity_in_bytes() const
inline pointer data()

Return a pointer to the vector’s buffer, even if empty().

inline const_pointer data() const

Return a pointer to the vector’s buffer, even if empty().

inline reference operator[](size_type idx)
inline const_reference operator[](size_type idx) const
inline reference front()
inline const_reference front() const
inline reference back()
inline const_reference back() const

Protected Functions

inline SmallVectorTemplateCommon(size_t Size)
inline void grow_pod(size_t MinCapacity, size_t TSize)
inline bool isSmall() const

Return true if this is a smallvector which has not had dynamic memory allocated for it.

inline void resetToSmall()

Put this vector in a state of being small.

Private Functions

inline void *getFirstEl() const

Find the address of the first element. For this pointer math to be valid with small-size of 0 for T with lots of alignment, it’s important that SmallVectorStorage is properly-aligned even for small-size of 0.

template<typename T, bool = std::is_trivially_copyable<T>::value>
class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T>
#include <SmallVector.hpp>

SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method implementations that are designed to work with non-POD-like T’s.

Public Functions

inline void push_back(const T &Elt)
inline void push_back(T &&Elt)
inline void pop_back()

Protected Functions

inline SmallVectorTemplateBase(size_t Size)
void grow(size_t MinSize = 0)

Grow the allocated memory (without initializing new elements), doubling the size of the allocated memory. Guarantees space for at least one more element, or MinSize more elements if specified.

Protected Static Functions

static inline void destroy_range(T *S, T *E)
template<typename It1, typename It2>
static inline void uninitialized_move(It1 I, It1 E, It2 Dest)

Move the range [I, E) into the uninitialized memory starting with “Dest”, constructing elements as needed.

template<typename It1, typename It2>
static inline void uninitialized_copy(It1 I, It1 E, It2 Dest)

Copy the range [I, E) onto the uninitialized memory starting with “Dest”, constructing elements as needed.

template<typename T>
class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T>
#include <SmallVector.hpp>

SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put method implementations that are designed to work with POD-like T’s.

Public Functions

inline void push_back(const T &Elt)
inline void pop_back()

Protected Functions

inline SmallVectorTemplateBase(size_t Size)
inline void grow(size_t MinSize = 0)

Double the size of the allocated memory, guaranteeing space for at least one more element or MinSize if specified.

Protected Static Functions

static inline void destroy_range(T*, T*)
template<typename It1, typename It2>
static inline void uninitialized_move(It1 I, It1 E, It2 Dest)

Move the range [I, E) onto the uninitialized memory starting with “Dest”, constructing elements into it as needed.

template<typename It1, typename It2>
static inline void uninitialized_copy(It1 I, It1 E, It2 Dest)

Copy the range [I, E) onto the uninitialized memory starting with “Dest”, constructing elements into it as needed.

template<typename T1, typename T2>
static inline void uninitialized_copy(T1 *I, T1 *E, T2 *Dest, typename std::enable_if<std::is_same<typename std::remove_const<T1>::type, T2>::value>::type* = nullptr)

Copy the range [I, E) onto the uninitialized memory starting with “Dest”, constructing elements into it as needed.

template<typename T, unsigned N>
class SmallVector : public SmallVectorImpl<T>, private SmallVectorStorage<T, N>
#include <SmallVector.hpp>

This is a ‘vector’ (really, a variable-sized array), optimized for the case when the array is small. It contains some number of elements in-place, which allows it to avoid heap allocation when the actual number of elements is below that threshold. This allows normal “small” cases to be fast without losing generality for large inputs.

Note that this does not attempt to be exception safe.

Public Functions

inline SmallVector()
inline ~SmallVector()
inline explicit SmallVector(size_t Size, const T &Value = T())
template<typename ItTy, typename = typename std::enable_if<std::is_convertible<typename std::iterator_traits<ItTy>::iterator_category, std::input_iterator_tag>::value>::type>
inline SmallVector(ItTy S, ItTy E)
inline SmallVector(std::initializer_list<T> IL)
inline SmallVector(const SmallVector &RHS)
inline const SmallVector &operator=(const SmallVector &RHS)
inline SmallVector(SmallVector &&RHS)
inline SmallVector(SmallVectorImpl<T> &&RHS)
inline const SmallVector &operator=(SmallVector &&RHS)
inline const SmallVector &operator=(SmallVectorImpl<T> &&RHS)
inline const SmallVector &operator=(std::initializer_list<T> IL)