1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
|
#ifndef STL_LITE_H
#define STL_LITE_H
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
namespace std_lite{
/**
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
* @return The lesser of the parameters.
*
* This is the simple classic generic implementation. It will work on
* temporary expressions, since they are only evaluated once, unlike a
* preprocessor macro.
*/
template<typename _Tp>
inline const _Tp&
min(const _Tp& __a, const _Tp& __b)
{
//return __b < __a ? __b : __a;
if (__b < __a)
return __b;
return __a;
}
/**
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
* @return The greater of the parameters.
*
* This is the simple classic generic implementation. It will work on
* temporary expressions, since they are only evaluated once, unlike a
* preprocessor macro.
*/
template<typename _Tp>
inline const _Tp&
max(const _Tp& __a, const _Tp& __b)
{
//return __a < __b ? __b : __a;
if (__a < __b)
return __b;
return __a;
}
/**
* @brief Swaps two values.
* @ingroup mutating_algorithms
* @param __a A thing of arbitrary type.
* @param __b Another thing of arbitrary type.
* @return Nothing.
*/
template<typename _Tp>
inline void
swap(_Tp& __a, _Tp& __b)
{
_Tp __tmp = __a;
__a = __b;
__b = __tmp;
}
/**
* This is one of the @link s20_3_1_base functor base classes@endlink.
*/
template <class _Arg1, class _Arg2, class _Result>
struct binary_function
{
typedef _Arg1 first_argument_type; ///< the type of the first argument
/// (no surprises here)
typedef _Arg2 second_argument_type; ///< the type of the second argument
typedef _Result result_type; ///< type of the return type
};
/// pair holds two objects of arbitrary type.
template<class _T1, class _T2>
struct pair
{
typedef _T1 first_type; ///< @c first_type is the first bound type
typedef _T2 second_type; ///< @c second_type is the second bound type
_T1 first; ///< @c first is a copy of the first object
_T2 second; ///< @c second is a copy of the second object
/** The default constructor creates @c first and @c second using their
* respective default constructors. */
pair()
: first(), second() { }
/** Two objects may be passed to a @c pair constructor to be copied. */
pair(const _T1& __a, const _T2& __b)
: first(__a), second(__b) { }
/** There is also a templated copy ctor for the @c pair class itself. */
template<class _U1, class _U2>
pair(const pair<_U1, _U2>& __p)
: first(__p.first), second(__p.second) { }
};
/// Two pairs of the same type are equal iff their members are equal.
template<class _T1, class _T2>
inline bool
operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return __x.first == __y.first && __x.second == __y.second; }
/// <http://gcc.gnu.org/onlinedocs/libstdc++/20_util/howto.html#pairlt>
template<class _T1, class _T2>
inline bool
operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return __x.first < __y.first
|| (!(__y.first < __x.first) && __x.second < __y.second); }
/// Uses @c operator== to find the result.
template<class _T1, class _T2>
inline bool
operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return !(__x == __y); }
/// Uses @c operator< to find the result.
template<class _T1, class _T2>
inline bool
operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return __y < __x; }
/// Uses @c operator< to find the result.
template<class _T1, class _T2>
inline bool
operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return !(__y < __x); }
/// Uses @c operator< to find the result.
template<class _T1, class _T2>
inline bool
operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return !(__x < __y); }
/**
* @brief A convenience wrapper for creating a pair from two objects.
* @param x The first object.
* @param y The second object.
* @return A newly-constructed pair<> object of the appropriate type.
*
* The standard requires that the objects be passed by reference-to-const,
* but LWG issue #181 says they should be passed by const value. We follow
* the LWG by default.
*/
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 181. make_pair() unintended behavior
template<class _T1, class _T2>
inline pair<_T1, _T2>
make_pair(_T1 __x, _T2 __y)
{ return pair<_T1, _T2>(__x, __y); }
/**
* @brief Finds the first position in which @a val could be inserted
* without changing the ordering.
* @param first An iterator.
* @param last Another iterator.
* @param val The search term.
* @param comp A functor to use for comparisons.
* @return An iterator pointing to the first element "not less than" @a val,
* or end() if every element is less than @a val.
* @ingroup binarysearch
*
* The comparison function should have the same effects on ordering as
* the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator
lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
{
typedef size_t _DistanceType;
_DistanceType __len = __last - __first;
_DistanceType __half;
_ForwardIterator __middle;
while (__len > 0)
{
__half = __len >> 1;
__middle = __first;
__middle += __half;
if (__comp(*__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
/**
* @brief Finds the last position in which @a val could be inserted
* without changing the ordering.
* @param first An iterator.
* @param last Another iterator.
* @param val The search term.
* @param comp A functor to use for comparisons.
* @return An iterator pointing to the first element greater than @a val,
* or end() if no elements are greater than @a val.
* @ingroup binarysearch
*
* The comparison function should have the same effects on ordering as
* the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
{
typedef size_t _DistanceType;
_DistanceType __len = __last - __first;
_DistanceType __half;
_ForwardIterator __middle;
while (__len > 0)
{
__half = __len >> 1;
__middle = __first;
__middle += __half;
if (__comp(__val, *__middle))
__len = __half;
else
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
}
return __first;
}
/**
* @brief Finds the largest subrange in which @a val could be inserted
* at any place in it without changing the ordering.
* @param first An iterator.
* @param last Another iterator.
* @param val The search term.
* @param comp A functor to use for comparisons.
* @return An pair of iterators defining the subrange.
* @ingroup binarysearch
*
* This is equivalent to
* @code
* std_lite::make_pair(lower_bound(first, last, val, comp),
* upper_bound(first, last, val, comp))
* @endcode
* but does not actually call those functions.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
pair<_ForwardIterator, _ForwardIterator>
equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val,
_Compare __comp)
{
typedef size_t _DistanceType;
_DistanceType __len = __last - __first;
_DistanceType __half;
_ForwardIterator __middle, __left, __right;
while (__len > 0)
{
__half = __len >> 1;
__middle = __first;
__middle += __half;
if (__comp(*__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else if (__comp(__val, *__middle))
__len = __half;
else
{
__left = lower_bound(__first, __middle, __val, __comp);
__first += __len;
__right = upper_bound(++__middle, __first, __val, __comp);
return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
}
}
return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
}
}
#endif
|
