aboutsummaryrefslogtreecommitdiff
path: root/libbutl/small-vector.mxx
blob: 2a921825f6955ae8b24fc0fbfdaa7220bd1474ae (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
// file      : libbutl/small-vector.mxx -*- C++ -*-
// license   : MIT; see accompanying LICENSE file

#ifndef __cpp_modules_ts
#pragma once
#endif

#ifndef __cpp_lib_modules_ts
#include <vector>
#include <cstddef>     // size_t
#include <utility>     // move()
#endif

// Other includes.

#ifdef __cpp_modules_ts
export module butl.small_vector;
#ifdef __cpp_lib_modules_ts
import std.core;
#endif
import butl.small_allocator;
#else
#include <libbutl/small-allocator.mxx>
#endif

#include <libbutl/export.hxx>

LIBBUTL_MODEXPORT namespace butl
{
  // 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_allocator_buffer<T, N>,
                      public std::vector<T, small_allocator<T, N>>
  {
  public:
    static constexpr const std::size_t small_size = N;

    using buffer_type = small_allocator_buffer<T, N>;
    using allocator_type = small_allocator<T, N>;
    using base_type = std::vector<T, allocator_type>;

    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&
    operator= (const small_vector& v)
    {
      // Note: propagate_on_container_copy_assignment = false
      //
      static_cast<base_type&> (*this) = v;
      return *this;
    }

    small_vector (small_vector&& v)
      : base_type (allocator_type (this))
    {
      if (v.size () <= N)
        reserve ();

      *this = std::move (v); // Delegate to operator=(&&).
    }

    small_vector&
    operator= (small_vector&& v)
    {
      // VC's implementation of operator=(&&) (both 14 and 15) frees the
      // memory and then reallocated with capacity equal to v.size(). This is
      // clearly sub-optimal (the existing buffer could be reused) so we hope
      // this will be fixed eventually (VSO#367146; reportedly fixed for
      // VC15U1).
      //
#if defined(_MSC_VER) && _MSC_VER <= 1910
      if (v.size () <= N)
      {
        clear ();
        for (T& x: v)
          push_back (std::move (x));
        v.clear ();
      }
      else
#endif

      // 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 ();
    }
  };
}