]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Bits and pieces used in algorithms -*- C++ -*- |
2 | ||
46c4e5d6 | 3 | // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. |
42526146 PE |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
725dc051 BK |
30 | /* |
31 | * | |
32 | * Copyright (c) 1994 | |
33 | * Hewlett-Packard Company | |
34 | * | |
35 | * Permission to use, copy, modify, distribute and sell this software | |
36 | * and its documentation for any purpose is hereby granted without fee, | |
37 | * provided that the above copyright notice appear in all copies and | |
38 | * that both that copyright notice and this permission notice appear | |
39 | * in supporting documentation. Hewlett-Packard Company makes no | |
40 | * representations about the suitability of this software for any | |
41 | * purpose. It is provided "as is" without express or implied warranty. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1996-1998 | |
45 | * Silicon Graphics Computer Systems, Inc. | |
46 | * | |
47 | * Permission to use, copy, modify, distribute and sell this software | |
48 | * and its documentation for any purpose is hereby granted without fee, | |
49 | * provided that the above copyright notice appear in all copies and | |
50 | * that both that copyright notice and this permission notice appear | |
51 | * in supporting documentation. Silicon Graphics makes no | |
52 | * representations about the suitability of this software for any | |
53 | * purpose. It is provided "as is" without express or implied warranty. | |
54 | */ | |
55 | ||
729e3d3f PE |
56 | /** @file stl_algobase.h |
57 | * This is an internal header file, included by other library headers. | |
58 | * You should not attempt to use it directly. | |
725dc051 BK |
59 | */ |
60 | ||
3d7c150e BK |
61 | #ifndef _ALGOBASE_H |
62 | #define _ALGOBASE_H 1 | |
725dc051 | 63 | |
9cfeea6e | 64 | #include <bits/c++config.h> |
54c1bf78 BK |
65 | #include <cstring> |
66 | #include <climits> | |
67 | #include <cstdlib> | |
68 | #include <cstddef> | |
69 | #include <new> | |
70 | #include <iosfwd> | |
725dc051 | 71 | #include <bits/stl_pair.h> |
725dc051 | 72 | #include <bits/type_traits.h> |
30a20a1e PE |
73 | #include <bits/stl_iterator_base_types.h> |
74 | #include <bits/stl_iterator_base_funcs.h> | |
725dc051 | 75 | #include <bits/stl_iterator.h> |
30a20a1e | 76 | #include <bits/concept_check.h> |
285b36d6 | 77 | #include <debug/debug.h> |
725dc051 | 78 | |
d53d7f6e PE |
79 | namespace std |
80 | { | |
729e3d3f PE |
81 | /** |
82 | * @brief Swaps the contents of two iterators. | |
83 | * @param a An iterator. | |
84 | * @param b Another iterator. | |
85 | * @return Nothing. | |
86 | * | |
87 | * This function swaps the values pointed to by two iterators, not the | |
88 | * iterators themselves. | |
89 | */ | |
08addde6 | 90 | template<typename _ForwardIterator1, typename _ForwardIterator2> |
02d92e3b | 91 | inline void |
08addde6 | 92 | iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) |
02d92e3b | 93 | { |
08addde6 PE |
94 | typedef typename iterator_traits<_ForwardIterator1>::value_type _ValueType1; |
95 | typedef typename iterator_traits<_ForwardIterator2>::value_type _ValueType2; | |
02d92e3b SW |
96 | |
97 | // concept requirements | |
3d7c150e BK |
98 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator1>) |
99 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator2>) | |
100 | __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, _ValueType2>) | |
101 | __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, _ValueType1>) | |
02d92e3b SW |
102 | |
103 | _ValueType1 __tmp = *__a; | |
104 | *__a = *__b; | |
105 | *__b = __tmp; | |
106 | } | |
107 | ||
729e3d3f PE |
108 | /** |
109 | * @brief Swaps two values. | |
110 | * @param a A thing of arbitrary type. | |
111 | * @param b Another thing of arbitrary type. | |
112 | * @return Nothing. | |
113 | * | |
114 | * This is the simple classic generic implementation. It will work on | |
115 | * any type which has a copy constructor and an assignment operator. | |
116 | */ | |
02d92e3b SW |
117 | template<typename _Tp> |
118 | inline void | |
119 | swap(_Tp& __a, _Tp& __b) | |
120 | { | |
121 | // concept requirements | |
3d7c150e | 122 | __glibcxx_function_requires(_SGIAssignableConcept<_Tp>) |
02d92e3b SW |
123 | |
124 | _Tp __tmp = __a; | |
125 | __a = __b; | |
126 | __b = __tmp; | |
127 | } | |
128 | ||
02d92e3b SW |
129 | #undef min |
130 | #undef max | |
131 | ||
729e3d3f PE |
132 | /** |
133 | * @brief This does what you think it does. | |
134 | * @param a A thing of arbitrary type. | |
135 | * @param b Another thing of arbitrary type. | |
136 | * @return The lesser of the parameters. | |
137 | * | |
138 | * This is the simple classic generic implementation. It will work on | |
139 | * temporary expressions, since they are only evaluated once, unlike a | |
140 | * preprocessor macro. | |
141 | */ | |
02d92e3b SW |
142 | template<typename _Tp> |
143 | inline const _Tp& | |
144 | min(const _Tp& __a, const _Tp& __b) | |
145 | { | |
146 | // concept requirements | |
3d7c150e | 147 | __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
02d92e3b SW |
148 | //return __b < __a ? __b : __a; |
149 | if (__b < __a) return __b; return __a; | |
150 | } | |
151 | ||
1b4a6975 PE |
152 | /** |
153 | * @brief This does what you think it does. | |
154 | * @param a A thing of arbitrary type. | |
155 | * @param b Another thing of arbitrary type. | |
156 | * @return The greater of the parameters. | |
157 | * | |
158 | * This is the simple classic generic implementation. It will work on | |
159 | * temporary expressions, since they are only evaluated once, unlike a | |
160 | * preprocessor macro. | |
161 | */ | |
02d92e3b SW |
162 | template<typename _Tp> |
163 | inline const _Tp& | |
164 | max(const _Tp& __a, const _Tp& __b) | |
165 | { | |
166 | // concept requirements | |
3d7c150e | 167 | __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
02d92e3b SW |
168 | //return __a < __b ? __b : __a; |
169 | if (__a < __b) return __b; return __a; | |
170 | } | |
171 | ||
1b4a6975 PE |
172 | /** |
173 | * @brief This does what you think it does. | |
174 | * @param a A thing of arbitrary type. | |
175 | * @param b Another thing of arbitrary type. | |
176 | * @param comp A @link s20_3_3_comparisons comparison functor@endlink. | |
177 | * @return The lesser of the parameters. | |
178 | * | |
179 | * This will work on temporary expressions, since they are only evaluated | |
180 | * once, unlike a preprocessor macro. | |
181 | */ | |
02d92e3b SW |
182 | template<typename _Tp, typename _Compare> |
183 | inline const _Tp& | |
184 | min(const _Tp& __a, const _Tp& __b, _Compare __comp) | |
185 | { | |
186 | //return __comp(__b, __a) ? __b : __a; | |
187 | if (__comp(__b, __a)) return __b; return __a; | |
188 | } | |
189 | ||
1b4a6975 PE |
190 | /** |
191 | * @brief This does what you think it does. | |
192 | * @param a A thing of arbitrary type. | |
193 | * @param b Another thing of arbitrary type. | |
194 | * @param comp A @link s20_3_3_comparisons comparison functor@endlink. | |
195 | * @return The greater of the parameters. | |
196 | * | |
197 | * This will work on temporary expressions, since they are only evaluated | |
198 | * once, unlike a preprocessor macro. | |
199 | */ | |
02d92e3b SW |
200 | template<typename _Tp, typename _Compare> |
201 | inline const _Tp& | |
202 | max(const _Tp& __a, const _Tp& __b, _Compare __comp) | |
203 | { | |
204 | //return __comp(__a, __b) ? __b : __a; | |
205 | if (__comp(__a, __b)) return __b; return __a; | |
206 | } | |
207 | ||
02d92e3b SW |
208 | // All of these auxiliary functions serve two purposes. (1) Replace |
209 | // calls to copy with memmove whenever possible. (Memmove, not memcpy, | |
210 | // because the input and output ranges are permitted to overlap.) | |
211 | // (2) If we're using random access iterators, then write the loop as | |
212 | // a for loop with an explicit count. | |
213 | ||
08addde6 PE |
214 | template<typename _InputIterator, typename _OutputIterator> |
215 | inline _OutputIterator | |
216 | __copy(_InputIterator __first, _InputIterator __last, | |
217 | _OutputIterator __result, input_iterator_tag) | |
02d92e3b | 218 | { |
46c4e5d6 | 219 | for (; __first != __last; ++__result, ++__first) |
02d92e3b SW |
220 | *__result = *__first; |
221 | return __result; | |
222 | } | |
223 | ||
08addde6 PE |
224 | template<typename _RandomAccessIterator, typename _OutputIterator> |
225 | inline _OutputIterator | |
226 | __copy(_RandomAccessIterator __first, _RandomAccessIterator __last, | |
227 | _OutputIterator __result, random_access_iterator_tag) | |
02d92e3b | 228 | { |
08addde6 | 229 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
725dc051 | 230 | _Distance; |
46c4e5d6 BK |
231 | for (_Distance __n = __last - __first; __n > 0; --__n) |
232 | { | |
233 | *__result = *__first; | |
234 | ++__first; | |
235 | ++__result; | |
236 | } | |
02d92e3b SW |
237 | return __result; |
238 | } | |
239 | ||
240 | template<typename _Tp> | |
241 | inline _Tp* | |
242 | __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) | |
243 | { | |
884a757a | 244 | std::memmove(__result, __first, sizeof(_Tp) * (__last - __first)); |
02d92e3b SW |
245 | return __result + (__last - __first); |
246 | } | |
247 | ||
08addde6 PE |
248 | template<typename _InputIterator, typename _OutputIterator> |
249 | inline _OutputIterator | |
250 | __copy_aux2(_InputIterator __first, _InputIterator __last, | |
251 | _OutputIterator __result, __false_type) | |
369b78b0 | 252 | { return std::__copy(__first, __last, __result, std::__iterator_category(__first)); } |
02d92e3b | 253 | |
08addde6 PE |
254 | template<typename _InputIterator, typename _OutputIterator> |
255 | inline _OutputIterator | |
256 | __copy_aux2(_InputIterator __first, _InputIterator __last, | |
257 | _OutputIterator __result, __true_type) | |
369b78b0 | 258 | { return std::__copy(__first, __last, __result, std::__iterator_category(__first)); } |
02d92e3b SW |
259 | |
260 | template<typename _Tp> | |
261 | inline _Tp* | |
46c4e5d6 | 262 | __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result, __true_type) |
884a757a | 263 | { return std::__copy_trivial(__first, __last, __result); } |
02d92e3b SW |
264 | |
265 | template<typename _Tp> | |
266 | inline _Tp* | |
46c4e5d6 BK |
267 | __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result, |
268 | __true_type) | |
884a757a | 269 | { return std::__copy_trivial(__first, __last, __result); } |
02d92e3b | 270 | |
08addde6 PE |
271 | template<typename _InputIterator, typename _OutputIterator> |
272 | inline _OutputIterator | |
273 | __copy_ni2(_InputIterator __first, _InputIterator __last, | |
274 | _OutputIterator __result, __true_type) | |
02d92e3b | 275 | { |
08addde6 | 276 | typedef typename iterator_traits<_InputIterator>::value_type |
02d92e3b SW |
277 | _ValueType; |
278 | typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator | |
279 | _Trivial; | |
884a757a PC |
280 | return _OutputIterator(std::__copy_aux2(__first, __last, __result.base(), |
281 | _Trivial())); | |
02d92e3b SW |
282 | } |
283 | ||
08addde6 PE |
284 | template<typename _InputIterator, typename _OutputIterator> |
285 | inline _OutputIterator | |
286 | __copy_ni2(_InputIterator __first, _InputIterator __last, | |
287 | _OutputIterator __result, __false_type) | |
02d92e3b | 288 | { |
08addde6 | 289 | typedef typename iterator_traits<_InputIterator>::value_type _ValueType; |
02d92e3b | 290 | typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator |
725dc051 | 291 | _Trivial; |
884a757a | 292 | return std::__copy_aux2(__first, __last, __result, _Trivial()); |
02d92e3b SW |
293 | } |
294 | ||
08addde6 PE |
295 | template<typename _InputIterator, typename _OutputIterator> |
296 | inline _OutputIterator | |
297 | __copy_ni1(_InputIterator __first, _InputIterator __last, | |
298 | _OutputIterator __result, __true_type) | |
02d92e3b | 299 | { |
08addde6 | 300 | typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal; |
884a757a | 301 | return std::__copy_ni2(__first.base(), __last.base(), __result, __Normal()); |
02d92e3b SW |
302 | } |
303 | ||
08addde6 PE |
304 | template<typename _InputIterator, typename _OutputIterator> |
305 | inline _OutputIterator | |
306 | __copy_ni1(_InputIterator __first, _InputIterator __last, | |
307 | _OutputIterator __result, __false_type) | |
02d92e3b | 308 | { |
08addde6 | 309 | typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal; |
884a757a | 310 | return std::__copy_ni2(__first, __last, __result, __Normal()); |
02d92e3b SW |
311 | } |
312 | ||
1b4a6975 PE |
313 | /** |
314 | * @brief Copies the range [first,last) into result. | |
315 | * @param first An input iterator. | |
316 | * @param last An input iterator. | |
317 | * @param result An output iterator. | |
318 | * @return result + (first - last) | |
319 | * | |
320 | * This inline function will boil down to a call to @c memmove whenever | |
321 | * possible. Failing that, if random access iterators are passed, then the | |
322 | * loop count will be known (and therefore a candidate for compiler | |
119dbb1f JQ |
323 | * optimizations such as unrolling). Result may not be contained within |
324 | * [first,last); the copy_backward function should be used instead. | |
325 | * | |
326 | * Note that the end of the output range is permitted to be contained | |
327 | * within [first,last). | |
1b4a6975 | 328 | */ |
08addde6 PE |
329 | template<typename _InputIterator, typename _OutputIterator> |
330 | inline _OutputIterator | |
331 | copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) | |
02d92e3b SW |
332 | { |
333 | // concept requirements | |
3d7c150e BK |
334 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
335 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, | |
08addde6 | 336 | typename iterator_traits<_InputIterator>::value_type>) |
285b36d6 | 337 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 338 | |
08addde6 | 339 | typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal; |
884a757a | 340 | return std::__copy_ni1(__first, __last, __result, __Normal()); |
02d92e3b SW |
341 | } |
342 | ||
08addde6 PE |
343 | template<typename _BidirectionalIterator1, typename _BidirectionalIterator2> |
344 | inline _BidirectionalIterator2 | |
345 | __copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, | |
346 | _BidirectionalIterator2 __result, bidirectional_iterator_tag) | |
02d92e3b SW |
347 | { |
348 | while (__first != __last) | |
349 | *--__result = *--__last; | |
350 | return __result; | |
351 | } | |
352 | ||
08addde6 PE |
353 | template<typename _RandomAccessIterator, typename _BidirectionalIterator> |
354 | inline _BidirectionalIterator | |
355 | __copy_backward(_RandomAccessIterator __first, _RandomAccessIterator __last, | |
356 | _BidirectionalIterator __result, random_access_iterator_tag) | |
02d92e3b | 357 | { |
08addde6 | 358 | typename iterator_traits<_RandomAccessIterator>::difference_type __n; |
02d92e3b SW |
359 | for (__n = __last - __first; __n > 0; --__n) |
360 | *--__result = *--__last; | |
361 | return __result; | |
362 | } | |
363 | ||
364 | ||
365 | // This dispatch class is a workaround for compilers that do not | |
366 | // have partial ordering of function templates. All we're doing is | |
367 | // creating a specialization so that we can turn a call to copy_backward | |
368 | // into a memmove whenever possible. | |
08addde6 | 369 | template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, |
02d92e3b SW |
370 | typename _BoolType> |
371 | struct __copy_backward_dispatch | |
372 | { | |
08addde6 PE |
373 | static _BidirectionalIterator2 |
374 | copy(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, | |
375 | _BidirectionalIterator2 __result) | |
02d92e3b | 376 | { |
884a757a | 377 | return std::__copy_backward(__first, __last, __result, |
369b78b0 | 378 | std::__iterator_category(__first)); |
02d92e3b SW |
379 | } |
380 | }; | |
381 | ||
382 | template<typename _Tp> | |
383 | struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type> | |
384 | { | |
385 | static _Tp* | |
386 | copy(const _Tp* __first, const _Tp* __last, _Tp* __result) | |
387 | { | |
388 | const ptrdiff_t _Num = __last - __first; | |
884a757a | 389 | std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num); |
02d92e3b SW |
390 | return __result - _Num; |
391 | } | |
392 | }; | |
393 | ||
394 | template<typename _Tp> | |
395 | struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type> | |
396 | { | |
397 | static _Tp* | |
398 | copy(const _Tp* __first, const _Tp* __last, _Tp* __result) | |
399 | { | |
884a757a | 400 | return std::__copy_backward_dispatch<_Tp*, _Tp*, __true_type> |
02d92e3b SW |
401 | ::copy(__first, __last, __result); |
402 | } | |
403 | }; | |
404 | ||
405 | template<typename _BI1, typename _BI2> | |
406 | inline _BI2 | |
407 | __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) | |
408 | { | |
409 | typedef typename __type_traits<typename iterator_traits<_BI2>::value_type> | |
410 | ::has_trivial_assignment_operator _Trivial; | |
884a757a PC |
411 | return std::__copy_backward_dispatch<_BI1, _BI2, _Trivial>::copy(__first, |
412 | __last, | |
413 | __result); | |
02d92e3b SW |
414 | } |
415 | ||
416 | template <typename _BI1, typename _BI2> | |
417 | inline _BI2 | |
418 | __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, | |
419 | _BI2 __result, __true_type) | |
884a757a | 420 | { return _BI2(std::__copy_backward_aux(__first, __last, __result.base())); } |
02d92e3b SW |
421 | |
422 | template <typename _BI1, typename _BI2> | |
423 | inline _BI2 | |
424 | __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, | |
425 | _BI2 __result, __false_type) | |
884a757a | 426 | { return std::__copy_backward_aux(__first, __last, __result); } |
02d92e3b SW |
427 | |
428 | template <typename _BI1, typename _BI2> | |
429 | inline _BI2 | |
430 | __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, | |
431 | _BI2 __result, __true_type) | |
432 | { | |
433 | typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; | |
884a757a PC |
434 | return std::__copy_backward_output_normal_iterator(__first.base(), |
435 | __last.base(), __result, | |
436 | __Normal()); | |
02d92e3b SW |
437 | } |
438 | ||
439 | template <typename _BI1, typename _BI2> | |
440 | inline _BI2 | |
441 | __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, | |
442 | _BI2 __result, __false_type) | |
443 | { | |
444 | typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; | |
884a757a PC |
445 | return std::__copy_backward_output_normal_iterator(__first, __last, __result, |
446 | __Normal()); | |
02d92e3b SW |
447 | } |
448 | ||
1b4a6975 PE |
449 | /** |
450 | * @brief Copies the range [first,last) into result. | |
119dbb1f JQ |
451 | * @param first A bidirectional iterator. |
452 | * @param last A bidirectional iterator. | |
453 | * @param result A bidirectional iterator. | |
1b4a6975 PE |
454 | * @return result - (first - last) |
455 | * | |
456 | * The function has the same effect as copy, but starts at the end of the | |
457 | * range and works its way to the start, returning the start of the result. | |
458 | * This inline function will boil down to a call to @c memmove whenever | |
459 | * possible. Failing that, if random access iterators are passed, then the | |
460 | * loop count will be known (and therefore a candidate for compiler | |
461 | * optimizations such as unrolling). | |
119dbb1f JQ |
462 | * |
463 | * Result may not be in the range [first,last). Use copy instead. Note | |
464 | * that the start of the output range may overlap [first,last). | |
1b4a6975 | 465 | */ |
02d92e3b SW |
466 | template <typename _BI1, typename _BI2> |
467 | inline _BI2 | |
468 | copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) | |
469 | { | |
470 | // concept requirements | |
3d7c150e BK |
471 | __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) |
472 | __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) | |
473 | __glibcxx_function_requires(_ConvertibleConcept< | |
02d92e3b | 474 | typename iterator_traits<_BI1>::value_type, |
4d16bdbb | 475 | typename iterator_traits<_BI2>::value_type>) |
285b36d6 | 476 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b SW |
477 | |
478 | typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal; | |
884a757a PC |
479 | return std::__copy_backward_input_normal_iterator(__first, __last, __result, |
480 | __Normal()); | |
02d92e3b SW |
481 | } |
482 | ||
02d92e3b | 483 | |
1b4a6975 PE |
484 | /** |
485 | * @brief Fills the range [first,last) with copies of value. | |
486 | * @param first A forward iterator. | |
487 | * @param last A forward iterator. | |
488 | * @param value A reference-to-const of arbitrary type. | |
489 | * @return Nothing. | |
490 | * | |
491 | * This function fills a range with copies of the same value. For one-byte | |
492 | * types filling contiguous areas of memory, this becomes an inline call to | |
493 | * @c memset. | |
494 | */ | |
08addde6 | 495 | template<typename _ForwardIterator, typename _Tp> |
02d92e3b | 496 | void |
08addde6 | 497 | fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) |
02d92e3b SW |
498 | { |
499 | // concept requirements | |
3d7c150e | 500 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>) |
285b36d6 | 501 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b SW |
502 | |
503 | for ( ; __first != __last; ++__first) | |
504 | *__first = __value; | |
505 | } | |
506 | ||
1b4a6975 PE |
507 | /** |
508 | * @brief Fills the range [first,first+n) with copies of value. | |
509 | * @param first An output iterator. | |
510 | * @param n The count of copies to perform. | |
511 | * @param value A reference-to-const of arbitrary type. | |
512 | * @return The iterator at first+n. | |
513 | * | |
514 | * This function fills a range with copies of the same value. For one-byte | |
515 | * types filling contiguous areas of memory, this becomes an inline call to | |
516 | * @c memset. | |
517 | */ | |
08addde6 PE |
518 | template<typename _OutputIterator, typename _Size, typename _Tp> |
519 | _OutputIterator | |
520 | fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) | |
02d92e3b SW |
521 | { |
522 | // concept requirements | |
3d7c150e | 523 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,_Tp>) |
02d92e3b SW |
524 | |
525 | for ( ; __n > 0; --__n, ++__first) | |
526 | *__first = __value; | |
527 | return __first; | |
528 | } | |
529 | ||
530 | // Specialization: for one-byte types we can use memset. | |
02d92e3b SW |
531 | inline void |
532 | fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c) | |
533 | { | |
285b36d6 | 534 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 535 | unsigned char __tmp = __c; |
884a757a | 536 | std::memset(__first, __tmp, __last - __first); |
725dc051 | 537 | } |
725dc051 | 538 | |
02d92e3b SW |
539 | inline void |
540 | fill(signed char* __first, signed char* __last, const signed char& __c) | |
541 | { | |
285b36d6 | 542 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 543 | signed char __tmp = __c; |
884a757a | 544 | std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first); |
725dc051 | 545 | } |
30a20a1e | 546 | |
02d92e3b SW |
547 | inline void |
548 | fill(char* __first, char* __last, const char& __c) | |
549 | { | |
285b36d6 | 550 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 551 | char __tmp = __c; |
884a757a | 552 | std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first); |
725dc051 | 553 | } |
725dc051 | 554 | |
02d92e3b SW |
555 | template<typename _Size> |
556 | inline unsigned char* | |
557 | fill_n(unsigned char* __first, _Size __n, const unsigned char& __c) | |
558 | { | |
884a757a | 559 | std::fill(__first, __first + __n, __c); |
02d92e3b SW |
560 | return __first + __n; |
561 | } | |
562 | ||
563 | template<typename _Size> | |
564 | inline signed char* | |
565 | fill_n(char* __first, _Size __n, const signed char& __c) | |
566 | { | |
884a757a | 567 | std::fill(__first, __first + __n, __c); |
02d92e3b SW |
568 | return __first + __n; |
569 | } | |
570 | ||
571 | template<typename _Size> | |
572 | inline char* | |
573 | fill_n(char* __first, _Size __n, const char& __c) | |
574 | { | |
884a757a | 575 | std::fill(__first, __first + __n, __c); |
02d92e3b SW |
576 | return __first + __n; |
577 | } | |
578 | ||
579 | ||
1b4a6975 PE |
580 | /** |
581 | * @brief Finds the places in ranges which don't match. | |
582 | * @param first1 An input iterator. | |
583 | * @param last1 An input iterator. | |
584 | * @param first2 An input iterator. | |
585 | * @return A pair of iterators pointing to the first mismatch. | |
586 | * | |
587 | * This compares the elements of two ranges using @c == and returns a pair | |
588 | * of iterators. The first iterator points into the first range, the | |
589 | * second iterator points into the second range, and the elements pointed | |
590 | * to by the iterators are not equal. | |
591 | */ | |
08addde6 PE |
592 | template<typename _InputIterator1, typename _InputIterator2> |
593 | pair<_InputIterator1, _InputIterator2> | |
594 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, | |
595 | _InputIterator2 __first2) | |
02d92e3b SW |
596 | { |
597 | // concept requirements | |
3d7c150e BK |
598 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
599 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
600 | __glibcxx_function_requires(_EqualityComparableConcept< | |
08addde6 | 601 | typename iterator_traits<_InputIterator1>::value_type>) |
3d7c150e | 602 | __glibcxx_function_requires(_EqualityComparableConcept< |
08addde6 | 603 | typename iterator_traits<_InputIterator2>::value_type>) |
285b36d6 | 604 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b | 605 | |
08addde6 PE |
606 | while (__first1 != __last1 && *__first1 == *__first2) |
607 | { | |
46c4e5d6 BK |
608 | ++__first1; |
609 | ++__first2; | |
08addde6 | 610 | } |
369b78b0 | 611 | return pair<_InputIterator1, _InputIterator2>(__first1, __first2); |
02d92e3b SW |
612 | } |
613 | ||
1b4a6975 PE |
614 | /** |
615 | * @brief Finds the places in ranges which don't match. | |
616 | * @param first1 An input iterator. | |
617 | * @param last1 An input iterator. | |
618 | * @param first2 An input iterator. | |
619 | * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. | |
620 | * @return A pair of iterators pointing to the first mismatch. | |
621 | * | |
622 | * This compares the elements of two ranges using the binary_pred | |
623 | * parameter, and returns a pair | |
624 | * of iterators. The first iterator points into the first range, the | |
625 | * second iterator points into the second range, and the elements pointed | |
626 | * to by the iterators are not equal. | |
627 | */ | |
08addde6 PE |
628 | template<typename _InputIterator1, typename _InputIterator2, typename _BinaryPredicate> |
629 | pair<_InputIterator1, _InputIterator2> | |
630 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, | |
631 | _InputIterator2 __first2, _BinaryPredicate __binary_pred) | |
02d92e3b SW |
632 | { |
633 | // concept requirements | |
3d7c150e BK |
634 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
635 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
285b36d6 | 636 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b | 637 | |
08addde6 PE |
638 | while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) |
639 | { | |
46c4e5d6 BK |
640 | ++__first1; |
641 | ++__first2; | |
08addde6 | 642 | } |
369b78b0 | 643 | return pair<_InputIterator1, _InputIterator2>(__first1, __first2); |
02d92e3b SW |
644 | } |
645 | ||
1b4a6975 PE |
646 | /** |
647 | * @brief Tests a range for element-wise equality. | |
648 | * @param first1 An input iterator. | |
649 | * @param last1 An input iterator. | |
650 | * @param first2 An input iterator. | |
651 | * @return A boolean true or false. | |
652 | * | |
653 | * This compares the elements of two ranges using @c == and returns true or | |
654 | * false depending on whether all of the corresponding elements of the | |
655 | * ranges are equal. | |
656 | */ | |
08addde6 | 657 | template<typename _InputIterator1, typename _InputIterator2> |
02d92e3b | 658 | inline bool |
08addde6 | 659 | equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) |
02d92e3b SW |
660 | { |
661 | // concept requirements | |
3d7c150e BK |
662 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
663 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
664 | __glibcxx_function_requires(_EqualOpConcept< | |
08addde6 PE |
665 | typename iterator_traits<_InputIterator1>::value_type, |
666 | typename iterator_traits<_InputIterator2>::value_type>) | |
285b36d6 | 667 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b SW |
668 | |
669 | for ( ; __first1 != __last1; ++__first1, ++__first2) | |
670 | if (!(*__first1 == *__first2)) | |
671 | return false; | |
725dc051 | 672 | return true; |
02d92e3b SW |
673 | } |
674 | ||
1b4a6975 PE |
675 | /** |
676 | * @brief Tests a range for element-wise equality. | |
677 | * @param first1 An input iterator. | |
678 | * @param last1 An input iterator. | |
679 | * @param first2 An input iterator. | |
680 | * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. | |
681 | * @return A boolean true or false. | |
682 | * | |
683 | * This compares the elements of two ranges using the binary_pred | |
684 | * parameter, and returns true or | |
685 | * false depending on whether all of the corresponding elements of the | |
686 | * ranges are equal. | |
687 | */ | |
08addde6 | 688 | template<typename _InputIterator1, typename _InputIterator2, typename _BinaryPredicate> |
02d92e3b | 689 | inline bool |
08addde6 PE |
690 | equal(_InputIterator1 __first1, _InputIterator1 __last1, |
691 | _InputIterator2 __first2, | |
02d92e3b SW |
692 | _BinaryPredicate __binary_pred) |
693 | { | |
694 | // concept requirements | |
3d7c150e BK |
695 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
696 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
285b36d6 | 697 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b SW |
698 | |
699 | for ( ; __first1 != __last1; ++__first1, ++__first2) | |
700 | if (!__binary_pred(*__first1, *__first2)) | |
701 | return false; | |
725dc051 | 702 | return true; |
02d92e3b SW |
703 | } |
704 | ||
1b4a6975 PE |
705 | /** |
706 | * @brief Performs "dictionary" comparison on ranges. | |
707 | * @param first1 An input iterator. | |
708 | * @param last1 An input iterator. | |
709 | * @param first2 An input iterator. | |
710 | * @param last2 An input iterator. | |
711 | * @return A boolean true or false. | |
712 | * | |
713 | * "Returns true if the sequence of elements defined by the range | |
714 | * [first1,last1) is lexicographically less than the sequence of elements | |
715 | * defined by the range [first2,last2). Returns false otherwise." | |
716 | * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, | |
717 | * then this is an inline call to @c memcmp. | |
718 | */ | |
08addde6 | 719 | template<typename _InputIterator1, typename _InputIterator2> |
02d92e3b | 720 | bool |
08addde6 PE |
721 | lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, |
722 | _InputIterator2 __first2, _InputIterator2 __last2) | |
02d92e3b SW |
723 | { |
724 | // concept requirements | |
3d7c150e BK |
725 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
726 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
727 | __glibcxx_function_requires(_LessThanComparableConcept< | |
08addde6 | 728 | typename iterator_traits<_InputIterator1>::value_type>) |
3d7c150e | 729 | __glibcxx_function_requires(_LessThanComparableConcept< |
08addde6 | 730 | typename iterator_traits<_InputIterator2>::value_type>) |
285b36d6 BK |
731 | __glibcxx_requires_valid_range(__first1, __last1); |
732 | __glibcxx_requires_valid_range(__first2, __last2); | |
02d92e3b | 733 | |
46c4e5d6 BK |
734 | for (;__first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) |
735 | { | |
736 | if (*__first1 < *__first2) | |
737 | return true; | |
738 | if (*__first2 < *__first1) | |
739 | return false; | |
740 | } | |
02d92e3b SW |
741 | return __first1 == __last1 && __first2 != __last2; |
742 | } | |
743 | ||
1b4a6975 PE |
744 | /** |
745 | * @brief Performs "dictionary" comparison on ranges. | |
746 | * @param first1 An input iterator. | |
747 | * @param last1 An input iterator. | |
748 | * @param first2 An input iterator. | |
749 | * @param last2 An input iterator. | |
750 | * @param comp A @link s20_3_3_comparisons comparison functor@endlink. | |
751 | * @return A boolean true or false. | |
752 | * | |
753 | * The same as the four-parameter @c lexigraphical_compare, but uses the | |
754 | * comp parameter instead of @c <. | |
755 | */ | |
08addde6 | 756 | template<typename _InputIterator1, typename _InputIterator2, typename _Compare> |
02d92e3b | 757 | bool |
08addde6 PE |
758 | lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, |
759 | _InputIterator2 __first2, _InputIterator2 __last2, | |
02d92e3b SW |
760 | _Compare __comp) |
761 | { | |
762 | // concept requirements | |
3d7c150e BK |
763 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
764 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
285b36d6 BK |
765 | __glibcxx_requires_valid_range(__first1, __last1); |
766 | __glibcxx_requires_valid_range(__first2, __last2); | |
02d92e3b SW |
767 | |
768 | for ( ; __first1 != __last1 && __first2 != __last2 | |
46c4e5d6 BK |
769 | ; ++__first1, ++__first2) |
770 | { | |
771 | if (__comp(*__first1, *__first2)) | |
772 | return true; | |
773 | if (__comp(*__first2, *__first1)) | |
774 | return false; | |
775 | } | |
02d92e3b SW |
776 | return __first1 == __last1 && __first2 != __last2; |
777 | } | |
778 | ||
779 | inline bool | |
46c4e5d6 BK |
780 | lexicographical_compare(const unsigned char* __first1, |
781 | const unsigned char* __last1, | |
782 | const unsigned char* __first2, | |
783 | const unsigned char* __last2) | |
02d92e3b | 784 | { |
285b36d6 BK |
785 | __glibcxx_requires_valid_range(__first1, __last1); |
786 | __glibcxx_requires_valid_range(__first2, __last2); | |
787 | ||
02d92e3b SW |
788 | const size_t __len1 = __last1 - __first1; |
789 | const size_t __len2 = __last2 - __first2; | |
884a757a | 790 | const int __result = std::memcmp(__first1, __first2, std::min(__len1, __len2)); |
02d92e3b | 791 | return __result != 0 ? __result < 0 : __len1 < __len2; |
725dc051 | 792 | } |
02d92e3b SW |
793 | |
794 | inline bool | |
795 | lexicographical_compare(const char* __first1, const char* __last1, | |
796 | const char* __first2, const char* __last2) | |
797 | { | |
285b36d6 BK |
798 | __glibcxx_requires_valid_range(__first1, __last1); |
799 | __glibcxx_requires_valid_range(__first2, __last2); | |
800 | ||
725dc051 | 801 | #if CHAR_MAX == SCHAR_MAX |
884a757a PC |
802 | return std::lexicographical_compare((const signed char*) __first1, |
803 | (const signed char*) __last1, | |
804 | (const signed char*) __first2, | |
805 | (const signed char*) __last2); | |
725dc051 | 806 | #else /* CHAR_MAX == SCHAR_MAX */ |
884a757a PC |
807 | return std::lexicographical_compare((const unsigned char*) __first1, |
808 | (const unsigned char*) __last1, | |
809 | (const unsigned char*) __first2, | |
810 | (const unsigned char*) __last2); | |
725dc051 | 811 | #endif /* CHAR_MAX == SCHAR_MAX */ |
725dc051 | 812 | } |
02d92e3b | 813 | |
d53d7f6e | 814 | } // namespace std |
725dc051 | 815 | |
46c4e5d6 | 816 | #endif |