libstdc++-v3/include/bits/stl_algobase.h

   1 // Core algorithmic facilities -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  *
  28  * Copyright (c) 1994
  29  * Hewlett-Packard Company
  30  *
  31  * Permission to use, copy, modify, distribute and sell this software
  32  * and its documentation for any purpose is hereby granted without fee,
  33  * provided that the above copyright notice appear in all copies and
  34  * that both that copyright notice and this permission notice appear
  35  * in supporting documentation.  Hewlett-Packard Company makes no
  36  * representations about the suitability of this software for any
  37  * purpose.  It is provided "as is" without express or implied warranty.
  38  *
  39  *
  40  * Copyright (c) 1996-1998
  41  * Silicon Graphics Computer Systems, Inc.
  42  *
  43  * Permission to use, copy, modify, distribute and sell this software
  44  * and its documentation for any purpose is hereby granted without fee,
  45  * provided that the above copyright notice appear in all copies and
  46  * that both that copyright notice and this permission notice appear
  47  * in supporting documentation.  Silicon Graphics makes no
  48  * representations about the suitability of this software for any
  49  * purpose.  It is provided "as is" without express or implied warranty.
  50  */
  51
  52 /** @file stl_algobase.h
  53  *  This is an internal header file, included by other library headers.
  54  *  You should not attempt to use it directly.
  55  */
  56
  57 #ifndef _STL_ALGOBASE_H
  58 #define _STL_ALGOBASE_H 1
  59
  60 #include <bits/c++config.h>
  61 #include <cstddef>
  62 #include <bits/functexcept.h>
  63 #include <bits/cpp_type_traits.h>
  64 #include <ext/type_traits.h>
  65 #include <ext/numeric_traits.h>
  66 #include <bits/stl_pair.h>
  67 #include <bits/stl_iterator_base_types.h>
  68 #include <bits/stl_iterator_base_funcs.h>
  69 #include <bits/stl_iterator.h>
  70 #include <bits/concept_check.h>
  71 #include <debug/debug.h>
  72 #include <bits/move.h> // For std::swap and _GLIBCXX_MOVE
  73
  74 _GLIBCXX_BEGIN_NAMESPACE(std)
  75
  76   // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
  77   // nutshell, we are partially implementing the resolution of DR 187,
  78   // when it's safe, i.e., the value_types are equal.
  79   template<bool _BoolType>
  80     struct __iter_swap
  81     {
  82       template<typename _ForwardIterator1, typename _ForwardIterator2>
  83         static void
  84         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
  85         {
  86           typedef typename iterator_traits<_ForwardIterator1>::value_type
  87             _ValueType1;
  88           _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);
  89           *__a = _GLIBCXX_MOVE(*__b);
  90           *__b = _GLIBCXX_MOVE(__tmp);
  91         }
  92     };
  93
  94   template<>
  95     struct __iter_swap<true>
  96     {
  97       template<typename _ForwardIterator1, typename _ForwardIterator2>
  98         static void
  99         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
 100         {
 101           swap(*__a, *__b);
 102         }
 103     };
 104
 105   /**
 106    *  @brief Swaps the contents of two iterators.
 107    *  @ingroup mutating_algorithms
 108    *  @param  a  An iterator.
 109    *  @param  b  Another iterator.
 110    *  @return   Nothing.
 111    *
 112    *  This function swaps the values pointed to by two iterators, not the
 113    *  iterators themselves.
 114   */
 115   template<typename _ForwardIterator1, typename _ForwardIterator2>
 116     inline void
 117     iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
 118     {
 119       typedef typename iterator_traits<_ForwardIterator1>::value_type
 120         _ValueType1;
 121       typedef typename iterator_traits<_ForwardIterator2>::value_type
 122         _ValueType2;
 123
 124       // concept requirements
 125       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 126                                   _ForwardIterator1>)
 127       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 128                                   _ForwardIterator2>)
 129       __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
 130                                   _ValueType2>)
 131       __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
 132                                   _ValueType1>)
 133
 134       typedef typename iterator_traits<_ForwardIterator1>::reference
 135         _ReferenceType1;
 136       typedef typename iterator_traits<_ForwardIterator2>::reference
 137         _ReferenceType2;
 138       std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
 139         && __are_same<_ValueType1&, _ReferenceType1>::__value
 140         && __are_same<_ValueType2&, _ReferenceType2>::__value>::
 141         iter_swap(__a, __b);
 142     }
 143
 144   /**
 145    *  @brief Swap the elements of two sequences.
 146    *  @ingroup mutating_algorithms
 147    *  @param  first1  A forward iterator.
 148    *  @param  last1   A forward iterator.
 149    *  @param  first2  A forward iterator.
 150    *  @return   An iterator equal to @p first2+(last1-first1).
 151    *
 152    *  Swaps each element in the range @p [first1,last1) with the
 153    *  corresponding element in the range @p [first2,(last1-first1)).
 154    *  The ranges must not overlap.
 155   */
 156   template<typename _ForwardIterator1, typename _ForwardIterator2>
 157     _ForwardIterator2
 158     swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 159                 _ForwardIterator2 __first2)
 160     {
 161       // concept requirements
 162       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 163                                   _ForwardIterator1>)
 164       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 165                                   _ForwardIterator2>)
 166       __glibcxx_requires_valid_range(__first1, __last1);
 167
 168       for (; __first1 != __last1; ++__first1, ++__first2)
 169         std::iter_swap(__first1, __first2);
 170       return __first2;
 171     }
 172
 173   /**
 174    *  @brief This does what you think it does.
 175    *  @ingroup sorting_algorithms
 176    *  @param  a  A thing of arbitrary type.
 177    *  @param  b  Another thing of arbitrary type.
 178    *  @return   The lesser of the parameters.
 179    *
 180    *  This is the simple classic generic implementation.  It will work on
 181    *  temporary expressions, since they are only evaluated once, unlike a
 182    *  preprocessor macro.
 183   */
 184   template<typename _Tp>
 185     inline const _Tp&
 186     min(const _Tp& __a, const _Tp& __b)
 187     {
 188       // concept requirements
 189       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
 190       //return __b < __a ? __b : __a;
 191       if (__b < __a)
 192         return __b;
 193       return __a;
 194     }
 195
 196   /**
 197    *  @brief This does what you think it does.
 198    *  @ingroup sorting_algorithms
 199    *  @param  a  A thing of arbitrary type.
 200    *  @param  b  Another thing of arbitrary type.
 201    *  @return   The greater of the parameters.
 202    *
 203    *  This is the simple classic generic implementation.  It will work on
 204    *  temporary expressions, since they are only evaluated once, unlike a
 205    *  preprocessor macro.
 206   */
 207   template<typename _Tp>
 208     inline const _Tp&
 209     max(const _Tp& __a, const _Tp& __b)
 210     {
 211       // concept requirements
 212       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
 213       //return  __a < __b ? __b : __a;
 214       if (__a < __b)
 215         return __b;
 216       return __a;
 217     }
 218
 219   /**
 220    *  @brief This does what you think it does.
 221    *  @ingroup sorting_algorithms
 222    *  @param  a  A thing of arbitrary type.
 223    *  @param  b  Another thing of arbitrary type.
 224    *  @param  comp  A @link comparison_functors comparison functor@endlink.
 225    *  @return   The lesser of the parameters.
 226    *
 227    *  This will work on temporary expressions, since they are only evaluated
 228    *  once, unlike a preprocessor macro.
 229   */
 230   template<typename _Tp, typename _Compare>
 231     inline const _Tp&
 232     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
 233     {
 234       //return __comp(__b, __a) ? __b : __a;
 235       if (__comp(__b, __a))
 236         return __b;
 237       return __a;
 238     }
 239
 240   /**
 241    *  @brief This does what you think it does.
 242    *  @ingroup sorting_algorithms
 243    *  @param  a  A thing of arbitrary type.
 244    *  @param  b  Another thing of arbitrary type.
 245    *  @param  comp  A @link comparison_functors comparison functor@endlink.
 246    *  @return   The greater of the parameters.
 247    *
 248    *  This will work on temporary expressions, since they are only evaluated
 249    *  once, unlike a preprocessor macro.
 250   */
 251   template<typename _Tp, typename _Compare>
 252     inline const _Tp&
 253     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
 254     {
 255       //return __comp(__a, __b) ? __b : __a;
 256       if (__comp(__a, __b))
 257         return __b;
 258       return __a;
 259     }
 260
 261
 262   // If _Iterator has a base returns it otherwise _Iterator is returned
 263   // untouched
 264   template<typename _Iterator, bool _HasBase>
 265     struct _Iter_base
 266     {
 267       typedef _Iterator iterator_type;
 268       static iterator_type
 269       _S_base(_Iterator __it)
 270       { return __it; }
 271     };
 272
 273   template<typename _Iterator>
 274     struct _Iter_base<_Iterator, true>
 275     {
 276       typedef typename _Iterator::iterator_type iterator_type;
 277       static iterator_type
 278       _S_base(_Iterator __it)
 279       { return __it.base(); }
 280     };
 281
 282   // If _Iterator is a __normal_iterator return its base (a plain pointer,
 283   // normally) otherwise return it untouched.  See copy, fill, ...
 284   template<typename _Iterator>
 285     struct _Niter_base
 286     : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>
 287     { };
 288
 289   template<typename _Iterator>
 290     inline typename _Niter_base<_Iterator>::iterator_type
 291     __niter_base(_Iterator __it)
 292     { return std::_Niter_base<_Iterator>::_S_base(__it); }
 293
 294   // Likewise, for move_iterator.
 295   template<typename _Iterator>
 296     struct _Miter_base
 297     : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value>
 298     { };
 299
 300   template<typename _Iterator>
 301     inline typename _Miter_base<_Iterator>::iterator_type
 302     __miter_base(_Iterator __it)
 303     { return std::_Miter_base<_Iterator>::_S_base(__it); }
 304
 305   // All of these auxiliary structs serve two purposes.  (1) Replace
 306   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
 307   // because the input and output ranges are permitted to overlap.)
 308   // (2) If we're using random access iterators, then write the loop as
 309   // a for loop with an explicit count.
 310
 311   template<bool, bool, typename>
 312     struct __copy_move
 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 = *__first;
 320           return __result;
 321         }
 322     };
 323
 324 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 325   template<typename _Category>
 326     struct __copy_move<true, false, _Category>
 327     {
 328       template<typename _II, typename _OI>
 329         static _OI
 330         __copy_m(_II __first, _II __last, _OI __result)
 331         {
 332           for (; __first != __last; ++__result, ++__first)
 333             *__result = std::move(*__first);
 334           return __result;
 335         }
 336     };
 337 #endif
 338
 339   template<>
 340     struct __copy_move<false, false, random_access_iterator_tag>
 341     {
 342       template<typename _II, typename _OI>
 343         static _OI
 344         __copy_m(_II __first, _II __last, _OI __result)
 345         {
 346           typedef typename iterator_traits<_II>::difference_type _Distance;
 347           for(_Distance __n = __last - __first; __n > 0; --__n)
 348             {
 349               *__result = *__first;
 350               ++__first;
 351               ++__result;
 352             }
 353           return __result;
 354         }
 355     };
 356
 357 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 358   template<>
 359     struct __copy_move<true, false, random_access_iterator_tag>
 360     {
 361       template<typename _II, typename _OI>
 362         static _OI
 363         __copy_m(_II __first, _II __last, _OI __result)
 364         {
 365           typedef typename iterator_traits<_II>::difference_type _Distance;
 366           for(_Distance __n = __last - __first; __n > 0; --__n)
 367             {
 368               *__result = std::move(*__first);
 369               ++__first;
 370               ++__result;
 371             }
 372           return __result;
 373         }
 374     };
 375 #endif
 376
 377   template<bool _IsMove>
 378     struct __copy_move<_IsMove, true, random_access_iterator_tag>
 379     {
 380       template<typename _Tp>
 381         static _Tp*
 382         __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
 383         {
 384           const ptrdiff_t _Num = __last - __first;
 385           if (_Num)
 386             __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
 387           return __result + _Num;
 388         }
 389     };
 390
 391   template<bool _IsMove, typename _II, typename _OI>
 392     inline _OI
 393     __copy_move_a(_II __first, _II __last, _OI __result)
 394     {
 395       typedef typename iterator_traits<_II>::value_type _ValueTypeI;
 396       typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
 397       typedef typename iterator_traits<_II>::iterator_category _Category;
 398       const bool __simple = (__is_pod(_ValueTypeI)
 399                              && __is_pointer<_II>::__value
 400                              && __is_pointer<_OI>::__value
 401                              && __are_same<_ValueTypeI, _ValueTypeO>::__value);
 402
 403       return std::__copy_move<_IsMove, __simple,
 404                               _Category>::__copy_m(__first, __last, __result);
 405     }
 406
 407   // Helpers for streambuf iterators (either istream or ostream).
 408   // NB: avoid including <iosfwd>, relatively large.
 409   template<typename _CharT>
 410     struct char_traits;
 411
 412   template<typename _CharT, typename _Traits>
 413     class istreambuf_iterator;
 414
 415   template<typename _CharT, typename _Traits>
 416     class ostreambuf_iterator;
 417
 418   template<bool _IsMove, typename _CharT>
 419     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 420              ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
 421     __copy_move_a2(_CharT*, _CharT*,
 422                    ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 423
 424   template<bool _IsMove, typename _CharT>
 425     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 426              ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
 427     __copy_move_a2(const _CharT*, const _CharT*,
 428                    ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 429
 430   template<bool _IsMove, typename _CharT>
 431     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 432                                     _CharT*>::__type
 433     __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
 434                    istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
 435
 436   template<bool _IsMove, typename _II, typename _OI>
 437     inline _OI
 438     __copy_move_a2(_II __first, _II __last, _OI __result)
 439     {
 440       return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
 441                                              std::__niter_base(__last),
 442                                              std::__niter_base(__result)));
 443     }
 444
 445   /**
 446    *  @brief Copies the range [first,last) into result.
 447    *  @ingroup mutating_algorithms
 448    *  @param  first  An input iterator.
 449    *  @param  last   An input iterator.
 450    *  @param  result An output iterator.
 451    *  @return   result + (first - last)
 452    *
 453    *  This inline function will boil down to a call to @c memmove whenever
 454    *  possible.  Failing that, if random access iterators are passed, then the
 455    *  loop count will be known (and therefore a candidate for compiler
 456    *  optimizations such as unrolling).  Result may not be contained within
 457    *  [first,last); the copy_backward function should be used instead.
 458    *
 459    *  Note that the end of the output range is permitted to be contained
 460    *  within [first,last).
 461   */
 462   template<typename _II, typename _OI>
 463     inline _OI
 464     copy(_II __first, _II __last, _OI __result)
 465     {
 466       // concept requirements
 467       __glibcxx_function_requires(_InputIteratorConcept<_II>)
 468       __glibcxx_function_requires(_OutputIteratorConcept<_OI,
 469             typename iterator_traits<_II>::value_type>)
 470       __glibcxx_requires_valid_range(__first, __last);
 471
 472       return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
 473               (std::__miter_base(__first), std::__miter_base(__last),
 474                __result));
 475     }
 476
 477 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 478   /**
 479    *  @brief Moves the range [first,last) into result.
 480    *  @ingroup mutating_algorithms
 481    *  @param  first  An input iterator.
 482    *  @param  last   An input iterator.
 483    *  @param  result An output iterator.
 484    *  @return   result + (first - last)
 485    *
 486    *  This inline function will boil down to a call to @c memmove whenever
 487    *  possible.  Failing that, if random access iterators are passed, then the
 488    *  loop count will be known (and therefore a candidate for compiler
 489    *  optimizations such as unrolling).  Result may not be contained within
 490    *  [first,last); the move_backward function should be used instead.
 491    *
 492    *  Note that the end of the output range is permitted to be contained
 493    *  within [first,last).
 494   */
 495   template<typename _II, typename _OI>
 496     inline _OI
 497     move(_II __first, _II __last, _OI __result)
 498     {
 499       // concept requirements
 500       __glibcxx_function_requires(_InputIteratorConcept<_II>)
 501       __glibcxx_function_requires(_OutputIteratorConcept<_OI,
 502             typename iterator_traits<_II>::value_type>)
 503       __glibcxx_requires_valid_range(__first, __last);
 504
 505       return std::__copy_move_a2<true>(std::__miter_base(__first),
 506                                        std::__miter_base(__last), __result);
 507     }
 508
 509 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
 510 #else
 511 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
 512 #endif
 513
 514   template<bool, bool, typename>
 515     struct __copy_move_backward
 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 = *--__last;
 523           return __result;
 524         }
 525     };
 526
 527 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 528   template<typename _Category>
 529     struct __copy_move_backward<true, false, _Category>
 530     {
 531       template<typename _BI1, typename _BI2>
 532         static _BI2
 533         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
 534         {
 535           while (__first != __last)
 536             *--__result = std::move(*--__last);
 537           return __result;
 538         }
 539     };
 540 #endif
 541
 542   template<>
 543     struct __copy_move_backward<false, false, random_access_iterator_tag>
 544     {
 545       template<typename _BI1, typename _BI2>
 546         static _BI2
 547         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
 548         {
 549           typename iterator_traits<_BI1>::difference_type __n;
 550           for (__n = __last - __first; __n > 0; --__n)
 551             *--__result = *--__last;
 552           return __result;
 553         }
 554     };
 555
 556 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 557   template<>
 558     struct __copy_move_backward<true, false, random_access_iterator_tag>
 559     {
 560       template<typename _BI1, typename _BI2>
 561         static _BI2
 562         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
 563         {
 564           typename iterator_traits<_BI1>::difference_type __n;
 565           for (__n = __last - __first; __n > 0; --__n)
 566             *--__result = std::move(*--__last);
 567           return __result;
 568         }
 569     };
 570 #endif
 571
 572   template<bool _IsMove>
 573     struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
 574     {
 575       template<typename _Tp>
 576         static _Tp*
 577         __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
 578         {
 579           const ptrdiff_t _Num = __last - __first;
 580           if (_Num)
 581             __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
 582           return __result - _Num;
 583         }
 584     };
 585
 586   template<bool _IsMove, typename _BI1, typename _BI2>
 587     inline _BI2
 588     __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
 589     {
 590       typedef typename iterator_traits<_BI1>::value_type _ValueType1;
 591       typedef typename iterator_traits<_BI2>::value_type _ValueType2;
 592       typedef typename iterator_traits<_BI1>::iterator_category _Category;
 593       const bool __simple = (__is_pod(_ValueType1)
 594                              && __is_pointer<_BI1>::__value
 595                              && __is_pointer<_BI2>::__value
 596                              && __are_same<_ValueType1, _ValueType2>::__value);
 597
 598       return std::__copy_move_backward<_IsMove, __simple,
 599                                        _Category>::__copy_move_b(__first,
 600                                                                  __last,
 601                                                                  __result);
 602     }
 603
 604   template<bool _IsMove, typename _BI1, typename _BI2>
 605     inline _BI2
 606     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
 607     {
 608       return _BI2(std::__copy_move_backward_a<_IsMove>
 609                   (std::__niter_base(__first), std::__niter_base(__last),
 610                    std::__niter_base(__result)));
 611     }
 612
 613   /**
 614    *  @brief Copies the range [first,last) into result.
 615    *  @ingroup mutating_algorithms
 616    *  @param  first  A bidirectional iterator.
 617    *  @param  last   A bidirectional iterator.
 618    *  @param  result A bidirectional iterator.
 619    *  @return   result - (first - last)
 620    *
 621    *  The function has the same effect as copy, but starts at the end of the
 622    *  range and works its way to the start, returning the start of the result.
 623    *  This inline function will boil down to a call to @c memmove whenever
 624    *  possible.  Failing that, if random access iterators are passed, then the
 625    *  loop count will be known (and therefore a candidate for compiler
 626    *  optimizations such as unrolling).
 627    *
 628    *  Result may not be in the range [first,last).  Use copy instead.  Note
 629    *  that the start of the output range may overlap [first,last).
 630   */
 631   template<typename _BI1, typename _BI2>
 632     inline _BI2
 633     copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
 634     {
 635       // concept requirements
 636       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
 637       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
 638       __glibcxx_function_requires(_ConvertibleConcept<
 639             typename iterator_traits<_BI1>::value_type,
 640             typename iterator_traits<_BI2>::value_type>)
 641       __glibcxx_requires_valid_range(__first, __last);
 642
 643       return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
 644               (std::__miter_base(__first), std::__miter_base(__last),
 645                __result));
 646     }
 647
 648 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 649   /**
 650    *  @brief Moves the range [first,last) into result.
 651    *  @ingroup mutating_algorithms
 652    *  @param  first  A bidirectional iterator.
 653    *  @param  last   A bidirectional iterator.
 654    *  @param  result A bidirectional iterator.
 655    *  @return   result - (first - last)
 656    *
 657    *  The function has the same effect as move, but starts at the end of the
 658    *  range and works its way to the start, returning the start of the result.
 659    *  This inline function will boil down to a call to @c memmove whenever
 660    *  possible.  Failing that, if random access iterators are passed, then the
 661    *  loop count will be known (and therefore a candidate for compiler
 662    *  optimizations such as unrolling).
 663    *
 664    *  Result may not be in the range [first,last).  Use move instead.  Note
 665    *  that the start of the output range may overlap [first,last).
 666   */
 667   template<typename _BI1, typename _BI2>
 668     inline _BI2
 669     move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
 670     {
 671       // concept requirements
 672       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
 673       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
 674       __glibcxx_function_requires(_ConvertibleConcept<
 675             typename iterator_traits<_BI1>::value_type,
 676             typename iterator_traits<_BI2>::value_type>)
 677       __glibcxx_requires_valid_range(__first, __last);
 678
 679       return std::__copy_move_backward_a2<true>(std::__miter_base(__first),
 680                                                 std::__miter_base(__last),
 681                                                 __result);
 682     }
 683
 684 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
 685 #else
 686 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
 687 #endif
 688
 689   template<typename _ForwardIterator, typename _Tp>
 690     inline typename
 691     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
 692     __fill_a(_ForwardIterator __first, _ForwardIterator __last,
 693              const _Tp& __value)
 694     {
 695       for (; __first != __last; ++__first)
 696         *__first = __value;
 697     }
 698
 699   template<typename _ForwardIterator, typename _Tp>
 700     inline typename
 701     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
 702     __fill_a(_ForwardIterator __first, _ForwardIterator __last,
 703              const _Tp& __value)
 704     {
 705       const _Tp __tmp = __value;
 706       for (; __first != __last; ++__first)
 707         *__first = __tmp;
 708     }
 709
 710   // Specialization: for char types we can use memset.
 711   template<typename _Tp>
 712     inline typename
 713     __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
 714     __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
 715     {
 716       const _Tp __tmp = __c;
 717       __builtin_memset(__first, static_cast<unsigned char>(__tmp),
 718                        __last - __first);
 719     }
 720
 721   /**
 722    *  @brief Fills the range [first,last) with copies of value.
 723    *  @ingroup mutating_algorithms
 724    *  @param  first  A forward iterator.
 725    *  @param  last   A forward iterator.
 726    *  @param  value  A reference-to-const of arbitrary type.
 727    *  @return   Nothing.
 728    *
 729    *  This function fills a range with copies of the same value.  For char
 730    *  types filling contiguous areas of memory, this becomes an inline call
 731    *  to @c memset or @c wmemset.
 732   */
 733   template<typename _ForwardIterator, typename _Tp>
 734     inline void
 735     fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
 736     {
 737       // concept requirements
 738       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 739                                   _ForwardIterator>)
 740       __glibcxx_requires_valid_range(__first, __last);
 741
 742       std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),
 743                     __value);
 744     }
 745
 746   template<typename _OutputIterator, typename _Size, typename _Tp>
 747     inline typename
 748     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
 749     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
 750     {
 751       for (; __n > 0; --__n, ++__first)
 752         *__first = __value;
 753       return __first;
 754     }
 755
 756   template<typename _OutputIterator, typename _Size, typename _Tp>
 757     inline typename
 758     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
 759     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
 760     {
 761       const _Tp __tmp = __value;
 762       for (; __n > 0; --__n, ++__first)
 763         *__first = __tmp;
 764       return __first;
 765     }
 766
 767   template<typename _Size, typename _Tp>
 768     inline typename
 769     __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
 770     __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
 771     {
 772       std::__fill_a(__first, __first + __n, __c);
 773       return __first + __n;
 774     }
 775
 776   /**
 777    *  @brief Fills the range [first,first+n) with copies of value.
 778    *  @ingroup mutating_algorithms
 779    *  @param  first  An output iterator.
 780    *  @param  n      The count of copies to perform.
 781    *  @param  value  A reference-to-const of arbitrary type.
 782    *  @return   The iterator at first+n.
 783    *
 784    *  This function fills a range with copies of the same value.  For char
 785    *  types filling contiguous areas of memory, this becomes an inline call
 786    *  to @c memset or @ wmemset.
 787    *
 788    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
 789    *  DR 865. More algorithms that throw away information
 790   */
 791   template<typename _OI, typename _Size, typename _Tp>
 792     inline _OI
 793     fill_n(_OI __first, _Size __n, const _Tp& __value)
 794     {
 795       // concept requirements
 796       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
 797
 798       return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
 799     }
 800
 801   template<bool _BoolType>
 802     struct __equal
 803     {
 804       template<typename _II1, typename _II2>
 805         static bool
 806         equal(_II1 __first1, _II1 __last1, _II2 __first2)
 807         {
 808           for (; __first1 != __last1; ++__first1, ++__first2)
 809             if (!(*__first1 == *__first2))
 810               return false;
 811           return true;
 812         }
 813     };
 814
 815   template<>
 816     struct __equal<true>
 817     {
 818       template<typename _Tp>
 819         static bool
 820         equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
 821         {
 822           return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
 823                                    * (__last1 - __first1));
 824         }
 825     };
 826
 827   template<typename _II1, typename _II2>
 828     inline bool
 829     __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
 830     {
 831       typedef typename iterator_traits<_II1>::value_type _ValueType1;
 832       typedef typename iterator_traits<_II2>::value_type _ValueType2;
 833       const bool __simple = (__is_integer<_ValueType1>::__value
 834                              && __is_pointer<_II1>::__value
 835                              && __is_pointer<_II2>::__value
 836                              && __are_same<_ValueType1, _ValueType2>::__value);
 837
 838       return std::__equal<__simple>::equal(__first1, __last1, __first2);
 839     }
 840
 841
 842   template<typename, typename>
 843     struct __lc_rai
 844     {
 845       template<typename _II1, typename _II2>
 846         static _II1
 847         __newlast1(_II1, _II1 __last1, _II2, _II2)
 848         { return __last1; }
 849
 850       template<typename _II>
 851         static bool
 852         __cnd2(_II __first, _II __last)
 853         { return __first != __last; }
 854     };
 855
 856   template<>
 857     struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
 858     {
 859       template<typename _RAI1, typename _RAI2>
 860         static _RAI1
 861         __newlast1(_RAI1 __first1, _RAI1 __last1,
 862                    _RAI2 __first2, _RAI2 __last2)
 863         {
 864           const typename iterator_traits<_RAI1>::difference_type
 865             __diff1 = __last1 - __first1;
 866           const typename iterator_traits<_RAI2>::difference_type
 867             __diff2 = __last2 - __first2;
 868           return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
 869         }
 870
 871       template<typename _RAI>
 872         static bool
 873         __cnd2(_RAI, _RAI)
 874         { return true; }
 875     };
 876
 877   template<bool _BoolType>
 878     struct __lexicographical_compare
 879     {
 880       template<typename _II1, typename _II2>
 881         static bool __lc(_II1, _II1, _II2, _II2);
 882     };
 883
 884   template<bool _BoolType>
 885     template<typename _II1, typename _II2>
 886       bool
 887       __lexicographical_compare<_BoolType>::
 888       __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
 889       {
 890         typedef typename iterator_traits<_II1>::iterator_category _Category1;
 891         typedef typename iterator_traits<_II2>::iterator_category _Category2;
 892         typedef std::__lc_rai<_Category1, _Category2>   __rai_type;
 893
 894         __last1 = __rai_type::__newlast1(__first1, __last1,
 895                                          __first2, __last2);
 896         for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
 897              ++__first1, ++__first2)
 898           {
 899             if (*__first1 < *__first2)
 900               return true;
 901             if (*__first2 < *__first1)
 902               return false;
 903           }
 904         return __first1 == __last1 && __first2 != __last2;
 905       }
 906
 907   template<>
 908     struct __lexicographical_compare<true>
 909     {
 910       template<typename _Tp, typename _Up>
 911         static bool
 912         __lc(const _Tp* __first1, const _Tp* __last1,
 913              const _Up* __first2, const _Up* __last2)
 914         {
 915           const size_t __len1 = __last1 - __first1;
 916           const size_t __len2 = __last2 - __first2;
 917           const int __result = __builtin_memcmp(__first1, __first2,
 918                                                 std::min(__len1, __len2));
 919           return __result != 0 ? __result < 0 : __len1 < __len2;
 920         }
 921     };
 922
 923   template<typename _II1, typename _II2>
 924     inline bool
 925     __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
 926                                   _II2 __first2, _II2 __last2)
 927     {
 928       typedef typename iterator_traits<_II1>::value_type _ValueType1;
 929       typedef typename iterator_traits<_II2>::value_type _ValueType2;
 930       const bool __simple =
 931         (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
 932          && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
 933          && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
 934          && __is_pointer<_II1>::__value
 935          && __is_pointer<_II2>::__value);
 936
 937       return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
 938                                                             __first2, __last2);
 939     }
 940
 941   /**
 942    *  @brief Finds the first position in which @a val could be inserted
 943    *         without changing the ordering.
 944    *  @param  first   An iterator.
 945    *  @param  last    Another iterator.
 946    *  @param  val     The search term.
 947    *  @return         An iterator pointing to the first element <em>not less
 948    *                  than</em> @a val, or end() if every element is less than
 949    *                  @a val.
 950    *  @ingroup binary_search_algorithms
 951   */
 952   template<typename _ForwardIterator, typename _Tp>
 953     _ForwardIterator
 954     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
 955                 const _Tp& __val)
 956     {
 957       typedef typename iterator_traits<_ForwardIterator>::value_type
 958         _ValueType;
 959       typedef typename iterator_traits<_ForwardIterator>::difference_type
 960         _DistanceType;
 961
 962       // concept requirements
 963       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 964       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
 965       __glibcxx_requires_partitioned_lower(__first, __last, __val);
 966
 967       _DistanceType __len = std::distance(__first, __last);
 968       _DistanceType __half;
 969       _ForwardIterator __middle;
 970
 971       while (__len > 0)
 972         {
 973           __half = __len >> 1;
 974           __middle = __first;
 975           std::advance(__middle, __half);
 976           if (*__middle < __val)
 977             {
 978               __first = __middle;
 979               ++__first;
 980               __len = __len - __half - 1;
 981             }
 982           else
 983             __len = __half;
 984         }
 985       return __first;
 986     }
 987
 988   /// This is a helper function for the sort routines and for random.tcc.
 989   //  Precondition: __n > 0.
 990   template<typename _Size>
 991     inline _Size
 992     __lg(_Size __n)
 993     {
 994       _Size __k;
 995       for (__k = 0; __n != 0; __n >>= 1)
 996         ++__k;
 997       return __k - 1;
 998     }
 999
