tpl_small_vector.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef TPL_SMALL_VECTOR_H
#define TPL_SMALL_VECTOR_H
 
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>
 
#include <ah-errors.H>
 
namespace Aleph {
 
template <typename T, size_t N = 8>
class SmallVector
{
  static_assert(N > 0, "SmallVector requires a positive inline capacity");
  static_assert(std::is_move_constructible_v<T>,
                "SmallVector requires a move-constructible element type");
 
  // Raw inline storage for the first N elements. The buffer is aligned as T so
  // placement-new can construct T objects here without a separate heap allocation.
  alignas(T) std::byte storage_[N * sizeof(T)];
  T *ptr_;
  size_t n_ = 0;
  size_t cap_ = N;
 
  T *inline_ptr() noexcept
  {
    return reinterpret_cast<T *>(storage_);
  }
 
  const T *inline_ptr() const noexcept
  {
    return reinterpret_cast<const T *>(storage_);
  }
 
  static T *allocate(size_t m)
  {
    return std::allocator<T>().allocate(m);
  }
 
  static void deallocate(T *p, size_t m) noexcept
  {
    std::allocator<T>().deallocate(p, m);
  }
 
  // Moves the elements into a fresh heap buffer of capacity new_cap
  // (strong guarantee via move_if_noexcept) and releases the old buffer.
  void relocate(const size_t new_cap)
  {
    T *np = allocate(new_cap);
    size_t i = 0;
    try
      {
        for (; i < n_; ++i)
          ::new (static_cast<void *>(np + i)) T(std::move_if_noexcept(ptr_[i]));
      }
    catch (...)
      {
        std::destroy(np, np + i);
        deallocate(np, new_cap);
        throw;
      }
    std::destroy(ptr_, ptr_ + n_);
    if (not is_small())
      deallocate(ptr_, cap_);
    ptr_ = np;
    cap_ = new_cap;
  }
 
  // Ensures room for at least min_cap elements, growing geometrically.
  void grow(const size_t min_cap)
  {
    size_t new_cap = cap_;
    while (new_cap < min_cap)
      {
        ah_overflow_error_if(new_cap > (static_cast<size_t>(-1) >> 1))
          << "SmallVector::grow(): capacity overflow";
        new_cap <<= 1;
      }
    relocate(new_cap);
  }
 
  // Takes over o's contents. *this must be empty and inline.
  void steal(SmallVector &&o) noexcept(std::is_nothrow_move_constructible_v<T>)
  {
    if (o.is_small())
      {
        if constexpr (std::is_nothrow_move_constructible_v<T>)
          {
            for (; n_ < o.n_; ++n_)
              ::new (static_cast<void *>(ptr_ + n_)) T(std::move(o.ptr_[n_]));
          }
        else
          {
            try
              {
                for (; n_ < o.n_; ++n_)
                  ::new (static_cast<void *>(ptr_ + n_)) T(std::move(o.ptr_[n_]));
              }
            catch (...)
              {
                release();
                throw;
              }
          }
        std::destroy(o.ptr_, o.ptr_ + o.n_);
        o.n_ = 0;
      }
    else
      {
        ptr_ = o.ptr_;
        cap_ = o.cap_;
        n_ = o.n_;
        o.ptr_ = o.inline_ptr();
        o.cap_ = N;
        o.n_ = 0;
      }
  }
 
  // Destroys all elements and releases the heap buffer, back to inline.
  void release() noexcept
  {
    std::destroy(ptr_, ptr_ + n_);
    if (not is_small())
      deallocate(ptr_, cap_);
    ptr_ = inline_ptr();
    cap_ = N;
    n_ = 0;
  }
 
public:
  using Item_Type = T;               
  using value_type = T;              
  using size_type = size_t;          
  using iterator = T *;              
  using const_iterator = const T *;  
 
  SmallVector() noexcept : ptr_(inline_ptr()) {}
 
  SmallVector(const size_t n, const T &value)
    requires std::is_copy_constructible_v<T>
    : ptr_(inline_ptr())
  {
    if (n > cap_)
      grow(n);
    try
      {
        for (; n_ < n; ++n_)
          ::new (static_cast<void *>(ptr_ + n_)) T(value);
      }
    catch (...)
      {
        release();
        throw;
      }
  }
 
  SmallVector(std::initializer_list<T> l)
    requires std::is_copy_constructible_v<T>
    : ptr_(inline_ptr())
  {
    if (l.size() > cap_)
      grow(l.size());
    try
      {
        for (const T &x : l)
          {
            ::new (static_cast<void *>(ptr_ + n_)) T(x);
            ++n_;
          }
      }
    catch (...)
      {
        release();
        throw;
      }
  }
 
  template <std::input_iterator It>
  SmallVector(It first, It last) : ptr_(inline_ptr())
  {
    try
      {
        for (; first != last; ++first)
          append(*first);
      }
    catch (...)
      {
        release();
        throw;
      }
  }
 
