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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
|
// file : libbutl/small-vector.hxx -*- C++ -*-
// license : MIT; see accompanying LICENSE file
#pragma once
#include <vector>
#include <cstddef> // size_t
#include <utility> // move()
#include <type_traits> // is_nothrow_move_constructible
#include <libbutl/small-allocator.hxx>
#include <libbutl/export.hxx>
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).
//
// - In contrast to std::vector, the references, pointers, and iterators
// referring to elements are invalidated after moving from it.
//
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;
}
// Note that while the move constructor is implemented via the move
// assignment it may not throw if the value type is no-throw move
// constructible.
//
// Specifically, if v.size() > N then allocators evaluate as equal and the
// buffer ownership is transferred. Otherwise, the allocators do not
// evaluate as equal and the individual elements are move-constructed in
// the preallocated buffer.
//
// Also note that this constructor ends up calling
// base_type::operator=(base_type&&) whose noexcept expression evaluates
// to false (propagate_on_container_move_assignment and is_always_equal
// are false for small_allocator; see std::vector documentation for
// details). We, however, assume that the noexcept expression we use here
// is strict enough for all "sane" std::vector implementations since
// small_allocator never throws directly.
//
small_vector (small_vector&& v)
noexcept (std::is_nothrow_move_constructible<T>::value)
: base_type (allocator_type (this))
{
if (v.size () <= N)
reserve ();
*this = std::move (v); // Delegate to operator=(&&).
// Note that in contrast to the move assignment operator, the
// constructor must clear the other vector.
//
v.clear ();
}
// Note that when size() <= N and v.size() > N, then allocators of this
// and other containers do not evaluate as equal. Thus, the memory for the
// new elements is allocated on the heap and so std::bad_alloc can be
// thrown. @@ TODO: maybe we could re-implement this case in terms of
// swap()?
//
small_vector&
operator= (small_vector&& v) noexcept (false)
{
// 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 ();
}
};
}
|
