+
+ /// Returns the index of the partition point according to the given predicate
+ // (the index of the first element of the second partition).
+ ///
+ /// The slice is assumed to be partitioned according to the given predicate.
+ /// This means that all elements for which the predicate returns true are at the start of the slice
+ /// and all elements for which the predicate returns false are at the end.
+ /// For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0
+ /// (all odd numbers are at the start, all even at the end).
+ ///
+ /// If this slice is not partitioned, the returned result is unspecified and meaningless,
+ /// as this method performs a kind of binary search.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(partition_point)]
+ ///
+ /// let v = [1, 2, 3, 3, 5, 6, 7];
+ /// let i = v.partition_point(|&x| x < 5);
+ ///
+ /// assert_eq!(i, 4);
+ /// assert!(v[..i].iter().all(|&x| x < 5));
+ /// assert!(v[i..].iter().all(|&x| !(x < 5)));
+ /// ```
+ #[unstable(feature = "partition_point", reason = "new API", issue = "73831")]
+ pub fn partition_point<P>(&self, mut pred: P) -> usize
+ where
+ P: FnMut(&T) -> bool,
+ {
+ let mut left = 0;
+ let mut right = self.len();
+
+ while left != right {
+ let mid = left + (right - left) / 2;
+ // SAFETY:
+ // When left < right, left <= mid < right.
+ // Therefore left always increases and right always decreases,
+ // and eigher of them is selected.
+ // In both cases left <= right is satisfied.
+ // Therefore if left < right in a step,
+ // left <= right is satisfied in the next step.
+ // Therefore as long as left != right, 0 <= left < right <= len is satisfied
+ // and if this case 0 <= mid < len is satisfied too.
+ let value = unsafe { self.get_unchecked(mid) };
+ if pred(value) {
+ left = mid + 1;
+ } else {
+ right = mid;
+ }
+ }
+
+ left
+ }