STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Functions
Non-Mutating
Algorithms

Functions

namespace std _GLIBCXX_VISIBILITY (default)
 

Detailed Description

Function Documentation

namespace std _GLIBCXX_VISIBILITY ( default  )

Swaps the contents of two iterators.

Parameters
__aAn iterator.
__bAnother iterator.
Returns
Nothing.

This function swaps the values pointed to by two iterators, not the iterators themselves.

Swap the elements of two sequences.

Parameters
__first1A forward iterator.
__last1A forward iterator.
__first2A forward iterator.
Returns
An iterator equal to first2+(last1-first1).

Swaps each element in the range [first1,last1) with the corresponding element in the range [first2,(last1-first1)). The ranges must not overlap.

This does what you think it does.

Parameters
__aA thing of arbitrary type.
__bAnother thing of arbitrary type.
Returns
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.

This does what you think it does.

Parameters
__aA thing of arbitrary type.
__bAnother thing of arbitrary type.
Returns
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.

This does what you think it does.

Parameters
__aA thing of arbitrary type.
__bAnother thing of arbitrary type.
__compA comparison functor.
Returns
The lesser of the parameters.

This will work on temporary expressions, since they are only evaluated once, unlike a preprocessor macro.

This does what you think it does.

Parameters
__aA thing of arbitrary type.
__bAnother thing of arbitrary type.
__compA comparison functor.
Returns
The greater of the parameters.

This will work on temporary expressions, since they are only evaluated once, unlike a preprocessor macro.

Copies the range [first,last) into result.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
Returns
result + (first - last)

This inline function will boil down to a call to memmove whenever possible. Failing that, if random access iterators are passed, then the loop count will be known (and therefore a candidate for compiler optimizations such as unrolling). Result may not be contained within [first,last); the copy_backward function should be used instead.

Note that the end of the output range is permitted to be contained within [first,last).

Copies the range [first,last) into result.

Parameters
__firstA bidirectional iterator.
__lastA bidirectional iterator.
__resultA bidirectional iterator.
Returns
result - (first - last)

The function has the same effect as copy, but starts at the end of the range and works its way to the start, returning the start of the result. This inline function will boil down to a call to memmove whenever possible. Failing that, if random access iterators are passed, then the loop count will be known (and therefore a candidate for compiler optimizations such as unrolling).

Result may not be in the range (first,last]. Use copy instead. Note that the start of the output range may overlap [first,last).

Fills the range [first,last) with copies of value.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__valueA reference-to-const of arbitrary type.
Returns
Nothing.

This function fills a range with copies of the same value. For char types filling contiguous areas of memory, this becomes an inline call to memset or wmemset.

Fills the range [first,first+n) with copies of value.

Parameters
__firstAn output iterator.
__nThe count of copies to perform.
__valueA reference-to-const of arbitrary type.
Returns
The iterator at first+n.

This function fills a range with copies of the same value. For char types filling contiguous areas of memory, this becomes an inline call to memset or @ wmemset.

_GLIBCXX_RESOLVE_LIB_DEFECTS DR 865. More algorithms that throw away information

Finds the first position in which val could be inserted without changing the ordering.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
Returns
An iterator pointing to the first element not less than val, or end() if every element is less than val.

This is a helper function for the sort routines and for random.tcc.

Tests a range for element-wise equality.

Parameters
__first1An input iterator.
__last1An input iterator.
__first2An input iterator.
Returns
A boolean true or false.

This compares the elements of two ranges using == and returns true or false depending on whether all of the corresponding elements of the ranges are equal.

Tests a range for element-wise equality.

Parameters
__first1An input iterator.
__last1An input iterator.
__first2An input iterator.
__binary_predA binary predicate functor.
Returns
A boolean true or false.

This compares the elements of two ranges using the binary_pred parameter, and returns true or false depending on whether all of the corresponding elements of the ranges are equal.

Performs dictionary comparison on ranges.

Parameters
__first1An input iterator.
__last1An input iterator.
__first2An input iterator.
__last2An input iterator.
Returns
A boolean true or false.

