summaryrefslogtreecommitdiffstats
path: root/library/alloc/src/collections/btree
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--library/alloc/src/collections/btree/dedup_sorted_iter.rs4
-rw-r--r--library/alloc/src/collections/btree/map.rs41
-rw-r--r--library/alloc/src/collections/btree/map/entry.rs10
-rw-r--r--library/alloc/src/collections/btree/node.rs22
-rw-r--r--library/alloc/src/collections/btree/set.rs26
5 files changed, 63 insertions, 40 deletions
diff --git a/library/alloc/src/collections/btree/dedup_sorted_iter.rs b/library/alloc/src/collections/btree/dedup_sorted_iter.rs
index 60bf83b83..17ee78045 100644
--- a/library/alloc/src/collections/btree/dedup_sorted_iter.rs
+++ b/library/alloc/src/collections/btree/dedup_sorted_iter.rs
@@ -3,7 +3,9 @@ use core::iter::Peekable;
/// A iterator for deduping the key of a sorted iterator.
/// When encountering the duplicated key, only the last key-value pair is yielded.
///
-/// Used by [`BTreeMap::bulk_build_from_sorted_iter`].
+/// Used by [`BTreeMap::bulk_build_from_sorted_iter`][1].
+///
+/// [1]: crate::collections::BTreeMap::bulk_build_from_sorted_iter
pub struct DedupSortedIter<K, V, I>
where
I: Iterator<Item = (K, V)>,
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index cacbd54b6..8a7719347 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -580,7 +580,7 @@ impl<K, V> BTreeMap<K, V> {
/// map.insert(1, "a");
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
+ #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
#[must_use]
pub const fn new() -> BTreeMap<K, V> {
BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global), _marker: PhantomData }
@@ -703,7 +703,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// Basic usage:
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
@@ -712,7 +711,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// map.insert(2, "a");
/// assert_eq!(map.first_key_value(), Some((&1, &"b")));
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn first_key_value(&self) -> Option<(&K, &V)>
where
K: Ord,
@@ -727,7 +726,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// # Examples
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
@@ -741,7 +739,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// assert_eq!(*map.get(&1).unwrap(), "first");
/// assert_eq!(*map.get(&2).unwrap(), "b");
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
where
K: Ord,
@@ -765,7 +763,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// Draining elements in ascending order, while keeping a usable map each iteration.
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
@@ -776,7 +773,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// }
/// assert!(map.is_empty());
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn pop_first(&mut self) -> Option<(K, V)>
where
K: Ord,
@@ -792,7 +789,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// Basic usage:
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
@@ -800,7 +796,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// map.insert(2, "a");
/// assert_eq!(map.last_key_value(), Some((&2, &"a")));
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn last_key_value(&self) -> Option<(&K, &V)>
where
K: Ord,
@@ -815,7 +811,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// # Examples
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
@@ -829,7 +824,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// assert_eq!(*map.get(&1).unwrap(), "a");
/// assert_eq!(*map.get(&2).unwrap(), "last");
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
where
K: Ord,
@@ -853,7 +848,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// Draining elements in descending order, while keeping a usable map each iteration.
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
@@ -864,7 +858,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// }
/// assert!(map.is_empty());
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn pop_last(&mut self) -> Option<(K, V)>
where
K: Ord,
@@ -1099,6 +1093,9 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// Moves all elements from `other` into `self`, leaving `other` empty.
///
+ /// If a key from `other` is already present in `self`, the respective
+ /// value from `self` will be overwritten with the respective value from `other`.
+ ///
/// # Examples
///
/// ```
@@ -1107,10 +1104,10 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// let mut a = BTreeMap::new();
/// a.insert(1, "a");
/// a.insert(2, "b");
- /// a.insert(3, "c");
+ /// a.insert(3, "c"); // Note: Key (3) also present in b.
///
/// let mut b = BTreeMap::new();
- /// b.insert(3, "d");
+ /// b.insert(3, "d"); // Note: Key (3) also present in a.
/// b.insert(4, "e");
/// b.insert(5, "f");
///
@@ -1121,7 +1118,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
///
/// assert_eq!(a[&1], "a");
/// assert_eq!(a[&2], "b");
- /// assert_eq!(a[&3], "d");
+ /// assert_eq!(a[&3], "d"); // Note: "c" has been overwritten.
/// assert_eq!(a[&4], "e");
/// assert_eq!(a[&5], "f");
/// ```
@@ -2392,7 +2389,11 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// ```
#[must_use]
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
+ #[rustc_const_unstable(
+ feature = "const_btree_len",
+ issue = "71835",
+ implied_by = "const_btree_new"
+ )]
pub const fn len(&self) -> usize {
self.length
}
@@ -2413,7 +2414,11 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
/// ```
#[must_use]
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
+ #[rustc_const_unstable(
+ feature = "const_btree_len",
+ issue = "71835",
+ implied_by = "const_btree_new"
+ )]
pub const fn is_empty(&self) -> bool {
self.len() == 0
}
diff --git a/library/alloc/src/collections/btree/map/entry.rs b/library/alloc/src/collections/btree/map/entry.rs
index b6eecf9b0..370b58864 100644
--- a/library/alloc/src/collections/btree/map/entry.rs
+++ b/library/alloc/src/collections/btree/map/entry.rs
@@ -133,6 +133,16 @@ impl<'a, K: Debug + Ord, V: Debug, A: Allocator + Clone> fmt::Display
}
}
+#[unstable(feature = "map_try_insert", issue = "82766")]
+impl<'a, K: core::fmt::Debug + Ord, V: core::fmt::Debug> core::error::Error
+ for crate::collections::btree_map::OccupiedError<'a, K, V>
+{
+ #[allow(deprecated)]
+ fn description(&self) -> &str {
+ "key already exists"
+ }
+}
+
impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> {
/// Ensures a value is in the entry by inserting the default if empty, and returns
/// a mutable reference to the value in the entry.
diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs
index d831161bc..da766b67a 100644
--- a/library/alloc/src/collections/btree/node.rs
+++ b/library/alloc/src/collections/btree/node.rs
@@ -206,9 +206,9 @@ impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {}
-unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {}
-unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {}
-unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {}
+unsafe impl<K: Sync, V: Sync, Type> Send for NodeRef<marker::Immut<'_>, K, V, Type> {}
+unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Mut<'_>, K, V, Type> {}
+unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::ValMut<'_>, K, V, Type> {}
unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {}
unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {}
@@ -318,7 +318,7 @@ impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type>
pub fn ascend(
self,
) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> {
- assert!(BorrowType::PERMITS_TRAVERSAL);
+ let _ = BorrowType::TRAVERSAL_PERMIT;
// We need to use raw pointers to nodes because, if BorrowType is marker::ValMut,
// there might be outstanding mutable references to values that we must not invalidate.
let leaf_ptr: *const _ = Self::as_leaf_ptr(&self);
@@ -1003,7 +1003,7 @@ impl<BorrowType: marker::BorrowType, K, V>
/// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
/// both, upon success, do nothing.
pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
- assert!(BorrowType::PERMITS_TRAVERSAL);
+ let _ = BorrowType::TRAVERSAL_PERMIT;
// We need to use raw pointers to nodes because, if BorrowType is
// marker::ValMut, there might be outstanding mutable references to
// values that we must not invalidate. There's no worry accessing the
@@ -1666,15 +1666,17 @@ pub mod marker {
pub struct ValMut<'a>(PhantomData<&'a mut ()>);
pub trait BorrowType {
- // Whether node references of this borrow type allow traversing
- // to other nodes in the tree.
- const PERMITS_TRAVERSAL: bool = true;
+ // If node references of this borrow type allow traversing to other
+ // nodes in the tree, this constant can be evaluated. Thus reading it
+ // serves as a compile-time assertion.
+ const TRAVERSAL_PERMIT: () = ();
}
impl BorrowType for Owned {
- // Traversal isn't needed, it happens using the result of `borrow_mut`.
+ // Reject evaluation, because traversal isn't needed. Instead traversal
+ // happens using the result of `borrow_mut`.
// By disabling traversal, and only creating new references to roots,
// we know that every reference of the `Owned` type is to a root node.
- const PERMITS_TRAVERSAL: bool = false;
+ const TRAVERSAL_PERMIT: () = panic!();
}
impl BorrowType for Dying {}
impl<'a> BorrowType for Immut<'a> {}
diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs
index 2cfc08074..4ddb21192 100644
--- a/library/alloc/src/collections/btree/set.rs
+++ b/library/alloc/src/collections/btree/set.rs
@@ -343,7 +343,7 @@ impl<T> BTreeSet<T> {
/// let mut set: BTreeSet<i32> = BTreeSet::new();
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
+ #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
#[must_use]
pub const fn new() -> BTreeSet<T> {
BTreeSet { map: BTreeMap::new() }
@@ -786,7 +786,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// Basic usage:
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeSet;
///
/// let mut set = BTreeSet::new();
@@ -797,7 +796,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// assert_eq!(set.first(), Some(&1));
/// ```
#[must_use]
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn first(&self) -> Option<&T>
where
T: Ord,
@@ -813,7 +812,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// Basic usage:
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeSet;
///
/// let mut set = BTreeSet::new();
@@ -824,7 +822,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// assert_eq!(set.last(), Some(&2));
/// ```
#[must_use]
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn last(&self) -> Option<&T>
where
T: Ord,
@@ -838,7 +836,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// # Examples
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeSet;
///
/// let mut set = BTreeSet::new();
@@ -849,7 +846,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// }
/// assert!(set.is_empty());
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn pop_first(&mut self) -> Option<T>
where
T: Ord,
@@ -863,7 +860,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// # Examples
///
/// ```
- /// #![feature(map_first_last)]
/// use std::collections::BTreeSet;
///
/// let mut set = BTreeSet::new();
@@ -874,7 +870,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// }
/// assert!(set.is_empty());
/// ```
- #[unstable(feature = "map_first_last", issue = "62924")]
+ #[stable(feature = "map_first_last", since = "1.66.0")]
pub fn pop_last(&mut self) -> Option<T>
where
T: Ord,
@@ -1174,7 +1170,11 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// ```
#[must_use]
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
+ #[rustc_const_unstable(
+ feature = "const_btree_len",
+ issue = "71835",
+ implied_by = "const_btree_new"
+ )]
pub const fn len(&self) -> usize {
self.map.len()
}
@@ -1193,7 +1193,11 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
/// ```
#[must_use]
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
+ #[rustc_const_unstable(
+ feature = "const_btree_len",
+ issue = "71835",
+ implied_by = "const_btree_new"
+ )]
pub const fn is_empty(&self) -> bool {
self.len() == 0
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-23 14:37:14 +0000