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 constexpr bool contains(ITER first, ITER last, const VAL& val)
93 {
94  // c++20: return std::find(first, last, val) != last;
95  while (first != last) {
96  if (*first == val) return true;
97  ++first;
98  }
99  return false;
100 }
101 template<typename RANGE, typename VAL>
102 [[nodiscard]] inline constexpr bool contains(const RANGE& range, const VAL& val)
103 {
104  return contains(std::begin(range), std::end(range), val);
105 }
106 
107 
115 template<typename ITER, typename VAL>
116 [[nodiscard]] inline ITER find_unguarded(ITER first, ITER last, const VAL& val)
117 {
118  (void)last;
119  while (true) {
120  assert(first != last);
121  if (*first == val) return first;
122  ++first;
123  }
124 }
125 template<typename RANGE, typename VAL>
126 [[nodiscard]] inline auto find_unguarded(RANGE& range, const VAL& val)
127 {
128  return find_unguarded(std::begin(range), std::end(range), val);
129 }
130 
135 template<typename ITER, typename PRED>
136 [[nodiscard]] inline ITER find_if_unguarded(ITER first, ITER last, PRED pred)
137 {
138  (void)last;
139  while (true) {
140  assert(first != last);
141  if (pred(*first)) return first;
142  ++first;
143  }
144 }
145 template<typename RANGE, typename PRED>
146 [[nodiscard]] inline auto find_if_unguarded(RANGE& range, PRED pred)
147 {
148  return find_if_unguarded(std::begin(range), std::end(range), pred);
149 }
150 
156 template<typename RANGE, typename VAL>
157 [[nodiscard]] inline auto rfind_unguarded(RANGE& range, const VAL& val)
158 {
159  auto it = find_unguarded(std::rbegin(range), std::rend(range), val);
160  ++it;
161  return it.base();
162 }
163 
164 template<typename RANGE, typename PRED>
165 [[nodiscard]] inline auto rfind_if_unguarded(RANGE& range, PRED pred)
166 {
167  auto it = find_if_unguarded(std::rbegin(range), std::rend(range), pred);
168  ++it;
169  return it.base();
170 }
171 
172 
181 template<typename VECTOR>
182 void move_pop_back(VECTOR& v, typename VECTOR::iterator it)
183 {
184  // Check for self-move-assignment.
185  //
186  // This check is only needed in libstdc++ when compiled with
187  // -D_GLIBCXX_DEBUG. In non-debug mode this routine works perfectly
188  // fine without the check.
189  //
190  // See here for a related discussion:
191  // http://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor
192  // It's not clear whether the assert in libstdc++ is conforming
193  // behavior.
194  if (&*it != &v.back()) {
195  *it = std::move(v.back());
196  }
197  v.pop_back();
198 }
199 
200 
216 template<typename ForwardIt, typename OutputIt, typename UnaryPredicate>
217 [[nodiscard]] std::pair<OutputIt, ForwardIt> partition_copy_remove(
218  ForwardIt first, ForwardIt last, OutputIt out_true, UnaryPredicate p)
219 {
220  first = std::find_if(first, last, p);
221  auto out_false = first;
222  if (first != last) {
223  goto l_true;
224  while (first != last) {
225  if (p(*first)) {
226 l_true: *out_true++ = std::move(*first++);
227  } else {
228  *out_false++ = std::move(*first++);
229  }
230  }
231  }
232  return std::pair(out_true, out_false);
233 }
234 
235 template<typename ForwardRange, typename OutputIt, typename UnaryPredicate>
236 [[nodiscard]] auto partition_copy_remove(ForwardRange&& range, OutputIt out_true, UnaryPredicate p)
237 {
238  return partition_copy_remove(std::begin(range), std::end(range), out_true, p);
239 }
240 
241 
242 // Like range::transform(), but with equal source and destination.
243 template<typename ForwardRange, typename UnaryOperation>
244 auto transform_in_place(ForwardRange&& range, UnaryOperation op)
245 {
246  return std::transform(std::begin(range), std::end(range), std::begin(range), op);
247 }
248 
249 
250 // Returns (a copy of) the minimum value in [first, last).
251 // Requires: first != last.
252 template<typename InputIterator>
253 [[nodiscard]] auto min_value(InputIterator first, InputIterator last)
254 {
255  assert(first != last);
256  auto result = *first++;
257  while (first != last) {
258  result = std::min(result, *first++);
259  }
260  return result;
261 }
262 
263 template<typename InputRange>
264 [[nodiscard]] auto min_value(InputRange&& range)
265 {
266  return min_value(std::begin(range), std::end(range));
267 }
268 
269 // Returns (a copy of) the maximum value in [first, last).
270 // Requires: first != last.
271 template<typename InputIterator>
272 [[nodiscard]] auto max_value(InputIterator first, InputIterator last)
273 {
274  assert(first != last);
275  auto result = *first++;
276  while (first != last) {
277  result = std::max(result, *first++);
278  }
279  return result;
280 }
281 
282 template<typename InputRange>
283 [[nodiscard]] auto max_value(InputRange&& range)
284 {
285  return max_value(std::begin(range), std::end(range));
286 }
287 
288 
289 // Returns the sum of the elements in the given range.
290 // Assumes: elements can be summed via operator+, with a default constructed
291 // value being the identity-element for this operator.
292 template<typename InputRange>
293 [[nodiscard]] auto sum(InputRange&& range)
294 {
295  using Iter = decltype(std::begin(range));
296  using T = typename std::iterator_traits<Iter>::value_type;
297  return std::accumulate(std::begin(range), std::end(range), T());
298 }
299 
300 
301 // to_vector
302 namespace detail {
303  template<typename T, typename Iterator>
304  using ToVectorType = std::conditional_t<
305  std::is_same_v<T, void>,
306  typename std::iterator_traits<Iterator>::value_type,
307  T>;
308 }
309 
310 // Convert any range to a vector. Optionally specify the type of the elements
311 // in the result.
312 // Example:
313 // auto v1 = to_vector(view::drop(my_list, 3));
314 // auto v2 = to_vector<Base*>(getDerivedPtrs());
315 template<typename T = void, typename Range>
316 [[nodiscard]] auto to_vector(Range&& range)
317  -> std::vector<detail::ToVectorType<T, decltype(std::begin(range))>>
318 {
319  return {std::begin(range), std::end(range)};
320 }
321 
322 // Optimized version for r-value input and no type conversion.
323 template<typename T>
324 [[nodiscard]] auto to_vector(std::vector<T>&& v)
325 {
326  return std::move(v);
327 }
328 
329 
330 // append() / concat()
331 namespace detail {
332 
333 template<typename... Ranges>
334 [[nodiscard]] size_t sum_of_sizes(const Ranges&... ranges)
335 {
336  return (0 + ... + std::distance(std::begin(ranges), std::end(ranges)));
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 {
415  using T2 = detail::ToVectorType<T, decltype(std::begin(range))>;
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
EqualTupleValue
auto EqualTupleValue(const T &t)
Definition: stl.hh:80
min_value
auto min_value(InputIterator first, InputIterator last)
Definition: stl.hh:253
gl::min
vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:274
contains
constexpr bool contains(ITER first, ITER last, const VAL &val)
Check if a range contains a given value, using linear search.
Definition: stl.hh:92
CmpTupleElement::operator()
bool operator()(const std::pair< T1, T2 > &x, const std::pair< T1, T2 > &y) const
Definition: stl.hh:46
find_unguarded
ITER find_unguarded(ITER first, ITER last, const VAL &val)
Faster alternative to 'find' when it's guaranteed that the value will be found (if not the behavior i...
Definition: stl.hh:116
EqualTupleValueImpl::EqualTupleValueImpl
EqualTupleValueImpl(const T &t_)
Definition: stl.hh:71
ranges
Definition: ranges.hh:20
EqualTupleValueImpl::operator()
bool operator()(const TUPLE &tup) const
Definition: stl.hh:73
detail
Definition: join.hh:10
t
TclObject t
Definition: TclObject_test.cc:264
detail::ToVectorType
std::conditional_t< std::is_same_v< T, void >, typename std::iterator_traits< Iterator >::value_type, T > ToVectorType
Definition: stl.hh:307
CmpTupleElement::operator()
bool operator()(const std::tuple< Args... > &x, const T &y) const
Definition: stl.hh:41
ranges::transform
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
Definition: ranges.hh:161
CmpTupleElement::operator()
bool operator()(const std::tuple< Args... > &x, const std::tuple< Args... > &y) const
Definition: stl.hh:31
CmpTupleElement::operator()
bool operator()(const std::pair< T1, T2 > &x, const T &y) const
Definition: stl.hh:56
detail::sum_of_sizes
size_t sum_of_sizes(const Ranges &... ranges)
Definition: stl.hh:334
concat
auto concat(const Range &range, Tail &&... tail)
Definition: stl.hh:413
move_pop_back
void move_pop_back(VECTOR &v, typename VECTOR::iterator it)
Erase the pointed to element from the given vector.
Definition: stl.hh:182
LessDeref
Definition: stl.hh:17
max_value
auto max_value(InputIterator first, InputIterator last)
Definition: stl.hh:272
utf8::distance
auto distance(octet_iterator first, octet_iterator last)
Definition: utf8_checked.hh:194
partition_copy_remove
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:217
EqualTupleValueImpl
Definition: stl.hh:70
Iter
Definition: semiregular_test.cc:8
openmsx::x
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:1416
CmpTupleElement
Definition: stl.hh:29
transform_in_place
auto transform_in_place(ForwardRange &&range, UnaryOperation op)
Definition: stl.hh:244
lookup
const Value * lookup(const std::map< Key, Value > &m, const Key &k)
Definition: stl.hh:431
detail::append
void append(Result &)
Definition: stl.hh:340
LessDeref::operator()
bool operator()(PTR p1, PTR p2) const
Definition: stl.hh:19
gl::max
vecN< N, T > max(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:292
append
void append(std::vector< T > &v, Tail &&... tail)
Definition: stl.hh:379
find_if_unguarded
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:136
ranges::find_if
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:113
ranges::accumulate
T accumulate(InputRange &&range, T init)
Definition: ranges.hh:197
rfind_unguarded
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:157
to_vector
auto to_vector(Range &&range) -> std::vector< detail::ToVectorType< T, decltype(std::begin(range))>>
Definition: stl.hh:316
sum
auto sum(InputRange &&range)
Definition: stl.hh:293
rfind_if_unguarded
auto rfind_if_unguarded(RANGE &range, PRED pred)
Definition: stl.hh:165
CmpTupleElement::operator()
bool operator()(const T &x, const std::pair< T1, T2 > &y) const
Definition: stl.hh:51
CmpTupleElement::operator()
bool operator()(const T &x, const std::tuple< Args... > &y) const
Definition: stl.hh:36