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 // Dereference the two given (pointer-like) parameters and then compare
15 // them with the less-than operator.
16 struct LessDeref
17 {
18  template<typename PTR>
19  [[nodiscard]] bool operator()(PTR p1, PTR p2) const { return *p1 < *p2; }
20 };
21 
22 
23 // Compare the N-th element of two tuples using a custom comparison functor.
24 // Also provides overloads to compare the N-the element of a tuple with a
25 // single value (of a compatible type).
26 // ATM the functor cannot take constructor arguments, possibly refactor this in
27 // the future.
28 template<int N, typename CMP> struct CmpTupleElement
29 {
30  template<typename... Args>
31  [[nodiscard]] bool operator()(const std::tuple<Args...>& x, const std::tuple<Args...>& y) const {
32  return cmp(std::get<N>(x), std::get<N>(y));
33  }
34 
35  template<typename T, typename... Args>
36  [[nodiscard]] bool operator()(const T& x, const std::tuple<Args...>& y) const {
37  return cmp(x, std::get<N>(y));
38  }
39 
40  template<typename T, typename... Args>
41  [[nodiscard]] bool operator()(const std::tuple<Args...>& x, const T& y) const {
42  return cmp(std::get<N>(x), y);
43  }
44 
45  template<typename T1, typename T2>
46  [[nodiscard]] bool operator()(const std::pair<T1, T2>& x, const std::pair<T1, T2>& y) const {
47  return cmp(std::get<N>(x), std::get<N>(y));
48  }
49 
50  template<typename T, typename T1, typename T2>
51  [[nodiscard]] bool operator()(const T& x, const std::pair<T1, T2>& y) const {
52  return cmp(x, std::get<N>(y));
53  }
54 
55  template<typename T, typename T1, typename T2>
56  [[nodiscard]] bool operator()(const std::pair<T1, T2>& x, const T& y) const {
57  return cmp(std::get<N>(x), y);
58  }
59 
60 private:
61  CMP cmp;
62 };
63 
64 // Similar to CmpTupleElement above, but uses the less-than operator.
66 
67 
68 // Check whether the N-the element of a tuple is equal to the given value.
69 template<int N, typename T> struct EqualTupleValueImpl
70 {
71  explicit EqualTupleValueImpl(const T& t_) : t(t_) {}
72  template<typename TUPLE>
73  [[nodiscard]] bool operator()(const TUPLE& tup) const {
74  return std::get<N>(tup) == t;
75  }
76 private:
77  const T& t;
78 };
79 template<int N, typename T>
80 [[nodiscard]] auto EqualTupleValue(const T& t) {
82 }
83 
84 
91 template<typename ITER, typename VAL>
92 [[nodiscard]] inline bool contains(ITER first, ITER last, const VAL& val)
93 {
94  return std::find(first, last, val) != last;
95 }
96 template<typename RANGE, typename VAL>
97 [[nodiscard]] inline bool contains(const RANGE& range, const VAL& val)
98 {
99  return contains(std::begin(range), std::end(range), val);
100 }
101 
102 
110 template<typename ITER, typename VAL>
111 [[nodiscard]] inline ITER find_unguarded(ITER first, ITER last, const VAL& val)
112 {
113  (void)last;
114  while (true) {
115  assert(first != last);
116  if (*first == val) return first;
117  ++first;
118  }
119 }
120 template<typename RANGE, typename VAL>
121 [[nodiscard]] inline auto find_unguarded(RANGE& range, const VAL& val)
122 {
123  return find_unguarded(std::begin(range), std::end(range), val);
124 }
125 
130 template<typename ITER, typename PRED>
131 [[nodiscard]] inline ITER find_if_unguarded(ITER first, ITER last, PRED pred)
132 {
133  (void)last;
134  while (true) {
135  assert(first != last);
136  if (pred(*first)) return first;
137  ++first;
138  }
139 }
140 template<typename RANGE, typename PRED>
141 [[nodiscard]] inline auto find_if_unguarded(RANGE& range, PRED pred)
142 {
143  return find_if_unguarded(std::begin(range), std::end(range), pred);
144 }
145 
151 template<typename RANGE, typename VAL>
152 [[nodiscard]] inline auto rfind_unguarded(RANGE& range, const VAL& val)
153 {
154  auto it = find_unguarded(std::rbegin(range), std::rend(range), val);
155  ++it;
156  return it.base();
157 }
158 
159 template<typename RANGE, typename PRED>
160 [[nodiscard]] inline auto rfind_if_unguarded(RANGE& range, PRED pred)
161 {
162  auto it = find_if_unguarded(std::rbegin(range), std::rend(range), pred);
163  ++it;
164  return it.base();
165 }
166 
167 
176 template<typename VECTOR>
177 void move_pop_back(VECTOR& v, typename VECTOR::iterator it)
178 {
179  // Check for self-move-assignment.
180  //
181  // This check is only needed in libstdc++ when compiled with
182  // -D_GLIBCXX_DEBUG. In non-debug mode this routine works perfectly
183  // fine without the check.
184  //
185  // See here for a related discussion:
186  // http://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor
187  // It's not clear whether the assert in libstdc++ is conforming
188  // behavior.
189  if (&*it != &v.back()) {
190  *it = std::move(v.back());
191  }
192  v.pop_back();
193 }
194 
195 
211 template<typename ForwardIt, typename OutputIt, typename UnaryPredicate>
212 [[nodiscard]] std::pair<OutputIt, ForwardIt> partition_copy_remove(
213  ForwardIt first, ForwardIt last, OutputIt out_true, UnaryPredicate p)
214 {
215  first = std::find_if(first, last, p);
216  auto out_false = first;
217  if (first != last) {
218  goto l_true;
219  while (first != last) {
220  if (p(*first)) {
221 l_true: *out_true++ = std::move(*first++);
222  } else {
223  *out_false++ = std::move(*first++);
224  }
225  }
226  }
227  return std::pair(out_true, out_false);
228 }
229 
230 template<typename ForwardRange, typename OutputIt, typename UnaryPredicate>
231 [[nodiscard]] auto partition_copy_remove(ForwardRange&& range, OutputIt out_true, UnaryPredicate p)
232 {
233  return partition_copy_remove(std::begin(range), std::end(range), out_true, p);
234 }
235 
236 
237 // Like range::transform(), but with equal source and destination.
238 template<typename ForwardRange, typename UnaryOperation>
239 auto transform_in_place(ForwardRange&& range, UnaryOperation op)
240 {
241  return std::transform(std::begin(range), std::end(range), std::begin(range), op);
242 }
243 
244 
245 // Returns (a copy of) the minimum value in [first, last).
246 // Requires: first != last.
247 template<typename InputIterator>
248 [[nodiscard]] auto min_value(InputIterator first, InputIterator last)
249 {
250  assert(first != last);
251  auto result = *first++;
252  while (first != last) {
253  result = std::min(result, *first++);
254  }
255  return result;
256 }
257 
258 template<typename InputRange>
259 [[nodiscard]] auto min_value(InputRange&& range)
260 {
261  return min_value(std::begin(range), std::end(range));
262 }
263 
264 // Returns (a copy of) the maximum value in [first, last).
265 // Requires: first != last.
266 template<typename InputIterator>
267 [[nodiscard]] auto max_value(InputIterator first, InputIterator last)
268 {
269  assert(first != last);
270  auto result = *first++;
271  while (first != last) {
272  result = std::max(result, *first++);
273  }
274  return result;
275 }
276 
277 template<typename InputRange>
278 [[nodiscard]] auto max_value(InputRange&& range)
279 {
280  return max_value(std::begin(range), std::end(range));
281 }
282 
283 
284 // Returns the sum of the elements in the given range.
285 // Assumes: elements can be summed via operator+, with a default constructed
286 // value being the identity-element for this operator.
287 template<typename InputRange>
288 [[nodiscard]] auto sum(InputRange&& range)
289 {
290  using Iter = decltype(std::begin(range));
291  using T = typename std::iterator_traits<Iter>::value_type;
292  return std::accumulate(std::begin(range), std::end(range), T());
293 }
294 
295 
296 // to_vector
297 namespace detail {
298  template<typename T, typename Iterator>
299  using ToVectorType = std::conditional_t<
300  std::is_same_v<T, void>,
301  typename std::iterator_traits<Iterator>::value_type,
302  T>;
303 }
304 
305 // Convert any range to a vector. Optionally specify the type of the elements
306 // in the result.
307 // Example:
308 // auto v1 = to_vector(view::drop(my_list, 3));
309 // auto v2 = to_vector<Base*>(getDerivedPtrs());
310 template<typename T = void, typename Range>
311 [[nodiscard]] auto to_vector(Range&& range)
312  -> std::vector<detail::ToVectorType<T, decltype(std::begin(range))>>
313 {
314  return {std::begin(range), std::end(range)};
315 }
316 
317 // Optimized version for r-value input and no type conversion.
318 template<typename T>
319 [[nodiscard]] auto to_vector(std::vector<T>&& v)
320 {
321  return std::move(v);
322 }
323 
324 
325 // append() / concat()
326 namespace detail {
327 
328 [[nodiscard]] inline size_t sum_of_sizes()
329 {
330  return 0;
331 }
332 template<typename Range, typename... Tail>
333 [[nodiscard]] size_t sum_of_sizes(const Range& r, Tail&&... tail)
334 {
335  return std::distance(std::begin(r), std::end(r)) +
336  sum_of_sizes(std::forward<Tail>(tail)...);
337 }
338 
339 template<typename Result>
340 void append(Result&)
341 {
342  // nothing
343 }
344 
345 template<typename Result, typename Range, typename... Tail>
346 void append(Result& x, Range&& y, Tail&&... tail)
347 {
348 #ifdef _GLIBCXX_DEBUG
349  // Range can be a view::transform
350  // but vector::insert in libstdc++ debug mode will wrongly try
351  // to take its address to check for self-insertion (see
352  // gcc/include/c++/7.1.0/debug/functions.h
353  // __foreign_iterator_aux functions). So avoid vector::insert
354  for (auto&& e : y) {
355  x.emplace_back(std::forward<decltype(e)>(e));
356  }
357 #else
358  x.insert(std::end(x), std::begin(y), std::end(y));
359 #endif
360  detail::append(x, std::forward<Tail>(tail)...);
361 }
362 
363 // Allow move from an rvalue-vector.
364 // But don't allow to move from any rvalue-range. It breaks stuff like
365 // append(v, view::reverse(w));
366 template<typename Result, typename T2, typename... Tail>
367 void append(Result& x, std::vector<T2>&& y, Tail&&... tail)
368 {
369  x.insert(std::end(x),
370  std::move_iterator(std::begin(y)),
371  std::move_iterator(std::end(y)));
372  detail::append(x, std::forward<Tail>(tail)...);
373 }
374 
375 } // namespace detail
376 
377 // Append a range to a vector.
378 template<typename T, typename... Tail>
379 void append(std::vector<T>& v, Tail&&... tail)
380 {
381  auto extra = detail::sum_of_sizes(std::forward<Tail>(tail)...);
382  auto current = v.size();
383  auto required = current + extra;
384  if (v.capacity() < required) {
385  v.reserve(current + std::max(current, extra));
386  }
387  detail::append(v, std::forward<Tail>(tail)...);
388 }
389 
390 // If both source and destination are vectors of the same type and the
391 // destination is empty and the source is an rvalue, then move the whole vector
392 // at once instead of moving element by element.
393 template<typename T>
394 void append(std::vector<T>& v, std::vector<T>&& range)
395 {
396  if (v.empty()) {
397  v = std::move(range);
398  } else {
399  v.insert(std::end(v),
400  std::move_iterator(std::begin(range)),
401  std::move_iterator(std::end(range)));
402  }
403 }
404 
405 template<typename T>
406 void append(std::vector<T>& x, std::initializer_list<T> list)
407 {
408  x.insert(x.end(), list);
409 }
410 
411 
412 template<typename T = void, typename Range, typename... Tail>
413 [[nodiscard]] auto concat(const Range& range, Tail&&... tail)
414 {
416  std::vector<T2> result;
417  append(result, range, std::forward<Tail>(tail)...);
418  return result;
419 }
420 
421 template<typename T, typename... Tail>
422 [[nodiscard]] std::vector<T> concat(std::vector<T>&& v, Tail&&... tail)
423 {
424  append(v, std::forward<Tail>(tail)...);
425  return std::move(v);
426 }
427 
428 
429 // lookup in std::map
430 template<typename Key, typename Value>
431 [[nodiscard]] const Value* lookup(const std::map<Key, Value>& m, const Key& k)
432 {
433  auto it = m.find(k);
434  return (it != m.end()) ? &it->second : nullptr;
435 }
436 
437 template<typename Key, typename Value>
438 [[nodiscard]] Value* lookup(std::map<Key, Value>& m, const Key& k)
439 {
440  auto it = m.find(k);
441  return (it != m.end()) ? &it->second : nullptr;
442 }
443 
444 #endif
bool operator()(const std::tuple< Args... > &x, const T &y) const
Definition: stl.hh:41
bool operator()(const T &x, const std::tuple< Args... > &y) const
Definition: stl.hh:36
auto find(InputRange &&range, const T &value)
Definition: ranges.hh:107
auto EqualTupleValue(const T &t)
Definition: stl.hh:80
auto sum(InputRange &&range)
Definition: stl.hh:288
ITER find_unguarded(ITER first, ITER last, const VAL &val)
Faster alternative to &#39;find&#39; when it&#39;s guaranteed that the value will be found (if not the behavior i...
Definition: stl.hh:111
auto distance(octet_iterator first, octet_iterator last)
vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:269
size_t sum_of_sizes(const Range &r, Tail &&... tail)
Definition: stl.hh:333
auto min_value(InputIterator first, InputIterator last)
Definition: stl.hh:248
bool contains(ITER first, ITER last, const VAL &val)
Check if a range contains a given value, using linear search.
Definition: stl.hh:92
std::conditional_t< std::is_same_v< T, void >, typename std::iterator_traits< Iterator >::value_type, T > ToVectorType
Definition: stl.hh:302
bool operator()(const std::pair< T1, T2 > &x, const std::pair< T1, T2 > &y) const
Definition: stl.hh:46
vecN< N, T > max(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:287
bool operator()(const std::pair< T1, T2 > &x, const T &y) const
Definition: stl.hh:56
void move_pop_back(VECTOR &v, typename VECTOR::iterator it)
Erase the pointed to element from the given vector.
Definition: stl.hh:177
T accumulate(InputRange &&range, T init)
Definition: ranges.hh:197
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:113
void append(Result &)
Definition: stl.hh:340
auto concat(const Range &range, Tail &&... tail)
Definition: stl.hh:413
Definition: join.hh:10
EqualTupleValueImpl(const T &t_)
Definition: stl.hh:71
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:212
auto max_value(InputIterator first, InputIterator last)
Definition: stl.hh:267
Definition: stl.hh:16
bool operator()(const std::tuple< Args... > &x, const std::tuple< Args... > &y) const
Definition: stl.hh:31
size_t sum_of_sizes()
Definition: stl.hh:328
auto transform_in_place(ForwardRange &&range, UnaryOperation op)
Definition: stl.hh:239
const Value * lookup(const std::map< Key, Value > &m, const Key &k)
Definition: stl.hh:431
bool operator()(const TUPLE &tup) const
Definition: stl.hh:73
void append(std::vector< T > &v, Tail &&... tail)
Definition: stl.hh:379
ITER find_if_unguarded(ITER first, ITER last, PRED pred)
Faster alternative to &#39;find_if&#39; when it&#39;s guaranteed that the predicate will be true for at least one...
Definition: stl.hh:131
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:1377
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
Definition: ranges.hh:161
auto rfind_unguarded(RANGE &range, const VAL &val)
Similar to the find(_if)_unguarded functions above, but searches from the back to front...
Definition: stl.hh:152
bool operator()(const T &x, const std::pair< T1, T2 > &y) const
Definition: stl.hh:51
auto rfind_if_unguarded(RANGE &range, PRED pred)
Definition: stl.hh:160
TclObject t
auto to_vector(Range &&range) -> std::vector< detail::ToVectorType< T, decltype(std::begin(range))>>
Definition: stl.hh:311
bool operator()(PTR p1, PTR p2) const
Definition: stl.hh:19