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 // Reimplementation of c++20 std::identity.
17 struct identity {
18  template<typename T>
19  [[nodiscard]] constexpr T&& operator()(T&& t) const noexcept {
20  return std::forward<T>(t);
21  }
22 };
23 
24 
31 template<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 }
41 template<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 
47 template<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 }
57 template<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 
71 template<typename ITER, typename VAL, typename Proj = 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 }
77 template<typename RANGE, typename VAL, typename Proj = 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 
87 template<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 }
97 template<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 
108 template<typename RANGE, typename VAL, typename Proj = 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 
116 template<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 
133 template<typename VECTOR>
134 void 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 
168 template<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)) {
178 l_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 
187 template<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.
195 template<typename ForwardRange, typename UnaryOperation>
196 auto 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.
204 template<typename InputIterator, typename Proj = 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 
215 template<typename InputRange, typename Proj = 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.
223 template<typename InputIterator, typename Proj = 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 
234 template<typename InputRange, typename Proj = 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.
244 template<typename InputRange, typename Proj = 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
261 namespace 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());
274 template<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.
282 template<typename T>
283 [[nodiscard]] auto to_vector(std::vector<T>&& v)
284 {
285  return std::move(v);
286 }
287 
288 
289 // append() / concat()
290 namespace detail {
291 
292 template<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 
298 template<typename Result>
299 void append(Result&)
300 {
301  // nothing
302 }
303 
304 template<typename Result, typename Range, typename... Tail>
305 void 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));
325 template<typename Result, typename T2, typename... Tail>
326 void 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.
337 template<typename T, typename... Tail>
338 void 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.
352 template<typename T>
353 void 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 
364 template<typename T>
365 void append(std::vector<T>& x, std::initializer_list<T> list)
366 {
367  x.insert(x.end(), list);
368 }
369 
370 
371 template<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 
380 template<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).
389 template<typename T, size_t X, size_t Y>
390 constexpr 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
400 template<typename T, size_t X, size_t Y, size_t Z>
401 constexpr 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
414 template<typename Key, typename Value>
415 [[nodiscard]] const Value* lookup(const std::map<Key, Value>& m, const Key& k)
416 {
417  auto it = m.find(k);
418  return (it != m.end()) ? &it->second : nullptr;
419 }
420 
421 template<typename Key, typename Value>
422 [[nodiscard]] Value* lookup(std::map<Key, Value>& m, const Key& 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
429 template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
430 // explicit deduction guide (not needed as of C++20)
431 template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
432 
433 
434 // --- Utility to retrieve the index for a given type from a std::variant ---
435 
436 template<typename> struct get_index_tag {};
437 
438 template<typename T, typename V> struct get_index;
439 
440 template<typename T, typename... Ts>
441 struct 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 
448 template<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 
455 template<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
TclObject t
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
constexpr vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:269
constexpr vecN< N, T > max(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:287
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:118
Definition: ranges.hh:22
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:143
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
Definition: ranges.hh:191
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:72
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
const Value * lookup(const std::map< Key, Value > &m, const Key &k)
Definition: stl.hh:415
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
auto to_vector(Range &&range) -> std::vector< detail::ToVectorType< T, decltype(std::begin(range))>>
Definition: stl.hh:275
Definition: view_test.cc:239
Definition: stl.hh:17
constexpr T && operator()(T &&t) const noexcept
Definition: stl.hh:19
constexpr auto begin(const zstring_view &x)
Definition: zstring_view.hh:83
constexpr auto end(const zstring_view &x)
Definition: zstring_view.hh:84