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) throw (std::bad_alloc);
1671 void* operator new[](std::size_t) throw (std::bad_alloc);
1672 void operator delete(void*) throw();
1673 void operator delete[](void*) throw();
1674 void* operator new(std::size_t, const std::nothrow_t&) throw();
1675 void* operator new[](std::size_t, const std::nothrow_t&) throw();
1676 void operator delete(void*, const std::nothrow_t&) throw();
1677 void operator delete[](void*, const std::nothrow_t&) throw();
1678 inline void* operator new(std::size_t, void* __p) throw() { return __p; }
1679 inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
1680 inline void operator delete (void*, void*) throw() { }
1681 inline void operator delete[](void*, void*) throw() { }
1682 }
1683 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
1684   using std::size_t;
1685   using std::ptrdiff_t;
1686   template<typename _Tp>
1687     class new_allocator
1688     {
1689     public:
1690       typedef size_t size_type;
1691       typedef ptrdiff_t difference_type;
1692       typedef _Tp* pointer;
1693       typedef const _Tp* const_pointer;
1694       typedef _Tp& reference;
1695       typedef const _Tp& const_reference;
1696       typedef _Tp value_type;
1697       template<typename _Tp1>
1698         struct rebind
1699         { typedef new_allocator<_Tp1> other; };
1700       new_allocator() throw() { }
1701       new_allocator(const new_allocator&) throw() { }
1702       template<typename _Tp1>
1703         new_allocator(const new_allocator<_Tp1>&) throw() { }
1704       ~new_allocator() throw() { }
1705       pointer
1706       address(reference __x) const { return &__x; }
1707       const_pointer
1708       address(const_reference __x) const { return &__x; }
1709       pointer
1710       allocate(size_type __n, const void* = 0)
1711       {
1712  if (__builtin_expect(__n > this->max_size(), false))
1713    std::__throw_bad_alloc();
1714  return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
1715       }
1716       void
1717       deallocate(pointer __p, size_type)
1718       { ::operator delete(__p); }
1719       size_type
1720       max_size() const throw()
1721       { return size_t(-1) / sizeof(_Tp); }
1722       void
1723       construct(pointer __p, const _Tp& __val)
1724       { ::new((void *)__p) _Tp(__val); }
1725       void
1726       destroy(pointer __p) { __p->~_Tp(); }
1727     };
1728   template<typename _Tp>
1729     inline bool
1730     operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
1731     { return true; }
1732   template<typename _Tp>
1733     inline bool
1734     operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
1735     { return false; }
1736 }
1737 namespace std __attribute__ ((__visibility__ ("default"))) {
1738   template<typename _Tp>
1739     class allocator;
1740   template<>
1741     class allocator<void>
1742     {
1743     public:
1744       typedef size_t size_type;
1745       typedef ptrdiff_t difference_type;
1746       typedef void* pointer;
1747       typedef const void* const_pointer;
1748       typedef void value_type;
1749       template<typename _Tp1>
1750         struct rebind
1751         { typedef allocator<_Tp1> other; };
1752     };
1753   template<typename _Tp>
1754     class allocator: public __gnu_cxx::new_allocator<_Tp>
1755     {
1756    public:
1757       typedef size_t size_type;
1758       typedef ptrdiff_t difference_type;
1759       typedef _Tp* pointer;
1760       typedef const _Tp* const_pointer;
1761       typedef _Tp& reference;
1762       typedef const _Tp& const_reference;
1763       typedef _Tp value_type;
1764       template<typename _Tp1>
1765         struct rebind
1766         { typedef allocator<_Tp1> other; };
1767       allocator() throw() { }
1768       allocator(const allocator& __a) throw()
1769       : __gnu_cxx::new_allocator<_Tp>(__a) { }
1770       template<typename _Tp1>
1771         allocator(const allocator<_Tp1>&) throw() { }
1772       ~allocator() throw() { }
1773     };
1774   template<typename _T1, typename _T2>
1775     inline bool
1776     operator==(const allocator<_T1>&, const allocator<_T2>&)
1777     { return true; }
1778   template<typename _Tp>
1779     inline bool
1780     operator==(const allocator<_Tp>&, const allocator<_Tp>&)
1781     { return true; }
1782   template<typename _T1, typename _T2>
1783     inline bool
1784     operator!=(const allocator<_T1>&, const allocator<_T2>&)
1785     { return false; }
1786   template<typename _Tp>
1787     inline bool
1788     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
1789     { return false; }
1790   extern template class allocator<char>;
1791   extern template class allocator<wchar_t>;
1792   template<typename _Alloc, bool = __is_empty(_Alloc)>
1793     struct __alloc_swap
1794     { static void _S_do_it(_Alloc&, _Alloc&) { } };
1795   template<typename _Alloc>
1796     struct __alloc_swap<_Alloc, false>
1797     {
1798       static void
1799       _S_do_it(_Alloc& __one, _Alloc& __two)
1800       {
1801  if (__one != __two)
1802    swap(__one, __two);
1803       }
1804     };
1805   template<typename _Alloc, bool = __is_empty(_Alloc)>
1806     struct __alloc_neq
1807     {
1808       static bool
1809       _S_do_it(const _Alloc&, const _Alloc&)
1810       { return false; }
1811     };
1812   template<typename _Alloc>
1813     struct __alloc_neq<_Alloc, false>
1814     {
1815       static bool
1816       _S_do_it(const _Alloc& __one, const _Alloc& __two)
1817       { return __one != __two; }
1818     };
1819 }
1820 namespace std __attribute__ ((__visibility__ ("default"))) {
1821   struct _List_node_base
1822   {
1823     _List_node_base* _M_next;
1824     _List_node_base* _M_prev;
1825     static void
1826     swap(_List_node_base& __x, _List_node_base& __y);
1827     void
1828     transfer(_List_node_base * const __first,
1829       _List_node_base * const __last);
1830     void
1831     reverse();
1832     void
1833     hook(_List_node_base * const __position);
1834     void
1835     unhook();
1836   };
1837   template<typename _Tp>
1838     struct _List_node : public _List_node_base
1839     {
1840       _Tp _M_data;
1841     };
1842   template<typename _Tp>
1843     struct _List_iterator
1844     {
1845       typedef _List_iterator<_Tp> _Self;
1846       typedef _List_node<_Tp> _Node;
1847       typedef ptrdiff_t difference_type;
1848       typedef std::bidirectional_iterator_tag iterator_category;
1849       typedef _Tp value_type;
1850       typedef _Tp* pointer;
1851       typedef _Tp& reference;
1852       _List_iterator()
1853       : _M_node() { }
1854       explicit
1855       _List_iterator(_List_node_base* __x)
1856       : _M_node(__x) { }
1857       reference
1858       operator*() const
1859       { return static_cast<_Node*>(_M_node)->_M_data; }
1860       pointer
1861       operator->() const
1862       { return &static_cast<_Node*>(_M_node)->_M_data; }
1863       _Self&
1864       operator++()
1865       {
1866  _M_node = _M_node->_M_next;
1867  return *this;
1868       }
1869       _Self
1870       operator++(int)
1871       {
1872  _Self __tmp = *this;
1873  _M_node = _M_node->_M_next;
1874  return __tmp;
1875       }
1876       _Self&
1877       operator--()
1878       {
1879  _M_node = _M_node->_M_prev;
1880  return *this;
1881       }
1882       _Self
1883       operator--(int)
1884       {
1885  _Self __tmp = *this;
1886  _M_node = _M_node->_M_prev;
1887  return __tmp;
1888       }
1889       bool
1890       operator==(const _Self& __x) const
1891       { return _M_node == __x._M_node; }
1892       bool
1893       operator!=(const _Self& __x) const
1894       { return _M_node != __x._M_node; }
1895       _List_node_base* _M_node;
1896     };
1897   template<typename _Tp>
1898     struct _List_const_iterator
1899     {
1900       typedef _List_const_iterator<_Tp> _Self;
1901       typedef const _List_node<_Tp> _Node;
1902       typedef _List_iterator<_Tp> iterator;
1903       typedef ptrdiff_t difference_type;
1904       typedef std::bidirectional_iterator_tag iterator_category;
1905       typedef _Tp value_type;
1906       typedef const _Tp* pointer;
1907       typedef const _Tp& reference;
1908       _List_const_iterator()
1909       : _M_node() { }
1910       explicit
1911       _List_const_iterator(const _List_node_base* __x)
1912       : _M_node(__x) { }
1913       _List_const_iterator(const iterator& __x)
1914       : _M_node(__x._M_node) { }
1915       reference
1916       operator*() const
1917       { return static_cast<_Node*>(_M_node)->_M_data; }
1918       pointer
1919       operator->() const
1920       { return &static_cast<_Node*>(_M_node)->_M_data; }
1921       _Self&
1922       operator++()
1923       {
1924  _M_node = _M_node->_M_next;
1925  return *this;
1926       }
1927       _Self
1928       operator++(int)
1929       {
1930  _Self __tmp = *this;
1931  _M_node = _M_node->_M_next;
1932  return __tmp;
1933       }
1934       _Self&
1935       operator--()
1936       {
1937  _M_node = _M_node->_M_prev;
1938  return *this;
1939       }
1940       _Self
1941       operator--(int)
1942       {
1943  _Self __tmp = *this;
1944  _M_node = _M_node->_M_prev;
1945  return __tmp;
1946       }
1947       bool
1948       operator==(const _Self& __x) const
1949       { return _M_node == __x._M_node; }
1950       bool
1951       operator!=(const _Self& __x) const
1952       { return _M_node != __x._M_node; }
1953       const _List_node_base* _M_node;
1954     };
1955   template<typename _Val>
1956     inline bool
1957     operator==(const _List_iterator<_Val>& __x,
1958         const _List_const_iterator<_Val>& __y)
1959     { return __x._M_node == __y._M_node; }
1960   template<typename _Val>
1961     inline bool
1962     operator!=(const _List_iterator<_Val>& __x,
1963                const _List_const_iterator<_Val>& __y)
1964     { return __x._M_node != __y._M_node; }
1965   template<typename _Tp, typename _Alloc>
1966     class _List_base
1967     {
1968     protected:
1969       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
1970         _Node_alloc_type;
1971       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
1972       struct _List_impl
1973       : public _Node_alloc_type
1974       {
1975  _List_node_base _M_node;
1976  _List_impl()
1977  : _Node_alloc_type(), _M_node()
1978  { }
1979  _List_impl(const _Node_alloc_type& __a)
1980  : _Node_alloc_type(__a), _M_node()
1981  { }
1982       };
1983       _List_impl _M_impl;
1984       _List_node<_Tp>*
1985       _M_get_node()
1986       { return _M_impl._Node_alloc_type::allocate(1); }
1987       void
1988       _M_put_node(_List_node<_Tp>* __p)
1989       { _M_impl._Node_alloc_type::deallocate(__p, 1); }
1990   public:
1991       typedef _Alloc allocator_type;
1992       _Node_alloc_type&
1993       _M_get_Node_allocator()
1994       { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
1995       const _Node_alloc_type&
1996       _M_get_Node_allocator() const
1997       { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
1998       _Tp_alloc_type
1999       _M_get_Tp_allocator() const
2000       { return _Tp_alloc_type(_M_get_Node_allocator()); }
2001       allocator_type
2002       get_allocator() const
2003       { return allocator_type(_M_get_Node_allocator()); }
2004       _List_base()
2005       : _M_impl()
2006       { _M_init(); }
2007       _List_base(const allocator_type& __a)
2008       : _M_impl(__a)
2009       { _M_init(); }
2010       ~_List_base()
2011       { _M_clear(); }
2012       void
2013       _M_clear();
2014       void
2015       _M_init()
2016       {
2017         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
2018         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
2019       }
2020     };
2021   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
2022     class list : protected _List_base<_Tp, _Alloc>
2023     {
2024       typedef typename _Alloc::value_type _Alloc_value_type;
2025
2026
2027       typedef _List_base<_Tp, _Alloc> _Base;
2028       typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
2029     public:
2030       typedef _Tp value_type;
2031       typedef typename _Tp_alloc_type::pointer pointer;
2032       typedef typename _Tp_alloc_type::const_pointer const_pointer;
2033       typedef typename _Tp_alloc_type::reference reference;
2034       typedef typename _Tp_alloc_type::const_reference const_reference;
2035       typedef _List_iterator<_Tp> iterator;
2036       typedef _List_const_iterator<_Tp> const_iterator;
2037       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2038       typedef std::reverse_iterator<iterator> reverse_iterator;
2039       typedef size_t size_type;
2040       typedef ptrdiff_t difference_type;
2041       typedef _Alloc allocator_type;
2042     protected:
2043       typedef _List_node<_Tp> _Node;
2044       using _Base::_M_impl;
2045       using _Base::_M_put_node;
2046       using _Base::_M_get_node;
2047       using _Base::_M_get_Tp_allocator;
2048       using _Base::_M_get_Node_allocator;
2049       _Node*
2050       _M_create_node(const value_type& __x)
2051       {
2052  _Node* __p = this->_M_get_node();
2053  try
2054    {
2055      _M_get_Tp_allocator().construct(&__p->_M_data, __x);
2056    }
2057  catch(...)
2058    {
2059      _M_put_node(__p);
2060      throw;
2061    }
2062  return __p;
2063       }
2064     public:
2065       list()
2066       : _Base() { }
2067       explicit
2068       list(const allocator_type& __a)
2069       : _Base(__a) { }
2070       explicit
2071       list(size_type __n, const value_type& __value = value_type(),
2072     const allocator_type& __a = allocator_type())
2073       : _Base(__a)
2074       { _M_fill_initialize(__n, __value); }
2075       list(const list& __x)
2076       : _Base(__x._M_get_Node_allocator())
2077       { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
2078       template<typename _InputIterator>
2079         list(_InputIterator __first, _InputIterator __last,
2080       const allocator_type& __a = allocator_type())
2081         : _Base(__a)
2082         {
2083    typedef typename std::__is_integer<_InputIterator>::__type _Integral;
2084    _M_initialize_dispatch(__first, __last, _Integral());
2085  }
2086       list&
2087       operator=(const list& __x);
2088       void
2089       assign(size_type __n, const value_type& __val)
2090       { _M_fill_assign(__n, __val); }
2091       template<typename _InputIterator>
2092         void
2093         assign(_InputIterator __first, _InputIterator __last)
2094         {
2095    typedef typename std::__is_integer<_InputIterator>::__type _Integral;
2096    _M_assign_dispatch(__first, __last, _Integral());
2097  }
2098       allocator_type
2099       get_allocator() const
2100       { return _Base::get_allocator(); }
2101       iterator
2102       begin()
2103       { return iterator(this->_M_impl._M_node._M_next); }
2104       const_iterator
2105       begin() const
2106       { return const_iterator(this->_M_impl._M_node._M_next); }
2107       iterator
2108       end()
2109       { return iterator(&this->_M_impl._M_node); }
2110       const_iterator
2111       end() const
2112       { return const_iterator(&this->_M_impl._M_node); }
2113       reverse_iterator
2114       rbegin()
2115       { return reverse_iterator(end()); }
2116       const_reverse_iterator
2117       rbegin() const
2118       { return const_reverse_iterator(end()); }
2119       reverse_iterator
2120       rend()
2121       { return reverse_iterator(begin()); }
2122       const_reverse_iterator
2123       rend() const
2124       { return const_reverse_iterator(begin()); }
2125       bool
2126       empty() const
2127       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
2128       size_type
2129       size() const
2130       { return std::distance(begin(), end()); }
2131       size_type
2132       max_size() const
2133       { return _M_get_Node_allocator().max_size(); }
2134       void
2135       resize(size_type __new_size, value_type __x = value_type());
2136       reference
2137       front()
2138       { return *begin(); }
2139       const_reference
2140       front() const
2141       { return *begin(); }
2142       reference
2143       back()
2144       {
2145  iterator __tmp = end();
2146  --__tmp;
2147  return *__tmp;
2148       }
2149       const_reference
2150       back() const
2151       {
2152  const_iterator __tmp = end();
2153  --__tmp;
2154  return *__tmp;
2155       }
2156       void
2157       push_front(const value_type& __x)
2158       { this->_M_insert(begin(), __x); }
2159       void
2160       pop_front()
2161       { this->_M_erase(begin()); }
2162       void
2163       push_back(const value_type& __x)
2164       { this->_M_insert(end(), __x); }
2165       void
2166       pop_back()
2167       { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
2168       iterator
2169       insert(iterator __position, const value_type& __x);
2170       void
2171       insert(iterator __position, size_type __n, const value_type& __x)
2172       {
2173  list __tmp(__n, __x, _M_get_Node_allocator());
2174  splice(__position, __tmp);
2175       }
2176       template<typename _InputIterator>
2177         void
2178         insert(iterator __position, _InputIterator __first,
2179         _InputIterator __last)
2180         {
2181    list __tmp(__first, __last, _M_get_Node_allocator());
2182    splice(__position, __tmp);
2183  }
2184       iterator
2185       erase(iterator __position);
2186       iterator
2187       erase(iterator __first, iterator __last)
2188       {
2189  while (__first != __last)
2190    __first = erase(__first);
2191  return __last;
2192       }
2193       void
2194       swap(list& __x)
2195       {
2196  _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node);
2197  std::__alloc_swap<typename _Base::_Node_alloc_type>::
2198    _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
2199       }
2200       void
2201       clear()
2202       {
2203         _Base::_M_clear();
2204         _Base::_M_init();
2205       }
2206       void
2207       splice(iterator __position, list& __x)
2208       {
2209  if (!__x.empty())
2210    {
2211      _M_check_equal_allocators(__x);
2212      this->_M_transfer(__position, __x.begin(), __x.end());
2213    }
2214       }
2215       void
2216       splice(iterator __position, list& __x, iterator __i)
2217       {
2218  iterator __j = __i;
2219  ++__j;
2220  if (__position == __i || __position == __j)
2221    return;
2222  if (this != &__x)
2223    _M_check_equal_allocators(__x);
2224  this->_M_transfer(__position, __i, __j);
2225       }
2226       void
2227       splice(iterator __position, list& __x, iterator __first,
2228       iterator __last)
2229       {
2230  if (__first != __last)
2231    {
2232      if (this != &__x)
2233        _M_check_equal_allocators(__x);
2234      this->_M_transfer(__position, __first, __last);
2235    }
2236       }
2237       void
2238       remove(const _Tp& __value);
2239       template<typename _Predicate>
2240         void
2241         remove_if(_Predicate);
2242       void
2243       unique();
2244       template<typename _BinaryPredicate>
2245         void
2246         unique(_BinaryPredicate);
2247       void
2248       merge(list& __x);
2249       template<typename _StrictWeakOrdering>
2250         void
2251         merge(list&, _StrictWeakOrdering);
2252       void
2253       reverse()
2254       { this->_M_impl._M_node.reverse(); }
2255       void
2256       sort();
2257       template<typename _StrictWeakOrdering>
2258         void
2259         sort(_StrictWeakOrdering);
2260     protected:
2261       template<typename _Integer>
2262         void
2263         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
2264         { _M_fill_initialize(static_cast<size_type>(__n), __x); }
2265       template<typename _InputIterator>
2266         void
2267         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
2268           __false_type)
2269         {
2270    for (; __first != __last; ++__first)
2271      push_back(*__first);
2272  }
2273       void
2274       _M_fill_initialize(size_type __n, const value_type& __x)
2275       {
2276  for (; __n > 0; --__n)
2277    push_back(__x);
2278       }
2279       template<typename _Integer>
2280         void
2281         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2282         { _M_fill_assign(__n, __val); }
2283       template<typename _InputIterator>
2284         void
2285         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2286       __false_type);
2287       void
2288       _M_fill_assign(size_type __n, const value_type& __val);
2289       void
2290       _M_transfer(iterator __position, iterator __first, iterator __last)
2291       { __position._M_node->transfer(__first._M_node, __last._M_node); }
2292       void
2293       _M_insert(iterator __position, const value_type& __x)
2294       {
2295         _Node* __tmp = _M_create_node(__x);
2296         __tmp->hook(__position._M_node);
2297       }
2298       void
2299       _M_erase(iterator __position)
2300       {
2301         __position._M_node->unhook();
2302         _Node* __n = static_cast<_Node*>(__position._M_node);
2303  _M_get_Tp_allocator().destroy(&__n->_M_data);
2304         _M_put_node(__n);
2305       }
2306       void
2307       _M_check_equal_allocators(list& __x)
2308       {
2309  if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
2310      _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
2311    __throw_runtime_error(("list::_M_check_equal_allocators"));
2312       }
2313     };
2314   template<typename _Tp, typename _Alloc>
2315     inline bool
2316     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2317     {
2318       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
2319       const_iterator __end1 = __x.end();
2320       const_iterator __end2 = __y.end();
2321       const_iterator __i1 = __x.begin();
2322       const_iterator __i2 = __y.begin();
2323       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
2324  {
2325    ++__i1;
2326    ++__i2;
2327  }
2328       return __i1 == __end1 && __i2 == __end2;
2329     }
2330   template<typename _Tp, typename _Alloc>
2331     inline bool
2332     operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2333     { return std::lexicographical_compare(__x.begin(), __x.end(),
2334        __y.begin(), __y.end()); }
2335   template<typename _Tp, typename _Alloc>
2336     inline bool
2337     operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2338     { return !(__x == __y); }
2339   template<typename _Tp, typename _Alloc>
2340     inline bool
2341     operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2342     { return __y < __x; }
2343   template<typename _Tp, typename _Alloc>
2344     inline bool
2345     operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2346     { return !(__y < __x); }
2347   template<typename _Tp, typename _Alloc>
2348     inline bool
2349     operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2350     { return !(__x < __y); }
2351   template<typename _Tp, typename _Alloc>
2352     inline void
2353     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2354     { __x.swap(__y); }
2355 }
2356 namespace std __attribute__ ((__visibility__ ("default"))) {
2357   template<typename _Tp, typename _Alloc>
2358     void
2359     _List_base<_Tp, _Alloc>::
2360     _M_clear()
2361     {
2362       typedef _List_node<_Tp> _Node;
2363       _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
2364       while (__cur != &this->_M_impl._M_node)
2365  {
2366    _Node* __tmp = __cur;
2367    __cur = static_cast<_Node*>(__cur->_M_next);
2368    _M_get_Tp_allocator().destroy(&__tmp->_M_data);
2369    _M_put_node(__tmp);
2370  }
2371     }
2372   template<typename _Tp, typename _Alloc>
2373     typename list<_Tp, _Alloc>::iterator
2374     list<_Tp, _Alloc>::
2375     insert(iterator __position, const value_type& __x)
2376     {
2377       _Node* __tmp = _M_create_node(__x);
2378       __tmp->hook(__position._M_node);
2379       return iterator(__tmp);
2380     }
2381   template<typename _Tp, typename _Alloc>
2382     typename list<_Tp, _Alloc>::iterator
2383     list<_Tp, _Alloc>::
2384     erase(iterator __position)
2385     {
2386       iterator __ret = iterator(__position._M_node->_M_next);
2387       _M_erase(__position);
2388       return __ret;
2389     }
2390   template<typename _Tp, typename _Alloc>
2391     void
2392     list<_Tp, _Alloc>::
2393     resize(size_type __new_size, value_type __x)
2394     {
2395       iterator __i = begin();
2396       size_type __len = 0;
2397       for (; __i != end() && __len < __new_size; ++__i, ++__len)
2398         ;
2399       if (__len == __new_size)
2400         erase(__i, end());
2401       else
2402         insert(end(), __new_size - __len, __x);
2403     }
2404   template<typename _Tp, typename _Alloc>
2405     list<_Tp, _Alloc>&
2406     list<_Tp, _Alloc>::
2407     operator=(const list& __x)
2408     {
2409       if (this != &__x)
2410  {
2411    iterator __first1 = begin();
2412    iterator __last1 = end();
2413    const_iterator __first2 = __x.begin();
2414    const_iterator __last2 = __x.end();
2415    for (; __first1 != __last1 && __first2 != __last2;
2416         ++__first1, ++__first2)
2417      *__first1 = *__first2;
2418    if (__first2 == __last2)
2419      erase(__first1, __last1);
2420    else
2421      insert(__last1, __first2, __last2);
2422  }
2423       return *this;
2424     }
2425   template<typename _Tp, typename _Alloc>
2426     void
2427     list<_Tp, _Alloc>::
2428     _M_fill_assign(size_type __n, const value_type& __val)
2429     {
2430       iterator __i = begin();
2431       for (; __i != end() && __n > 0; ++__i, --__n)
2432         *__i = __val;
2433       if (__n > 0)
2434         insert(end(), __n, __val);
2435       else
2436         erase(__i, end());
2437     }
2438   template<typename _Tp, typename _Alloc>
2439     template <typename _InputIterator>
2440       void
2441       list<_Tp, _Alloc>::
2442       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
2443     __false_type)
2444       {
2445         iterator __first1 = begin();
2446         iterator __last1 = end();
2447         for (; __first1 != __last1 && __first2 != __last2;
2448       ++__first1, ++__first2)
2449           *__first1 = *__first2;
2450         if (__first2 == __last2)
2451           erase(__first1, __last1);
2452         else
2453           insert(__last1, __first2, __last2);
2454       }
2455   template<typename _Tp, typename _Alloc>
2456     void
2457     list<_Tp, _Alloc>::
2458     remove(const value_type& __value)
2459     {
2460       iterator __first = begin();
2461       iterator __last = end();
2462       iterator __extra = __last;
2463       while (__first != __last)
2464  {
2465    iterator __next = __first;
2466    ++__next;
2467    if (*__first == __value)
2468      {
2469        if (&*__first != &__value)
2470   _M_erase(__first);
2471        else
2472   __extra = __first;
2473      }
2474    __first = __next;
2475  }
2476       if (__extra != __last)
2477  _M_erase(__extra);
2478     }
2479   template<typename _Tp, typename _Alloc>
2480     void
2481     list<_Tp, _Alloc>::
2482     unique()
2483     {
2484       iterator __first = begin();
2485       iterator __last = end();
2486       if (__first == __last)
2487  return;
2488       iterator __next = __first;
2489       while (++__next != __last)
2490  {
2491    if (*__first == *__next)
2492      _M_erase(__next);
2493    else
2494      __first = __next;
2495    __next = __first;
2496  }
2497     }
2498   template<typename _Tp, typename _Alloc>
2499     void
2500     list<_Tp, _Alloc>::
2501     merge(list& __x)
2502     {
2503       if (this != &__x)
2504  {
2505    _M_check_equal_allocators(__x);
2506    iterator __first1 = begin();
2507    iterator __last1 = end();
2508    iterator __first2 = __x.begin();
2509    iterator __last2 = __x.end();
2510    while (__first1 != __last1 && __first2 != __last2)
2511      if (*__first2 < *__first1)
2512        {
2513   iterator __next = __first2;
2514   _M_transfer(__first1, __first2, ++__next);
2515   __first2 = __next;
2516        }
2517      else
2518        ++__first1;
2519    if (__first2 != __last2)
2520      _M_transfer(__last1, __first2, __last2);
2521  }
2522     }
2523   template<typename _Tp, typename _Alloc>
2524     template <typename _StrictWeakOrdering>
2525       void
2526       list<_Tp, _Alloc>::
2527       merge(list& __x, _StrictWeakOrdering __comp)
2528       {
2529  if (this != &__x)
2530    {
2531      _M_check_equal_allocators(__x);
2532      iterator __first1 = begin();
2533      iterator __last1 = end();
2534      iterator __first2 = __x.begin();
2535      iterator __last2 = __x.end();
2536      while (__first1 != __last1 && __first2 != __last2)
2537        if (__comp(*__first2, *__first1))
2538   {
2539     iterator __next = __first2;
2540     _M_transfer(__first1, __first2, ++__next);
2541     __first2 = __next;
2542   }
2543        else
2544   ++__first1;
2545      if (__first2 != __last2)
2546        _M_transfer(__last1, __first2, __last2);
2547    }
2548       }
2549   template<typename _Tp, typename _Alloc>
2550     void
2551     list<_Tp, _Alloc>::
2552     sort()
2553     {
2554       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
2555    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
2556       {
2557         list __carry;
2558         list __tmp[64];
2559         list * __fill = &__tmp[0];
2560         list * __counter;
2561         do
2562    {
2563      __carry.splice(__carry.begin(), *this, begin());
2564      for(__counter = &__tmp[0];
2565   __counter != __fill && !__counter->empty();
2566   ++__counter)
2567        {
2568   __counter->merge(__carry);
2569   __carry.swap(*__counter);
2570        }
2571      __carry.swap(*__counter);
2572      if (__counter == __fill)
2573        ++__fill;
2574    }
2575  while ( !empty() );
2576         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
2577           __counter->merge(*(__counter - 1));
2578         swap( *(__fill - 1) );
2579       }
2580     }
2581   template<typename _Tp, typename _Alloc>
2582     template <typename _Predicate>
2583       void
2584       list<_Tp, _Alloc>::
2585       remove_if(_Predicate __pred)
2586       {
2587         iterator __first = begin();
2588         iterator __last = end();
2589         while (__first != __last)
2590    {
2591      iterator __next = __first;
2592      ++__next;
2593      if (__pred(*__first))
2594        _M_erase(__first);
2595      __first = __next;
2596    }
2597       }
2598   template<typename _Tp, typename _Alloc>
2599     template <typename _BinaryPredicate>
2600       void
2601       list<_Tp, _Alloc>::
2602       unique(_BinaryPredicate __binary_pred)
2603       {
2604         iterator __first = begin();
2605         iterator __last = end();
2606         if (__first == __last)
2607    return;
2608         iterator __next = __first;
2609         while (++__next != __last)
2610    {
2611      if (__binary_pred(*__first, *__next))
2612        _M_erase(__next);
2613      else
2614        __first = __next;
2615      __next = __first;
2616    }
2617       }
2618   template<typename _Tp, typename _Alloc>
2619     template <typename _StrictWeakOrdering>
2620       void
2621       list<_Tp, _Alloc>::
2622       sort(_StrictWeakOrdering __comp)
2623       {
2624  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
2625      && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
2626    {
2627      list __carry;
2628      list __tmp[64];
2629      list * __fill = &__tmp[0];
2630      list * __counter;
2631      do
2632        {
2633   __carry.splice(__carry.begin(), *this, begin());
2634   for(__counter = &__tmp[0];
2635       __counter != __fill && !__counter->empty();
2636       ++__counter)
2637     {
2638       __counter->merge(__carry, __comp);
2639       __carry.swap(*__counter);
2640     }
2641   __carry.swap(*__counter);
2642   if (__counter == __fill)
2643     ++__fill;
2644        }
2645      while ( !empty() );
2646      for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
2647        __counter->merge(*(__counter - 1), __comp);
2648      swap(*(__fill - 1));
2649    }
2650       }
2651 }
2652 extern void foobarit(void);
2653 class Game
2654 {
2655 public:
2656         struct BuildProject
2657         {
2658                 int posX;
2659         };
2660         std::list<BuildProject> buildProjects;
2661 };
2662 static Game game;
2663 static std::list<std::list<Game::BuildProject>::iterator>
2664 erasableBuildProjects;
2665 void *buildProjectSyncStepConcurrently(int id, int localTeam)
2666 {
2667         __transaction_relaxed {
2668                 std::list<std::list<Game::BuildProject>::iterator>::iterator it
2669 = erasableBuildProjects.begin();
2670                 foobarit();
2671                 game.buildProjects.erase( (std::list<Game::BuildProject>
2672 ::iterator) *it);
2673         }
2674         return 0;
2675 }
2676