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