1// { dg-do compile } 2// { dg-options "-fgnu-tm -O2" } 3 4typedef __PTRDIFF_TYPE__ ptrdiff_t; 5typedef __SIZE_TYPE__ size_t; 6namespace std __attribute__ ((__visibility__ ("default"))) { 7 using ::ptrdiff_t; 8 using ::size_t; 9} 10namespace 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 43namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { 44 template<typename _Iterator, typename _Container> 45 class __normal_iterator; 46} 47namespace 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 281namespace __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 400namespace __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 442namespace 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} 460namespace 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 509namespace 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 558namespace 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} 625namespace 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} 881namespace __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} 1026namespace std 1027{ 1028 namespace __debug { } 1029} 1030namespace __gnu_debug 1031{ 1032 using namespace std::__debug; 1033} 1034namespace 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} 1524namespace 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 1626extern "C++" { 1627namespace 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} 1651namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { 1652 void __verbose_terminate_handler(); 1653} 1654} 1655extern "C++" { 1656namespace 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} 1670void* operator new(std::size_t) throw (std::bad_alloc); 1671void* operator new[](std::size_t) throw (std::bad_alloc); 1672void operator delete(void*) throw(); 1673void operator delete[](void*) throw(); 1674void* operator new(std::size_t, const std::nothrow_t&) throw(); 1675void* operator new[](std::size_t, const std::nothrow_t&) throw(); 1676void operator delete(void*, const std::nothrow_t&) throw(); 1677void operator delete[](void*, const std::nothrow_t&) throw(); 1678inline void* operator new(std::size_t, void* __p) throw() { return __p; } 1679inline void* operator new[](std::size_t, void* __p) throw() { return __p; } 1680inline void operator delete (void*, void*) throw() { } 1681inline void operator delete[](void*, void*) throw() { } 1682} 1683namespace __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} 1737namespace 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} 1820namespace 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} 2356namespace 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} 2652extern void foobarit(void); 2653class Game 2654{ 2655public: 2656 struct BuildProject 2657 { 2658 int posX; 2659 }; 2660 std::list<BuildProject> buildProjects; 2661}; 2662static Game game; 2663static std::list<std::list<Game::BuildProject>::iterator> 2664erasableBuildProjects; 2665void *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 2677