openMSX
stl.hh
Go to the documentation of this file.
1 #ifndef STL_HH
2 #define STL_HH
3 
4 #include <algorithm>
5 #include <tuple>
6 #include <utility>
7 #include <cassert>
8 
9 // Dereference the two given (pointer-like) parameters and then compare
10 // them with the less-than operator.
11 struct LessDeref
12 {
13  template<typename PTR>
14  bool operator()(PTR p1, PTR p2) const { return *p1 < *p2; }
15 };
16 
17 // C++14 has an std::equal_to functor that is very much like this version.
18 // TODO remove this version once we switch to C++14.
19 struct EqualTo
20 {
21  template<typename T1, typename T2>
22  bool operator()(const T1& t1, const T2& t2) const { return t1 == t2; }
23 };
24 
25 // Heterogeneous version of std::less.
26 struct LessThan
27 {
28  template<typename T1, typename T2>
29  bool operator()(const T1& t1, const T2& t2) const { return t1 < t2; }
30 };
31 
32 
33 // Compare the N-th element of two tuples using a custom comparison functor.
34 // Also provides overloads to compare the N-the element of a tuple with a
35 // single value (of a compatible type).
36 // ATM the functor cannot take constructor arguments, possibly refactor this in
37 // the future.
38 template<int N, typename CMP> struct CmpTupleElement
39 {
40  template<typename... Args>
41  bool operator()(const std::tuple<Args...>& x, const std::tuple<Args...>& y) const {
42  return cmp(std::get<N>(x), std::get<N>(y));
43  }
44 
45  template<typename T, typename... Args>
46  bool operator()(const T& x, const std::tuple<Args...>& y) const {
47  return cmp(x, std::get<N>(y));
48  }
49 
50  template<typename T, typename... Args>
51  bool operator()(const std::tuple<Args...>& x, const T& y) const {
52  return cmp(std::get<N>(x), y);
53  }
54 
55  template<typename T1, typename T2>
56  bool operator()(const std::pair<T1, T2>& x, const std::pair<T1, T2>& y) const {
57  return cmp(std::get<N>(x), std::get<N>(y));
58  }
59 
60  template<typename T, typename T1, typename T2>
61  bool operator()(const T& x, const std::pair<T1, T2>& y) const {
62  return cmp(x, std::get<N>(y));
63  }
64 
65  template<typename T, typename T1, typename T2>
66  bool operator()(const std::pair<T1, T2>& x, const T& y) const {
67  return cmp(std::get<N>(x), y);
68  }
69 
70 private:
71  CMP cmp;
72 };
73 
74 // Similar to CmpTupleElement above, but uses the less-than operator.
76 
77 
78 // Check whether the N-the element of a tuple is equal to the given value.
79 template<int N, typename T> struct EqualTupleValueImpl
80 {
81  explicit EqualTupleValueImpl(const T& t_) : t(t_) {}
82  template<typename TUPLE>
83  bool operator()(const TUPLE& tup) const {
84  return std::get<N>(tup) == t;
85  }
86 private:
87  const T& t;
88 };
89 template<int N, typename T>
91  return EqualTupleValueImpl<N, T>(t);
92 }
93 
94 
101 template<typename ITER, typename VAL>
102 inline bool contains(ITER first, ITER last, const VAL& val)
103 {
104  return std::find(first, last, val) != last;
105 }
106 template<typename RANGE, typename VAL>
107 inline bool contains(const RANGE& range, const VAL& val)
108 {
109  return contains(std::begin(range), std::end(range), val);
110 }
111 
112 
120 template<typename ITER, typename VAL>
121 inline ITER find_unguarded(ITER first, ITER last, const VAL& val)
122 {
123  (void)last;
124  while (1) {
125  assert(first != last);
126  if (*first == val) return first;
127  ++first;
128  }
129 }
130 template<typename RANGE, typename VAL>
131 inline auto find_unguarded(RANGE& range, const VAL& val)
132 -> decltype(std::begin(range))
133 {
134  return find_unguarded(std::begin(range), std::end(range), val);
135 }
136 
141 template<typename ITER, typename PRED>
142 inline ITER find_if_unguarded(ITER first, ITER last, PRED pred)
143 {
144  (void)last;
145  while (1) {
146  assert(first != last);
147  if (pred(*first)) return first;
148  ++first;
149  }
150 }
151 template<typename RANGE, typename PRED>
152 inline auto find_if_unguarded(RANGE& range, PRED pred)
153 -> decltype(std::begin(range))
154 {
155  return find_if_unguarded(std::begin(range), std::end(range), pred);
156 }
157 
163 template<typename RANGE, typename VAL>
164 inline auto rfind_unguarded(RANGE& range, const VAL& val)
165 -> decltype(std::begin(range))
166 {
167  //auto it = find_unguarded(std::rbegin(range), std::rend(range), val); // c++14
168  auto it = find_unguarded(range.rbegin(), range.rend(), 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 -> decltype(std::begin(range))
176 {
177  auto it = find_if_unguarded(range.rbegin(), range.rend(), pred);
178  ++it;
179  return it.base();
180 }
181 
182 
191 template<typename VECTOR>
192 void move_pop_back(VECTOR& v, typename VECTOR::iterator it)
193 {
194  // Check for self-move-assignment.
195  //
196  // This check is only needed in libstdc++ when compiled with
197  // -D_GLIBCXX_DEBUG. In non-debug mode this routine works perfectly
198  // fine without the check.
199  //
200  // See here for a related discussion:
201  // http://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor
202  // It's not clear whether the assert in libstdc++ is conforming
203  // behavior.
204  if (&*it != &v.back()) {
205  *it = std::move(v.back());
206  }
207  v.pop_back();
208 }
209 
210 
226 template<typename ForwardIt, typename OutputIt, typename UnaryPredicate>
227 std::pair<OutputIt, ForwardIt> partition_copy_remove(
228  ForwardIt first, ForwardIt last, OutputIt out_true, UnaryPredicate p)
229 {
230  first = std::find_if(first, last, p);
231  auto out_false = first;
232  if (first != last) {
233  goto l_true;
234  while (first != last) {
235  if (p(*first)) {
236 l_true: *out_true++ = std::move(*first++);
237  } else {
238  *out_false++ = std::move(*first++);
239  }
240  }
241  }
242  return std::make_pair(out_true, out_false);
243 }
244 
245 #endif
bool operator()(const std::tuple< Args... > &x, const T &y) const
Definition: stl.hh:51
bool operator()(const T &x, const std::tuple< Args... > &y) const
Definition: stl.hh:46
string_ref::const_iterator end(const string_ref &x)
Definition: string_ref.hh:167
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:121
bool contains(ITER first, ITER last, const VAL &val)
Check if a range contains a given value, using linear search.
Definition: stl.hh:102
bool operator()(const std::pair< T1, T2 > &x, const std::pair< T1, T2 > &y) const
Definition: stl.hh:56
EqualTupleValueImpl< N, T > EqualTupleValue(const T &t)
Definition: stl.hh:90
bool operator()(const std::pair< T1, T2 > &x, const T &y) const
Definition: stl.hh:66
void move_pop_back(VECTOR &v, typename VECTOR::iterator it)
Erase the pointed to element from the given vector.
Definition: stl.hh:192
bool operator()(const T1 &t1, const T2 &t2) const
Definition: stl.hh:22
bool operator()(const T1 &t1, const T2 &t2) const
Definition: stl.hh:29
auto rfind_unguarded(RANGE &range, const VAL &val) -> decltype(std::begin(range))
Similar to the find(_if)_unguarded functions above, but searches from the back to front...
Definition: stl.hh:164
Definition: stl.hh:26
EqualTupleValueImpl(const T &t_)
Definition: stl.hh:81
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:227
Definition: stl.hh:19
Definition: stl.hh:11
bool operator()(const std::tuple< Args... > &x, const std::tuple< Args... > &y) const
Definition: stl.hh:41
bool operator()(const TUPLE &tup) const
Definition: stl.hh:83
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:142
string_ref::const_iterator begin(const string_ref &x)
Definition: string_ref.hh:166
bool operator()(const T &x, const std::pair< T1, T2 > &y) const
Definition: stl.hh:61
auto rfind_if_unguarded(RANGE &range, PRED pred) -> decltype(std::begin(range))
Definition: stl.hh:174
bool operator()(PTR p1, PTR p2) const
Definition: stl.hh:14