gcc/testsuite/g++.dg/tm/pr46567.C

   1 // { dg-do compile }
   2 // { dg-options "-fgnu-tm -O2" }
   3
   4 typedef __PTRDIFF_TYPE__ ptrdiff_t;
   5 typedef __SIZE_TYPE__ size_t;
   6 namespace std __attribute__ ((__visibility__ ("default"))) {
   7   using ::ptrdiff_t;
   8   using ::size_t;
   9 }
  10 namespace std __attribute__ ((__visibility__ ("default"))) {
  11   void
  12   __throw_bad_exception(void) __attribute__((__noreturn__));
  13   void
  14   __throw_bad_alloc(void) __attribute__((__noreturn__));
  15   void
  16   __throw_bad_cast(void) __attribute__((__noreturn__));
  17   void
  18   __throw_bad_typeid(void) __attribute__((__noreturn__));
  19   void
  20   __throw_logic_error(const char*) __attribute__((__noreturn__));
  21   void
  22   __throw_domain_error(const char*) __attribute__((__noreturn__));
  23   void
  24   __throw_invalid_argument(const char*) __attribute__((__noreturn__));
  25   void
  26   __throw_length_error(const char*) __attribute__((__noreturn__));
  27   void
  28   __throw_out_of_range(const char*) __attribute__((__noreturn__));
  29   void
  30   __throw_runtime_error(const char*) __attribute__((__noreturn__));
  31   void
  32   __throw_range_error(const char*) __attribute__((__noreturn__));
  33   void
  34   __throw_overflow_error(const char*) __attribute__((__noreturn__));
  35   void
  36   __throw_underflow_error(const char*) __attribute__((__noreturn__));
  37   void
  38   __throw_ios_failure(const char*) __attribute__((__noreturn__));
  39   void
  40   __throw_system_error(int) __attribute__((__noreturn__));
  41 }
  42
  43 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
  44   template<typename _Iterator, typename _Container>
  45     class __normal_iterator;
  46 }
  47 namespace std __attribute__ ((__visibility__ ("default"))) {
  48   struct __true_type { };
  49   struct __false_type { };
  50   template<bool>
  51     struct __truth_type
  52     { typedef __false_type __type; };
  53   template<>
  54     struct __truth_type<true>
  55     { typedef __true_type __type; };
  56   template<class _Sp, class _Tp>
  57     struct __traitor
  58     {
  59       enum { __value = bool(_Sp::__value) || bool(_Tp::__value) };
  60       typedef typename __truth_type<__value>::__type __type;
  61     };
  62   template<typename, typename>
  63     struct __are_same
  64     {
  65       enum { __value = 0 };
  66       typedef __false_type __type;
  67     };
  68   template<typename _Tp>
  69     struct __are_same<_Tp, _Tp>
  70     {
  71       enum { __value = 1 };
  72       typedef __true_type __type;
  73     };
  74   template<typename _Tp>
  75     struct __is_void
  76     {
  77       enum { __value = 0 };
  78       typedef __false_type __type;
  79     };
  80   template<>
  81     struct __is_void<void>
  82     {
  83       enum { __value = 1 };
  84       typedef __true_type __type;
  85     };
  86   template<typename _Tp>
  87     struct __is_integer
  88     {
  89       enum { __value = 0 };
  90       typedef __false_type __type;
  91     };
  92   template<>
  93     struct __is_integer<bool>
  94     {
  95       enum { __value = 1 };
  96       typedef __true_type __type;
  97     };
  98   template<>
  99     struct __is_integer<char>
 100     {
 101       enum { __value = 1 };
 102       typedef __true_type __type;
 103     };
 104   template<>
 105     struct __is_integer<signed char>
 106     {
 107       enum { __value = 1 };
 108       typedef __true_type __type;
 109     };
 110   template<>
 111     struct __is_integer<unsigned char>
 112     {
 113       enum { __value = 1 };
 114       typedef __true_type __type;
 115     };
 116   template<>
 117     struct __is_integer<wchar_t>
 118     {
 119       enum { __value = 1 };
 120       typedef __true_type __type;
 121     };
 122   template<>
 123     struct __is_integer<short>
 124     {
 125       enum { __value = 1 };
 126       typedef __true_type __type;
 127     };
 128   template<>
 129     struct __is_integer<unsigned short>
 130     {
 131       enum { __value = 1 };
 132       typedef __true_type __type;
 133     };
 134   template<>
 135     struct __is_integer<int>
 136     {
 137       enum { __value = 1 };
 138       typedef __true_type __type;
 139     };
 140   template<>
 141     struct __is_integer<unsigned int>
 142     {
 143       enum { __value = 1 };
 144       typedef __true_type __type;
 145     };
 146   template<>
 147     struct __is_integer<long>
 148     {
 149       enum { __value = 1 };
 150       typedef __true_type __type;
 151     };
 152   template<>
 153     struct __is_integer<unsigned long>
 154     {
 155       enum { __value = 1 };
 156       typedef __true_type __type;
 157     };
 158   template<>
 159     struct __is_integer<long long>
 160     {
 161       enum { __value = 1 };
 162       typedef __true_type __type;
 163     };
 164   template<>
 165     struct __is_integer<unsigned long long>
 166     {
 167       enum { __value = 1 };
 168       typedef __true_type __type;
 169     };
 170   template<typename _Tp>
 171     struct __is_floating
 172     {
 173       enum { __value = 0 };
 174       typedef __false_type __type;
 175     };
 176   template<>
 177     struct __is_floating<float>
 178     {
 179       enum { __value = 1 };
 180       typedef __true_type __type;
 181     };
 182   template<>
 183     struct __is_floating<double>
 184     {
 185       enum { __value = 1 };
 186       typedef __true_type __type;
 187     };
 188   template<>
 189     struct __is_floating<long double>
 190     {
 191       enum { __value = 1 };
 192       typedef __true_type __type;
 193     };
 194   template<typename _Tp>
 195     struct __is_pointer
 196     {
 197       enum { __value = 0 };
 198       typedef __false_type __type;
 199     };
 200   template<typename _Tp>
 201     struct __is_pointer<_Tp*>
 202     {
 203       enum { __value = 1 };
 204       typedef __true_type __type;
 205     };
 206   template<typename _Tp>
 207     struct __is_normal_iterator
 208     {
 209       enum { __value = 0 };
 210       typedef __false_type __type;
 211     };
 212   template<typename _Iterator, typename _Container>
 213     struct __is_normal_iterator< __gnu_cxx::__normal_iterator<_Iterator,
 214              _Container> >
 215     {
 216       enum { __value = 1 };
 217       typedef __true_type __type;
 218     };
 219   template<typename _Tp>
 220     struct __is_arithmetic
 221     : public __traitor<__is_integer<_Tp>, __is_floating<_Tp> >
 222     { };
 223   template<typename _Tp>
 224     struct __is_fundamental
 225     : public __traitor<__is_void<_Tp>, __is_arithmetic<_Tp> >
 226     { };
 227   template<typename _Tp>
 228     struct __is_scalar
 229     : public __traitor<__is_arithmetic<_Tp>, __is_pointer<_Tp> >
 230     { };
 231   template<typename _Tp>
 232     struct __is_char
 233     {
 234       enum { __value = 0 };
 235       typedef __false_type __type;
 236     };
 237   template<>
 238     struct __is_char<char>
 239     {
 240       enum { __value = 1 };
 241       typedef __true_type __type;
 242     };
 243   template<>
 244     struct __is_char<wchar_t>
 245     {
 246       enum { __value = 1 };
 247       typedef __true_type __type;
 248     };
 249   template<typename _Tp>
 250     struct __is_byte
 251     {
 252       enum { __value = 0 };
 253       typedef __false_type __type;
 254     };
 255   template<>
 256     struct __is_byte<char>
 257     {
 258       enum { __value = 1 };
 259       typedef __true_type __type;
 260     };
 261   template<>
 262     struct __is_byte<signed char>
 263     {
 264       enum { __value = 1 };
 265       typedef __true_type __type;
 266     };
 267   template<>
 268     struct __is_byte<unsigned char>
 269     {
 270       enum { __value = 1 };
 271       typedef __true_type __type;
 272     };
 273   template<typename _Tp>
 274     struct __is_move_iterator
 275     {
 276       enum { __value = 0 };
 277       typedef __false_type __type;
 278     };
 279 }
 280
 281 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 282   template<bool, typename>
 283     struct __enable_if
 284     { };
 285   template<typename _Tp>
 286     struct __enable_if<true, _Tp>
 287     { typedef _Tp __type; };
 288   template<bool _Cond, typename _Iftrue, typename _Iffalse>
 289     struct __conditional_type
 290     { typedef _Iftrue __type; };
 291   template<typename _Iftrue, typename _Iffalse>
 292     struct __conditional_type<false, _Iftrue, _Iffalse>
 293     { typedef _Iffalse __type; };
 294   template<typename _Tp>
 295     struct __add_unsigned
 296     {
 297     private:
 298       typedef __enable_if<std::__is_integer<_Tp>::__value, _Tp> __if_type;
 299     public:
 300       typedef typename __if_type::__type __type;
 301     };
 302   template<>
 303     struct __add_unsigned<char>
 304     { typedef unsigned char __type; };
 305   template<>
 306     struct __add_unsigned<signed char>
 307     { typedef unsigned char __type; };
 308   template<>
 309     struct __add_unsigned<short>
 310     { typedef unsigned short __type; };
 311   template<>
 312     struct __add_unsigned<int>
 313     { typedef unsigned int __type; };
 314   template<>
 315     struct __add_unsigned<long>
 316     { typedef unsigned long __type; };
 317   template<>
 318     struct __add_unsigned<long long>
 319     { typedef unsigned long long __type; };
 320   template<>
 321     struct __add_unsigned<bool>;
 322   template<>
 323     struct __add_unsigned<wchar_t>;
 324   template<typename _Tp>
 325     struct __remove_unsigned
 326     {
 327     private:
 328       typedef __enable_if<std::__is_integer<_Tp>::__value, _Tp> __if_type;
 329     public:
 330       typedef typename __if_type::__type __type;
 331     };
 332   template<>
 333     struct __remove_unsigned<char>
 334     { typedef signed char __type; };
 335   template<>
 336     struct __remove_unsigned<unsigned char>
 337     { typedef signed char __type; };
 338   template<>
 339     struct __remove_unsigned<unsigned short>
 340     { typedef short __type; };
 341   template<>
 342     struct __remove_unsigned<unsigned int>
 343     { typedef int __type; };
 344   template<>
 345     struct __remove_unsigned<unsigned long>
 346     { typedef long __type; };
 347   template<>
 348     struct __remove_unsigned<unsigned long long>
 349     { typedef long long __type; };
 350   template<>
 351     struct __remove_unsigned<bool>;
 352   template<>
 353     struct __remove_unsigned<wchar_t>;
 354   template<typename _Type>
 355     inline bool
 356     __is_null_pointer(_Type* __ptr)
 357     { return __ptr == 0; }
 358   template<typename _Type>
 359     inline bool
 360     __is_null_pointer(_Type)
 361     { return false; }
 362   template<typename _Tp, bool = std::__is_integer<_Tp>::__value>
 363     struct __promote
 364     { typedef double __type; };
 365   template<typename _Tp>
 366     struct __promote<_Tp, false>
 367     { typedef _Tp __type; };
 368   template<typename _Tp, typename _Up>
 369     struct __promote_2
 370     {
 371     private:
 372       typedef typename __promote<_Tp>::__type __type1;
 373       typedef typename __promote<_Up>::__type __type2;
 374     public:
 375       typedef __typeof__(__type1() + __type2()) __type;
 376     };
 377   template<typename _Tp, typename _Up, typename _Vp>
 378     struct __promote_3
 379     {
 380     private:
 381       typedef typename __promote<_Tp>::__type __type1;
 382       typedef typename __promote<_Up>::__type __type2;
 383       typedef typename __promote<_Vp>::__type __type3;
 384     public:
 385       typedef __typeof__(__type1() + __type2() + __type3()) __type;
 386     };
 387   template<typename _Tp, typename _Up, typename _Vp, typename _Wp>
 388     struct __promote_4
 389     {
 390     private:
 391       typedef typename __promote<_Tp>::__type __type1;
 392       typedef typename __promote<_Up>::__type __type2;
 393       typedef typename __promote<_Vp>::__type __type3;
 394       typedef typename __promote<_Wp>::__type __type4;
 395     public:
 396       typedef __typeof__(__type1() + __type2() + __type3() + __type4()) __type;
 397     };
 398 }
 399
 400 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 401   template<typename _Value>
 402     struct __numeric_traits_integer
 403     {
 404       static const _Value __min = (((_Value)(-1) < 0) ? (_Value)1 << (sizeof(_Value) * 8 - ((_Value)(-1) < 0)) : (_Value)0);
 405       static const _Value __max = (((_Value)(-1) < 0) ? (((((_Value)1 << ((sizeof(_Value) * 8 - ((_Value)(-1) < 0)) - 1)) - 1) << 1) + 1) : ~(_Value)0);
 406       static const bool __is_signed = ((_Value)(-1) < 0);
 407       static const int __digits = (sizeof(_Value) * 8 - ((_Value)(-1) < 0));
 408     };
 409   template<typename _Value>
 410     const _Value __numeric_traits_integer<_Value>::__min;
 411   template<typename _Value>
 412     const _Value __numeric_traits_integer<_Value>::__max;
 413   template<typename _Value>
 414     const bool __numeric_traits_integer<_Value>::__is_signed;
 415   template<typename _Value>
 416     const int __numeric_traits_integer<_Value>::__digits;
 417   template<typename _Value>
 418     struct __numeric_traits_floating
 419     {
 420       static const int __max_digits10 = (2 + (std::__are_same<_Value, float>::__value ? 24 : std::__are_same<_Value, double>::__value ? 53 : 64) * 3010 / 10000);
 421       static const bool __is_signed = true;
 422       static const int __digits10 = (std::__are_same<_Value, float>::__value ? 6 : std::__are_same<_Value, double>::__value ? 15 : 18);
 423       static const int __max_exponent10 = (std::__are_same<_Value, float>::__value ? 38 : std::__are_same<_Value, double>::__value ? 308 : 4932);
 424     };
 425   template<typename _Value>
 426     const int __numeric_traits_floating<_Value>::__max_digits10;
 427   template<typename _Value>
 428     const bool __numeric_traits_floating<_Value>::__is_signed;
 429   template<typename _Value>
 430     const int __numeric_traits_floating<_Value>::__digits10;
 431   template<typename _Value>
 432     const int __numeric_traits_floating<_Value>::__max_exponent10;
 433   template<typename _Value>
 434     struct __numeric_traits
 435     : public __conditional_type<std::__is_integer<_Value>::__value,
 436     __numeric_traits_integer<_Value>,
 437     __numeric_traits_floating<_Value> >::__type
 438     { };
 439 }
 440
 441
 442 namespace std __attribute__ ((__visibility__ ("default"))) {
 443   template<typename _Tp>
 444     inline void
 445     swap(_Tp& __a, _Tp& __b)
 446     {
 447
 448       _Tp __tmp = (__a);
 449       __a = (__b);
 450       __b = (__tmp);
 451     }
 452   template<typename _Tp, size_t _Nm>
 453     inline void
 454     swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
 455     {
 456       for (size_t __n = 0; __n < _Nm; ++__n)
 457  swap(__a[__n], __b[__n]);
 458     }
 459 }
 460 namespace std __attribute__ ((__visibility__ ("default"))) {
 461   template<class _T1, class _T2>
 462     struct pair
 463     {
 464       typedef _T1 first_type;
 465       typedef _T2 second_type;
 466       _T1 first;
 467       _T2 second;
 468       pair()
 469       : first(), second() { }
 470       pair(const _T1& __a, const _T2& __b)
 471       : first(__a), second(__b) { }
 472       template<class _U1, class _U2>
 473         pair(const pair<_U1, _U2>& __p)
 474  : first(__p.first),
 475    second(__p.second) { }
 476     };
 477   template<class _T1, class _T2>
 478     inline bool
 479     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 480     { return __x.first == __y.first && __x.second == __y.second; }
 481   template<class _T1, class _T2>
 482     inline bool
 483     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 484     { return __x.first < __y.first
 485       || (!(__y.first < __x.first) && __x.second < __y.second); }
 486   template<class _T1, class _T2>
 487     inline bool
 488     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 489     { return !(__x == __y); }
 490   template<class _T1, class _T2>
 491     inline bool
 492     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 493     { return __y < __x; }
 494   template<class _T1, class _T2>
 495     inline bool
 496     operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 497     { return !(__y < __x); }
 498   template<class _T1, class _T2>
 499     inline bool
 500     operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
 501     { return !(__x < __y); }
 502   template<class _T1, class _T2>
 503     inline pair<_T1, _T2>
 504     make_pair(_T1 __x, _T2 __y)
 505     { return pair<_T1, _T2>(__x, __y); }
 506 }
 507
 508
 509 namespace std __attribute__ ((__visibility__ ("default"))) {
 510   struct input_iterator_tag { };
 511   struct output_iterator_tag { };
 512   struct forward_iterator_tag : public input_iterator_tag { };
 513   struct bidirectional_iterator_tag : public forward_iterator_tag { };
 514   struct random_access_iterator_tag : public bidirectional_iterator_tag { };
 515   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
 516            typename _Pointer = _Tp*, typename _Reference = _Tp&>
 517     struct iterator
 518     {
 519       typedef _Category iterator_category;
 520       typedef _Tp value_type;
 521       typedef _Distance difference_type;
 522       typedef _Pointer pointer;
 523       typedef _Reference reference;
 524     };
 525   template<typename _Iterator>
 526     struct iterator_traits
 527     {
 528       typedef typename _Iterator::iterator_category iterator_category;
 529       typedef typename _Iterator::value_type value_type;
 530       typedef typename _Iterator::difference_type difference_type;
 531       typedef typename _Iterator::pointer pointer;
 532       typedef typename _Iterator::reference reference;
 533     };
 534   template<typename _Tp>
 535     struct iterator_traits<_Tp*>
 536     {
 537       typedef random_access_iterator_tag iterator_category;
 538       typedef _Tp value_type;
 539       typedef ptrdiff_t difference_type;
 540       typedef _Tp* pointer;
 541       typedef _Tp& reference;
 542     };
 543   template<typename _Tp>
 544     struct iterator_traits<const _Tp*>
 545     {
 546       typedef random_access_iterator_tag iterator_category;
 547       typedef _Tp value_type;
 548       typedef ptrdiff_t difference_type;
 549       typedef const _Tp* pointer;
 550       typedef const _Tp& reference;
 551     };
 552   template<typename _Iter>
 553     inline typename iterator_traits<_Iter>::iterator_category
 554     __iterator_category(const _Iter&)
 555     { return typename iterator_traits<_Iter>::iterator_category(); }
 556 }
 557
 558 namespace std __attribute__ ((__visibility__ ("default"))) {
 559   template<typename _InputIterator>
 560     inline typename iterator_traits<_InputIterator>::difference_type
 561     __distance(_InputIterator __first, _InputIterator __last,
 562                input_iterator_tag)
 563     {
 564
 565       typename iterator_traits<_InputIterator>::difference_type __n = 0;
 566       while (__first != __last)
 567  {
 568    ++__first;
 569    ++__n;
 570  }
 571       return __n;
 572     }
 573   template<typename _RandomAccessIterator>
 574     inline typename iterator_traits<_RandomAccessIterator>::difference_type
 575     __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
 576                random_access_iterator_tag)
 577     {
 578
 579       return __last - __first;
 580     }
 581   template<typename _InputIterator>
 582     inline typename iterator_traits<_InputIterator>::difference_type
 583     distance(_InputIterator __first, _InputIterator __last)
 584     {
 585       return std::__distance(__first, __last,
 586         std::__iterator_category(__first));
 587     }
 588   template<typename _InputIterator, typename _Distance>
 589     inline void
 590     __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
 591     {
 592
 593       while (__n--)
 594  ++__i;
 595     }
 596   template<typename _BidirectionalIterator, typename _Distance>
 597     inline void
 598     __advance(_BidirectionalIterator& __i, _Distance __n,
 599        bidirectional_iterator_tag)
 600     {
 601
 602       if (__n > 0)
 603         while (__n--)
 604    ++__i;
 605       else
 606         while (__n++)
 607    --__i;
 608     }
 609   template<typename _RandomAccessIterator, typename _Distance>
 610     inline void
 611     __advance(_RandomAccessIterator& __i, _Distance __n,
 612               random_access_iterator_tag)
 613     {
 614
 615       __i += __n;
 616     }
 617   template<typename _InputIterator, typename _Distance>
 618     inline void
 619     advance(_InputIterator& __i, _Distance __n)
 620     {
 621       typename iterator_traits<_InputIterator>::difference_type __d = __n;
 622       std::__advance(__i, __d, std::__iterator_category(__i));
 623     }
 624 }
 625 namespace std __attribute__ ((__visibility__ ("default"))) {
 626   template<typename _Iterator>
 627     class reverse_iterator
 628     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
 629         typename iterator_traits<_Iterator>::value_type,
 630         typename iterator_traits<_Iterator>::difference_type,
 631         typename iterator_traits<_Iterator>::pointer,
 632                       typename iterator_traits<_Iterator>::reference>
 633     {
 634     protected:
 635       _Iterator current;
 636     public:
 637       typedef _Iterator iterator_type;
 638       typedef typename iterator_traits<_Iterator>::difference_type
 639               difference_type;
 640       typedef typename iterator_traits<_Iterator>::reference reference;
 641       typedef typename iterator_traits<_Iterator>::pointer pointer;
 642     public:
 643       reverse_iterator() : current() { }
 644       explicit
 645       reverse_iterator(iterator_type __x) : current(__x) { }
 646       reverse_iterator(const reverse_iterator& __x)
 647       : current(__x.current) { }
 648       template<typename _Iter>
 649         reverse_iterator(const reverse_iterator<_Iter>& __x)
 650  : current(__x.base()) { }
 651       iterator_type
 652       base() const
 653       { return current; }
 654       reference
 655       operator*() const
 656       {
 657  _Iterator __tmp = current;
 658  return *--__tmp;
 659       }
 660       pointer
 661       operator->() const
 662       { return &(operator*()); }
 663       reverse_iterator&
 664       operator++()
 665       {
 666  --current;
 667  return *this;
 668       }
 669       reverse_iterator
 670       operator++(int)
 671       {
 672  reverse_iterator __tmp = *this;
 673  --current;
 674  return __tmp;
 675       }
 676       reverse_iterator&
 677       operator--()
 678       {
 679  ++current;
 680  return *this;
 681       }
 682       reverse_iterator
 683       operator--(int)
 684       {
 685  reverse_iterator __tmp = *this;
 686  ++current;
 687  return __tmp;
 688       }
 689       reverse_iterator
 690       operator+(difference_type __n) const
 691       { return reverse_iterator(current - __n); }
 692       reverse_iterator&
 693       operator+=(difference_type __n)
 694       {
 695  current -= __n;
 696  return *this;
 697       }
 698       reverse_iterator
 699       operator-(difference_type __n) const
 700       { return reverse_iterator(current + __n); }
 701       reverse_iterator&
 702       operator-=(difference_type __n)
 703       {
 704  current += __n;
 705  return *this;
 706       }
 707       reference
 708       operator[](difference_type __n) const
 709       { return *(*this + __n); }
 710     };
 711   template<typename _Iterator>
 712     inline bool
 713     operator==(const reverse_iterator<_Iterator>& __x,
 714         const reverse_iterator<_Iterator>& __y)
 715     { return __x.base() == __y.base(); }
 716   template<typename _Iterator>
 717     inline bool
 718     operator<(const reverse_iterator<_Iterator>& __x,
 719        const reverse_iterator<_Iterator>& __y)
 720     { return __y.base() < __x.base(); }
 721   template<typename _Iterator>
 722     inline bool
 723     operator!=(const reverse_iterator<_Iterator>& __x,
 724         const reverse_iterator<_Iterator>& __y)
 725     { return !(__x == __y); }
 726   template<typename _Iterator>
 727     inline bool
 728     operator>(const reverse_iterator<_Iterator>& __x,
 729        const reverse_iterator<_Iterator>& __y)
 730     { return __y < __x; }
 731   template<typename _Iterator>
 732     inline bool
 733     operator<=(const reverse_iterator<_Iterator>& __x,
 734         const reverse_iterator<_Iterator>& __y)
 735     { return !(__y < __x); }
 736   template<typename _Iterator>
 737     inline bool
 738     operator>=(const reverse_iterator<_Iterator>& __x,
 739         const reverse_iterator<_Iterator>& __y)
 740     { return !(__x < __y); }
 741   template<typename _Iterator>
 742     inline typename reverse_iterator<_Iterator>::difference_type
 743     operator-(const reverse_iterator<_Iterator>& __x,
 744        const reverse_iterator<_Iterator>& __y)
 745     { return __y.base() - __x.base(); }
 746   template<typename _Iterator>
 747     inline reverse_iterator<_Iterator>
 748     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
 749        const reverse_iterator<_Iterator>& __x)
 750     { return reverse_iterator<_Iterator>(__x.base() - __n); }
 751   template<typename _IteratorL, typename _IteratorR>
 752     inline bool
 753     operator==(const reverse_iterator<_IteratorL>& __x,
 754         const reverse_iterator<_IteratorR>& __y)
 755     { return __x.base() == __y.base(); }
 756   template<typename _IteratorL, typename _IteratorR>
 757     inline bool
 758     operator<(const reverse_iterator<_IteratorL>& __x,
 759        const reverse_iterator<_IteratorR>& __y)
 760     { return __y.base() < __x.base(); }
 761   template<typename _IteratorL, typename _IteratorR>
 762     inline bool
 763     operator!=(const reverse_iterator<_IteratorL>& __x,
 764         const reverse_iterator<_IteratorR>& __y)
 765     { return !(__x == __y); }
 766   template<typename _IteratorL, typename _IteratorR>
 767     inline bool
 768     operator>(const reverse_iterator<_IteratorL>& __x,
 769        const reverse_iterator<_IteratorR>& __y)
 770     { return __y < __x; }
 771   template<typename _IteratorL, typename _IteratorR>
 772     inline bool
 773     operator<=(const reverse_iterator<_IteratorL>& __x,
 774         const reverse_iterator<_IteratorR>& __y)
 775     { return !(__y < __x); }
 776   template<typename _IteratorL, typename _IteratorR>
 777     inline bool
 778     operator>=(const reverse_iterator<_IteratorL>& __x,
 779         const reverse_iterator<_IteratorR>& __y)
 780     { return !(__x < __y); }
 781   template<typename _IteratorL, typename _IteratorR>
 782     inline typename reverse_iterator<_IteratorL>::difference_type
 783     operator-(const reverse_iterator<_IteratorL>& __x,
 784        const reverse_iterator<_IteratorR>& __y)
 785     { return __y.base() - __x.base(); }
 786   template<typename _Container>
 787     class back_insert_iterator
 788     : public iterator<output_iterator_tag, void, void, void, void>
 789     {
 790     protected:
 791       _Container* container;
 792     public:
 793       typedef _Container container_type;
 794       explicit
 795       back_insert_iterator(_Container& __x) : container(&__x) { }
 796       back_insert_iterator&
 797       operator=(typename _Container::const_reference __value)
 798       {
 799  container->push_back(__value);
 800  return *this;
 801       }
 802       back_insert_iterator&
 803       operator*()
 804       { return *this; }
 805       back_insert_iterator&
 806       operator++()
 807       { return *this; }
 808       back_insert_iterator
 809       operator++(int)
 810       { return *this; }
 811     };
 812   template<typename _Container>
 813     inline back_insert_iterator<_Container>
 814     back_inserter(_Container& __x)
 815     { return back_insert_iterator<_Container>(__x); }
 816   template<typename _Container>
 817     class front_insert_iterator
 818     : public iterator<output_iterator_tag, void, void, void, void>
 819     {
 820     protected:
 821       _Container* container;
 822     public:
 823       typedef _Container container_type;
 824       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
 825       front_insert_iterator&
 826       operator=(typename _Container::const_reference __value)
 827       {
 828  container->push_front(__value);
 829  return *this;
 830       }
 831       front_insert_iterator&
 832       operator*()
 833       { return *this; }
 834       front_insert_iterator&
 835       operator++()
 836       { return *this; }
 837       front_insert_iterator
 838       operator++(int)
 839       { return *this; }
 840     };
 841   template<typename _Container>
 842     inline front_insert_iterator<_Container>
 843     front_inserter(_Container& __x)
 844     { return front_insert_iterator<_Container>(__x); }
 845   template<typename _Container>
 846     class insert_iterator
 847     : public iterator<output_iterator_tag, void, void, void, void>
 848     {
 849     protected:
 850       _Container* container;
 851       typename _Container::iterator iter;
 852     public:
 853       typedef _Container container_type;
 854       insert_iterator(_Container& __x, typename _Container::iterator __i)
 855       : container(&__x), iter(__i) {}
 856       insert_iterator&
 857       operator=(typename _Container::const_reference __value)
 858       {
 859  iter = container->insert(iter, __value);
 860  ++iter;
 861  return *this;
 862       }
 863       insert_iterator&
 864       operator*()
 865       { return *this; }
 866       insert_iterator&
 867       operator++()
 868       { return *this; }
 869       insert_iterator&
 870       operator++(int)
 871       { return *this; }
 872     };
 873   template<typename _Container, typename _Iterator>
 874     inline insert_iterator<_Container>
 875     inserter(_Container& __x, _Iterator __i)
 876     {
 877       return insert_iterator<_Container>(__x,
 878       typename _Container::iterator(__i));
 879     }
 880 }
 881 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 882   using std::iterator_traits;
 883   using std::iterator;
 884   template<typename _Iterator, typename _Container>
 885     class __normal_iterator
 886     {
 887     protected:
 888       _Iterator _M_current;
 889     public:
 890       typedef _Iterator iterator_type;
 891       typedef typename iterator_traits<_Iterator>::iterator_category
 892                                                              iterator_category;
 893       typedef typename iterator_traits<_Iterator>::value_type value_type;
 894       typedef typename iterator_traits<_Iterator>::difference_type
 895                                                              difference_type;
 896       typedef typename iterator_traits<_Iterator>::reference reference;
 897       typedef typename iterator_traits<_Iterator>::pointer pointer;
 898       __normal_iterator() : _M_current(_Iterator()) { }
 899       explicit
 900       __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 901       template<typename _Iter>
 902         __normal_iterator(const __normal_iterator<_Iter,
 903      typename __enable_if<
 904               (std::__are_same<_Iter, typename _Container::pointer>::__value),
 905         _Container>::__type>& __i)
 906         : _M_current(__i.base()) { }
 907       reference
 908       operator*() const
 909       { return *_M_current; }
 910       pointer
 911       operator->() const
 912       { return _M_current; }
 913       __normal_iterator&
 914       operator++()
 915       {
 916  ++_M_current;
 917  return *this;
 918       }
 919       __normal_iterator
 920       operator++(int)
 921       { return __normal_iterator(_M_current++); }
 922       __normal_iterator&
 923       operator--()
 924       {
 925  --_M_current;
 926  return *this;
 927       }
 928       __normal_iterator
 929       operator--(int)
 930       { return __normal_iterator(_M_current--); }
 931       reference
 932       operator[](const difference_type& __n) const
 933       { return _M_current[__n]; }
 934       __normal_iterator&
 935       operator+=(const difference_type& __n)
 936       { _M_current += __n; return *this; }
 937       __normal_iterator
 938       operator+(const difference_type& __n) const
 939       { return __normal_iterator(_M_current + __n); }
 940       __normal_iterator&
 941       operator-=(const difference_type& __n)
 942       { _M_current -= __n; return *this; }
 943       __normal_iterator
 944       operator-(const difference_type& __n) const
 945       { return __normal_iterator(_M_current - __n); }
 946       const _Iterator&
 947       base() const
 948       { return _M_current; }
 949     };
 950   template<typename _IteratorL, typename _IteratorR, typename _Container>
 951     inline bool
 952     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
 953         const __normal_iterator<_IteratorR, _Container>& __rhs)
 954     { return __lhs.base() == __rhs.base(); }
 955   template<typename _Iterator, typename _Container>
 956     inline bool
 957     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
 958         const __normal_iterator<_Iterator, _Container>& __rhs)
 959     { return __lhs.base() == __rhs.base(); }
 960   template<typename _IteratorL, typename _IteratorR, typename _Container>
 961     inline bool
 962     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 963         const __normal_iterator<_IteratorR, _Container>& __rhs)
 964     { return __lhs.base() != __rhs.base(); }
 965   template<typename _Iterator, typename _Container>
 966     inline bool
 967     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
 968         const __normal_iterator<_Iterator, _Container>& __rhs)
 969     { return __lhs.base() != __rhs.base(); }
 970   template<typename _IteratorL, typename _IteratorR, typename _Container>
 971     inline bool
 972     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
 973        const __normal_iterator<_IteratorR, _Container>& __rhs)
 974     { return __lhs.base() < __rhs.base(); }
 975   template<typename _Iterator, typename _Container>
 976     inline bool
 977     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
 978        const __normal_iterator<_Iterator, _Container>& __rhs)
 979     { return __lhs.base() < __rhs.base(); }
 980   template<typename _IteratorL, typename _IteratorR, typename _Container>
 981     inline bool
 982     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
 983        const __normal_iterator<_IteratorR, _Container>& __rhs)
 984     { return __lhs.base() > __rhs.base(); }
 985   template<typename _Iterator, typename _Container>
 986     inline bool
 987     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
 988        const __normal_iterator<_Iterator, _Container>& __rhs)
 989     { return __lhs.base() > __rhs.base(); }
 990   template<typename _IteratorL, typename _IteratorR, typename _Container>
 991     inline bool
 992     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 993         const __normal_iterator<_IteratorR, _Container>& __rhs)
 994     { return __lhs.base() <= __rhs.base(); }
 995   template<typename _Iterator, typename _Container>
 996     inline bool
 997     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
 998         const __normal_iterator<_Iterator, _Container>& __rhs)
 999     { return __lhs.base() <= __rhs.base(); }
