openMSX
stl.hh
Go to the documentation of this file.
1#ifndef STL_HH
2#define STL_HH
3
4#include <algorithm>
5#include <cassert>
6#include <functional>
7#include <iterator>
8#include <initializer_list>
9#include <map>
10#include <numeric>
11#include <tuple>
12#include <utility>
13#include <variant>
14#include <vector>
15
22template<typename ITER, typename VAL>
23[[nodiscard]] constexpr bool contains(ITER first, ITER last, const VAL& val)
24{
25 // c++20: return std::find(first, last, val) != last;
26 while (first != last) {
27 if (*first == val) return true;
28 ++first;
29 }
30 return false;
31}
32template<typename RANGE, typename VAL>
33[[nodiscard]] constexpr bool contains(const RANGE& range, const VAL& val)
34{
35 return contains(std::begin(range), std::end(range), val);
36}
37
38template<typename ITER, typename VAL, typename Proj>
39[[nodiscard]] /*constexpr*/ bool contains(ITER first, ITER last, const VAL& val, Proj proj)
40{
41 // c++20: return std::find(first, last, val) != last;
42 while (first != last) {
43 if (std::invoke(proj, *first) == val) return true;
44 ++first;
45 }
46 return false;
47}
48template<typename RANGE, typename VAL, typename Proj>
49[[nodiscard]] /*constexpr*/ bool contains(const RANGE& range, const VAL& val, Proj proj)
50{
51 return contains(std::begin(range), std::end(range), val, proj);
52}
53
54
62template<typename ITER, typename VAL, typename Proj = std::identity>
63[[nodiscard]] /*constexpr*/ ITER find_unguarded(ITER first, ITER last, const VAL& val, Proj proj = {})
64{
65 return find_if_unguarded(first, last,
66 [&](const auto& e) { return std::invoke(proj, e) == val; });
67}
68template<typename RANGE, typename VAL, typename Proj = std::identity>
69[[nodiscard]] /*constexpr*/ auto find_unguarded(RANGE& range, const VAL& val, Proj proj = {})
70{
71 return find_unguarded(std::begin(range), std::end(range), val, proj);
72}
73
78template<typename ITER, typename PRED>
79[[nodiscard]] constexpr ITER find_if_unguarded(ITER first, ITER last, PRED pred)
80{
81 (void)last;
82 while (true) {
83 assert(first != last);
84 if (pred(*first)) return first;
85 ++first;
86 }
87}
88template<typename RANGE, typename PRED>
89[[nodiscard]] constexpr auto find_if_unguarded(RANGE& range, PRED pred)
90{
91 return find_if_unguarded(std::begin(range), std::end(range), pred);
92}
93
99template<typename RANGE, typename VAL, typename Proj = std::identity>
100[[nodiscard]] /*constexpr*/ auto rfind_unguarded(RANGE& range, const VAL& val, Proj proj = {})
101{
102 auto it = find_unguarded(std::rbegin(range), std::rend(range), val, proj);
103 ++it;
104 return it.base();
105}
106
107template<typename RANGE, typename PRED>
108[[nodiscard]] constexpr auto rfind_if_unguarded(RANGE& range, PRED pred)
109{
110 auto it = find_if_unguarded(std::rbegin(range), std::rend(range), pred);
111 ++it;
112 return it.base();
113}
114
115
124template<typename VECTOR>
125void move_pop_back(VECTOR& v, typename VECTOR::iterator it)
126{
127 // Check for self-move-assignment.
128 //
129 // This check is only needed in libstdc++ when compiled with
130 // -D_GLIBCXX_DEBUG. In non-debug mode this routine works perfectly
131 // fine without the check.
132 //
133 // See here for a related discussion:
134 // http://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor
135 // It's not clear whether the assert in libstdc++ is conforming
136 // behavior.
137 if (&*it != &v.back()) {
138 *it = std::move(v.back());
139 }
140 v.pop_back();
141}
142
143
159template<typename ForwardIt, typename OutputIt, typename UnaryPredicate>
160[[nodiscard]] std::pair<OutputIt, ForwardIt> partition_copy_remove(
161 ForwardIt first, ForwardIt last, OutputIt out_true, UnaryPredicate p)
162{
163 first = std::find_if(first, last, p);
164 auto out_false = first;
165 if (first != last) {
166 goto l_true;
167 while (first != last) {
168 if (p(*first)) {
169l_true: *out_true++ = std::move(*first++);
170 } else {
171 *out_false++ = std::move(*first++);
172 }
173 }
174 }
175 return std::pair(out_true, out_false);
176}
177
178template<typename ForwardRange, typename OutputIt, typename UnaryPredicate>
179[[nodiscard]] auto partition_copy_remove(ForwardRange&& range, OutputIt out_true, UnaryPredicate p)
180{
181 return partition_copy_remove(std::begin(range), std::end(range), out_true, p);
182}
183
184
185// Like range::transform(), but with equal source and destination.
186template<typename ForwardRange, typename UnaryOperation>
187auto transform_in_place(ForwardRange&& range, UnaryOperation op)
188{
189 return std::transform(std::begin(range), std::end(range), std::begin(range), op);
190}
191
192
193// Returns (a copy of) the minimum value in [first, last).
194// Requires: first != last.
195template<typename InputIterator, typename Proj = std::identity>
196[[nodiscard]] /*constexpr*/ auto min_value(InputIterator first, InputIterator last, Proj proj = {})
197{
198 assert(first != last);
199 auto result = std::invoke(proj, *first++);
200 while (first != last) {
201 result = std::min(result, std::invoke(proj, *first++));
202 }
203 return result;
204}
205
206template<typename InputRange, typename Proj = std::identity>
207[[nodiscard]] /*constexpr*/ auto min_value(InputRange&& range, Proj proj = {})
208{
209 return min_value(std::begin(range), std::end(range), proj);
210}
211
212// Returns (a copy of) the maximum value in [first, last).
213// Requires: first != last.
214template<typename InputIterator, typename Proj = std::identity>
215[[nodiscard]] /*constexpr*/ auto max_value(InputIterator first, InputIterator last, Proj proj = {})
216{
217 assert(first != last);
218 auto result = std::invoke(proj, *first++);
219 while (first != last) {
220 result = std::max(result, std::invoke(proj, *first++));
221 }
222 return result;
223}
224
225template<typename InputRange, typename Proj = std::identity>
226[[nodiscard]] /*constexpr*/ auto max_value(InputRange&& range, Proj proj = {})
227{
228 return max_value(std::begin(range), std::end(range), proj);
229}
230
231
232// Returns the sum of the elements in the given range.
233// Assumes: elements can be summed via operator+, with a default constructed
234// value being the identity-element for this operator.
235template<typename InputRange, typename Proj = std::identity>
236[[nodiscard]] /*constexpr*/ auto sum(InputRange&& range, Proj proj = {})
237{
238 using Iter = decltype(std::begin(range));
239 using VT = typename std::iterator_traits<Iter>::value_type;
240 using RT = decltype(std::invoke(proj, std::declval<VT>()));
241
242 auto first = std::begin(range);
243 auto last = std::end(range);
244 RT init{};
245 while (first != last) {
246 init = std::move(init) + std::invoke(proj, *first++);
247 }
248 return init;
249}
250
251// to_vector
252namespace detail {
253 template<typename T, typename Iterator>
254 using ToVectorType = std::conditional_t<
255 std::is_same_v<T, void>,
256 typename std::iterator_traits<Iterator>::value_type,
257 T>;
258}
259
260// Convert any range to a vector. Optionally specify the type of the elements
261// in the result.
262// Example:
263// auto v1 = to_vector(view::drop(my_list, 3));
264// auto v2 = to_vector<Base*>(getDerivedPtrs());
265template<typename T = void, typename Range>
266[[nodiscard]] auto to_vector(Range&& range)
267 -> std::vector<detail::ToVectorType<T, decltype(std::begin(range))>>
268{
269 return {std::begin(range), std::end(range)};
270}
271
272// Optimized version for r-value input and no type conversion.
273template<typename T>
274[[nodiscard]] auto to_vector(std::vector<T>&& v)
275{
276 return std::move(v);
277}
278
279
280// append() / concat()
281namespace detail {
282
283template<typename... Ranges>
284[[nodiscard]] constexpr size_t sum_of_sizes(const Ranges&... ranges)
285{
286 return (0 + ... + std::distance(std::begin(ranges), std::end(ranges)));
287}
288
289template<typename Result>
290void append(Result&)
291{
292 // nothing
293}
294
295template<typename Result, typename Range, typename... Tail>
296void append(Result& x, Range&& y, Tail&&... tail)
297{
298#ifdef _GLIBCXX_DEBUG
299 // Range can be a view::transform
300 // but vector::insert in libstdc++ debug mode will wrongly try
301 // to take its address to check for self-insertion (see
302 // gcc/include/c++/7.1.0/debug/functions.h
303 // __foreign_iterator_aux functions). So avoid vector::insert
304 for (auto&& e : y) {
305 x.emplace_back(std::forward<decltype(e)>(e));
306 }
307#else
308 x.insert(std::end(x), std::begin(y), std::end(y));
309#endif
310 detail::append(x, std::forward<Tail>(tail)...);
311}
312
313// Allow move from an rvalue-vector.
314// But don't allow to move from any rvalue-range. It breaks stuff like
315// append(v, view::reverse(w));
316template<typename Result, typename T2, typename... Tail>
317void append(Result& x, std::vector<T2>&& y, Tail&&... tail)
318{
319 x.insert(std::end(x),
320 std::move_iterator(std::begin(y)),
321 std::move_iterator(std::end(y)));
322 detail::append(x, std::forward<Tail>(tail)...);
323}
324
325} // namespace detail
326
327// Append a range to a vector.
328template<typename T, typename... Tail>
329void append(std::vector<T>& v, Tail&&... tail)
330{
331 auto extra = detail::sum_of_sizes(std::forward<Tail>(tail)...);
332 auto current = v.size();
333 auto required = current + extra;
334 if (v.capacity() < required) {
335 v.reserve(current + std::max(current, extra));
336 }
337 detail::append(v, std::forward<Tail>(tail)...);
338}
339
340// If both source and destination are vectors of the same type and the
341// destination is empty and the source is an rvalue, then move the whole vector
342// at once instead of moving element by element.
343template<typename T>
344void append(std::vector<T>& v, std::vector<T>&& range)
345{
346 if (v.empty()) {
347 v = std::move(range);
348 } else {
349 v.insert(std::end(v),
350 std::move_iterator(std::begin(range)),
351 std::move_iterator(std::end(range)));
352 }
353}
354
355template<typename T>
356void append(std::vector<T>& x, std::initializer_list<T> list)
357{
358 x.insert(x.end(), list);
359}
360
361
362template<typename T = void, typename Range, typename... Tail>
363[[nodiscard]] auto concat(const Range& range, Tail&&... tail)
364{
365 using T2 = detail::ToVectorType<T, decltype(std::begin(range))>;
366 std::vector<T2> result;
367 append(result, range, std::forward<Tail>(tail)...);
368 return result;
369}
370
371template<typename T, typename... Tail>
372[[nodiscard]] std::vector<T> concat(std::vector<T>&& v, Tail&&... tail)
373{
374 append(v, std::forward<Tail>(tail)...);
375 return std::move(v);
376}
377
378
379// Concatenate two std::arrays (at compile time).
380template<typename T, size_t X, size_t Y>
381constexpr auto concatArray(const std::array<T, X>& x, const std::array<T, Y>& y)
382{
383 std::array<T, X + Y> result = {};
384 // c++20: std::ranges::copy(x, &result[0]);
385 // c++20: std::ranges::copy(y, &result[X]);
386 for (size_t i = 0; i < X; ++i) result[0 + i] = x[i];
387 for (size_t i = 0; i < Y; ++i) result[X + i] = y[i];
388 return result;
389}
390// TODO implement in a generic way for any number of arrays
391template<typename T, size_t X, size_t Y, size_t Z>
392constexpr auto concatArray(const std::array<T, X>& x,
393 const std::array<T, Y>& y,
394 const std::array<T, Z>& z)
395{
396 std::array<T, X + Y + Z> result = {};
397 for (size_t i = 0; i < X; ++i) result[ i] = x[i];
398 for (size_t i = 0; i < Y; ++i) result[X + i] = y[i];
399 for (size_t i = 0; i < Z; ++i) result[X + Y + i] = z[i];
400 return result;
401}
402
403
404// lookup in std::map
405template<typename Key, typename Value>
406[[nodiscard]] const Value* lookup(const std::map<Key, Value>& m, const Key& k)
407{
408 auto it = m.find(k);
409 return (it != m.end()) ? &it->second : nullptr;
410}
411
412template<typename Key, typename Value>
413[[nodiscard]] Value* lookup(std::map<Key, Value>& m, const Key& k)
414{
415 auto it = m.find(k);
416 return (it != m.end()) ? &it->second : nullptr;
417}
418
419// will likely become part of future c++ standard
420template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
421// explicit deduction guide (not needed as of C++20)
422template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
423
424
425// --- Utility to retrieve the index for a given type from a std::variant ---
426
427template<typename> struct get_index_tag {};
428
429template<typename T, typename V> struct get_index;
430
431template<typename T, typename... Ts>
432struct get_index<T, std::variant<Ts...>>
433 : std::integral_constant<size_t, std::variant<get_index_tag<Ts>...>(get_index_tag<T>()).index()> {};
434
435
436// Utility to initialize an array via a generator function,
437// without first default constructing the elements.
438
439template<typename T, typename F, size_t... Is>
440[[nodiscard]] static constexpr auto generate_array(F f, std::index_sequence<Is...>)
441 -> std::array<T, sizeof...(Is)>
442{
443 return {{f(Is)...}};
444}
445
446template<size_t N, typename F>
447[[nodiscard]] static constexpr auto generate_array(F f)
448{
449 using T = decltype(f(0));
450 return generate_array<T>(f, std::make_index_sequence<N>{});
451}
452
453#endif
constexpr double e
Definition: Math.hh:21
Definition: join.hh:10
void append(Result &)
Definition: stl.hh:290
std::conditional_t< std::is_same_v< T, void >, typename std::iterator_traits< Iterator >::value_type, T > ToVectorType
Definition: stl.hh:257
constexpr size_t sum_of_sizes(const Ranges &... ranges)
Definition: stl.hh:284
constexpr vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:267
constexpr vecN< N, T > max(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:285
Definition: ranges.hh:24
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:173
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
Definition: ranges.hh:251
STL namespace.
auto distance(octet_iterator first, octet_iterator last)
overloaded(Ts...) -> overloaded< Ts... >
ITER find_unguarded(ITER first, ITER last, const VAL &val, Proj proj={})
Faster alternative to 'find' when it's guaranteed that the value will be found (if not the behavior i...
Definition: stl.hh:63
const Value * lookup(const std::map< Key, Value > &m, const Key &k)
Definition: stl.hh:406
auto to_vector(Range &&range) -> std::vector< detail::ToVectorType< T, decltype(std::begin(range))> >
Definition: stl.hh:266
std::pair< OutputIt, ForwardIt > partition_copy_remove(ForwardIt first, ForwardIt last, OutputIt out_true, UnaryPredicate p)
This is like a combination of partition_copy() and remove().
Definition: stl.hh:160
constexpr ITER find_if_unguarded(ITER first, ITER last, PRED pred)
Faster alternative to 'find_if' when it's guaranteed that the predicate will be true for at least one...
Definition: stl.hh:79
auto min_value(InputIterator first, InputIterator last, Proj proj={})
Definition: stl.hh:196
void append(std::vector< T > &v, Tail &&... tail)
Definition: stl.hh:329
auto max_value(InputIterator first, InputIterator last, Proj proj={})
Definition: stl.hh:215
constexpr auto concatArray(const std::array< T, X > &x, const std::array< T, Y > &y)
Definition: stl.hh:381
auto transform_in_place(ForwardRange &&range, UnaryOperation op)
Definition: stl.hh:187
auto sum(InputRange &&range, Proj proj={})
Definition: stl.hh:236
void move_pop_back(VECTOR &v, typename VECTOR::iterator it)
Erase the pointed to element from the given vector.
Definition: stl.hh:125
auto rfind_unguarded(RANGE &range, const VAL &val, Proj proj={})
Similar to the find(_if)_unguarded functions above, but searches from the back to front.
Definition: stl.hh:100
auto concat(const Range &range, Tail &&... tail)
Definition: stl.hh:363
constexpr bool contains(ITER first, ITER last, const VAL &val)
Check if a range contains a given value, using linear search.
Definition: stl.hh:23
constexpr auto rfind_if_unguarded(RANGE &range, PRED pred)
Definition: stl.hh:108
Definition: view_test.cc:239
constexpr auto begin(const zstring_view &x)
constexpr auto end(const zstring_view &x)