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
buffermember which can be used as suitable storage for a placement new of any of these types.
-
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.
-
inline size_t size() const
-
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 const_reverse_iterator = std::reverse_iterator<const_iterator>
Public Functions
-
inline const_iterator begin() const
-
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_t capacity_in_bytes() const
-
inline const_pointer data() const
Return a pointer to the vector’s buffer, even if empty().
-
inline const_reference operator[](size_type idx) const
-
inline const_reference front() const
-
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.
-
using size_type = size_t
-
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 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.
-
inline void pop_back()
-
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.
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
-
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.
-
inline SmallVectorTemplateBase(size_t Size)
-
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()
-
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(const SmallVector &RHS)
-
inline const SmallVector &operator=(const SmallVector &RHS)
-
inline SmallVector(SmallVector &&RHS)
-
inline const SmallVector &operator=(SmallVector &&RHS)
-
inline const SmallVector &operator=(SmallVectorImpl<T> &&RHS)
-
inline const SmallVector &operator=(std::initializer_list<T> IL)
-
inline SmallVector()