1000   template<typename _IteratorL, typename _IteratorR, typename _Container>
1001     inline bool
1002     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1003         const __normal_iterator<_IteratorR, _Container>& __rhs)
1004     { return __lhs.base() >= __rhs.base(); }
1005   template<typename _Iterator, typename _Container>
1006     inline bool
1007     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1008         const __normal_iterator<_Iterator, _Container>& __rhs)
1009     { return __lhs.base() >= __rhs.base(); }
1010   template<typename _IteratorL, typename _IteratorR, typename _Container>
1011     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1012     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1013        const __normal_iterator<_IteratorR, _Container>& __rhs)
1014     { return __lhs.base() - __rhs.base(); }
1015   template<typename _Iterator, typename _Container>
1016     inline typename __normal_iterator<_Iterator, _Container>::difference_type
1017     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1018        const __normal_iterator<_Iterator, _Container>& __rhs)
1019     { return __lhs.base() - __rhs.base(); }
1020   template<typename _Iterator, typename _Container>
1021     inline __normal_iterator<_Iterator, _Container>
1022     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1023        __n, const __normal_iterator<_Iterator, _Container>& __i)
1024     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1025 }
1026 namespace std
1027 {
1028   namespace __debug { }
1029 }
1030 namespace __gnu_debug
1031 {
1032   using namespace std::__debug;
1033 }
1034 namespace std __attribute__ ((__visibility__ ("default"))) {
1035   template<bool _BoolType>
1036     struct __iter_swap
1037     {
1038       template<typename _ForwardIterator1, typename _ForwardIterator2>
1039         static void
1040         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1041         {
1042           typedef typename iterator_traits<_ForwardIterator1>::value_type
1043             _ValueType1;
1044           _ValueType1 __tmp = (*__a);
1045           *__a = (*__b);
1046           *__b = (__tmp);
1047  }
1048     };
1049   template<>
1050     struct __iter_swap<true>
1051     {
1052       template<typename _ForwardIterator1, typename _ForwardIterator2>
1053         static void
1054         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1055         {
1056           swap(*__a, *__b);
1057         }
1058     };
1059   template<typename _ForwardIterator1, typename _ForwardIterator2>
1060     inline void
1061     iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1062     {
1063       typedef typename iterator_traits<_ForwardIterator1>::value_type
1064  _ValueType1;
1065       typedef typename iterator_traits<_ForwardIterator2>::value_type
1066  _ValueType2;
1067
1068
1069
1070
1071       typedef typename iterator_traits<_ForwardIterator1>::reference
1072  _ReferenceType1;
1073       typedef typename iterator_traits<_ForwardIterator2>::reference
1074  _ReferenceType2;
1075       std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
1076  && __are_same<_ValueType1&, _ReferenceType1>::__value
1077  && __are_same<_ValueType2&, _ReferenceType2>::__value>::
1078  iter_swap(__a, __b);
1079     }
1080   template<typename _ForwardIterator1, typename _ForwardIterator2>
1081     _ForwardIterator2
1082     swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1083   _ForwardIterator2 __first2)
1084     {
1085
1086
1087       ;
1088       for (; __first1 != __last1; ++__first1, ++__first2)
1089  std::iter_swap(__first1, __first2);
1090       return __first2;
1091     }
1092   template<typename _Tp>
1093     inline const _Tp&
1094     min(const _Tp& __a, const _Tp& __b)
1095     {
1096
1097       if (__b < __a)
1098  return __b;
1099       return __a;
1100     }
1101   template<typename _Tp>
1102     inline const _Tp&
1103     max(const _Tp& __a, const _Tp& __b)
1104     {
1105
1106       if (__a < __b)
1107  return __b;
1108       return __a;
1109     }
1110   template<typename _Tp, typename _Compare>
1111     inline const _Tp&
1112     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
1113     {
1114       if (__comp(__b, __a))
1115  return __b;
1116       return __a;
1117     }
1118   template<typename _Tp, typename _Compare>
1119     inline const _Tp&
1120     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
1121     {
1122       if (__comp(__a, __b))
1123  return __b;
1124       return __a;
1125     }
1126   template<typename _Iterator,
1127     bool _IsNormal = __is_normal_iterator<_Iterator>::__value>
1128     struct __niter_base
1129     {
1130       static _Iterator
1131       __b(_Iterator __it)
1132       { return __it; }
1133     };
1134   template<typename _Iterator>
1135     struct __niter_base<_Iterator, true>
1136     {
1137       static typename _Iterator::iterator_type
1138       __b(_Iterator __it)
1139       { return __it.base(); }
1140     };
1141   template<typename _Iterator,
1142     bool _IsMove = __is_move_iterator<_Iterator>::__value>
1143     struct __miter_base
1144     {
1145       static _Iterator
1146       __b(_Iterator __it)
1147       { return __it; }
1148     };
1149   template<typename _Iterator>
1150     struct __miter_base<_Iterator, true>
1151     {
1152       static typename _Iterator::iterator_type
1153       __b(_Iterator __it)
1154       { return __it.base(); }
1155     };
1156   template<bool, bool, typename>
1157     struct __copy_move
1158     {
1159       template<typename _II, typename _OI>
1160         static _OI
1161         __copy_m(_II __first, _II __last, _OI __result)
1162         {
1163    for (; __first != __last; ++__result, ++__first)
1164      *__result = *__first;
1165    return __result;
1166  }
1167     };
1168   template<>
1169     struct __copy_move<false, false, random_access_iterator_tag>
1170     {
1171       template<typename _II, typename _OI>
1172         static _OI
1173         __copy_m(_II __first, _II __last, _OI __result)
1174         {
1175    typedef typename iterator_traits<_II>::difference_type _Distance;
1176    for(_Distance __n = __last - __first; __n > 0; --__n)
1177      {
1178        *__result = *__first;
1179        ++__first;
1180        ++__result;
1181      }
1182    return __result;
1183  }
1184     };
1185   template<bool _IsMove>
1186     struct __copy_move<_IsMove, true, random_access_iterator_tag>
1187     {
1188       template<typename _Tp>
1189         static _Tp*
1190         __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
1191         {
1192    __builtin_memmove(__result, __first,
1193        sizeof(_Tp) * (__last - __first));
1194    return __result + (__last - __first);
1195  }
1196     };
1197   template<bool _IsMove, typename _II, typename _OI>
1198     inline _OI
1199     __copy_move_a(_II __first, _II __last, _OI __result)
1200     {
1201       typedef typename iterator_traits<_II>::value_type _ValueTypeI;
1202       typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
1203       typedef typename iterator_traits<_II>::iterator_category _Category;
1204       const bool __simple = (__is_pod(_ValueTypeI)
1205                       && __is_pointer<_II>::__value
1206                       && __is_pointer<_OI>::__value
1207         && __are_same<_ValueTypeI, _ValueTypeO>::__value);
1208       return std::__copy_move<_IsMove, __simple,
1209                        _Category>::__copy_m(__first, __last, __result);
1210     }
1211   template<typename _CharT>
1212     struct char_traits;
1213   template<typename _CharT, typename _Traits>
1214     class istreambuf_iterator;
1215   template<typename _CharT, typename _Traits>
1216     class ostreambuf_iterator;
1217   template<bool _IsMove, typename _CharT>
1218     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
1219       ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
1220     __copy_move_a2(_CharT*, _CharT*,
1221      ostreambuf_iterator<_CharT, char_traits<_CharT> >);
1222   template<bool _IsMove, typename _CharT>
1223     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
1224       ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
1225     __copy_move_a2(const _CharT*, const _CharT*,
1226      ostreambuf_iterator<_CharT, char_traits<_CharT> >);
1227   template<bool _IsMove, typename _CharT>
1228     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
1229         _CharT*>::__type
1230     __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
1231      istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
1232   template<bool _IsMove, typename _II, typename _OI>
1233     inline _OI
1234     __copy_move_a2(_II __first, _II __last, _OI __result)
1235     {
1236       return _OI(std::__copy_move_a<_IsMove>
1237    (std::__niter_base<_II>::__b(__first),
1238     std::__niter_base<_II>::__b(__last),
1239     std::__niter_base<_OI>::__b(__result)));
1240     }
1241   template<typename _II, typename _OI>
1242     inline _OI
1243     copy(_II __first, _II __last, _OI __result)
1244     {
1245
1246
1247       ;
1248       return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
1249        (std::__miter_base<_II>::__b(__first),
1250         std::__miter_base<_II>::__b(__last), __result));
1251     }
1252   template<bool, bool, typename>
1253     struct __copy_move_backward
1254     {
1255       template<typename _BI1, typename _BI2>
1256         static _BI2
1257         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
1258         {
1259    while (__first != __last)
1260      *--__result = *--__last;
1261    return __result;
1262  }
1263     };
1264   template<>
1265     struct __copy_move_backward<false, false, random_access_iterator_tag>
1266     {
1267       template<typename _BI1, typename _BI2>
1268         static _BI2
1269         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
1270         {
1271    typename iterator_traits<_BI1>::difference_type __n;
1272    for (__n = __last - __first; __n > 0; --__n)
1273      *--__result = *--__last;
1274    return __result;
1275  }
1276     };
1277   template<bool _IsMove>
1278     struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
1279     {
1280       template<typename _Tp>
1281         static _Tp*
1282         __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
1283         {
1284    const ptrdiff_t _Num = __last - __first;
1285    __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
1286    return __result - _Num;
1287  }
1288     };
1289   template<bool _IsMove, typename _BI1, typename _BI2>
1290     inline _BI2
1291     __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
1292     {
1293       typedef typename iterator_traits<_BI1>::value_type _ValueType1;
1294       typedef typename iterator_traits<_BI2>::value_type _ValueType2;
1295       typedef typename iterator_traits<_BI1>::iterator_category _Category;
1296       const bool __simple = (__is_pod(_ValueType1)
1297                       && __is_pointer<_BI1>::__value
1298                       && __is_pointer<_BI2>::__value
1299         && __are_same<_ValueType1, _ValueType2>::__value);
1300       return std::__copy_move_backward<_IsMove, __simple,
1301                                 _Category>::__copy_move_b(__first,
1302          __last,
1303          __result);
1304     }
1305   template<bool _IsMove, typename _BI1, typename _BI2>
1306     inline _BI2
1307     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
1308     {
1309       return _BI2(std::__copy_move_backward_a<_IsMove>
1310     (std::__niter_base<_BI1>::__b(__first),
1311      std::__niter_base<_BI1>::__b(__last),
1312      std::__niter_base<_BI2>::__b(__result)));
1313     }
1314   template<typename _BI1, typename _BI2>
1315     inline _BI2
1316     copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
1317     {
1318
1319
1320
1321       ;
1322       return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
1323        (std::__miter_base<_BI1>::__b(__first),
1324         std::__miter_base<_BI1>::__b(__last), __result));
1325     }
1326   template<typename _ForwardIterator, typename _Tp>
1327     inline typename
1328     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
1329     __fill_a(_ForwardIterator __first, _ForwardIterator __last,
1330        const _Tp& __value)
1331     {
1332       for (; __first != __last; ++__first)
1333  *__first = __value;
1334     }
1335   template<typename _ForwardIterator, typename _Tp>
1336     inline typename
1337     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
1338     __fill_a(_ForwardIterator __first, _ForwardIterator __last,
1339       const _Tp& __value)
1340     {
1341       const _Tp __tmp = __value;
1342       for (; __first != __last; ++__first)
1343  *__first = __tmp;
1344     }
1345   template<typename _Tp>
1346     inline typename
1347     __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
1348     __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
1349     {
1350       const _Tp __tmp = __c;
1351       __builtin_memset(__first, static_cast<unsigned char>(__tmp),
1352          __last - __first);
1353     }
1354   template<typename _ForwardIterator, typename _Tp>
1355     inline void
1356     fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1357     {
1358
1359       ;
1360       std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first),
1361       std::__niter_base<_ForwardIterator>::__b(__last), __value);
1362     }
1363   template<typename _OutputIterator, typename _Size, typename _Tp>
1364     inline typename
1365     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
1366     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
1367     {
1368       for (; __n > 0; --__n, ++__first)
1369  *__first = __value;
1370       return __first;
1371     }
1372   template<typename _OutputIterator, typename _Size, typename _Tp>
1373     inline typename
1374     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1375     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
1376     {
1377       const _Tp __tmp = __value;
1378       for (; __n > 0; --__n, ++__first)
1379  *__first = __tmp;
1380       return __first;
1381     }
1382   template<typename _Size, typename _Tp>
1383     inline typename
1384     __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
1385     __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
1386     {
1387       std::__fill_a(__first, __first + __n, __c);
1388       return __first + __n;
1389     }
1390   template<typename _OI, typename _Size, typename _Tp>
1391     inline _OI
1392     fill_n(_OI __first, _Size __n, const _Tp& __value)
1393     {
1394
1395       return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first),
1396      __n, __value));
1397     }
1398   template<bool _BoolType>
1399     struct __equal
1400     {
1401       template<typename _II1, typename _II2>
1402         static bool
1403         equal(_II1 __first1, _II1 __last1, _II2 __first2)
1404         {
1405    for (; __first1 != __last1; ++__first1, ++__first2)
1406      if (!(*__first1 == *__first2))
1407        return false;
1408    return true;
1409  }
1410     };
1411   template<>
1412     struct __equal<true>
1413     {
1414       template<typename _Tp>
1415         static bool
1416         equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
1417         {
1418    return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
1419        * (__last1 - __first1));
1420  }
1421     };
1422   template<typename _II1, typename _II2>
1423     inline bool
1424     __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1425     {
1426       typedef typename iterator_traits<_II1>::value_type _ValueType1;
1427       typedef typename iterator_traits<_II2>::value_type _ValueType2;
1428       const bool __simple = (__is_integer<_ValueType1>::__value
1429                       && __is_pointer<_II1>::__value
1430                       && __is_pointer<_II2>::__value
1431         && __are_same<_ValueType1, _ValueType2>::__value);
1432       return std::__equal<__simple>::equal(__first1, __last1, __first2);
1433     }
1434   template<typename, typename>
1435     struct __lc_rai
1436     {
1437       template<typename _II1, typename _II2>
1438         static _II1
1439         __newlast1(_II1, _II1 __last1, _II2, _II2)
1440         { return __last1; }
1441       template<typename _II>
1442         static bool
1443         __cnd2(_II __first, _II __last)
1444         { return __first != __last; }
1445     };
1446   template<>
1447     struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1448     {
1449       template<typename _RAI1, typename _RAI2>
1450         static _RAI1
1451         __newlast1(_RAI1 __first1, _RAI1 __last1,
1452      _RAI2 __first2, _RAI2 __last2)
1453         {
1454    const typename iterator_traits<_RAI1>::difference_type
1455      __diff1 = __last1 - __first1;
1456    const typename iterator_traits<_RAI2>::difference_type
1457      __diff2 = __last2 - __first2;
1458    return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1459  }
1460       template<typename _RAI>
1461         static bool
1462         __cnd2(_RAI, _RAI)
1463         { return true; }
1464     };
1465   template<bool _BoolType>
1466     struct __lexicographical_compare
1467     {
1468       template<typename _II1, typename _II2>
1469         static bool __lc(_II1, _II1, _II2, _II2);
1470     };
1471   template<bool _BoolType>
1472     template<typename _II1, typename _II2>
1473       bool
1474       __lexicographical_compare<_BoolType>::
1475       __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1476       {
1477  typedef typename iterator_traits<_II1>::iterator_category _Category1;
1478  typedef typename iterator_traits<_II2>::iterator_category _Category2;
1479  typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1480  __last1 = __rai_type::__newlast1(__first1, __last1,
1481       __first2, __last2);
1482  for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1483       ++__first1, ++__first2)
1484    {
1485      if (*__first1 < *__first2)
1486        return true;
1487      if (*__first2 < *__first1)
1488        return false;
1489    }
1490  return __first1 == __last1 && __first2 != __last2;
1491       }
1492   template<>
1493     struct __lexicographical_compare<true>
1494     {
1495       template<typename _Tp, typename _Up>
1496         static bool
1497         __lc(const _Tp* __first1, const _Tp* __last1,
1498       const _Up* __first2, const _Up* __last2)
1499  {
1500    const size_t __len1 = __last1 - __first1;
1501    const size_t __len2 = __last2 - __first2;
1502    const int __result = __builtin_memcmp(__first1, __first2,
1503       std::min(__len1, __len2));
1504    return __result != 0 ? __result < 0 : __len1 < __len2;
1505  }
1506     };
1507   template<typename _II1, typename _II2>
1508     inline bool
1509     __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1510       _II2 __first2, _II2 __last2)
1511     {
1512       typedef typename iterator_traits<_II1>::value_type _ValueType1;
1513       typedef typename iterator_traits<_II2>::value_type _ValueType2;
1514       const bool __simple =
1515  (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
1516   && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
1517   && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
1518   && __is_pointer<_II1>::__value
1519   && __is_pointer<_II2>::__value);
1520       return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1521            __first2, __last2);
1522     }
1523 }
1524 namespace std __attribute__ ((__visibility__ ("default"))) {
1525   template<typename _II1, typename _II2>
1526     inline bool
1527     equal(_II1 __first1, _II1 __last1, _II2 __first2)
1528     {
1529
1530
1531
1532       ;
1533       return std::__equal_aux(std::__niter_base<_II1>::__b(__first1),
1534          std::__niter_base<_II1>::__b(__last1),
1535          std::__niter_base<_II2>::__b(__first2));
1536     }
1537   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1538     inline bool
1539     equal(_IIter1 __first1, _IIter1 __last1,
1540    _IIter2 __first2, _BinaryPredicate __binary_pred)
1541     {
1542
1543
1544       ;
1545       for (; __first1 != __last1; ++__first1, ++__first2)
1546  if (!bool(__binary_pred(*__first1, *__first2)))
1547    return false;
1548       return true;
1549     }
1550   template<typename _II1, typename _II2>
1551     inline bool
1552     lexicographical_compare(_II1 __first1, _II1 __last1,
1553        _II2 __first2, _II2 __last2)
1554     {
1555       typedef typename iterator_traits<_II1>::value_type _ValueType1;
1556       typedef typename iterator_traits<_II2>::value_type _ValueType2;
1557
1558
1559
1560
1561       ;
1562       ;
1563       return std::__lexicographical_compare_aux
1564  (std::__niter_base<_II1>::__b(__first1),
1565   std::__niter_base<_II1>::__b(__last1),
1566   std::__niter_base<_II2>::__b(__first2),
1567   std::__niter_base<_II2>::__b(__last2));
1568     }
1569   template<typename _II1, typename _II2, typename _Compare>
1570     bool
1571     lexicographical_compare(_II1 __first1, _II1 __last1,
1572        _II2 __first2, _II2 __last2, _Compare __comp)
1573     {
1574       typedef typename iterator_traits<_II1>::iterator_category _Category1;
1575       typedef typename iterator_traits<_II2>::iterator_category _Category2;
1576       typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1577
1578
1579       ;
1580       ;
1581       __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1582       for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1583     ++__first1, ++__first2)
1584  {
1585    if (__comp(*__first1, *__first2))
1586      return true;
1587    if (__comp(*__first2, *__first1))
1588      return false;
1589  }
1590       return __first1 == __last1 && __first2 != __last2;
1591     }
1592   template<typename _InputIterator1, typename _InputIterator2>
1593     pair<_InputIterator1, _InputIterator2>
1594     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1595       _InputIterator2 __first2)
1596     {
1597
1598
1599
1600       ;
1601       while (__first1 != __last1 && *__first1 == *__first2)
1602         {
1603    ++__first1;
1604    ++__first2;
1605         }
1606       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1607     }
1608   template<typename _InputIterator1, typename _InputIterator2,
1609     typename _BinaryPredicate>
1610     pair<_InputIterator1, _InputIterator2>
1611     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1612       _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1613     {
1614
1615
1616       ;
1617       while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
1618         {
1619    ++__first1;
1620    ++__first2;
1621         }
1622       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1623     }
1624 }
1625
1626 extern "C++" {
1627 namespace std
1628 {
1629   class exception
1630   {
1631   public:
1632     exception() throw() { }
1633     virtual ~exception() throw();
1634     virtual const char* what() const throw();
1635   };
1636   class bad_exception : public exception
1637   {
1638   public:
1639     bad_exception() throw() { }
1640     virtual ~bad_exception() throw();
1641     virtual const char* what() const throw();
1642   };
1643   typedef void (*terminate_handler) ();
1644   typedef void (*unexpected_handler) ();
1645   terminate_handler set_terminate(terminate_handler) throw();
1646   void terminate() __attribute__ ((__noreturn__));
1647   unexpected_handler set_unexpected(unexpected_handler) throw();
1648   void unexpected() __attribute__ ((__noreturn__));
1649   bool uncaught_exception() throw();
1650 }
1651 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
1652   void __verbose_terminate_handler();
1653 }
1654 }
1655 extern "C++" {
1656 namespace std
1657 {
1658   class bad_alloc : public exception
1659   {
1660   public:
1661     bad_alloc() throw() { }
1662     virtual ~bad_alloc() throw();
1663     virtual const char* what() const throw();
1664   };
1665   struct nothrow_t { };
1666   extern const nothrow_t nothrow;
1667   typedef void (*new_handler)();
1668   new_handler set_new_handler(new_handler) throw();
1669 }
1670 void* operator new(std::size_t)
1671 #if __cplusplus <= 201402L
1672 throw (std::bad_alloc)                  // { dg-warning "deprecated" "" { target { c++11 && { ! c++17 } } } }
1673 #endif
1674 ;
1675 void* operator new[](std::size_t)
1676 #if __cplusplus <= 201402L
1677 throw (std::bad_alloc)                  // { dg-warning "deprecated" "" { target { c++11 && { ! c++17 } } } }
1678 #endif
1679 ;
1680 void operator delete(void*) throw();
1681 void operator delete[](void*) throw();
1682 void* operator new(std::size_t, const std::nothrow_t&) throw();
1683 void* operator new[](std::size_t, const std::nothrow_t&) throw();
1684 void operator delete(void*, const std::nothrow_t&) throw();
1685 void operator delete[](void*, const std::nothrow_t&) throw();
1686 inline void* operator new(std::size_t, void* __p) throw() { return __p; }
1687 inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
1688 inline void operator delete (void*, void*) throw() { }
1689 inline void operator delete[](void*, void*) throw() { }
1690 }
1691 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
1692   using std::size_t;
1693   using std::ptrdiff_t;
1694   template<typename _Tp>
1695     class new_allocator
1696     {
1697     public:
1698       typedef size_t size_type;
1699       typedef ptrdiff_t difference_type;
1700       typedef _Tp* pointer;
1701       typedef const _Tp* const_pointer;
1702       typedef _Tp& reference;
1703       typedef const _Tp& const_reference;
1704       typedef _Tp value_type;
1705       template<typename _Tp1>
1706         struct rebind
1707         { typedef new_allocator<_Tp1> other; };
1708       new_allocator() throw() { }
1709       new_allocator(const new_allocator&) throw() { }
1710       template<typename _Tp1>
1711         new_allocator(const new_allocator<_Tp1>&) throw() { }
1712       ~new_allocator() throw() { }
1713       pointer
1714       address(reference __x) const { return &__x; }
1715       const_pointer
1716       address(const_reference __x) const { return &__x; }
1717       pointer
1718       allocate(size_type __n, const void* = 0)
1719       {
1720  if (__builtin_expect(__n > this->max_size(), false))
1721    std::__throw_bad_alloc();
1722  return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
1723       }
1724       void
1725       deallocate(pointer __p, size_type)
1726       { ::operator delete(__p); }
1727       size_type
1728       max_size() const throw()
1729       { return size_t(-1) / sizeof(_Tp); }
1730       void
1731       construct(pointer __p, const _Tp& __val)
1732       { ::new((void *)__p) _Tp(__val); }
1733       void
1734       destroy(pointer __p) { __p->~_Tp(); }
1735     };
1736   template<typename _Tp>
1737     inline bool
1738     operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
1739     { return true; }
1740   template<typename _Tp>
1741     inline bool
1742     operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
1743     { return false; }
1744 }
1745 namespace std __attribute__ ((__visibility__ ("default"))) {
1746   template<typename _Tp>
1747     class allocator;
1748   template<>
1749     class allocator<void>
1750     {
1751     public:
1752       typedef size_t size_type;
1753       typedef ptrdiff_t difference_type;
1754       typedef void* pointer;
1755       typedef const void* const_pointer;
1756       typedef void value_type;
1757       template<typename _Tp1>
1758         struct rebind
1759         { typedef allocator<_Tp1> other; };
1760     };
1761   template<typename _Tp>
1762     class allocator: public __gnu_cxx::new_allocator<_Tp>
1763     {
1764    public:
1765       typedef size_t size_type;
1766       typedef ptrdiff_t difference_type;
1767       typedef _Tp* pointer;
1768       typedef const _Tp* const_pointer;
1769       typedef _Tp& reference;
1770       typedef const _Tp& const_reference;
1771       typedef _Tp value_type;
1772       template<typename _Tp1>
1773         struct rebind
1774         { typedef allocator<_Tp1> other; };
1775       allocator() throw() { }
1776       allocator(const allocator& __a) throw()
1777       : __gnu_cxx::new_allocator<_Tp>(__a) { }
1778       template<typename _Tp1>
1779         allocator(const allocator<_Tp1>&) throw() { }
1780       ~allocator() throw() { }
1781     };
1782   template<typename _T1, typename _T2>
1783     inline bool
1784     operator==(const allocator<_T1>&, const allocator<_T2>&)
1785     { return true; }
1786   template<typename _Tp>
1787     inline bool
1788     operator==(const allocator<_Tp>&, const allocator<_Tp>&)
1789     { return true; }
1790   template<typename _T1, typename _T2>
1791     inline bool
1792     operator!=(const allocator<_T1>&, const allocator<_T2>&)
1793     { return false; }
1794   template<typename _Tp>
1795     inline bool
1796     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
1797     { return false; }
1798   extern template class allocator<char>;
1799   extern template class allocator<wchar_t>;
1800   template<typename _Alloc, bool = __is_empty(_Alloc)>
1801     struct __alloc_swap
1802     { static void _S_do_it(_Alloc&, _Alloc&) { } };
1803   template<typename _Alloc>
1804     struct __alloc_swap<_Alloc, false>
1805     {
1806       static void
1807       _S_do_it(_Alloc& __one, _Alloc& __two)
1808       {
1809  if (__one != __two)
1810    swap(__one, __two);
1811       }
1812     };
1813   template<typename _Alloc, bool = __is_empty(_Alloc)>
1814     struct __alloc_neq
1815     {
1816       static bool
1817       _S_do_it(const _Alloc&, const _Alloc&)
1818       { return false; }
1819     };
1820   template<typename _Alloc>
1821     struct __alloc_neq<_Alloc, false>
1822     {
1823       static bool
1824       _S_do_it(const _Alloc& __one, const _Alloc& __two)
1825       { return __one != __two; }
1826     };
1827 }
1828 namespace std __attribute__ ((__visibility__ ("default"))) {
1829   struct _List_node_base
1830   {
1831     _List_node_base* _M_next;
1832     _List_node_base* _M_prev;
1833     static void
1834     swap(_List_node_base& __x, _List_node_base& __y);
1835     void
1836     transfer(_List_node_base * const __first,
1837       _List_node_base * const __last);
1838     void
1839     reverse();
1840     void
1841     hook(_List_node_base * const __position);
1842     void
1843     unhook();
1844   };
1845   template<typename _Tp>
1846     struct _List_node : public _List_node_base
1847     {
1848       _Tp _M_data;
1849     };
1850   template<typename _Tp>
1851     struct _List_iterator
1852     {
1853       typedef _List_iterator<_Tp> _Self;
1854       typedef _List_node<_Tp> _Node;
1855       typedef ptrdiff_t difference_type;
1856       typedef std::bidirectional_iterator_tag iterator_category;
1857       typedef _Tp value_type;
1858       typedef _Tp* pointer;
1859       typedef _Tp& reference;
1860       _List_iterator()
1861       : _M_node() { }
1862       explicit
1863       _List_iterator(_List_node_base* __x)
1864       : _M_node(__x) { }
1865       reference
1866       operator*() const
1867       { return static_cast<_Node*>(_M_node)->_M_data; }
1868       pointer
1869       operator->() const
1870       { return &static_cast<_Node*>(_M_node)->_M_data; }
1871       _Self&
1872       operator++()
1873       {
1874  _M_node = _M_node->_M_next;
1875  return *this;
1876       }
1877       _Self
1878       operator++(int)
1879       {
1880  _Self __tmp = *this;
1881  _M_node = _M_node->_M_next;
1882  return __tmp;
1883       }
1884       _Self&
1885       operator--()
1886       {
1887  _M_node = _M_node->_M_prev;
1888  return *this;
1889       }
1890       _Self
1891       operator--(int)
1892       {
1893  _Self __tmp = *this;
1894  _M_node = _M_node->_M_prev;
1895  return __tmp;
1896       }
1897       bool
1898       operator==(const _Self& __x) const
1899       { return _M_node == __x._M_node; }
1900       bool
1901       operator!=(const _Self& __x) const
1902       { return _M_node != __x._M_node; }
1903       _List_node_base* _M_node;
1904     };
1905   template<typename _Tp>
1906     struct _List_const_iterator
1907     {
1908       typedef _List_const_iterator<_Tp> _Self;
1909       typedef const _List_node<_Tp> _Node;
1910       typedef _List_iterator<_Tp> iterator;
1911       typedef ptrdiff_t difference_type;
1912       typedef std::bidirectional_iterator_tag iterator_category;
1913       typedef _Tp value_type;
1914       typedef const _Tp* pointer;
1915       typedef const _Tp& reference;
1916       _List_const_iterator()
1917       : _M_node() { }
1918       explicit
1919       _List_const_iterator(const _List_node_base* __x)
1920       : _M_node(__x) { }
1921       _List_const_iterator(const iterator& __x)
1922       : _M_node(__x._M_node) { }
1923       reference
1924       operator*() const
1925       { return static_cast<_Node*>(_M_node)->_M_data; }
1926       pointer
1927       operator->() const
1928       { return &static_cast<_Node*>(_M_node)->_M_data; }
1929       _Self&
1930       operator++()
1931       {
1932  _M_node = _M_node->_M_next;
1933  return *this;
1934       }
1935       _Self
1936       operator++(int)
1937       {
1938  _Self __tmp = *this;
1939  _M_node = _M_node->_M_next;
1940  return __tmp;
1941       }
1942       _Self&
1943       operator--()
1944       {
1945  _M_node = _M_node->_M_prev;
1946  return *this;
1947       }
1948       _Self
1949       operator--(int)
1950       {
1951  _Self __tmp = *this;
1952  _M_node = _M_node->_M_prev;
1953  return __tmp;
1954       }
1955       bool
1956       operator==(const _Self& __x) const
1957       { return _M_node == __x._M_node; }
1958       bool
1959       operator!=(const _Self& __x) const
1960       { return _M_node != __x._M_node; }
1961       const _List_node_base* _M_node;
1962     };
1963   template<typename _Val>
1964     inline bool
1965     operator==(const _List_iterator<_Val>& __x,
1966         const _List_const_iterator<_Val>& __y)
1967     { return __x._M_node == __y._M_node; }
1968   template<typename _Val>
1969     inline bool
1970     operator!=(const _List_iterator<_Val>& __x,
1971                const _List_const_iterator<_Val>& __y)
1972     { return __x._M_node != __y._M_node; }
1973   template<typename _Tp, typename _Alloc>
1974     class _List_base
1975     {
1976     protected:
1977       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
1978         _Node_alloc_type;
1979       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
1980       struct _List_impl
1981       : public _Node_alloc_type
1982       {
1983  _List_node_base _M_node;
1984  _List_impl()
1985  : _Node_alloc_type(), _M_node()
1986  { }
1987  _List_impl(const _Node_alloc_type& __a)
1988  : _Node_alloc_type(__a), _M_node()
1989  { }
1990       };
1991       _List_impl _M_impl;
1992       _List_node<_Tp>*
1993       _M_get_node()
1994       { return _M_impl._Node_alloc_type::allocate(1); }
1995       void
1996       _M_put_node(_List_node<_Tp>* __p)
1997       { _M_impl._Node_alloc_type::deallocate(__p, 1); }
1998   public:
1999       typedef _Alloc allocator_type;
2000       _Node_alloc_type&
2001       _M_get_Node_allocator()
2002       { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
2003       const _Node_alloc_type&
2004       _M_get_Node_allocator() const
2005       { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
2006       _Tp_alloc_type
2007       _M_get_Tp_allocator() const
2008       { return _Tp_alloc_type(_M_get_Node_allocator()); }
2009       allocator_type
2010       get_allocator() const
2011       { return allocator_type(_M_get_Node_allocator()); }
2012       _List_base()
2013       : _M_impl()
2014       { _M_init(); }
2015       _List_base(const allocator_type& __a)
2016       : _M_impl(__a)
2017       { _M_init(); }
2018       ~_List_base()
2019       { _M_clear(); }
2020       void
2021       _M_clear();
2022       void
2023       _M_init()
2024       {
2025         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
2026         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
2027       }
2028     };
2029   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
2030     class list : protected _List_base<_Tp, _Alloc>
2031     {
2032       typedef typename _Alloc::value_type _Alloc_value_type;
2033
2034
2035       typedef _List_base<_Tp, _Alloc> _Base;
2036       typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
2037     public:
2038       typedef _Tp value_type;
2039       typedef typename _Tp_alloc_type::pointer pointer;
2040       typedef typename _Tp_alloc_type::const_pointer const_pointer;
2041       typedef typename _Tp_alloc_type::reference reference;
2042       typedef typename _Tp_alloc_type::const_reference const_reference;
2043       typedef _List_iterator<_Tp> iterator;
2044       typedef _List_const_iterator<_Tp> const_iterator;
2045       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2046       typedef std::reverse_iterator<iterator> reverse_iterator;
2047       typedef size_t size_type;
2048       typedef ptrdiff_t difference_type;
2049       typedef _Alloc allocator_type;
2050     protected:
2051       typedef _List_node<_Tp> _Node;
2052       using _Base::_M_impl;
2053       using _Base::_M_put_node;
2054       using _Base::_M_get_node;
2055       using _Base::_M_get_Tp_allocator;
2056       using _Base::_M_get_Node_allocator;
2057       _Node*
2058       _M_create_node(const value_type& __x)
2059       {
2060  _Node* __p = this->_M_get_node();
2061  try
2062    {
2063      _M_get_Tp_allocator().construct(&__p->_M_data, __x);
2064    }
2065  catch(...)
2066    {
2067      _M_put_node(__p);
2068      throw;
2069    }
2070  return __p;
2071       }
2072     public:
2073       list()
2074       : _Base() { }
2075       explicit
2076       list(const allocator_type& __a)
2077       : _Base(__a) { }
2078       explicit
2079       list(size_type __n, const value_type& __value = value_type(),
2080     const allocator_type& __a = allocator_type())
2081       : _Base(__a)
2082       { _M_fill_initialize(__n, __value); }
2083       list(const list& __x)
2084       : _Base(__x._M_get_Node_allocator())
2085       { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
2086       template<typename _InputIterator>
2087         list(_InputIterator __first, _InputIterator __last,
2088       const allocator_type& __a = allocator_type())
2089         : _Base(__a)
2090         {
2091    typedef typename std::__is_integer<_InputIterator>::__type _Integral;
2092    _M_initialize_dispatch(__first, __last, _Integral());
2093  }
2094       list&
2095       operator=(const list& __x);
2096       void
2097       assign(size_type __n, const value_type& __val)
2098       { _M_fill_assign(__n, __val); }
2099       template<typename _InputIterator>
2100         void
2101         assign(_InputIterator __first, _InputIterator __last)
2102         {
2103    typedef typename std::__is_integer<_InputIterator>::__type _Integral;
2104    _M_assign_dispatch(__first, __last, _Integral());
2105  }
2106       allocator_type
2107       get_allocator() const
2108       { return _Base::get_allocator(); }
2109       iterator
2110       begin()
2111       { return iterator(this->_M_impl._M_node._M_next); }
2112       const_iterator
2113       begin() const
2114       { return const_iterator(this->_M_impl._M_node._M_next); }
2115       iterator
2116       end()
2117       { return iterator(&this->_M_impl._M_node); }
2118       const_iterator
2119       end() const
2120       { return const_iterator(&this->_M_impl._M_node); }
2121       reverse_iterator
2122       rbegin()
2123       { return reverse_iterator(end()); }
2124       const_reverse_iterator
2125       rbegin() const
2126       { return const_reverse_iterator(end()); }
2127       reverse_iterator
2128       rend()
2129       { return reverse_iterator(begin()); }
2130       const_reverse_iterator
2131       rend() const
2132       { return const_reverse_iterator(begin()); }
2133       bool
2134       empty() const
2135       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
2136       size_type
2137       size() const
2138       { return std::distance(begin(), end()); }
2139       size_type
2140       max_size() const
2141       { return _M_get_Node_allocator().max_size(); }
2142       void
2143       resize(size_type __new_size, value_type __x = value_type());
2144       reference
2145       front()
2146       { return *begin(); }
2147       const_reference
2148       front() const
2149       { return *begin(); }
2150       reference
2151       back()
2152       {
2153  iterator __tmp = end();
2154  --__tmp;
2155  return *__tmp;
2156       }
2157       const_reference
2158       back() const
2159       {
2160  const_iterator __tmp = end();
2161  --__tmp;
2162  return *__tmp;
2163       }
2164       void
2165       push_front(const value_type& __x)
2166       { this->_M_insert(begin(), __x); }
2167       void
2168       pop_front()
2169       { this->_M_erase(begin()); }
2170       void
2171       push_back(const value_type& __x)
2172       { this->_M_insert(end(), __x); }
2173       void
2174       pop_back()
2175       { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
2176       iterator
2177       insert(iterator __position, const value_type& __x);
2178       void
2179       insert(iterator __position, size_type __n, const value_type& __x)
2180       {
2181  list __tmp(__n, __x, _M_get_Node_allocator());
2182  splice(__position, __tmp);
2183       }
2184       template<typename _InputIterator>
2185         void
2186         insert(iterator __position, _InputIterator __first,
2187         _InputIterator __last)
2188         {
2189    list __tmp(__first, __last, _M_get_Node_allocator());
2190    splice(__position, __tmp);
2191  }
2192       iterator
2193       erase(iterator __position);
2194       iterator
2195       erase(iterator __first, iterator __last)
2196       {
2197  while (__first != __last)
2198    __first = erase(__first);
2199  return __last;
2200       }
2201       void
2202       swap(list& __x)
2203       {
2204  _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node);
2205  std::__alloc_swap<typename _Base::_Node_alloc_type>::
2206    _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
2207       }
2208       void
2209       clear()
2210       {
2211         _Base::_M_clear();
2212         _Base::_M_init();
2213       }
2214       void
2215       splice(iterator __position, list& __x)
2216       {
2217  if (!__x.empty())
2218    {
2219      _M_check_equal_allocators(__x);
2220      this->_M_transfer(__position, __x.begin(), __x.end());
2221    }
2222       }
2223       void
2224       splice(iterator __position, list& __x, iterator __i)
2225       {
2226  iterator __j = __i;
2227  ++__j;
2228  if (__position == __i || __position == __j)
2229    return;
2230  if (this != &__x)
2231    _M_check_equal_allocators(__x);
2232  this->_M_transfer(__position, __i, __j);
2233       }
2234       void
2235       splice(iterator __position, list& __x, iterator __first,
2236       iterator __last)
2237       {
2238  if (__first != __last)
2239    {
2240      if (this != &__x)
2241        _M_check_equal_allocators(__x);
2242      this->_M_transfer(__position, __first, __last);
2243    }
2244       }
2245       void
2246       remove(const _Tp& __value);
2247       template<typename _Predicate>
2248         void
2249         remove_if(_Predicate);
2250       void
2251       unique();
2252       template<typename _BinaryPredicate>
2253         void
2254         unique(_BinaryPredicate);
2255       void
2256       merge(list& __x);
2257       template<typename _StrictWeakOrdering>
2258         void
2259         merge(list&, _StrictWeakOrdering);
2260       void
2261       reverse()
2262       { this->_M_impl._M_node.reverse(); }
2263       void
2264       sort();
2265       template<typename _StrictWeakOrdering>
2266         void
2267         sort(_StrictWeakOrdering);
2268     protected:
2269       template<typename _Integer>
2270         void
2271         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
2272         { _M_fill_initialize(static_cast<size_type>(__n), __x); }
2273       template<typename _InputIterator>
2274         void
2275         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
2276           __false_type)
2277         {
2278    for (; __first != __last; ++__first)
2279      push_back(*__first);
2280  }
2281       void
2282       _M_fill_initialize(size_type __n, const value_type& __x)
2283       {
2284  for (; __n > 0; --__n)
2285    push_back(__x);
2286       }
2287       template<typename _Integer>
2288         void
2289         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2290         { _M_fill_assign(__n, __val); }
2291       template<typename _InputIterator>
2292         void
2293         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2294       __false_type);
2295       void
2296       _M_fill_assign(size_type __n, const value_type& __val);
2297       void
2298       _M_transfer(iterator __position, iterator __first, iterator __last)
2299       { __position._M_node->transfer(__first._M_node, __last._M_node); }
2300       void
2301       _M_insert(iterator __position, const value_type& __x)
2302       {
2303         _Node* __tmp = _M_create_node(__x);
2304         __tmp->hook(__position._M_node);
2305       }
2306       void
2307       _M_erase(iterator __position)
2308       {
2309         __position._M_node->unhook();
2310         _Node* __n = static_cast<_Node*>(__position._M_node);
2311  _M_get_Tp_allocator().destroy(&__n->_M_data);
2312         _M_put_node(__n);
2313       }
2314       void
2315       _M_check_equal_allocators(list& __x)
2316       {
2317  if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
2318      _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
2319    __throw_runtime_error(("list::_M_check_equal_allocators"));
2320       }
2321     };
2322   template<typename _Tp, typename _Alloc>
2323     inline bool
2324     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2325     {
2326       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
2327       const_iterator __end1 = __x.end();
2328       const_iterator __end2 = __y.end();
2329       const_iterator __i1 = __x.begin();
2330       const_iterator __i2 = __y.begin();
2331       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
2332  {
2333    ++__i1;
2334    ++__i2;
2335  }
2336       return __i1 == __end1 && __i2 == __end2;
2337     }
2338   template<typename _Tp, typename _Alloc>
2339     inline bool
2340     operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2341     { return std::lexicographical_compare(__x.begin(), __x.end(),
2342        __y.begin(), __y.end()); }
2343   template<typename _Tp, typename _Alloc>
2344     inline bool
2345     operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2346     { return !(__x == __y); }
2347   template<typename _Tp, typename _Alloc>
2348     inline bool
2349     operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2350     { return __y < __x; }
2351   template<typename _Tp, typename _Alloc>
2352     inline bool
2353     operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2354     { return !(__y < __x); }
2355   template<typename _Tp, typename _Alloc>
2356     inline bool
2357     operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2358     { return !(__x < __y); }
2359   template<typename _Tp, typename _Alloc>
2360     inline void
2361     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2362     { __x.swap(__y); }
2363 }
2364 namespace std __attribute__ ((__visibility__ ("default"))) {
2365   template<typename _Tp, typename _Alloc>
2366     void
2367     _List_base<_Tp, _Alloc>::
2368     _M_clear()
2369     {
2370       typedef _List_node<_Tp> _Node;
2371       _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
2372       while (__cur != &this->_M_impl._M_node)
2373  {
2374    _Node* __tmp = __cur;
2375    __cur = static_cast<_Node*>(__cur->_M_next);
2376    _M_get_Tp_allocator().destroy(&__tmp->_M_data);
2377    _M_put_node(__tmp);
2378  }
2379     }
2380   template<typename _Tp, typename _Alloc>
2381     typename list<_Tp, _Alloc>::iterator
2382     list<_Tp, _Alloc>::
2383     insert(iterator __position, const value_type& __x)
2384     {
2385       _Node* __tmp = _M_create_node(__x);
2386       __tmp->hook(__position._M_node);
2387       return iterator(__tmp);
2388     }
2389   template<typename _Tp, typename _Alloc>
2390     typename list<_Tp, _Alloc>::iterator
2391     list<_Tp, _Alloc>::
2392     erase(iterator __position)
2393     {
2394       iterator __ret = iterator(__position._M_node->_M_next);
2395       _M_erase(__position);
2396       return __ret;
2397     }
2398   template<typename _Tp, typename _Alloc>
2399     void
2400     list<_Tp, _Alloc>::
2401     resize(size_type __new_size, value_type __x)
2402     {
2403       iterator __i = begin();
2404       size_type __len = 0;
2405       for (; __i != end() && __len < __new_size; ++__i, ++__len)
2406         ;
2407       if (__len == __new_size)
2408         erase(__i, end());
2409       else
2410         insert(end(), __new_size - __len, __x);
2411     }
2412   template<typename _Tp, typename _Alloc>
2413     list<_Tp, _Alloc>&
2414     list<_Tp, _Alloc>::
2415     operator=(const list& __x)
2416     {
2417       if (this != &__x)
2418  {
2419    iterator __first1 = begin();
2420    iterator __last1 = end();
2421    const_iterator __first2 = __x.begin();
2422    const_iterator __last2 = __x.end();
2423    for (; __first1 != __last1 && __first2 != __last2;
2424         ++__first1, ++__first2)
2425      *__first1 = *__first2;
2426    if (__first2 == __last2)
2427      erase(__first1, __last1);
2428    else
2429      insert(__last1, __first2, __last2);
2430  }
2431       return *this;
2432     }
2433   template<typename _Tp, typename _Alloc>
2434     void
2435     list<_Tp, _Alloc>::
2436     _M_fill_assign(size_type __n, const value_type& __val)
2437     {
2438       iterator __i = begin();
2439       for (; __i != end() && __n > 0; ++__i, --__n)
2440         *__i = __val;
2441       if (__n > 0)
2442         insert(end(), __n, __val);
2443       else
2444         erase(__i, end());
2445     }
2446   template<typename _Tp, typename _Alloc>
2447     template <typename _InputIterator>
2448       void
2449       list<_Tp, _Alloc>::
2450       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
2451     __false_type)
2452       {
2453         iterator __first1 = begin();
2454         iterator __last1 = end();
2455         for (; __first1 != __last1 && __first2 != __last2;
2456       ++__first1, ++__first2)
2457           *__first1 = *__first2;
2458         if (__first2 == __last2)
2459           erase(__first1, __last1);
2460         else
2461           insert(__last1, __first2, __last2);
2462       }
2463   template<typename _Tp, typename _Alloc>
2464     void
2465     list<_Tp, _Alloc>::
2466     remove(const value_type& __value)
2467     {
2468       iterator __first = begin();
2469       iterator __last = end();
2470       iterator __extra = __last;
2471       while (__first != __last)
2472  {
2473    iterator __next = __first;
2474    ++__next;
2475    if (*__first == __value)
2476      {
2477        if (&*__first != &__value)
2478   _M_erase(__first);
2479        else
2480   __extra = __first;
2481      }
2482    __first = __next;
2483  }
2484       if (__extra != __last)
2485  _M_erase(__extra);
2486     }
2487   template<typename _Tp, typename _Alloc>
2488     void
2489     list<_Tp, _Alloc>::
2490     unique()
2491     {
2492       iterator __first = begin();
2493       iterator __last = end();
2494       if (__first == __last)
2495  return;
2496       iterator __next = __first;
2497       while (++__next != __last)
2498  {
2499    if (*__first == *__next)
2500      _M_erase(__next);
2501    else
2502      __first = __next;
2503    __next = __first;
2504  }
2505     }
2506   template<typename _Tp, typename _Alloc>
2507     void
2508     list<_Tp, _Alloc>::
2509     merge(list& __x)
2510     {
2511       if (this != &__x)
2512  {
2513    _M_check_equal_allocators(__x);
2514    iterator __first1 = begin();
2515    iterator __last1 = end();
2516    iterator __first2 = __x.begin();
2517    iterator __last2 = __x.end();
2518    while (__first1 != __last1 && __first2 != __last2)
2519      if (*__first2 < *__first1)
2520        {
2521   iterator __next = __first2;
2522   _M_transfer(__first1, __first2, ++__next);
2523   __first2 = __next;
2524        }
2525      else
2526        ++__first1;
2527    if (__first2 != __last2)
2528      _M_transfer(__last1, __first2, __last2);
2529  }
2530     }
2531   template<typename _Tp, typename _Alloc>
2532     template <typename _StrictWeakOrdering>
2533       void
2534       list<_Tp, _Alloc>::
2535       merge(list& __x, _StrictWeakOrdering __comp)
2536       {
2537  if (this != &__x)
2538    {
2539      _M_check_equal_allocators(__x);
2540      iterator __first1 = begin();
2541      iterator __last1 = end();
2542      iterator __first2 = __x.begin();
2543      iterator __last2 = __x.end();
2544      while (__first1 != __last1 && __first2 != __last2)
2545        if (__comp(*__first2, *__first1))
2546   {
2547     iterator __next = __first2;
2548     _M_transfer(__first1, __first2, ++__next);
2549     __first2 = __next;
2550   }
2551        else
2552   ++__first1;
2553      if (__first2 != __last2)
2554        _M_transfer(__last1, __first2, __last2);
2555    }
2556       }
2557   template<typename _Tp, typename _Alloc>
2558     void
2559     list<_Tp, _Alloc>::
2560     sort()
2561     {
2562       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
2563    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
2564       {
2565         list __carry;
2566         list __tmp[64];
2567         list * __fill = &__tmp[0];
2568         list * __counter;
2569         do
2570    {
2571      __carry.splice(__carry.begin(), *this, begin());
2572      for(__counter = &__tmp[0];
2573   __counter != __fill && !__counter->empty();
2574   ++__counter)
2575        {
2576   __counter->merge(__carry);
2577   __carry.swap(*__counter);
2578        }
2579      __carry.swap(*__counter);
2580      if (__counter == __fill)
2581        ++__fill;
2582    }
2583  while ( !empty() );
2584         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
2585           __counter->merge(*(__counter - 1));
2586         swap( *(__fill - 1) );
2587       }
2588     }
2589   template<typename _Tp, typename _Alloc>
2590     template <typename _Predicate>
2591       void
2592       list<_Tp, _Alloc>::
2593       remove_if(_Predicate __pred)
2594       {
2595         iterator __first = begin();
2596         iterator __last = end();
2597         while (__first != __last)
2598    {
2599      iterator __next = __first;
2600      ++__next;
2601      if (__pred(*__first))
2602        _M_erase(__first);
2603      __first = __next;
2604    }
2605       }
2606   template<typename _Tp, typename _Alloc>
2607     template <typename _BinaryPredicate>
2608       void
2609       list<_Tp, _Alloc>::
2610       unique(_BinaryPredicate __binary_pred)
2611       {
2612         iterator __first = begin();
2613         iterator __last = end();
2614         if (__first == __last)
2615    return;
2616         iterator __next = __first;
2617         while (++__next != __last)
2618    {
2619      if (__binary_pred(*__first, *__next))
2620        _M_erase(__next);
2621      else
2622        __first = __next;
2623      __next = __first;
2624    }
2625       }
2626   template<typename _Tp, typename _Alloc>
2627     template <typename _StrictWeakOrdering>
2628       void
2629       list<_Tp, _Alloc>::
2630       sort(_StrictWeakOrdering __comp)
2631       {
2632  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
2633      && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
2634    {
2635      list __carry;
2636      list __tmp[64];
2637      list * __fill = &__tmp[0];
2638      list * __counter;
2639      do
2640        {
2641   __carry.splice(__carry.begin(), *this, begin());
2642   for(__counter = &__tmp[0];
2643       __counter != __fill && !__counter->empty();
2644       ++__counter)
2645     {
2646       __counter->merge(__carry, __comp);
2647       __carry.swap(*__counter);
2648     }
2649   __carry.swap(*__counter);
2650   if (__counter == __fill)
2651     ++__fill;
2652        }
2653      while ( !empty() );
2654      for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
2655        __counter->merge(*(__counter - 1), __comp);
2656      swap(*(__fill - 1));
2657    }
2658       }
2659 }
2660 extern void foobarit(void);
2661 class Game
2662 {
2663 public:
2664         struct BuildProject
2665         {
2666                 int posX;
2667         };
2668         std::list<BuildProject> buildProjects;
2669 };
2670 static Game game;
2671 static std::list<std::list<Game::BuildProject>::iterator>
2672 erasableBuildProjects;
2673 void *buildProjectSyncStepConcurrently(int id, int localTeam)
2674 {
2675         __transaction_relaxed {
2676                 std::list<std::list<Game::BuildProject>::iterator>::iterator it
2677 = erasableBuildProjects.begin();
2678                 foobarit();
2679                 game.buildProjects.erase( (std::list<Game::BuildProject>
2680 ::iterator) *it);
2681         }
2682         return 0;
2683 }
2684