  SmallVector(const SmallVector &v)
    requires std::is_copy_constructible_v<T>
    : ptr_(inline_ptr())
  {
    if (v.n_ > cap_)
      grow(v.n_);
    try
      {
        for (; n_ < v.n_; ++n_)
          ::new (static_cast<void *>(ptr_ + n_)) T(v.ptr_[n_]);
      }
    catch (...)
      {
        release();
        throw;
      }
  }
 
  SmallVector(SmallVector &&v) noexcept(std::is_nothrow_move_constructible_v<T>)
    : ptr_(inline_ptr())
  {
    steal(std::move(v));
  }
 
  SmallVector &operator = (const SmallVector &v)
    requires std::is_copy_constructible_v<T>
  {
    if (this == &v)
      return *this;
    release();
    if (v.n_ > cap_)
      grow(v.n_);
    for (; n_ < v.n_; ++n_)
      ::new (static_cast<void *>(ptr_ + n_)) T(v.ptr_[n_]);
    return *this;
  }
 
  SmallVector &operator = (SmallVector &&v) noexcept(std::is_nothrow_move_constructible_v<T>)
  {
    if (this == &v)
      return *this;
    release();
    steal(std::move(v));
    return *this;
  }
 
  ~SmallVector()
  {
    release();
  }
 
  void swap(SmallVector &v) noexcept(std::is_nothrow_move_constructible_v<T>)
  {
    if (not is_small() and not v.is_small())
      {
        std::swap(ptr_, v.ptr_);
        std::swap(n_, v.n_);
        std::swap(cap_, v.cap_);
        return;
      }
    SmallVector tmp(std::move(*this));
    *this = std::move(v);
    v = std::move(tmp);
  }
 
  // -- capacity -------------------------------------------------------------
 
  [[nodiscard]] size_t size() const noexcept
  {
    return n_;
  }
 
  [[nodiscard]] size_t capacity() const noexcept
  {
    return cap_;
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return n_ == 0;
  }
 
  [[nodiscard]] bool is_small() const noexcept
  {
    return ptr_ == inline_ptr();
  }
 
  void reserve(const size_t cap)
  {
    if (cap > cap_)
      grow(cap);
  }
 
  void empty() noexcept
  {
    std::destroy(ptr_, ptr_ + n_);
    n_ = 0;
  }
 
  void clear() noexcept
  {
    empty();
  }
 
  // -- element access -------------------------------------------------------
 
  [[nodiscard]] T &operator [] (size_t i)
  {
    ah_out_of_range_error_if(i >= n_) << "SmallVector: index out of range";
    return ptr_[i];
  }
 
  [[nodiscard]] const T &operator [] (size_t i) const
  {
    ah_out_of_range_error_if(i >= n_) << "SmallVector: index out of range";
    return ptr_[i];
  }
 
  [[nodiscard]] T &operator () (size_t i) noexcept
  {
    return ptr_[i];
  }
 
  [[nodiscard]] const T &operator () (size_t i) const noexcept
  {
    return ptr_[i];
  }
 
  [[nodiscard]] T &get_first()
  {
    ah_underflow_error_if(n_ == 0) << "SmallVector::get_first(): empty";
    return ptr_[0];
  }
 
  [[nodiscard]] const T &get_first() const
  {
    ah_underflow_error_if(n_ == 0) << "SmallVector::get_first(): empty";
    return ptr_[0];
  }
 
  [[nodiscard]] T &get_last()
  {
    ah_underflow_error_if(n_ == 0) << "SmallVector::get_last(): empty";
    return ptr_[n_ - 1];
  }
 
  [[nodiscard]] const T &get_last() const
  {
    ah_underflow_error_if(n_ == 0) << "SmallVector::get_last(): empty";
    return ptr_[n_ - 1];
  }
 
  [[nodiscard]] T *data() noexcept
  {
    return ptr_;
  }
 
  [[nodiscard]] const T *data() const noexcept
  {
    return ptr_;
  }
 
  // -- modifiers ------------------------------------------------------------
 
  template <class... Args>
  T &emplace_back(Args &&...args)
  {
    if (n_ == cap_)
      {
        T tmp(std::forward<Args>(args)...);
        grow(n_ + 1);
        ::new (static_cast<void *>(ptr_ + n_)) T(std::move(tmp));
      }
    else
      ::new (static_cast<void *>(ptr_ + n_)) T(std::forward<Args>(args)...);
    return ptr_[n_++];
  }
 
  T &append(const T &item)
    requires std::is_copy_constructible_v<T>
  {
    return emplace_back(item);
  }
 
  T &append(T &&item)
  {
    return emplace_back(std::move(item));
  }
 
