1// { dg-do compile } 2 3// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING3. If not see 18// <http://www.gnu.org/licenses/>. 19 20#include <algorithm> 21 22namespace std 23 { 24 // 25.1, non-modifying sequence operations: 25 template<typename _IIter, typename _Funct> 26 _Funct 27 for_each(_IIter, _IIter, _Funct); 28 29 template<typename _IIter, typename _Tp> 30 _IIter 31 find(_IIter, _IIter, const _Tp&); 32 33 template<typename _IIter, typename _Predicate> 34 _IIter 35 find_if(_IIter, _IIter, _Predicate); 36 37#ifdef __GXX_EXPERIMENTAL_CXX0X__ 38 template<typename _IIter, typename _Predicate> 39 bool 40 all_of(_IIter, _IIter, _Predicate); 41 42 template<typename _IIter, typename _Predicate> 43 bool 44 any_of(_IIter, _IIter, _Predicate); 45 46 template<typename _IIter, typename _Predicate> 47 bool 48 none_of(_IIter, _IIter, _Predicate); 49 50 template<typename _IIter, typename _Predicate> 51 _IIter 52 find_if_not(_IIter, _IIter, _Predicate); 53 54 template<typename _IIter, typename _Predicate> 55 bool 56 is_partitioned(_IIter, _IIter, _Predicate); 57 58 template<typename _FIter, typename _Predicate> 59 _FIter 60 partition_point(_FIter, _FIter, _Predicate); 61#endif 62 63 template<typename _FIter1, typename _FIter2> 64 _FIter1 65 find_end(_FIter1, _FIter1, _FIter2, _FIter2); 66 67 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate> 68 _FIter1 69 find_end(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate); 70 71 template<typename _FIter1, typename _FIter2> 72 _FIter1 73 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2); 74 75 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate> 76 _FIter1 77 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate); 78 79 template<typename _FIter> 80 _FIter 81 adjacent_find(_FIter, _FIter); 82 83 template<typename _FIter, typename _BinaryPredicate> 84 _FIter 85 adjacent_find(_FIter, _FIter, _BinaryPredicate); 86 87 template<typename _IIter, typename _Tp> 88 typename iterator_traits<_IIter>::difference_type 89 count(_IIter, _IIter, const _Tp&); 90 91 template<typename _IIter, typename _Predicate> 92 typename iterator_traits<_IIter>::difference_type 93 count_if(_IIter, _IIter, _Predicate); 94 95 template<typename _IIter1, typename _IIter2> 96 pair<_IIter1, _IIter2> 97 mismatch(_IIter1, _IIter1, _IIter2); 98 99 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 100 pair<_IIter1, _IIter2> 101 mismatch(_IIter1, _IIter1, _IIter2, _BinaryPredicate); 102 103 template<typename _IIter1, typename _IIter2> 104 bool 105 equal(_IIter1, _IIter1, _IIter2); 106 107 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 108 bool 109 equal(_IIter1, _IIter1, _IIter2, _BinaryPredicate); 110 111 template<typename _FIter1, typename _FIter2> 112 _FIter1 113 search(_FIter1, _FIter1, _FIter2, _FIter2); 114 115 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate> 116 _FIter1 117 search(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate); 118 119 template<typename _FIter, typename _Size, typename _Tp> 120 _FIter 121 search_n(_FIter, _FIter, _Size, const _Tp&); 122 123 template<typename _FIter, typename _Size, typename _Tp, 124 typename _BinaryPredicate> 125 _FIter 126 search_n(_FIter, _FIter, _Size, const _Tp&, _BinaryPredicate); 127 128 // 25.2, modifying sequence operations: 129 // 25.2.1, copy: 130 template<typename _IIter, typename _OIter> 131 _OIter 132 copy(_IIter, _IIter, _OIter); 133 134 template<typename _BIter1, typename _BIter2> 135 _BIter2 136 copy_backward (_BIter1, _BIter1, _BIter2); 137 138 // 25.2.2, swap: 139 template<typename _Tp> 140 void 141 swap(_Tp&, _Tp& b); 142 143#ifdef __GXX_EXPERIMENTAL_CXX0X__ 144 template<typename _Tp, size_t _Nm> 145 void 146 swap(_Tp (&)[_Nm], _Tp (&)[_Nm]); 147#endif 148 149 template<typename _FIter1, typename _FIter2> 150 _FIter2 151 swap_ranges(_FIter1 first1, _FIter1, _FIter2); 152 153 template<typename _FIter1, typename _FIter2> 154 void 155 iter_swap(_FIter1, _FIter2 b); 156 157 template<typename _IIter, typename _OIter, typename _UnaryOperation> 158 _OIter 159 transform(_IIter, _IIter, _OIter, _UnaryOperation op); 160 161 template<typename _IIter1, typename _IIter2, typename _OIter, 162 typename _BinaryOperation> 163 _OIter 164 transform(_IIter1, _IIter1, _IIter2, _OIter, _BinaryOperation); 165 166 template<typename _FIter, typename _Tp> 167 void 168 replace(_FIter, _FIter, const _Tp&, const _Tp&); 169 170 template<typename _FIter, typename _Predicate, typename _Tp> 171 void 172 replace_if(_FIter, _FIter, _Predicate, const _Tp&); 173 174 template<typename _IIter, typename _OIter, typename _Tp> 175 _OIter 176 replace_copy(_IIter, _IIter, _OIter, const _Tp&, const _Tp&); 177 178 template<typename _Iter, typename _OIter, typename _Predicate, typename _Tp> 179 _OIter 180 replace_copy_if(_Iter, _Iter, _OIter, _Predicate, const _Tp&); 181 182 template<typename _FIter, typename _Tp> 183 void 184 fill(_FIter, _FIter, const _Tp&); 185 186 template<typename _OIter, typename _Size, typename _Tp> 187 void 188 fill_n(_OIter, _Size n, const _Tp&); 189 190 template<typename _FIter, typename _Generator> 191 void 192 generate(_FIter, _FIter, _Generator); 193 194 template<typename _OIter, typename _Size, typename _Generator> 195 void 196 generate_n(_OIter, _Size, _Generator); 197 198 template<typename _FIter, typename _Tp> 199 _FIter 200 remove(_FIter, _FIter, const _Tp&); 201 202 template<typename _FIter, typename _Predicate> 203 _FIter 204 remove_if(_FIter, _FIter, _Predicate); 205 206 template<typename _IIter, typename _OIter, typename _Tp> 207 _OIter 208 remove_copy(_IIter, _IIter, _OIter, const _Tp&); 209 210 template<typename _IIter, typename _OIter, typename _Predicate> 211 _OIter 212 remove_copy_if(_IIter, _IIter, _OIter, _Predicate); 213 214#ifdef __GXX_EXPERIMENTAL_CXX0X__ 215 template<typename _IIter, typename _OIter, typename _Predicate> 216 _OIter 217 copy_if(_IIter, _IIter, _OIter, _Predicate); 218 219 template<typename _IIter, typename _Size, typename _OIter> 220 _OIter 221 copy_n(_IIter, _Size, _OIter); 222 223 template<typename _IIter, typename _OIter1, 224 typename _OIter2, typename _Predicate> 225 pair<_OIter1, _OIter2> 226 partition_copy(_IIter, _IIter, _OIter1, _OIter2, _Predicate); 227#endif 228 229 template<typename _FIter> 230 _FIter 231 unique(_FIter, _FIter); 232 233 template<typename _FIter, typename _BinaryPredicate> 234 _FIter 235 unique(_FIter, _FIter, _BinaryPredicate); 236 237 template<typename _IIter, typename _OIter> 238 _OIter 239 unique_copy(_IIter, _IIter, _OIter); 240 241 template<typename _IIter, typename _OIter, typename _BinaryPredicate> 242 _OIter 243 unique_copy(_IIter, _IIter, _OIter, _BinaryPredicate); 244 245 template<typename _BIter> 246 void 247 reverse(_BIter, _BIter); 248 249 template<typename _BIter, typename _OIter> 250 _OIter 251 reverse_copy(_BIter, _BIter, _OIter); 252 253 template<typename _FIter> 254 void 255 rotate(_FIter, _FIter, _FIter); 256 257 template<typename _FIter, typename _OIter> 258 _OIter 259 rotate_copy (_FIter, _FIter, _FIter, _OIter); 260 261 template<typename _RAIter> 262 void 263 random_shuffle(_RAIter, _RAIter); 264 265 template<typename _RAIter, typename _Generator> 266 void 267 random_shuffle(_RAIter, _RAIter, _Generator&); 268 269 // 25.2.12, partitions: 270 template<typename _BIter, typename _Predicate> 271 _BIter 272 partition(_BIter, _BIter, _Predicate); 273 274 template<typename _BIter, typename _Predicate> 275 _BIter 276 stable_partition(_BIter, _BIter, _Predicate); 277 278 // 25.3, sorting and related operations: 279 // 25.3.1, sorting: 280 template<typename _RAIter> 281 void 282 sort(_RAIter, _RAIter); 283 284 template<typename _RAIter, typename _Compare> 285 void 286 sort(_RAIter, _RAIter, _Compare); 287 288 template<typename _RAIter> 289 void 290 stable_sort(_RAIter, _RAIter); 291 292 template<typename _RAIter, typename _Compare> 293 void 294 stable_sort(_RAIter, _RAIter, _Compare); 295 296 template<typename _RAIter> 297 void 298 partial_sort(_RAIter, _RAIter, _RAIter); 299 300 template<typename _RAIter, typename _Compare> 301 void 302 partial_sort(_RAIter, _RAIter, _RAIter, _Compare); 303 304 template<typename _IIter, typename _RAIter> 305 _RAIter 306 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter); 307 308 template<typename _IIter, typename _RAIter, typename _Compare> 309 _RAIter 310 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter, _Compare); 311 312 template<typename _RAIter> 313 void 314 nth_element(_RAIter, _RAIter, _RAIter); 315 316 template<typename _RAIter, typename _Compare> 317 void 318 nth_element(_RAIter, _RAIter, _RAIter, _Compare); 319 320 // 25.3.3, binary search: 321 template<typename _FIter, typename _Tp> 322 _FIter 323 lower_bound(_FIter, _FIter, const _Tp&); 324 325 template<typename _FIter, typename _Tp, typename _Compare> 326 _FIter 327 lower_bound(_FIter, _FIter, const _Tp&, _Compare); 328 329 template<typename _FIter, typename _Tp> 330 _FIter 331 upper_bound(_FIter, _FIter, const _Tp&); 332 333 template<typename _FIter, typename _Tp, typename _Compare> 334 _FIter 335 upper_bound(_FIter, _FIter, const _Tp&, _Compare); 336 337 template<typename _FIter, typename _Tp> 338 pair<_FIter, _FIter> 339 equal_range(_FIter, _FIter, const _Tp&); 340 341 template<typename _FIter, typename _Tp, typename _Compare> 342 pair<_FIter, _FIter> 343 equal_range(_FIter, _FIter, const _Tp&, _Compare); 344 345 template<typename _FIter, typename _Tp> 346 bool 347 binary_search(_FIter, _FIter, const _Tp&); 348 349 template<typename _FIter, typename _Tp, typename _Compare> 350 bool 351 binary_search(_FIter, _FIter, const _Tp&, _Compare); 352 353 // 25.3.4, merge: 354 template<typename _IIter1, typename _IIter2, typename _OIter> 355 _OIter 356 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); 357 358 template<typename _IIter1, typename _IIter2, typename _OIter, 359 typename _Compare> 360 _OIter 361 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); 362 363 template<typename _BIter> 364 void 365 inplace_merge(_BIter, _BIter, _BIter); 366 367 template<typename _BIter, typename _Compare> 368 void 369 inplace_merge(_BIter, _BIter, _BIter, _Compare); 370 371 // 25.3.5, set operations: 372 template<typename _IIter1, typename _IIter2> 373 bool 374 includes(_IIter1, _IIter1, _IIter2, _IIter2); 375 376 template<typename _IIter1, typename _IIter2, typename _Compare> 377 bool 378 includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare); 379 380 template<typename _IIter1, typename _IIter2, typename _OIter> 381 _OIter 382 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); 383 384 template<typename _IIter1, typename _IIter2, typename _OIter, 385 typename _Compare> 386 _OIter 387 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); 388 389 template<typename _IIter1, typename _IIter2, typename _OIter> 390 _OIter 391 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); 392 393 template<typename _IIter1, typename _IIter2, typename _OIter, 394 typename _Compare> 395 _OIter 396 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); 397 398 template<typename _IIter1, typename _IIter2, typename _OIter> 399 _OIter 400 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); 401 402 template<typename _IIter1, typename _IIter2, typename _OIter, 403 typename _Compare> 404 _OIter 405 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); 406 407 template<typename _IIter1, typename _IIter2, typename _OIter> 408 _OIter 409 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); 410 411 template<typename _IIter1, typename _IIter2, typename _OIter, 412 typename _Compare> 413 _OIter 414 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, 415 _OIter, _Compare); 416 417 // 25.3.6, heap operations: 418 template<typename _RAIter> 419 void 420 push_heap(_RAIter, _RAIter); 421 422 template<typename _RAIter, typename _Compare> 423 void 424 push_heap(_RAIter, _RAIter, _Compare); 425 426 template<typename _RAIter> 427 void 428 pop_heap(_RAIter, _RAIter); 429 430 template<typename _RAIter, typename _Compare> 431 void 432 pop_heap(_RAIter, _RAIter, _Compare); 433 434 template<typename _RAIter> 435 void 436 make_heap(_RAIter, _RAIter); 437 438 template<typename _RAIter, typename _Compare> 439 void 440 make_heap(_RAIter, _RAIter, _Compare); 441 442 template<typename _RAIter> 443 void 444 sort_heap(_RAIter, _RAIter); 445 446 template<typename _RAIter, typename _Compare> 447 void 448 sort_heap(_RAIter, _RAIter, _Compare); 449 450#ifdef __GXX_EXPERIMENTAL_CXX0X__ 451 template<typename _RAIter> 452 bool 453 is_heap(_RAIter, _RAIter); 454 455 template<typename _RAIter, typename _Compare> 456 bool 457 is_heap(_RAIter, _RAIter, _Compare); 458 459 template<typename _RAIter> 460 _RAIter 461 is_heap_until(_RAIter, _RAIter); 462 463 template<typename _RAIter, typename _Compare> 464 _RAIter 465 is_heap_until(_RAIter, _RAIter, _Compare); 466 467 template<typename _FIter> 468 bool 469 is_sorted(_FIter, _FIter); 470 471 template<typename _FIter, typename _Compare> 472 bool 473 is_sorted(_FIter, _FIter, _Compare); 474 475 template<typename _FIter> 476 _FIter 477 is_sorted_until(_FIter, _FIter); 478 479 template<typename _FIter, typename _Compare> 480 _FIter 481 is_sorted_until(_FIter, _FIter, _Compare); 482#endif 483 484 // 25.3.7, minimum and maximum: 485 template<typename _Tp> 486 const _Tp& 487 min(const _Tp&, const _Tp&); 488 489 template<typename _Tp, typename _Compare> 490 const _Tp& 491 min(const _Tp&, const _Tp&, _Compare); 492 493 template<typename _Tp> 494 const _Tp& 495 max(const _Tp&, const _Tp&); 496 497 template<typename _Tp, typename _Compare> 498 const _Tp& 499 max(const _Tp&, const _Tp&, _Compare); 500 501 template<typename _FIter> 502 _FIter 503 min_element(_FIter, _FIter); 504 505 template<typename _FIter, typename _Compare> 506 _FIter 507 min_element(_FIter, _FIter, _Compare); 508 509 template<typename _FIter> 510 _FIter 511 max_element(_FIter, _FIter); 512 513 template<typename _FIter, typename _Compare> 514 _FIter 515 max_element(_FIter, _FIter, _Compare); 516 517#ifdef __GXX_EXPERIMENTAL_CXX0X__ 518 template<typename _Tp> 519 pair<const _Tp&, const _Tp&> 520 minmax(const _Tp&, const _Tp&); 521 522 template<typename _Tp, typename _Compare> 523 pair<const _Tp&, const _Tp&> 524 minmax(const _Tp&, const _Tp&, _Compare); 525 526 template<typename _FIter> 527 pair<_FIter, _FIter> 528 minmax_element(_FIter, _FIter); 529 530 template<typename _FIter, typename _Compare> 531 pair<_FIter, _FIter> 532 minmax_element(_FIter, _FIter, _Compare); 533 534 template<typename _Tp> 535 _Tp 536 min(initializer_list<_Tp>); 537 538 template<typename _Tp, typename _Compare> 539 _Tp 540 min(initializer_list<_Tp>, _Compare); 541 542 template<typename _Tp> 543 _Tp 544 max(initializer_list<_Tp>); 545 546 template<typename _Tp, typename _Compare> 547 _Tp 548 max(initializer_list<_Tp>, _Compare); 549 550 template<typename _Tp> 551 pair<_Tp, _Tp> 552 minmax(initializer_list<_Tp>); 553 554 template<typename _Tp, typename _Compare> 555 pair<_Tp, _Tp> 556 minmax(initializer_list<_Tp>, _Compare); 557#endif 558 559 template<typename _IIter1, typename _IIter2> 560 bool 561 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2); 562 563 template<typename _IIter1, typename _IIter2, typename _Compare> 564 bool 565 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Compare); 566 567 // 25.3.9, permutations 568 template<typename _BIter> 569 bool 570 next_permutation(_BIter, _BIter); 571 572 template<typename _BIter, typename _Compare> 573 bool 574 next_permutation(_BIter, _BIter, _Compare); 575 576 template<typename _BIter> 577 bool 578 prev_permutation(_BIter, _BIter); 579 580 template<typename _BIter, typename _Compare> 581 bool 582 prev_permutation(_BIter, _BIter, _Compare); 583} 584