Returns true if the sequence of elements defined by the range [first1,last1) is lexicographically less than the sequence of elements defined by the range [first2,last2). Returns false otherwise. (Quoted from [25.3.8]/1.) If the iterators are all character pointers, then this is an inline call to memcmp.

Performs dictionary comparison on ranges.

Parameters
__first1An input iterator.
__last1An input iterator.
__first2An input iterator.
__last2An input iterator.
__compA comparison functor.
Returns
A boolean true or false.

The same as the four-parameter lexicographical_compare, but uses the comp parameter instead of <.

Finds the places in ranges which don't match.

Parameters
__first1An input iterator.
__last1An input iterator.
__first2An input iterator.
Returns
A pair of iterators pointing to the first mismatch.

This compares the elements of two ranges using == and returns a pair of iterators. The first iterator points into the first range, the second iterator points into the second range, and the elements pointed to by the iterators are not equal.

Finds the places in ranges which don't match.

Parameters
__first1An input iterator.
__last1An input iterator.
__first2An input iterator.
__binary_predA binary predicate functor.
Returns
A pair of iterators pointing to the first mismatch.

This compares the elements of two ranges using the binary_pred parameter, and returns a pair of iterators. The first iterator points into the first range, the second iterator points into the second range, and the elements pointed to by the iterators are not equal.

