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