projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | [/ File partition_point.qbk] |
| 2 | ||
| 3 | [section:partition_point partition_point ] | |
| 4 | ||
| 5 | [/license | |
| 6 | Copyright (c) 2010-2012 Marshall Clow | |
| 7 | ||
| 8 | Distributed under the Boost Software License, Version 1.0. | |
| 9 | (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
| 10 | ] | |
| 11 | ||
| 12 | The header file 'partition_point.hpp' contains two variants of a single algorithm, `partition_point`. Given a partitioned sequence and a predicate, the algorithm finds the partition point; i.e, the first element in the sequence that does not satisfy the predicate. | |
| 13 | ||
| 14 | The routine `partition_point` takes a partitioned sequence and a predicate. It returns an iterator which 'points to' the first element in the sequence that does not satisfy the predicate. If all the items in the sequence satisfy the predicate, then it returns one past the final element in the sequence. | |
| 15 | ||
| 16 | `partition_point` come in two forms; the first one takes two iterators to define the range. The second form takes a single range parameter, and uses Boost.Range to traverse it. | |
| 17 | ||
| 18 | ||
| 19 | [heading interface] | |
| 20 | ||
| 21 | There are two versions; one takes two iterators, and the other takes a range. | |
| 22 | ||
| 23 | `` | |
| 24 | template<typename ForwardIterator, typename Predicate> | |
| 25 | ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p ); | |
| 26 | template<typename Range, typename Predicate> | |
| 27 | boost::range_iterator<Range> partition_point ( const Range &r, Predicate p ); | |
| 28 | `` | |
| 29 | ||
| 30 | [heading Examples] | |
| 31 | ||
| 32 | Given the container `c` containing `{ 0, 1, 2, 3, 14, 15 }`, then | |
| 33 | `` | |
| 34 | bool lessThan10 ( int i ) { return i < 10; } | |
| 35 | bool isOdd ( int i ) { return i % 2 == 1; } | |
| 36 | ||
| 37 | partition_point ( c, lessThan10 ) --> c.begin () + 4 (pointing at 14) | |
| 38 | partition_point ( c.begin (), c.end (), lessThan10 ) --> c.begin () + 4 (pointing at 14) | |
| 39 | partition_point ( c.begin (), c.begin () + 3, lessThan10 ) -> c.begin () + 3 (end) | |
| 40 | partition_point ( c.end (), c.end (), isOdd ) --> c.end () // empty range | |
| 41 | `` | |
| 42 | ||
| 43 | [heading Iterator Requirements] | |
| 44 | ||
| 45 | `partition_point` requires forward iterators or better; it will not work on input iterators or output iterators. | |
| 46 | ||
| 47 | [heading Complexity] | |
| 48 | ||
| 49 | Both of the variants of `partition_point` run in ['O( log (N))] (logarithmic) time; that is, the predicate will be will be applied approximately ['log(N)] times. To do this, however, the algorithm needs to know the size of the sequence. For forward and bidirectional iterators, calculating the size of the sequence is an ['O(N)] operation. | |
| 50 | ||
| 51 | [heading Exception Safety] | |
| 52 | ||
| 53 | Both of the variants of `partition_point` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee. | |
| 54 | ||
| 55 | [heading Notes] | |
| 56 | ||
| 57 | * The iterator-based version of the routine `partition_point` is also available as part of the C++11 standard. | |
| 58 | ||
| 59 | * For empty ranges, the partition point is the end of the range. | |
| 60 | ||
| 61 | [endsect] | |
| 62 | ||
| 63 | [/ File partition_point.qbk | |
| 64 | Copyright 2011 Marshall Clow | |
| 65 | Distributed under the Boost Software License, Version 1.0. | |
| 66 | (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt). | |
| 67 | ] | |
| 68 |