Add small_vector<T, N> class template

It has a (mostly) std::vector interface (it derives from it) and will store
up to N elements in the same storage as the vector instance itself.

1 files changed, 257 insertions, 0 deletions

diff --git a/butl/small-vector b/butl/small-vector
new file mode 100644
index 0000000..f09d91d
--- /dev/null
+++ b/butl/small-vector
@@ -0,0 +1,257 @@
+// file      : butl/small-vector -*- C++ -*-
+// copyright : Copyright (c) 2014-2016 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUTL_SMALL_VECTOR
+#define BUTL_SMALL_VECTOR
+
+#include <vector>
+#include <cassert>
+#include <cstddef> // size_t
+#include <utility> // more(), forward()
+
+namespace butl
+{
+  template <typename T, std::size_t N>
+  struct small_vector_buffer
+  {
+    // Size keeps track of the number of elements that are constructed in
+    // the buffer. Size equal N + 1 means the buffer is not allocated.
+    //
+    // Note that the names are decorated in order no to conflict with
+    // std::vector interface.
+    //
+    alignas (alignof (T)) char data_[sizeof (T) * N];
+    bool free_ = true;
+
+    // Note that the buffer should be constructed before std::vector and
+    // destroyed after (since std::vector's destructor will be destroying
+    // elements potentially residing in the buffer). This means that the
+    // buffer should be inherited from and before std::vector.
+    //
+    small_vector_buffer () = default;
+
+    small_vector_buffer (small_vector_buffer&&) = delete;
+    small_vector_buffer (const small_vector_buffer&) = delete;
+
+    small_vector_buffer& operator= (small_vector_buffer&&) = delete;
+    small_vector_buffer& operator= (const small_vector_buffer&) = delete;
+  };
+
+  template <typename T, std::size_t N>
+  class small_vector_allocator
+  {
+  public:
+    using buffer_type = small_vector_buffer<T, N>;
+
+    explicit
+    small_vector_allocator (buffer_type* b) noexcept: buf_ (b) {}
+
+    // Allocator interface.
+    //
+  public:
+    using value_type = T;
+
+    T*
+    allocate(std::size_t n)
+    {
+      if (n <= N)
+      {
+        assert (buf_->free_); // Why would we need another small buffer?
+        buf_->free_ = false;
+        return reinterpret_cast<T*> (buf_->data_);
+      }
+      else
+        return static_cast<T*> (::operator new (sizeof (T) * n));
+    }
+
+    void
+    deallocate (void* p, std::size_t) noexcept
+    {
+      if (p == buf_->data_)
+        buf_->free_ = true;
+      else
+        ::operator delete (p);
+    }
+
+    friend bool
+    operator== (small_vector_allocator x, small_vector_allocator y) noexcept
+    {
+      // We can use y to deallocate x's allocations if they use the same small
+      // buffer or neither uses its small buffer (which means all allocations,
+      // if any, have been from the shared heap). Of course this assumes no
+      // copy will be called to deallocate what has been allocated after said
+      // copy was made:
+      //
+      // A x;
+      // A y (x);
+      // p = x.allocate ();
+      // y.deallocate (p);  // Ouch.
+      //
+      return (x.buf_ == y.buf_) || (x.buf_->free_ && y.buf_->free_);
+    }
+
+    friend bool
+    operator!= (small_vector_allocator x, small_vector_allocator y) noexcept
+    {
+      return !(x == y);
+    }
+
+    // It might get instantiated but should not be called.
+    //
+    small_vector_allocator
+    select_on_container_copy_construction () const noexcept
+    {
+      return small_vector_allocator (nullptr);
+    }
+
+    // propagate_on_container_copy_assignment = false
+    // propagate_on_container_move_assignment = false
+    // propagate_on_container_swap = false
+
+    // Shouldn't be needed except to satisfy some static_assert's.
+    //
+    template <typename U>
+    struct rebind {using other = small_vector_allocator<U, N>;};
+
+  private:
+    buffer_type* buf_;
+  };
+
+  // Issues and limitations.
+  //
+  // - vector::reserve() may allocate more per the spec. But the three main
+  //   C++ runtimes (libstdc++, libc++, and msvc) all seem to do the right
+  //   thing.
+  //
+  // - What if in most cases the vector is empty? How can we avoid initial
+  //   reserve? Provide no_reserve flag or some such? Is it really worth it?
+  //
+  // - swap() is deleted (see notes below).
+  //
+  template <typename T, std::size_t N>
+  class small_vector: private small_vector_buffer<T, N>,
+                      public std::vector<T, small_vector_allocator<T, N>>
+  {
+  public:
+    using allocator_type = small_vector_allocator<T, N>;
+    using buffer_type = small_vector_buffer<T, N>;
+    using base_type = std::vector<T, small_vector_allocator<T, N>>;
+
+    small_vector ()
+      : base_type (allocator_type (this))
+    {
+      reserve ();
+    }
+
+    small_vector (std::initializer_list<T> v)
+      : base_type (allocator_type (this))
+    {
+      if (v.size () <= N)
+        reserve ();
+
+      static_cast<base_type&> (*this) = v;
+    }
+
+    template <typename I>
+    small_vector (I b, I e)
+      : base_type (allocator_type (this))
+    {
+      // While we could optimize this for random access iterators, N will
+      // usually be pretty small. Let's hope the compiler sees this and does
+      // some magic for us.
+      //
+      std::size_t n (0);
+      for (I i (b); i != e && n <= N; ++i) ++n;
+
+      if (n <= N)
+        reserve ();
+
+      this->assign (b, e);
+    }
+
+    explicit
+    small_vector (std::size_t n)
+      : base_type (allocator_type (this))
+    {
+      if (n <= N)
+        reserve ();
+
+      this->resize (n);
+    }
+
+    small_vector (std::size_t n, const T& x)
+      : base_type (allocator_type (this))
+    {
+      if (n <= N)
+        reserve ();
+
+      this->assign (n, x);
+    }
+
+    small_vector (const small_vector& v)
+      : buffer_type (), base_type (allocator_type (this))
+    {
+      if (v.size () <= N)
+        reserve ();
+
+      static_cast<base_type&> (*this) = v;
+    }
+
+    small_vector (small_vector&& v)
+      : base_type (allocator_type (this))
+    {
+      if (v.size () <= N)
+        reserve ();
+
+      static_cast<base_type&> (*this) = std::move (v);
+    }
+
+    small_vector&
+    operator= (const small_vector& v)
+    {
+      // Note: propagate_on_container_copy_assignment = false
+      //
+      static_cast<base_type&> (*this) = v;
+      return *this;
+    }
+
+    small_vector&
+    operator= (small_vector&& v)
+    {
+      // Note: propagate_on_container_move_assignment = false
+      //
+      static_cast<base_type&> (*this) = std::move (v);
+      return *this;
+    }
+
+    small_vector&
+    operator= (std::initializer_list<T> v)
+    {
+      static_cast<base_type&> (*this) = v;
+      return *this;
+    }
+
+    // Implementing swap() under small buffer optimization is not trivial, to
+    // say the least (think of swapping two such buffers of different sizes).
+    // One easy option would be to force both in to the heap.
+    //
+    void
+    swap (small_vector&) = delete;
+
+    void
+    reserve (std::size_t n = N)
+    {
+      base_type::reserve (n < N ? N : n);
+    }
+
+    void
+    shrink_to_fit ()
+    {
+      if (this->capacity () > N)
+        base_type::shrink_to_fit ();
+    }
+  };
+}
+
+#endif // BUTL_SMALL_VECTOR