1000   inline int
1001   __lg(int __n)
1002   { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
1003
1004   inline long
1005   __lg(long __n)
1006   { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
1007
1008   inline long long
1009   __lg(long long __n)
1010   { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1011
1012 _GLIBCXX_END_NAMESPACE
1013
1014 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
1015
1016   /**
1017    *  @brief Tests a range for element-wise equality.
1018    *  @ingroup non_mutating_algorithms
1019    *  @param  first1  An input iterator.
1020    *  @param  last1   An input iterator.
1021    *  @param  first2  An input iterator.
1022    *  @return   A boolean true or false.
1023    *
1024    *  This compares the elements of two ranges using @c == and returns true or
1025    *  false depending on whether all of the corresponding elements of the
1026    *  ranges are equal.
1027   */
1028   template<typename _II1, typename _II2>
1029     inline bool
1030     equal(_II1 __first1, _II1 __last1, _II2 __first2)
1031     {
1032       // concept requirements
1033       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1034       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1035       __glibcxx_function_requires(_EqualOpConcept<
1036             typename iterator_traits<_II1>::value_type,
1037             typename iterator_traits<_II2>::value_type>)
1038       __glibcxx_requires_valid_range(__first1, __last1);
1039
1040       return std::__equal_aux(std::__niter_base(__first1),
1041                               std::__niter_base(__last1),
1042                               std::__niter_base(__first2));
1043     }
1044
1045   /**
1046    *  @brief Tests a range for element-wise equality.
1047    *  @ingroup non_mutating_algorithms
1048    *  @param  first1  An input iterator.
1049    *  @param  last1   An input iterator.
1050    *  @param  first2  An input iterator.
1051    *  @param binary_pred A binary predicate @link functors
1052    *                  functor@endlink.
1053    *  @return         A boolean true or false.
1054    *
1055    *  This compares the elements of two ranges using the binary_pred
1056    *  parameter, and returns true or
1057    *  false depending on whether all of the corresponding elements of the
1058    *  ranges are equal.
1059   */
1060   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1061     inline bool
1062     equal(_IIter1 __first1, _IIter1 __last1,
1063           _IIter2 __first2, _BinaryPredicate __binary_pred)
1064     {
1065       // concept requirements
1066       __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1067       __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1068       __glibcxx_requires_valid_range(__first1, __last1);
1069
1070       for (; __first1 != __last1; ++__first1, ++__first2)
1071         if (!bool(__binary_pred(*__first1, *__first2)))
1072           return false;
1073       return true;
1074     }
1075
1076   /**
1077    *  @brief Performs @b dictionary comparison on ranges.
1078    *  @ingroup sorting_algorithms
1079    *  @param  first1  An input iterator.
1080    *  @param  last1   An input iterator.
1081    *  @param  first2  An input iterator.
1082    *  @param  last2   An input iterator.
1083    *  @return   A boolean true or false.
1084    *
1085    *  <em>Returns true if the sequence of elements defined by the range
1086    *  [first1,last1) is lexicographically less than the sequence of elements
1087    *  defined by the range [first2,last2).  Returns false otherwise.</em>
1088    *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
1089    *  then this is an inline call to @c memcmp.
1090   */
1091   template<typename _II1, typename _II2>
1092     inline bool
1093     lexicographical_compare(_II1 __first1, _II1 __last1,
1094                             _II2 __first2, _II2 __last2)
1095     {
1096       // concept requirements
1097       typedef typename iterator_traits<_II1>::value_type _ValueType1;
1098       typedef typename iterator_traits<_II2>::value_type _ValueType2;
1099       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1100       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1101       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1102       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1103       __glibcxx_requires_valid_range(__first1, __last1);
1104       __glibcxx_requires_valid_range(__first2, __last2);
1105
1106       return std::__lexicographical_compare_aux(std::__niter_base(__first1),
1107                                                 std::__niter_base(__last1),
1108                                                 std::__niter_base(__first2),
1109                                                 std::__niter_base(__last2));
1110     }
1111
1112   /**
1113    *  @brief Performs @b dictionary comparison on ranges.
1114    *  @ingroup sorting_algorithms
1115    *  @param  first1  An input iterator.
1116    *  @param  last1   An input iterator.
1117    *  @param  first2  An input iterator.
1118    *  @param  last2   An input iterator.
1119    *  @param  comp  A @link comparison_functors comparison functor@endlink.
1120    *  @return   A boolean true or false.
1121    *
1122    *  The same as the four-parameter @c lexicographical_compare, but uses the
1123    *  comp parameter instead of @c <.
1124   */
1125   template<typename _II1, typename _II2, typename _Compare>
1126     bool
1127     lexicographical_compare(_II1 __first1, _II1 __last1,
1128                             _II2 __first2, _II2 __last2, _Compare __comp)
1129     {
1130       typedef typename iterator_traits<_II1>::iterator_category _Category1;
1131       typedef typename iterator_traits<_II2>::iterator_category _Category2;
1132       typedef std::__lc_rai<_Category1, _Category2>     __rai_type;
1133
1134       // concept requirements
1135       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1136       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1137       __glibcxx_requires_valid_range(__first1, __last1);
1138       __glibcxx_requires_valid_range(__first2, __last2);
1139
1140       __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1141       for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1142            ++__first1, ++__first2)
1143         {
1144           if (__comp(*__first1, *__first2))
1145             return true;
1146           if (__comp(*__first2, *__first1))
1147             return false;
1148         }
1149       return __first1 == __last1 && __first2 != __last2;
1150     }
1151
1152   /**
1153    *  @brief Finds the places in ranges which don't match.
1154    *  @ingroup non_mutating_algorithms
1155    *  @param  first1  An input iterator.
1156    *  @param  last1   An input iterator.
1157    *  @param  first2  An input iterator.
1158    *  @return   A pair of iterators pointing to the first mismatch.
1159    *
1160    *  This compares the elements of two ranges using @c == and returns a pair
1161    *  of iterators.  The first iterator points into the first range, the
1162    *  second iterator points into the second range, and the elements pointed
1163    *  to by the iterators are not equal.
1164   */
1165   template<typename _InputIterator1, typename _InputIterator2>
1166     pair<_InputIterator1, _InputIterator2>
1167     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1168              _InputIterator2 __first2)
1169     {
1170       // concept requirements
1171       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1172       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1173       __glibcxx_function_requires(_EqualOpConcept<
1174             typename iterator_traits<_InputIterator1>::value_type,
1175             typename iterator_traits<_InputIterator2>::value_type>)
1176       __glibcxx_requires_valid_range(__first1, __last1);
1177
1178       while (__first1 != __last1 && *__first1 == *__first2)
1179         {
1180           ++__first1;
1181           ++__first2;
1182         }
1183       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1184     }
1185
1186   /**
1187    *  @brief Finds the places in ranges which don't match.
1188    *  @ingroup non_mutating_algorithms
1189    *  @param  first1  An input iterator.
1190    *  @param  last1   An input iterator.
1191    *  @param  first2  An input iterator.
1192    *  @param binary_pred A binary predicate @link functors
1193    *         functor@endlink.
1194    *  @return   A pair of iterators pointing to the first mismatch.
1195    *
1196    *  This compares the elements of two ranges using the binary_pred
1197    *  parameter, and returns a pair
1198    *  of iterators.  The first iterator points into the first range, the
1199    *  second iterator points into the second range, and the elements pointed
1200    *  to by the iterators are not equal.
1201   */
1202   template<typename _InputIterator1, typename _InputIterator2,
1203            typename _BinaryPredicate>
1204     pair<_InputIterator1, _InputIterator2>
1205     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1206              _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1207     {
1208       // concept requirements
1209       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1210       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1211       __glibcxx_requires_valid_range(__first1, __last1);
1212
1213       while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
1214         {
1215           ++__first1;
1216           ++__first2;
1217         }
1218       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1219     }
1220
1221 _GLIBCXX_END_NESTED_NAMESPACE
1222
1223 // NB: This file is included within many other C++ includes, as a way
1224 // of getting the base algorithms. So, make sure that parallel bits
1225 // come in too if requested.
1226 #ifdef _GLIBCXX_PARALLEL
1227 # include <parallel/algobase.h>
1228 #endif
1229
1230 #endif