static_vector.h

#ifndef _STATIC_VECTOR_H_
#define _STATIC_VECTOR_H_

#include <algorithm>
#include <type_traits>
#include "macros.h"

template <typename T, size_t StaticSize = SMALL_SIZE_VEC>
class static_vector {

  static const bool is_trivially_destructible =
    private_::is_trivially_destructible<T>::value;

  // std::is_trivially_copyable not supported in g++-4.7
  static const bool is_trivially_copyable = std::is_scalar<T>::value;

public:

  typedef T value_type;
  typedef T & reference;
  typedef const T & const_reference;
  typedef size_t size_type;

  inline static_vector() : n(0) {}
  inline ~static_vector() { clear(); }

  inline static_vector(const static_vector &that)
    : n(0)
  {
    assignFrom(that);
  }

  // not efficient, don't use in performance critical parts
  static_vector(std::initializer_list<T> l)
    : n(0)
  {
    for (auto &p : l)
      push_back(p);
  }

  static_vector &
  operator=(const static_vector &that)
  {
    assignFrom(that);
    return *this;
  }

  inline size_t
  size() const
  {
    return n;
  }

  inline bool
  empty() const
  {
    return !n;
  }

  inline reference
  front()
  {
    INVARIANT(n > 0);
    INVARIANT(n <= StaticSize);
    return *ptr();
  }

  inline const_reference
  front() const
  {
    return const_cast<static_vector *>(this)->front();
  }

  inline reference
  back()
  {
    INVARIANT(n > 0);
    INVARIANT(n <= StaticSize);
    return ptr()[n - 1];
  }

  inline const_reference
  back() const
  {
    return const_cast<static_vector *>(this)->back();
  }

  inline void
  pop_back()
  {
    INVARIANT(n > 0);
    if (!is_trivially_destructible)
      ptr()[n - 1].~T();
    n--;
  }

  inline void
  push_back(const T &obj)
  {
    emplace_back(obj);
  }

  inline void
  push_back(T &&obj)
  {
    emplace_back(std::move(obj));
  }

  // C++11 goodness- a strange syntax this is

  template <class... Args>
  inline void
  emplace_back(Args &&... args)
  {
    INVARIANT(n < StaticSize);
    new (&(ptr()[n++])) T(std::forward<Args>(args)...);
  }

  inline reference
  operator[](int i)
  {
    return ptr()[i];
  }

  inline const_reference
  operator[](int i) const
  {
    return const_cast<static_vector *>(this)->operator[](i);
  }

  void
  clear()
  {
    if (!is_trivially_destructible)
      for (size_t i = 0; i < n; i++)
        ptr()[i].~T();
    n = 0;
  }

  inline void
  reserve(size_t n)
  {
  }

  inline void
  resize(size_t n, value_type val = value_type())
  {
    INVARIANT(n <= StaticSize);
    if (n > this->n) {
      // expand
      while (this->n < n)
        new (&ptr()[this->n++]) T(val);
    } else if (n < this->n) {
      // shrink
      while (this->n > n) {
        if (!is_trivially_destructible)
          ptr()[this->n - 1].~T();
        this->n--;
      }
    }
  }

  // non-standard API
  inline bool is_small_type() const { return true; }

  template <typename Compare = std::less<T>>
  inline void
  sort(Compare c = Compare())
  {
    std::sort(begin(), end(), c);
  }

private:

  template <typename ObjType>
  class iterator_ : public std::iterator<std::bidirectional_iterator_tag, ObjType> {
    friend class static_vector;
  public:
    inline iterator_() : p(0) {}

    template <typename O>
    inline iterator_(const iterator_<O> &other)
      : p(other.p)
    {}

    inline ObjType &
    operator*() const
    {
      return *p;
    }

    inline ObjType *
    operator->() const
    {
      return p;
    }

    inline bool
    operator==(const iterator_ &o) const
    {
      return p == o.p;
    }

    inline bool
    operator!=(const iterator_ &o) const
    {
      return !operator==(o);
    }

    inline bool
    operator<(const iterator_ &o) const
    {
      return p < o.p;
    }

    inline bool
    operator>=(const iterator_ &o) const
    {
      return !operator<(o);
    }

    inline bool
    operator>(const iterator_ &o) const
    {
      return p > o.p;
    }

    inline bool
    operator<=(const iterator_ &o) const
    {
      return !operator>(o);
    }

    inline iterator_ &
    operator+=(int n)
    {
      p += n;
      return *this;
    }

    inline iterator_ &
    operator-=(int n)
    {
      p -= n;
      return *this;
    }

    inline iterator_
    operator+(int n) const
    {
      iterator_ cpy = *this;
      return cpy += n;
    }

    inline iterator_
    operator-(int n) const
    {
      iterator_ cpy = *this;
      return cpy -= n;
    }

    inline intptr_t
    operator-(const iterator_ &o) const
    {
      return p - o.p;
    }

    inline iterator_ &
    operator++()
    {
      ++p;
      return *this;
    }

    inline iterator_
    operator++(int)
    {
      iterator_ cur = *this;
      ++(*this);
      return cur;
    }

    inline iterator_ &
    operator--()
    {
      --p;
      return *this;
    }

    inline iterator_
    operator--(int)
    {
      iterator_ cur = *this;
      --(*this);
      return cur;
    }

  protected:
    inline iterator_(ObjType *p) : p(p) {}

  private:
    ObjType *p;
  };

public:

  typedef iterator_<T> iterator;
  typedef iterator_<const T> const_iterator;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  inline iterator
  begin()
  {
    return iterator(ptr());
  }

  inline const_iterator
  begin() const
  {
    return const_iterator(ptr());
  }

  inline iterator
  end()
  {
    return iterator(endptr());
  }

  inline const_iterator
  end() const
  {
    return const_iterator(endptr());
  }

  inline reverse_iterator
  rbegin()
  {
    return reverse_iterator(end());
  }

  inline const_reverse_iterator
  rbegin() const
  {
    return const_reverse_iterator(end());
  }

  inline reverse_iterator
  rend()
  {
    return reverse_iterator(begin());
  }

  inline const_reverse_iterator
  rend() const
  {
    return const_reverse_iterator(begin());
  }

private:
  void
  assignFrom(const static_vector &that)
  {
    if (unlikely(this == &that))
      return;
    clear();
    INVARIANT(that.n <= StaticSize);
    if (is_trivially_copyable) {
      NDB_MEMCPY(ptr(), that.ptr(), that.n * sizeof(T));
    } else {
      for (size_t i = 0; i < that.n; i++)
        new (&(ptr()[i])) T(that.ptr()[i]);
    }
    n = that.n;
  }

  inline ALWAYS_INLINE T *
  ptr()
  {
    return reinterpret_cast<T *>(&elems_buf[0]);
  }

  inline ALWAYS_INLINE const T *
  ptr() const
  {
    return reinterpret_cast<const T *>(&elems_buf[0]);
  }

  inline ALWAYS_INLINE T *
  endptr()
  {
    return ptr() + n;
  }

  inline ALWAYS_INLINE const T *
  endptr() const
  {
    return ptr() + n;
  }

  size_t n;
  char elems_buf[sizeof(T) * StaticSize];
};

#endif /* _STATIC_VECTOR_H_ */