1 // (C) Copyright Herve Bronnimann 2004. 2 // 3 // Distributed under the Boost Software License, Version 1.0. (See accompanying 4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 6 /* 7 Revision history: 8 1 July 2004 9 Split the code into two headers to lessen dependence on 10 Boost.tuple. (Herve) 11 26 June 2004 12 Added the code for the boost minmax library. (Herve) 13 */ 14 15 #ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP 16 #define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP 17 18 /* PROPOSED STANDARD EXTENSIONS: 19 * 20 * minmax_element(first, last) 21 * Effect: std::make_pair( std::min_element(first, last), 22 * std::max_element(first, last) ); 23 * 24 * minmax_element(first, last, comp) 25 * Effect: std::make_pair( std::min_element(first, last, comp), 26 * std::max_element(first, last, comp) ); 27 */ 28 29 #include <utility> // for std::pair and std::make_pair 30 31 namespace boost { 32 33 namespace detail { // for obtaining a uniform version of minmax_element 34 // that compiles with VC++ 6.0 -- avoid the iterator_traits by 35 // having comparison object over iterator, not over dereferenced value 36 37 template <typename Iterator> 38 struct less_over_iter { operator ()boost::detail::less_over_iter39 bool operator()(Iterator const& it1, 40 Iterator const& it2) const { return *it1 < *it2; } 41 }; 42 43 template <typename Iterator, class BinaryPredicate> 44 struct binary_pred_over_iter { binary_pred_over_iterboost::detail::binary_pred_over_iter45 explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {} operator ()boost::detail::binary_pred_over_iter46 bool operator()(Iterator const& it1, 47 Iterator const& it2) const { return m_p(*it1, *it2); } 48 private: 49 BinaryPredicate m_p; 50 }; 51 52 // common base for the two minmax_element overloads 53 54 template <typename ForwardIter, class Compare > 55 std::pair<ForwardIter,ForwardIter> basic_minmax_element(ForwardIter first,ForwardIter last,Compare comp)56 basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp) 57 { 58 if (first == last) 59 return std::make_pair(last,last); 60 61 ForwardIter min_result = first; 62 ForwardIter max_result = first; 63 64 // if only one element 65 ForwardIter second = first; ++second; 66 if (second == last) 67 return std::make_pair(min_result, max_result); 68 69 // treat first pair separately (only one comparison for first two elements) 70 ForwardIter potential_min_result = last; 71 if (comp(first, second)) 72 max_result = second; 73 else { 74 min_result = second; 75 potential_min_result = first; 76 } 77 78 // then each element by pairs, with at most 3 comparisons per pair 79 first = ++second; if (first != last) ++second; 80 while (second != last) { 81 if (comp(first, second)) { 82 if (comp(first, min_result)) { 83 min_result = first; 84 potential_min_result = last; 85 } 86 if (comp(max_result, second)) 87 max_result = second; 88 } else { 89 if (comp(second, min_result)) { 90 min_result = second; 91 potential_min_result = first; 92 } 93 if (comp(max_result, first)) 94 max_result = first; 95 } 96 first = ++second; 97 if (first != last) ++second; 98 } 99 100 // if odd number of elements, treat last element 101 if (first != last) { // odd number of elements 102 if (comp(first, min_result)) 103 min_result = first, potential_min_result = last; 104 else if (comp(max_result, first)) 105 max_result = first; 106 } 107 108 // resolve min_result being incorrect with one extra comparison 109 // (in which case potential_min_result is necessarily the correct result) 110 if (potential_min_result != last 111 && !comp(min_result, potential_min_result)) 112 min_result = potential_min_result; 113 114 return std::make_pair(min_result,max_result); 115 } 116 117 } // namespace detail 118 119 template <typename ForwardIter> 120 std::pair<ForwardIter,ForwardIter> minmax_element(ForwardIter first,ForwardIter last)121 minmax_element(ForwardIter first, ForwardIter last) 122 { 123 return detail::basic_minmax_element(first, last, 124 detail::less_over_iter<ForwardIter>() ); 125 } 126 127 template <typename ForwardIter, class BinaryPredicate> 128 std::pair<ForwardIter,ForwardIter> minmax_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)129 minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 130 { 131 return detail::basic_minmax_element(first, last, 132 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 133 } 134 135 } 136 137 /* PROPOSED BOOST EXTENSIONS 138 * In the description below, [rfirst,rlast) denotes the reversed range 139 * of [first,last). Even though the iterator type of first and last may 140 * be only a Forward Iterator, it is possible to explain the semantics 141 * by assuming that it is a Bidirectional Iterator. In the sequel, 142 * reverse(ForwardIterator&) returns the reverse_iterator adaptor. 143 * This is not how the functions would be implemented! 144 * 145 * first_min_element(first, last) 146 * Effect: std::min_element(first, last); 147 * 148 * first_min_element(first, last, comp) 149 * Effect: std::min_element(first, last, comp); 150 * 151 * last_min_element(first, last) 152 * Effect: reverse( std::min_element(reverse(last), reverse(first)) ); 153 * 154 * last_min_element(first, last, comp) 155 * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) ); 156 * 157 * first_max_element(first, last) 158 * Effect: std::max_element(first, last); 159 * 160 * first_max_element(first, last, comp) 161 * Effect: max_element(first, last); 162 * 163 * last_max_element(first, last) 164 * Effect: reverse( std::max_element(reverse(last), reverse(first)) ); 165 * 166 * last_max_element(first, last, comp) 167 * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) ); 168 * 169 * first_min_first_max_element(first, last) 170 * Effect: std::make_pair( first_min_element(first, last), 171 * first_max_element(first, last) ); 172 * 173 * first_min_first_max_element(first, last, comp) 174 * Effect: std::make_pair( first_min_element(first, last, comp), 175 * first_max_element(first, last, comp) ); 176 * 177 * first_min_last_max_element(first, last) 178 * Effect: std::make_pair( first_min_element(first, last), 179 * last_max_element(first, last) ); 180 * 181 * first_min_last_max_element(first, last, comp) 182 * Effect: std::make_pair( first_min_element(first, last, comp), 183 * last_max_element(first, last, comp) ); 184 * 185 * last_min_first_max_element(first, last) 186 * Effect: std::make_pair( last_min_element(first, last), 187 * first_max_element(first, last) ); 188 * 189 * last_min_first_max_element(first, last, comp) 190 * Effect: std::make_pair( last_min_element(first, last, comp), 191 * first_max_element(first, last, comp) ); 192 * 193 * last_min_last_max_element(first, last) 194 * Effect: std::make_pair( last_min_element(first, last), 195 * last_max_element(first, last) ); 196 * 197 * last_min_last_max_element(first, last, comp) 198 * Effect: std::make_pair( last_min_element(first, last, comp), 199 * last_max_element(first, last, comp) ); 200 */ 201 202 namespace boost { 203 204 // Min_element and max_element variants 205 206 namespace detail { // common base for the overloads 207 208 template <typename ForwardIter, class BinaryPredicate> 209 ForwardIter 210 basic_first_min_element(ForwardIter first, ForwardIter last, 211 BinaryPredicate comp) 212 { 213 if (first == last) return last; 214 ForwardIter min_result = first; 215 while (++first != last) 216 if (comp(first, min_result)) 217 min_result = first; 218 return min_result; 219 } 220 221 template <typename ForwardIter, class BinaryPredicate> 222 ForwardIter 223 basic_last_min_element(ForwardIter first, ForwardIter last, 224 BinaryPredicate comp) 225 { 226 if (first == last) return last; 227 ForwardIter min_result = first; 228 while (++first != last) 229 if (!comp(min_result, first)) 230 min_result = first; 231 return min_result; 232 } 233 234 template <typename ForwardIter, class BinaryPredicate> 235 ForwardIter 236 basic_first_max_element(ForwardIter first, ForwardIter last, 237 BinaryPredicate comp) 238 { 239 if (first == last) return last; 240 ForwardIter max_result = first; 241 while (++first != last) 242 if (comp(max_result, first)) 243 max_result = first; 244 return max_result; 245 } 246 247 template <typename ForwardIter, class BinaryPredicate> 248 ForwardIter 249 basic_last_max_element(ForwardIter first, ForwardIter last, 250 BinaryPredicate comp) 251 { 252 if (first == last) return last; 253 ForwardIter max_result = first; 254 while (++first != last) 255 if (!comp(first, max_result)) 256 max_result = first; 257 return max_result; 258 } 259 260 } // namespace detail 261 262 template <typename ForwardIter> 263 ForwardIter first_min_element(ForwardIter first,ForwardIter last)264 first_min_element(ForwardIter first, ForwardIter last) 265 { 266 return detail::basic_first_min_element(first, last, 267 detail::less_over_iter<ForwardIter>() ); 268 } 269 270 template <typename ForwardIter, class BinaryPredicate> 271 ForwardIter 272 first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 273 { 274 return detail::basic_first_min_element(first, last, 275 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 276 } 277 278 template <typename ForwardIter> 279 ForwardIter last_min_element(ForwardIter first,ForwardIter last)280 last_min_element(ForwardIter first, ForwardIter last) 281 { 282 return detail::basic_last_min_element(first, last, 283 detail::less_over_iter<ForwardIter>() ); 284 } 285 286 template <typename ForwardIter, class BinaryPredicate> 287 ForwardIter 288 last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 289 { 290 return detail::basic_last_min_element(first, last, 291 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 292 } 293 294 template <typename ForwardIter> 295 ForwardIter first_max_element(ForwardIter first,ForwardIter last)296 first_max_element(ForwardIter first, ForwardIter last) 297 { 298 return detail::basic_first_max_element(first, last, 299 detail::less_over_iter<ForwardIter>() ); 300 } 301 302 template <typename ForwardIter, class BinaryPredicate> 303 ForwardIter 304 first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 305 { 306 return detail::basic_first_max_element(first, last, 307 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 308 } 309 310 template <typename ForwardIter> 311 ForwardIter last_max_element(ForwardIter first,ForwardIter last)312 last_max_element(ForwardIter first, ForwardIter last) 313 { 314 return detail::basic_last_max_element(first, last, 315 detail::less_over_iter<ForwardIter>() ); 316 } 317 318 template <typename ForwardIter, class BinaryPredicate> 319 ForwardIter 320 last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 321 { 322 return detail::basic_last_max_element(first, last, 323 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 324 } 325 326 327 // Minmax_element variants -- comments removed 328 329 namespace detail { 330 331 template <typename ForwardIter, class BinaryPredicate> 332 std::pair<ForwardIter,ForwardIter> basic_first_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)333 basic_first_min_last_max_element(ForwardIter first, ForwardIter last, 334 BinaryPredicate comp) 335 { 336 if (first == last) 337 return std::make_pair(last,last); 338 339 ForwardIter min_result = first; 340 ForwardIter max_result = first; 341 342 ForwardIter second = ++first; 343 if (second == last) 344 return std::make_pair(min_result, max_result); 345 346 if (comp(second, min_result)) 347 min_result = second; 348 else 349 max_result = second; 350 351 first = ++second; if (first != last) ++second; 352 while (second != last) { 353 if (!comp(second, first)) { 354 if (comp(first, min_result)) 355 min_result = first; 356 if (!comp(second, max_result)) 357 max_result = second; 358 } else { 359 if (comp(second, min_result)) 360 min_result = second; 361 if (!comp(first, max_result)) 362 max_result = first; 363 } 364 first = ++second; if (first != last) ++second; 365 } 366 367 if (first != last) { 368 if (comp(first, min_result)) 369 min_result = first; 370 else if (!comp(first, max_result)) 371 max_result = first; 372 } 373 374 return std::make_pair(min_result, max_result); 375 } 376 377 template <typename ForwardIter, class BinaryPredicate> 378 std::pair<ForwardIter,ForwardIter> basic_last_min_first_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)379 basic_last_min_first_max_element(ForwardIter first, ForwardIter last, 380 BinaryPredicate comp) 381 { 382 if (first == last) return std::make_pair(last,last); 383 384 ForwardIter min_result = first; 385 ForwardIter max_result = first; 386 387 ForwardIter second = ++first; 388 if (second == last) 389 return std::make_pair(min_result, max_result); 390 391 if (comp(max_result, second)) 392 max_result = second; 393 else 394 min_result = second; 395 396 first = ++second; if (first != last) ++second; 397 while (second != last) { 398 if (comp(first, second)) { 399 if (!comp(min_result, first)) 400 min_result = first; 401 if (comp(max_result, second)) 402 max_result = second; 403 } else { 404 if (!comp(min_result, second)) 405 min_result = second; 406 if (comp(max_result, first)) 407 max_result = first; 408 } 409 first = ++second; if (first != last) ++second; 410 } 411 412 if (first != last) { 413 if (!comp(min_result, first)) 414 min_result = first; 415 else if (comp(max_result, first)) 416 max_result = first; 417 } 418 419 return std::make_pair(min_result, max_result); 420 } 421 422 template <typename ForwardIter, class BinaryPredicate> 423 std::pair<ForwardIter,ForwardIter> basic_last_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)424 basic_last_min_last_max_element(ForwardIter first, ForwardIter last, 425 BinaryPredicate comp) 426 { 427 if (first == last) return std::make_pair(last,last); 428 429 ForwardIter min_result = first; 430 ForwardIter max_result = first; 431 432 ForwardIter second = first; ++second; 433 if (second == last) 434 return std::make_pair(min_result,max_result); 435 436 ForwardIter potential_max_result = last; 437 if (comp(first, second)) 438 max_result = second; 439 else { 440 min_result = second; 441 potential_max_result = second; 442 } 443 444 first = ++second; if (first != last) ++second; 445 while (second != last) { 446 if (comp(first, second)) { 447 if (!comp(min_result, first)) 448 min_result = first; 449 if (!comp(second, max_result)) { 450 max_result = second; 451 potential_max_result = last; 452 } 453 } else { 454 if (!comp(min_result, second)) 455 min_result = second; 456 if (!comp(first, max_result)) { 457 max_result = first; 458 potential_max_result = second; 459 } 460 } 461 first = ++second; 462 if (first != last) ++second; 463 } 464 465 if (first != last) { 466 if (!comp(min_result, first)) 467 min_result = first; 468 if (!comp(first, max_result)) { 469 max_result = first; 470 potential_max_result = last; 471 } 472 } 473 474 if (potential_max_result != last 475 && !comp(potential_max_result, max_result)) 476 max_result = potential_max_result; 477 478 return std::make_pair(min_result,max_result); 479 } 480 481 } // namespace detail 482 483 template <typename ForwardIter> 484 inline std::pair<ForwardIter,ForwardIter> first_min_first_max_element(ForwardIter first,ForwardIter last)485 first_min_first_max_element(ForwardIter first, ForwardIter last) 486 { 487 return minmax_element(first, last); 488 } 489 490 template <typename ForwardIter, class BinaryPredicate> 491 inline std::pair<ForwardIter,ForwardIter> first_min_first_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)492 first_min_first_max_element(ForwardIter first, ForwardIter last, 493 BinaryPredicate comp) 494 { 495 return minmax_element(first, last, comp); 496 } 497 498 template <typename ForwardIter> 499 std::pair<ForwardIter,ForwardIter> first_min_last_max_element(ForwardIter first,ForwardIter last)500 first_min_last_max_element(ForwardIter first, ForwardIter last) 501 { 502 return detail::basic_first_min_last_max_element(first, last, 503 detail::less_over_iter<ForwardIter>() ); 504 } 505 506 template <typename ForwardIter, class BinaryPredicate> 507 inline std::pair<ForwardIter,ForwardIter> first_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)508 first_min_last_max_element(ForwardIter first, ForwardIter last, 509 BinaryPredicate comp) 510 { 511 return detail::basic_first_min_last_max_element(first, last, 512 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 513 } 514 515 template <typename ForwardIter> 516 std::pair<ForwardIter,ForwardIter> last_min_first_max_element(ForwardIter first,ForwardIter last)517 last_min_first_max_element(ForwardIter first, ForwardIter last) 518 { 519 return detail::basic_last_min_first_max_element(first, last, 520 detail::less_over_iter<ForwardIter>() ); 521 } 522 523 template <typename ForwardIter, class BinaryPredicate> 524 inline std::pair<ForwardIter,ForwardIter> last_min_first_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)525 last_min_first_max_element(ForwardIter first, ForwardIter last, 526 BinaryPredicate comp) 527 { 528 return detail::basic_last_min_first_max_element(first, last, 529 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 530 } 531 532 template <typename ForwardIter> 533 std::pair<ForwardIter,ForwardIter> last_min_last_max_element(ForwardIter first,ForwardIter last)534 last_min_last_max_element(ForwardIter first, ForwardIter last) 535 { 536 return detail::basic_last_min_last_max_element(first, last, 537 detail::less_over_iter<ForwardIter>() ); 538 } 539 540 template <typename ForwardIter, class BinaryPredicate> 541 inline std::pair<ForwardIter,ForwardIter> last_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)542 last_min_last_max_element(ForwardIter first, ForwardIter last, 543 BinaryPredicate comp) 544 { 545 return detail::basic_last_min_last_max_element(first, last, 546 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 547 } 548 549 } // namespace boost 550 551 #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP 552