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