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