  void append_range(const T *first, const size_t count)
    requires std::is_copy_constructible_v<T>
  {
    if (count == 0)
      return;
    ah_invalid_argument_if(first == nullptr)
      << "SmallVector::append_range(): null source pointer";
    // Checked *before* computing `n_ + count`, not after: for an
    // adversarial or mistaken huge `count`, the raw sum can wrap around
    // `size_t` and come out `<= cap_`, which would skip the `grow()`
    // call below entirely and then `memcpy` (or the placement-new loop)
    // straight past the end of the real, too-small buffer.
    ah_overflow_error_if(count > std::numeric_limits<size_t>::max() - n_)
      << "SmallVector::append_range(): count overflows size_t when added "
         "to the current size";
    if (n_ + count > cap_)
      grow(n_ + count);
    if constexpr (std::is_trivially_copyable_v<T>)
      {
        // std::uninitialized_copy_n, not a raw memcpy: copying the object
        // representation into storage that holds no object yet only
        // implicitly starts a `T` object's lifetime there (C++20
        // [basic.types.general]) when `T` is an *implicit-lifetime*
        // type -- trivially copyable does not by itself guarantee that
        // (e.g. a type whose only non-deleted special member is a
        // trivial assignment operator, with every constructor deleted,
        // is trivially copyable but not implicit-lifetime). Standard
        // library implementations detect the trivially-copyable case
        // and lower this to the same memcpy, so this costs nothing.
        std::uninitialized_copy_n(first, count, ptr_ + n_);
        n_ += count;
      }
    else
      {
        size_t i = 0;
        try
          {
            for (; i < count; ++i)
              ::new (static_cast<void *>(ptr_ + n_ + i)) T(first[i]);
          }
        catch (...)
          {
            std::destroy(ptr_ + n_, ptr_ + n_ + i);
            throw;
          }
        n_ += count;
      }
  }
 
  T &push_back(const T &item)
    requires std::is_copy_constructible_v<T>
  {
    return append(item);
  }
 
  T &push_back(T &&item)
  {
    return append(std::move(item));
  }
 
  T remove_last()
  {
    ah_underflow_error_if(n_ == 0) << "SmallVector::remove_last(): empty";
    T ret = std::move(ptr_[n_ - 1]);
    std::destroy_at(ptr_ + --n_);
    return ret;
  }
 
  void pop_back()
  {
    ah_underflow_error_if(n_ == 0) << "SmallVector::pop_back(): empty";
    std::destroy_at(ptr_ + --n_);
  }
 
  T &insert(size_t pos, T item)
    requires std::is_move_assignable_v<T>
  {
    ah_out_of_range_error_if(pos > n_) << "SmallVector::insert(): position out of range";
    if (n_ == cap_)
      grow(n_ + 1);
    if (pos == n_)
      {
        ::new (static_cast<void *>(ptr_ + n_)) T(std::move(item));
        return ptr_[n_++];
      }
    ::new (static_cast<void *>(ptr_ + n_)) T(std::move(ptr_[n_ - 1]));
    for (size_t i = n_ - 1; i > pos; --i)
      ptr_[i] = std::move(ptr_[i - 1]);
    ptr_[pos] = std::move(item);
    ++n_;
    return ptr_[pos];
  }
 
  void erase(const size_t pos)
    requires std::is_move_assignable_v<T>
  {
    ah_out_of_range_error_if(pos >= n_) << "SmallVector::erase(): position out of range";
    for (size_t i = pos; i + 1 < n_; ++i)
      ptr_[i] = std::move(ptr_[i + 1]);
    std::destroy_at(ptr_ + --n_);
  }
 
  // -- iteration ------------------------------------------------------------
 
  iterator begin() noexcept
  {
    return ptr_;
  }
 
  iterator end() noexcept
  {
    return ptr_ + n_;
  }
 
  const_iterator begin() const noexcept
  {
    return ptr_;
  }
 
  const_iterator end() const noexcept
  {
    return ptr_ + n_;
  }
 
  const_iterator cbegin() const noexcept
  {
    return ptr_;
  }
 
  const_iterator cend() const noexcept
  {
    return ptr_ + n_;
  }
 
  template <class Operation>
  bool traverse(Operation operation)
  {
    for (size_t i = 0; i < n_; ++i)
      if (not operation(ptr_[i]))
        return false;
    return true;
  }
 
  template <class Operation>
  bool traverse(Operation operation) const
  {
    for (size_t i = 0; i < n_; ++i)
      if (not operation(ptr_[i]))
        return false;
    return true;
  }
 
  // -- comparison -----------------------------------------------------------
 
  template <size_t M>
  bool operator == (const SmallVector<T, M> &v) const
  {
    if (n_ != v.size())
      return false;
    for (size_t i = 0; i < n_; ++i)
      if (not (ptr_[i] == v(i)))
        return false;
    return true;
  }
 
  template <size_t M>
  bool operator != (const SmallVector<T, M> &v) const
  {
    return not (*this == v);
  }
};
 
}  // end namespace Aleph
 
#endif  // TPL_SMALL_VECTOR_H