1// Copyright (C) 2019 T. Zachary Laine
2//
3// Distributed under the Boost Software License, Version 1.0. (See
4// accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6#include <boost/stl_interfaces/sequence_container_interface.hpp>
7
8#include <algorithm>
9#include <iterator>
10#include <memory>
11#include <tuple>
12
13#include <cassert>
14
15
16// There's a test that uses this example header; this controls whether the
17// C++14 version (v1::) of sequence_container_interface gets used, or the
18// C++20 version (v2::).
19#if defined(USE_V2)
20template<typename Derived, boost::stl_interfaces::element_layout Contiguity>
21using sequence_container_interface =
22 boost::stl_interfaces::v2::sequence_container_interface<Derived>;
23#else
24template<typename Derived, boost::stl_interfaces::element_layout Contiguity>
25using sequence_container_interface =
26 boost::stl_interfaces::v1::sequence_container_interface<Derived, Contiguity>;
27#endif
28
29
30//[ static_vector_defn
31// The sections of member functions below are commented as they are in the
32// standard for std::vector. Each section has two numbers: the number of
33// member functions in that section, and the number that are missing, because
34// they are provided by sequence_container_interface. The purely
35// allocator-specific members are neither present nor part of the counts.
36//
37// We're passing boost::stl_interfaces::contiguous here, so that
38// sequence_container_interface knows that it should provide data().
39template<typename T, std::size_t N>
40struct static_vector : sequence_container_interface<
41 static_vector<T, N>,
42 boost::stl_interfaces::element_layout::contiguous>
43{
44 // These are the types required for reversible containers. These must be
45 // user-defined.
46 using value_type = T;
47 using pointer = T *;
48 using const_pointer = T const *;
49 using reference = value_type &;
50 using const_reference = value_type const &;
51 using size_type = std::size_t;
52 using difference_type = std::ptrdiff_t;
53 using iterator = T *;
54 using const_iterator = T const *;
55 using reverse_iterator = boost::stl_interfaces::reverse_iterator<iterator>;
56 using const_reverse_iterator =
57 boost::stl_interfaces::reverse_iterator<const_iterator>;
58
59 // construct/copy/destroy (9 members, skipped 2)
60 //
61 // Constructors and special member functions all must be user-provided.
62 // Were they provided by sequence_container_interface, everything would
63 // break, due to the language rules related to them. However, assignment
64 // from std::initializer_list can come from sequence_container_interface.
65 static_vector() noexcept : size_(0) {}
66 explicit static_vector(size_type n) : size_(0) { resize(n); }
67 explicit static_vector(size_type n, T const & x) : size_(0)
68 {
69 // Note that you must write "this->" before all the member functions
70 // provided by sequence_container_interface, which is slightly annoying.
71 this->assign(n, x);
72 }
73 template<
74 typename InputIterator,
75 typename Enable = std::enable_if_t<std::is_convertible<
76 typename std::iterator_traits<InputIterator>::iterator_category,
77 std::input_iterator_tag>::value>>
78 static_vector(InputIterator first, InputIterator last) : size_(0)
79 {
80 this->assign(first, last);
81 }
82 static_vector(std::initializer_list<T> il) :
83 static_vector(il.begin(), il.end())
84 {}
85 static_vector(static_vector const & other) : size_(0)
86 {
87 this->assign(other.begin(), other.end());
88 }
89 static_vector(static_vector && other) noexcept(
90 noexcept(std::declval<static_vector>().emplace_back(
91 std::move(*other.begin())))) :
92 size_(0)
93 {
94 for (auto & element : other) {
95 emplace_back(std::move(element));
96 }
97 other.clear();
98 }
99 static_vector & operator=(static_vector const & other)
100 {
101 this->clear();
102 this->assign(other.begin(), other.end());
103 return *this;
104 }
105 static_vector & operator=(static_vector && other) noexcept(noexcept(
106 std::declval<static_vector>().emplace_back(std::move(*other.begin()))))
107 {
108 this->clear();
109 for (auto & element : other) {
110 emplace_back(std::move(element));
111 }
112 other.clear();
113 return *this;
114 }
115 ~static_vector() { this->clear(); }
116
117 // iterators (2 members, skipped 10)
118 //
119 // This section is the first big win. Instead of having to write 12
120 // overloads line begin, cbegin, rbegin, crbegin, etc., we can just write
121 // 2.
122 iterator begin() noexcept { return reinterpret_cast<T *>(buf_); }
123 iterator end() noexcept
124 {
125 return reinterpret_cast<T *>(buf_ + size_ * sizeof(T));
126 }
127
128 // capacity (6 members, skipped 2)
129 //
130 // Most of these are not even part of the general requirements, because
131 // some are specific to std::vector and related types. However, we do get
132 // empty and size from sequence_container_interface.
133 size_type max_size() const noexcept { return N; }
134 size_type capacity() const noexcept { return N; }
135 void resize(size_type sz) noexcept
136 {
137 resize_impl(sz, [] { return T(); });
138 }
139 void resize(size_type sz, T const & x) noexcept
140 {
141 resize_impl(sz, [&]() -> T const & { return x; });
142 }
143 void reserve(size_type n) noexcept { assert(n < capacity()); }
144 void shrink_to_fit() noexcept {}
145
146 // element access (skipped 8)
147 // data access (skipped 2)
148 //
149 // Another big win. sequence_container_interface provides all of the
150 // overloads of operator[], at, front, back, and data.
151
152 // modifiers (5 members, skipped 9)
153 //
154 // In this section we again get most of the API from
155 // sequence_container_interface.
156
157 // emplace_back does not look very necessary -- just look at its trivial
158 // implementation -- but we can't provide it from
159 // sequence_container_interface, because it is an optional sequence
160 // container interface. We would not want emplace_front to suddenly
161 // appear on our std::vector-like type, and there may be some other type
162 // for which emplace_back is a bad idea.
163 //
164 // However, by providing emplace_back here, we signal to the
165 // sequence_container_interface template that our container is
166 // back-mutation-friendly, and this allows it to provide all the overloads
167 // of push_back and pop_back.
168 template<typename... Args>
169 reference emplace_back(Args &&... args)
170 {
171 return *emplace(end(), std::forward<Args>(args)...);
172 }
173 template<typename... Args>
174 iterator emplace(const_iterator pos, Args &&... args)
175 {
176 auto position = const_cast<T *>(pos);
177 bool const insert_before_end = position < end();
178 if (insert_before_end) {
179 auto last = end();
180 emplace_back(std::move(this->back()));
181 std::move_backward(position, last - 1, last);
182 }
183 new (position) T(std::forward<Args>(args)...);
184 if (!insert_before_end)
185 ++size_;
186 return position;
187 }
188 // Note: The iterator category here was upgraded to ForwardIterator
189 // (instead of vector's InputIterator), to ensure linear time complexity.
190 template<
191 typename ForwardIterator,
192 typename Enable = std::enable_if_t<std::is_convertible<
193 typename std::iterator_traits<ForwardIterator>::iterator_category,
194 std::forward_iterator_tag>::value>>
195 iterator
196 insert(const_iterator pos, ForwardIterator first, ForwardIterator last)
197 {
198 auto position = const_cast<T *>(pos);
199 auto const insertions = std::distance(first, last);
200 assert(this->size() + insertions < capacity());
201 uninitialized_generate(end(), end() + insertions, [] { return T(); });
202 std::move_backward(position, end(), end() + insertions);
203 std::copy(first, last, position);
204 size_ += insertions;
205 return position;
206 }
207 iterator erase(const_iterator f, const_iterator l)
208 {
209 auto first = const_cast<T *>(f);
210 auto last = const_cast<T *>(l);
211 auto end_ = this->end();
212 auto it = std::move(last, end_, first);
213 for (; it != end_; ++it) {
214 it->~T();
215 }
216 size_ -= last - first;
217 return first;
218 }
219 void swap(static_vector & other)
220 {
221 size_type short_size, long_size;
222 std::tie(args&: short_size, args&: long_size) =
223 std::minmax(this->size(), other.size());
224 for (auto i = size_type(0); i < short_size; ++i) {
225 using std::swap;
226 swap((*this)[i], other[i]);
227 }
228
229 static_vector * longer = this;
230 static_vector * shorter = this;
231 if (this->size() < other.size())
232 longer = &other;
233 else
234 shorter = &other;
235
236 for (auto it = longer->begin() + short_size, last = longer->end();
237 it != last;
238 ++it) {
239 shorter->emplace_back(std::move(*it));
240 }
241
242 longer->resize(short_size);
243 shorter->size_ = long_size;
244 }
245
246 // Since we're getting so many overloads from
247 // sequence_container_interface, and since many of those overloads are
248 // implemented in terms of a user-defined function of the same name, we
249 // need to add quite a few using declarations here.
250 using base_type = sequence_container_interface<
251 static_vector<T, N>,
252 boost::stl_interfaces::element_layout::contiguous>;
253 using base_type::begin;
254 using base_type::end;
255 using base_type::insert;
256 using base_type::erase;
257
258 // comparisons (skipped 6)
259
260private:
261 template<typename F>
262 static void uninitialized_generate(iterator f, iterator l, F func)
263 {
264 for (; f != l; ++f) {
265 new (static_cast<void *>(std::addressof(*f))) T(func());
266 }
267 }
268 template<typename F>
269 void resize_impl(size_type sz, F func) noexcept
270 {
271 assert(sz < capacity());
272 if (sz < this->size())
273 erase(begin() + sz, end());
274 if (this->size() < sz)
275 uninitialized_generate(end(), begin() + sz, func);
276 size_ = sz;
277 }
278
279 alignas(T) unsigned char buf_[N * sizeof(T)];
280 size_type size_;
281};
282//]
283

source code of boost/libs/stl_interfaces/example/static_vector.hpp