73 {
74 _GLIBCXX_BEGIN_NAMESPACE_VERSION
75 
76 #if __cplusplus < 201103L
77  // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
78  // nutshell, we are partially implementing the resolution of DR 187,
79  // when it's safe, i.e., the value_types are equal.
80  template<bool _BoolType>
81  struct __iter_swap
82  {
83  template<typename _ForwardIterator1, typename _ForwardIterator2>
84  static void
85  iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
86  {
87  typedef typename iterator_traits<_ForwardIterator1>::value_type
88  _ValueType1;
89  _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);
90  *__a = _GLIBCXX_MOVE(*__b);
91  *__b = _GLIBCXX_MOVE(__tmp);
92  }
93  };
94 
95  template<>
96  struct __iter_swap<true>
97  {
98  template<typename _ForwardIterator1, typename _ForwardIterator2>
99  static void
100  iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
101  {
102  swap(*__a, *__b);
103  }
104  };
105 #endif
106 
117  template<typename _ForwardIterator1, typename _ForwardIterator2>
118  inline void
119  iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
120  {
121  // concept requirements
122  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
123  _ForwardIterator1>)
124  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
125  _ForwardIterator2>)
126 
127 #if __cplusplus < 201103L
128  typedef typename iterator_traits<_ForwardIterator1>::value_type
129  _ValueType1;
130  typedef typename iterator_traits<_ForwardIterator2>::value_type
131  _ValueType2;
132 
133  __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
134  _ValueType2>)
135  __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
136  _ValueType1>)
137 
138  typedef typename iterator_traits<_ForwardIterator1>::reference
139  _ReferenceType1;
140  typedef typename iterator_traits<_ForwardIterator2>::reference
141  _ReferenceType2;
142  std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
143  && __are_same<_ValueType1&, _ReferenceType1>::__value
144  && __are_same<_ValueType2&, _ReferenceType2>::__value>::
145  iter_swap(__a, __b);
146 #else
147  swap(*__a, *__b);
148 #endif
149  }
150 
163  template<typename _ForwardIterator1, typename _ForwardIterator2>
164  _ForwardIterator2
165  swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
166  _ForwardIterator2 __first2)
167  {
168  // concept requirements
169  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
170  _ForwardIterator1>)
171  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
172  _ForwardIterator2>)
173  __glibcxx_requires_valid_range(__first1, __last1);
174 
175  for (; __first1 != __last1; ++__first1, ++__first2)
176  std::iter_swap(__first1, __first2);
177  return __first2;
178  }
179 
191  template<typename _Tp>
192  inline const _Tp&
193  min(const _Tp& __a, const _Tp& __b)
194  {
195  // concept requirements
196  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
197  //return __b < __a ? __b : __a;
198  if (__b < __a)
199  return __b;
200  return __a;
201  }
202 
214  template<typename _Tp>
215  inline const _Tp&
216  max(const _Tp& __a, const _Tp& __b)
217  {
218  // concept requirements
219  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
220  //return __a < __b ? __b : __a;
221  if (__a < __b)
222  return __b;
223  return __a;
224  }
225 
237  template<typename _Tp, typename _Compare>
238  inline const _Tp&
239  min(const _Tp& __a, const _Tp& __b, _Compare __comp)
240  {
241  //return __comp(__b, __a) ? __b : __a;
242  if (__comp(__b, __a))
243  return __b;
244  return __a;
245  }
246 
258  template<typename _Tp, typename _Compare>
259  inline const _Tp&
260  max(const _Tp& __a, const _Tp& __b, _Compare __comp)
261  {
262  //return __comp(__a, __b) ? __b : __a;
263  if (__comp(__a, __b))
264  return __b;
265  return __a;
266  }
267 
268  // If _Iterator is a __normal_iterator return its base (a plain pointer,
269  // normally) otherwise return it untouched. See copy, fill, ...
270  template<typename _Iterator>
271  struct _Niter_base
272  : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>
273  { };
274 
275  template<typename _Iterator>
276  inline typename _Niter_base<_Iterator>::iterator_type
277  __niter_base(_Iterator __it)
278  { return std::_Niter_base<_Iterator>::_S_base(__it); }
279 
280  // Likewise, for move_iterator.
281  template<typename _Iterator>
282  struct _Miter_base
283  : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value>
284  { };
285 
286  template<typename _Iterator>
287  inline typename _Miter_base<_Iterator>::iterator_type
288  __miter_base(_Iterator __it)
289  { return std::_Miter_base<_Iterator>::_S_base(__it); }
290 
291  // All of these auxiliary structs serve two purposes. (1) Replace
292  // calls to copy with memmove whenever possible. (Memmove, not memcpy,
293  // because the input and output ranges are permitted to overlap.)
294  // (2) If we're using random access iterators, then write the loop as
295  // a for loop with an explicit count.
296 
297  template<bool, bool, typename>
298  struct __copy_move
299  {
300  template<typename _II, typename _OI>
301  static _OI
302  __copy_m(_II __first, _II __last, _OI __result)
303  {
304  for (; __first != __last; ++__result, ++__first)
305  *__result = *__first;
306  return __result;
307  }
308  };
309 
310 #if __cplusplus >= 201103L
311  template<typename _Category>
312  struct __copy_move<true, false, _Category>
313  {
314  template<typename _II, typename _OI>
315  static _OI
316  __copy_m(_II __first, _II __last, _OI __result)
317  {
318  for (; __first != __last; ++__result, ++__first)
319  *__result = std::move(*__first);
320  return __result;
321  }
322  };
323 #endif
324 
325  template<>
326  struct __copy_move<false, false, random_access_iterator_tag>
327  {
328  template<typename _II, typename _OI>
329  static _OI
330  __copy_m(_II __first, _II __last, _OI __result)
331  {
332  typedef typename iterator_traits<_II>::difference_type _Distance;
333  for(_Distance __n = __last - __first; __n > 0; --__n)
334  {
335  *__result = *__first;
336  ++__first;
337  ++__result;
338  }
339  return __result;
340  }
341  };
342 
343 #if __cplusplus >= 201103L
344  template<>
345  struct __copy_move<true, false, random_access_iterator_tag>
346  {
347  template<typename _II, typename _OI>
348  static _OI
349  __copy_m(_II __first, _II __last, _OI __result)
350  {
351  typedef typename iterator_traits<_II>::difference_type _Distance;
352  for(_Distance __n = __last - __first; __n > 0; --__n)
353  {
354  *__result = std::move(*__first);
355  ++__first;
356  ++__result;
357  }
358  return __result;
359  }
360  };
361 #endif
362 
363  template<bool _IsMove>
364  struct __copy_move<_IsMove, true, random_access_iterator_tag>
365  {
366  template<typename _Tp>
367  static _Tp*
368  __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
369  {
370  const ptrdiff_t _Num = __last - __first;
371  if (_Num)
372  __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
373  return __result + _Num;
374  }
375  };
376 
377  template<bool _IsMove, typename _II, typename _OI>
378  inline _OI
379  __copy_move_a(_II __first, _II __last, _OI __result)
380  {
381  typedef typename iterator_traits<_II>::value_type _ValueTypeI;
382  typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
383  typedef typename iterator_traits<_II>::iterator_category _Category;
384  const bool __simple = (__is_trivial(_ValueTypeI)
385  && __is_pointer<_II>::__value
386  && __is_pointer<_OI>::__value
387  && __are_same<_ValueTypeI, _ValueTypeO>::__value);
388 
389  return std::__copy_move<_IsMove, __simple,
390  _Category>::__copy_m(__first, __last, __result);
391  }
392 
393  // Helpers for streambuf iterators (either istream or ostream).
394  // NB: avoid including <iosfwd>, relatively large.
395  template<typename _CharT>
396  struct char_traits;
397 
398  template<typename _CharT, typename _Traits>
399  class istreambuf_iterator;
400 
401  template<typename _CharT, typename _Traits>
402  class ostreambuf_iterator;
403 
404  template<bool _IsMove, typename _CharT>
405  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
406  ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
407  __copy_move_a2(_CharT*, _CharT*,
408  ostreambuf_iterator<_CharT, char_traits<_CharT> >);
409 
410  template<bool _IsMove, typename _CharT>
411  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
412  ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
413  __copy_move_a2(const _CharT*, const _CharT*,
414  ostreambuf_iterator<_CharT, char_traits<_CharT> >);
415 
416  template<bool _IsMove, typename _CharT>
417  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
418  _CharT*>::__type
419  __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
420  istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
421 
422  template<bool _IsMove, typename _II, typename _OI>
423  inline _OI
424  __copy_move_a2(_II __first, _II __last, _OI __result)
425  {
426  return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
427  std::__niter_base(__last),
428  std::__niter_base(__result)));
429  }
430 
448  template<typename _II, typename _OI>
449  inline _OI
450  copy(_II __first, _II __last, _OI __result)
451  {
452  // concept requirements
453  __glibcxx_function_requires(_InputIteratorConcept<_II>)
454  __glibcxx_function_requires(_OutputIteratorConcept<_OI,
455  typename iterator_traits<_II>::value_type>)
456  __glibcxx_requires_valid_range(__first, __last);
457 
458  return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
459  (std::__miter_base(__first), std::__miter_base(__last),
460  __result));
461  }
462 
463 #if __cplusplus >= 201103L
464 
481  template<typename _II, typename _OI>
482  inline _OI
483  move(_II __first, _II __last, _OI __result)
484  {
485  // concept requirements
486  __glibcxx_function_requires(_InputIteratorConcept<_II>)
487  __glibcxx_function_requires(_OutputIteratorConcept<_OI,
488  typename iterator_traits<_II>::value_type>)
489  __glibcxx_requires_valid_range(__first, __last);
490 
491  return std::__copy_move_a2<true>(std::__miter_base(__first),
492  std::__miter_base(__last), __result);
493  }
494 
495 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
496 #else
497 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
498 #endif
499 
500  template<bool, bool, typename>
501  struct __copy_move_backward
502  {
503  template<typename _BI1, typename _BI2>
504  static _BI2
505  __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
506  {
507  while (__first != __last)
508  *--__result = *--__last;
509  return __result;
510  }
511  };
512 
513 #if __cplusplus >= 201103L
514  template<typename _Category>
515  struct __copy_move_backward<true, false, _Category>
516  {
517  template<typename _BI1, typename _BI2>
518  static _BI2
519  __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
520  {
521  while (__first != __last)
522  *--__result = std::move(*--__last);
523  return __result;
524  }
525  };
526 #endif
527 
528  template<>
529  struct __copy_move_backward<false, false, random_access_iterator_tag>
530  {
531  template<typename _BI1, typename _BI2>
532  static _BI2
533  __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
534  {
535  typename iterator_traits<_BI1>::difference_type __n;
536  for (__n = __last - __first; __n > 0; --__n)
537  *--__result = *--__last;
538  return __result;
539  }
540  };
541 
542 #if __cplusplus >= 201103L
543  template<>
544  struct __copy_move_backward<true, false, random_access_iterator_tag>
545  {
546  template<typename _BI1, typename _BI2>
547  static _BI2
548  __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
549  {
550  typename iterator_traits<_BI1>::difference_type __n;
551  for (__n = __last - __first; __n > 0; --__n)
552  *--__result = std::move(*--__last);
553  return __result;
554  }
555  };
556 #endif
557 
558  template<bool _IsMove>
559  struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
560  {
561  template<typename _Tp>
562  static _Tp*
563  __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
564  {
565  const ptrdiff_t _Num = __last - __first;
566  if (_Num)
567  __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
568  return __result - _Num;
569  }
570  };
571 
572  template<bool _IsMove, typename _BI1, typename _BI2>
573  inline _BI2
574  __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
575  {
576  typedef typename iterator_traits<_BI1>::value_type _ValueType1;
577  typedef typename iterator_traits<_BI2>::value_type _ValueType2;
578  typedef typename iterator_traits<_BI1>::iterator_category _Category;
579  const bool __simple = (__is_trivial(_ValueType1)
580  && __is_pointer<_BI1>::__value
581  && __is_pointer<_BI2>::__value
582  && __are_same<_ValueType1, _ValueType2>::__value);
583 
584  return std::__copy_move_backward<_IsMove, __simple,
585  _Category>::__copy_move_b(__first,
586  __last,
587  __result);
588  }
589 
590  template<bool _IsMove, typename _BI1, typename _BI2>
591  inline _BI2
592  __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
593  {
594  return _BI2(std::__copy_move_backward_a<_IsMove>
595  (std::__niter_base(__first), std::__niter_base(__last),
596  std::__niter_base(__result)));
597  }
598 
617  template<typename _BI1, typename _BI2>
618  inline _BI2
619  copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
620  {
621  // concept requirements
622  __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
623  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
624  __glibcxx_function_requires(_ConvertibleConcept<
625  typename iterator_traits<_BI1>::value_type,
626  typename iterator_traits<_BI2>::value_type>)
627  __glibcxx_requires_valid_range(__first, __last);
628 
629  return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
630  (std::__miter_base(__first), std::__miter_base(__last),
631  __result));
632  }
633 
634 #if __cplusplus >= 201103L
635 
653  template<typename _BI1, typename _BI2>
654  inline _BI2
655  move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
656  {
657  // concept requirements
658  __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
659  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
660  __glibcxx_function_requires(_ConvertibleConcept<
661  typename iterator_traits<_BI1>::value_type,
662  typename iterator_traits<_BI2>::value_type>)
663  __glibcxx_requires_valid_range(__first, __last);
664 
665  return std::__copy_move_backward_a2<true>(std::__miter_base(__first),
666  std::__miter_base(__last),
667  __result);
668  }
669 
670 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
671 #else
672 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
673 #endif
674 
675  template<typename _ForwardIterator, typename _Tp>
676  inline typename
677  __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
678  __fill_a(_ForwardIterator __first, _ForwardIterator __last,
679  const _Tp& __value)
680  {
681  for (; __first != __last; ++__first)
682  *__first = __value;
683  }
684 
685  template<typename _ForwardIterator, typename _Tp>
686  inline typename
687  __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
688  __fill_a(_ForwardIterator __first, _ForwardIterator __last,
689  const _Tp& __value)
690  {
691  const _Tp __tmp = __value;
692  for (; __first != __last; ++__first)
693  *__first = __tmp;
694  }
695 
696  // Specialization: for char types we can use memset.
697  template<typename _Tp>
698  inline typename
699  __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
700  __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
701  {
702  const _Tp __tmp = __c;
703  __builtin_memset(__first, static_cast<unsigned char>(__tmp),
704  __last - __first);
705  }
706 
719  template<typename _ForwardIterator, typename _Tp>
720  inline void
721  fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
722  {
723  // concept requirements
724  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
725  _ForwardIterator>)
726  __glibcxx_requires_valid_range(__first, __last);
727 
728  std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),
729  __value);
730  }
731 
732  template<typename _OutputIterator, typename _Size, typename _Tp>
733  inline typename
734  __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
735  __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
736  {
737  for (__decltype(__n + 0) __niter = __n;
738  __niter > 0; --__niter, ++__first)
739  *__first = __value;
740  return __first;
741  }
742 
743  template<typename _OutputIterator, typename _Size, typename _Tp>
744  inline typename
745  __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
746  __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
747  {
748  const _Tp __tmp = __value;
749  for (__decltype(__n + 0) __niter = __n;
750  __niter > 0; --__niter, ++__first)
751  *__first = __tmp;
752  return __first;
753  }
754 
755  template<typename _Size, typename _Tp>
756  inline typename
757  __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
758  __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
759  {
760  std::__fill_a(__first, __first + __n, __c);
761  return __first + __n;
762  }
763 
779  template<typename _OI, typename _Size, typename _Tp>
780  inline _OI
781  fill_n(_OI __first, _Size __n, const _Tp& __value)
782  {
783  // concept requirements
784  __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
785 
786  return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
787  }
788 
789  template<bool _BoolType>
790  struct __equal
791  {
792  template<typename _II1, typename _II2>
793  static bool
794  equal(_II1 __first1, _II1 __last1, _II2 __first2)
795  {
796  for (; __first1 != __last1; ++__first1, ++__first2)
797  if (!(*__first1 == *__first2))
798  return false;
799  return true;
800  }
801  };
802 
803  template<>
804  struct __equal<true>
805  {
806  template<typename _Tp>
807  static bool
808  equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
809  {
810  return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
811  * (__last1 - __first1));
812  }
813  };
814 
815  template<typename _II1, typename _II2>
816  inline bool
817  __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
818  {
819  typedef typename iterator_traits<_II1>::value_type _ValueType1;
820  typedef typename iterator_traits<_II2>::value_type _ValueType2;
821  const bool __simple = ((__is_integer<_ValueType1>::__value
822  || __is_pointer<_ValueType1>::__value)
823  && __is_pointer<_II1>::__value
824  && __is_pointer<_II2>::__value
825  && __are_same<_ValueType1, _ValueType2>::__value);
826 
827  return std::__equal<__simple>::equal(__first1, __last1, __first2);
828  }
829 
830 
831  template<typename, typename>
832  struct __lc_rai
833  {
834  template<typename _II1, typename _II2>
835  static _II1
836  __newlast1(_II1, _II1 __last1, _II2, _II2)
837  { return __last1; }
838 
839  template<typename _II>
840  static bool
841  __cnd2(_II __first, _II __last)
842  { return __first != __last; }
843  };
844 
845  template<>
846  struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
847  {
848  template<typename _RAI1, typename _RAI2>
849  static _RAI1
850  __newlast1(_RAI1 __first1, _RAI1 __last1,
851  _RAI2 __first2, _RAI2 __last2)
852  {
853  const typename iterator_traits<_RAI1>::difference_type
854  __diff1 = __last1 - __first1;
855  const typename iterator_traits<_RAI2>::difference_type
856  __diff2 = __last2 - __first2;
857  return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
858  }
859 
860  template<typename _RAI>
861  static bool
862  __cnd2(_RAI, _RAI)
863  { return true; }
864  };
865 
866  template<bool _BoolType>
867  struct __lexicographical_compare
868  {
869  template<typename _II1, typename _II2>
870  static bool __lc(_II1, _II1, _II2, _II2);
871  };
872 
873  template<bool _BoolType>
874  template<typename _II1, typename _II2>
875  bool
876  __lexicographical_compare<_BoolType>::
877  __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
878  {
879  typedef typename iterator_traits<_II1>::iterator_category _Category1;
880  typedef typename iterator_traits<_II2>::iterator_category _Category2;
881  typedef std::__lc_rai<_Category1, _Category2> __rai_type;
882 
883  __last1 = __rai_type::__newlast1(__first1, __last1,
884  __first2, __last2);
885  for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
886  ++__first1, ++__first2)
887  {
888  if (*__first1 < *__first2)
889  return true;
890  if (*__first2 < *__first1)
891  return false;
892  }
893  return __first1 == __last1 && __first2 != __last2;
894  }
895 
896  template<>
897  struct __lexicographical_compare<true>
898  {
899  template<typename _Tp, typename _Up>
900  static bool
901  __lc(const _Tp* __first1, const _Tp* __last1,
902  const _Up* __first2, const _Up* __last2)
903  {
904  const size_t __len1 = __last1 - __first1;
905  const size_t __len2 = __last2 - __first2;
906  const int __result = __builtin_memcmp(__first1, __first2,
907  std::min(__len1, __len2));
908  return __result != 0 ? __result < 0 : __len1 < __len2;
909  }
910  };
911 
912  template<typename _II1, typename _II2>
913  inline bool
914  __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
915  _II2 __first2, _II2 __last2)
916  {
917  typedef typename iterator_traits<_II1>::value_type _ValueType1;
918  typedef typename iterator_traits<_II2>::value_type _ValueType2;
919  const bool __simple =
920  (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
921  && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
922  && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
923  && __is_pointer<_II1>::__value
924  && __is_pointer<_II2>::__value);
925 
926  return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
927  __first2, __last2);
928  }
929 
941  template<typename _ForwardIterator, typename _Tp>
942  _ForwardIterator
943  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
944  const _Tp& __val)
945  {
946 #ifdef _GLIBCXX_CONCEPT_CHECKS
947  typedef typename iterator_traits<_ForwardIterator>::value_type
948  _ValueType;
949 #endif
950  typedef typename iterator_traits<_ForwardIterator>::difference_type
951  _DistanceType;
952 
953  // concept requirements
954  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
955  __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
956  __glibcxx_requires_partitioned_lower(__first, __last, __val);
957 
958  _DistanceType __len = std::distance(__first, __last);
959 
960  while (__len > 0)
961  {
962  _DistanceType __half = __len >> 1;
963  _ForwardIterator __middle = __first;
964  std::advance(__middle, __half);
965  if (*__middle < __val)
966  {
967  __first = __middle;
968  ++__first;
969  __len = __len - __half - 1;
970  }
971  else
972  __len = __half;
973  }
974  return __first;
975  }
976 
978  // Precondition: __n > 0.
979  inline _GLIBCXX_CONSTEXPR int
980  __lg(int __n)
981  { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
982 
983  inline _GLIBCXX_CONSTEXPR unsigned
984  __lg(unsigned __n)
985  { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
986 
987  inline _GLIBCXX_CONSTEXPR long
988  __lg(long __n)
989  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
990 
991  inline _GLIBCXX_CONSTEXPR unsigned long
992  __lg(unsigned long __n)
993  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
994 
995  inline _GLIBCXX_CONSTEXPR long long
996  __lg(long long __n)
997  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
998 
999  inline _GLIBCXX_CONSTEXPR unsigned long long
1000  __lg(unsigned long long __n)
1001  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1002 
1003 _GLIBCXX_END_NAMESPACE_VERSION
1004 
1005 _GLIBCXX_BEGIN_NAMESPACE_ALGO
1006 
1019  template<typename _II1, typename _II2>
1020  inline bool
1021  equal(_II1 __first1, _II1 __last1, _II2 __first2)
1022  {
1023  // concept requirements
1024  __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1025  __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1026  __glibcxx_function_requires(_EqualOpConcept<
1027  typename iterator_traits<_II1>::value_type,
1028  typename iterator_traits<_II2>::value_type>)
1029  __glibcxx_requires_valid_range(__first1, __last1);
1030 
1031  return std::__equal_aux(std::__niter_base(__first1),
1032  std::__niter_base(__last1),
1033  std::__niter_base(__first2));
1034  }
1035 
1051  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1052  inline bool
1053  equal(_IIter1 __first1, _IIter1 __last1,
1054  _IIter2 __first2, _BinaryPredicate __binary_pred)
1055  {
1056  // concept requirements
1057  __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1058  __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1059  __glibcxx_requires_valid_range(__first1, __last1);
1060 
1061  for (; __first1 != __last1; ++__first1, ++__first2)
1062  if (!bool(__binary_pred(*__first1, *__first2)))
1063  return false;
1064  return true;
1065  }
1066 
1082  template<typename _II1, typename _II2>
1083  inline bool
1084  lexicographical_compare(_II1 __first1, _II1 __last1,
1085  _II2 __first2, _II2 __last2)
1086  {
1087 #ifdef _GLIBCXX_CONCEPT_CHECKS
1088  // concept requirements
1089  typedef typename iterator_traits<_II1>::value_type _ValueType1;
1090  typedef typename iterator_traits<_II2>::value_type _ValueType2;
1091 #endif
1092  __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1093  __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1094  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1095  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1096  __glibcxx_requires_valid_range(__first1, __last1);
1097  __glibcxx_requires_valid_range(__first2, __last2);
1098 
1099  return std::__lexicographical_compare_aux(std::__niter_base(__first1),
1100  std::__niter_base(__last1),
1101  std::__niter_base(__first2),
1102  std::__niter_base(__last2));
1103  }
1104 
1118  template<typename _II1, typename _II2, typename _Compare>
1119  bool
1120  lexicographical_compare(_II1 __first1, _II1 __last1,
1121  _II2 __first2, _II2 __last2, _Compare __comp)
1122  {
1123  typedef typename iterator_traits<_II1>::iterator_category _Category1;
1124  typedef typename iterator_traits<_II2>::iterator_category _Category2;
1125  typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1126 
1127  // concept requirements
1128  __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1129  __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1130  __glibcxx_requires_valid_range(__first1, __last1);
1131  __glibcxx_requires_valid_range(__first2, __last2);
1132 
1133  __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1134  for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1135  ++__first1, ++__first2)
1136  {
1137  if (__comp(*__first1, *__first2))
1138  return true;
1139  if (__comp(*__first2, *__first1))
1140  return false;
1141  }
1142  return __first1 == __last1 && __first2 != __last2;
1143  }
1144 
1158  template<typename _InputIterator1, typename _InputIterator2>
1159  pair<_InputIterator1, _InputIterator2>
1160  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1161  _InputIterator2 __first2)
1162  {
1163  // concept requirements
1164  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1165  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1166  __glibcxx_function_requires(_EqualOpConcept<
1167  typename iterator_traits<_InputIterator1>::value_type,
1168  typename iterator_traits<_InputIterator2>::value_type>)
1169  __glibcxx_requires_valid_range(__first1, __last1);
1170 
1171  while (__first1 != __last1 && *__first1 == *__first2)
1172  {
1173  ++__first1;
1174  ++__first2;
1175  }
1176  return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1177  }
1178 
1195  template<typename _InputIterator1, typename _InputIterator2,
1196  typename _BinaryPredicate>
1197  pair<_InputIterator1, _InputIterator2>
1198  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1199  _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1200  {
1201  // concept requirements
1202  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1203  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1204  __glibcxx_requires_valid_range(__first1, __last1);
1205 
1206  while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
1207  {
1208  ++__first1;
1209  ++__first2;
1210  }
1211  return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1212  }
1213 
1214 _GLIBCXX_END_NAMESPACE_ALGO
1215 } // namespace std
__glibcxx_requires_partitioned_lower
#define __glibcxx_requires_partitioned_lower(_First, _Last, _Value)
Definition: debug.h:71
__glibcxx_function_requires
#define __glibcxx_function_requires(...)
Definition: concept_check.h:47
_GLIBCXX_MOVE
#define _GLIBCXX_MOVE(__val)
Definition: move.h:145
false
#define false
Definition: stdbool.h:35
true
#define true
Definition: stdbool.h:34
__gnu_parallel::min
const _Tp & min(const _Tp &__a, const _Tp &__b)
Equivalent to std::min.
Definition: base.h:144
return
return(unsigned int) __res
__gnu_parallel::max
const _Tp & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Definition: base.h:150
ptrdiff_t
__PTRDIFF_TYPE__ ptrdiff_t
Definition: stddef.h:147
__glibcxx_requires_valid_range
#define __glibcxx_requires_valid_range(_First, _Last)
Definition: debug.h:65
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
Generated on Sat Jul 22 2017 14:42:45 for STLdoc by   doxygen 1.8.6