Auto merge of #84111 - bstrie:hashfrom, r=joshtriplett

Stabilize `impl From<[(K, V); N]> for HashMap` (and friends)

In addition to allowing HashMap to participate in Into/From conversion, this adds the long-requested ability to use constructor-like syntax for initializing a HashMap:
```rust
let map = HashMap::from([
    (1, 2),
    (3, 4),
    (5, 6)
]);
```
This addition is highly motivated by existing precedence, e.g. it is already possible to similarly construct a Vec from a fixed-size array:
```rust
let vec = Vec::from([1, 2, 3]);
```
...and it is already possible to collect a Vec of tuples into a HashMap (and vice-versa):
```rust
let vec = Vec::from([(1, 2)]);
let map: HashMap<_, _> = vec.into_iter().collect();
let vec: Vec<(_, _)> = map.into_iter().collect();
```
...and of course it is likewise possible to collect a fixed-size array of tuples into a HashMap ([but not vice-versa just yet](https://github.com/rust-lang/rust/issues/81615)):
```rust
let arr = [(1, 2)];
let map: HashMap<_, _> = std::array::IntoIter::new(arr).collect();
```
Therefore this addition seems like a no-brainer.

As for any impl, this would be insta-stable.

7 files changed, 131 insertions, 1 deletions

diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs
index 2f656e4a6b4..8a29af3fe07 100644
--- a/library/alloc/src/collections/binary_heap.rs
+++ b/library/alloc/src/collections/binary_heap.rs
@@ -209,6 +209,14 @@ use super::SpecExtend;
 /// assert!(heap.is_empty())
 /// ```
 ///
+/// A `BinaryHeap` with a known list of items can be initialized from an array:
+///
+/// ```
+/// use std::collections::BinaryHeap;
+///
+/// let heap = BinaryHeap::from([1, 5, 2]);
+/// ```
+///
 /// ## Min-heap
 ///
 /// Either `std::cmp::Reverse` or a custom `Ord` implementation can be used to
@@ -1465,6 +1473,22 @@ impl<T: Ord> From<Vec<T>> for BinaryHeap<T> {
     }
 }
 
+#[stable(feature = "std_collections_from_array", since = "1.56.0")]
+impl<T: Ord, const N: usize> From<[T; N]> for BinaryHeap<T> {
+    /// ```
+    /// use std::collections::BinaryHeap;
+    ///
+    /// let mut h1 = BinaryHeap::from([1, 4, 2, 3]);
+    /// let mut h2: BinaryHeap<_> = [1, 4, 2, 3].into();
+    /// while let Some((a, b)) = h1.pop().zip(h2.pop()) {
+    ///     assert_eq!(a, b);
+    /// }
+    /// ```
+    fn from(arr: [T; N]) -> Self {
+        core::array::IntoIter::new(arr).collect()
+    }
+}
+
 #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
 impl<T> From<BinaryHeap<T>> for Vec<T> {
     /// Converts a `BinaryHeap<T>` into a `Vec<T>`.
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index 79042ab739c..2affbc032dc 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -109,7 +109,20 @@ pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT;
 /// }
 /// ```
 ///
-/// `BTreeMap` also implements an [`Entry API`], which allows for more complex
+/// A `BTreeMap` with a known list of items can be initialized from an array:
+///
+/// ```
+/// use std::collections::BTreeMap;
+///
+/// let solar_distance = BTreeMap::from([
+///     ("Mercury", 0.4),
+///     ("Venus", 0.7),
+///     ("Earth", 1.0),
+///     ("Mars", 1.5),
+/// ]);
+/// ```
+///
+/// `BTreeMap` implements an [`Entry API`], which allows for complex
 /// methods of getting, setting, updating and removing keys and their values:
 ///
 /// [`Entry API`]: BTreeMap::entry
@@ -2012,6 +2025,20 @@ where
     }
 }
 
+#[stable(feature = "std_collections_from_array", since = "1.56.0")]
+impl<K: Ord, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V> {
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let map1 = BTreeMap::from([(1, 2), (3, 4)]);
+    /// let map2: BTreeMap<_, _> = [(1, 2), (3, 4)].into();
+    /// assert_eq!(map1, map2);
+    /// ```
+    fn from(arr: [(K, V); N]) -> Self {
+        core::array::IntoIter::new(arr).collect()
+    }
+}
+
 impl<K, V> BTreeMap<K, V> {
     /// Gets an iterator over the entries of the map, sorted by key.
     ///
diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs
index 3a74b6a6fa8..1e61692b7c6 100644
--- a/library/alloc/src/collections/btree/map/tests.rs
+++ b/library/alloc/src/collections/btree/map/tests.rs
@@ -2173,3 +2173,10 @@ fn test_insert_remove_intertwined_ord_chaos() {
     }
     map.check_invariants();
 }
+
+#[test]
+fn from_array() {
+    let map = BTreeMap::from([(1, 2), (3, 4)]);
+    let unordered_duplicates = BTreeMap::from([(3, 4), (1, 2), (1, 2)]);
+    assert_eq!(map, unordered_duplicates);
+}
diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs
index 9711214aea6..0c268ad32b2 100644
--- a/library/alloc/src/collections/btree/set.rs
+++ b/library/alloc/src/collections/btree/set.rs
@@ -59,6 +59,14 @@ use super::Recover;
 ///     println!("{}", book);
 /// }
 /// ```
+///
+/// A `BTreeSet` with a known list of items can be initialized from an array:
+///
+/// ```
+/// use std::collections::BTreeSet;
+///
+/// let set = BTreeSet::from([1, 2, 3]);
+/// ```
 #[derive(Hash, PartialEq, Eq, Ord, PartialOrd)]
 #[stable(feature = "rust1", since = "1.0.0")]
 #[cfg_attr(not(test), rustc_diagnostic_item = "BTreeSet")]
@@ -1057,6 +1065,20 @@ impl<T: Ord> FromIterator<T> for BTreeSet<T> {
     }
 }
 
+#[stable(feature = "std_collections_from_array", since = "1.56.0")]
+impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> {
+    /// ```
+    /// use std::collections::BTreeSet;
+    ///
+    /// let set1 = BTreeSet::from([1, 2, 3, 4]);
+    /// let set2: BTreeSet<_> = [1, 2, 3, 4].into();
+    /// assert_eq!(set1, set2);
+    /// ```
+    fn from(arr: [T; N]) -> Self {
+        core::array::IntoIter::new(arr).collect()
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> IntoIterator for BTreeSet<T> {
     type Item = T;
diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs
index 4cb6e3d6619..de7a10dca7b 100644
--- a/library/alloc/src/collections/btree/set/tests.rs
+++ b/library/alloc/src/collections/btree/set/tests.rs
@@ -738,3 +738,10 @@ fn test_split_off_large_random_sorted() {
     assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
     assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
 }
+
+#[test]
+fn from_array() {
+    let set = BTreeSet::from([1, 2, 3, 4]);
+    let unordered_duplicates = BTreeSet::from([4, 1, 4, 3, 2]);
+    assert_eq!(set, unordered_duplicates);
+}
diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs
index 588ba2de220..7aa24ff4afa 100644
--- a/library/alloc/src/collections/linked_list.rs
+++ b/library/alloc/src/collections/linked_list.rs
@@ -31,6 +31,13 @@ mod tests;
 /// The `LinkedList` allows pushing and popping elements at either end
 /// in constant time.
 ///
+/// A `LinkedList` with a known list of items can be initialized from an array:
+/// ```
+/// use std::collections::LinkedList;
+///
+/// let list = LinkedList::from([1, 2, 3]);
+/// ```
+///
 /// NOTE: It is almost always better to use `Vec` or `VecDeque` because
 /// array-based containers are generally faster,
 /// more memory efficient, and make better use of CPU cache.
@@ -1901,6 +1908,20 @@ impl<T: Hash> Hash for LinkedList<T> {
     }
 }
 
+#[stable(feature = "std_collections_from_array", since = "1.56.0")]
+impl<T, const N: usize> From<[T; N]> for LinkedList<T> {
+    /// ```
+    /// use std::collections::LinkedList;
+    ///
+    /// let list1 = LinkedList::from([1, 2, 3, 4]);
+    /// let list2: LinkedList<_> = [1, 2, 3, 4].into();
+    /// assert_eq!(list1, list2);
+    /// ```
+    fn from(arr: [T; N]) -> Self {
+        core::array::IntoIter::new(arr).collect()
+    }
+}
+
 // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters.
 #[allow(dead_code)]
 fn assert_covariance() {
diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index 461e701be05..26c9415a4de 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -67,6 +67,14 @@ const MAXIMUM_ZST_CAPACITY: usize = 1 << (usize::BITS - 1); // Largest possible
 /// push onto the back in this manner, and iterating over `VecDeque` goes front
 /// to back.
 ///
+/// A `VecDeque` with a known list of items can be initialized from an array:
+///
+/// ```
+/// use std::collections::VecDeque;
+///
+/// let deq = VecDeque::from([-1, 0, 1]);
+/// ```
+///
 /// Since `VecDeque` is a ring buffer, its elements are not necessarily contiguous
 /// in memory. If you want to access the elements as a single slice, such as for
 /// efficient sorting, you can use [`make_contiguous`]. It rotates the `VecDeque`
@@ -2915,3 +2923,17 @@ impl<T> From<VecDeque<T>> for Vec<T> {
         }
     }
 }
+
+#[stable(feature = "std_collections_from_array", since = "1.56.0")]
+impl<T, const N: usize> From<[T; N]> for VecDeque<T> {
+    /// ```
+    /// use std::collections::VecDeque;
+    ///
+    /// let deq1 = VecDeque::from([1, 2, 3, 4]);
+    /// let deq2: VecDeque<_> = [1, 2, 3, 4].into();
+    /// assert_eq!(deq1, deq2);
+    /// ```
+    fn from(arr: [T; N]) -> Self {
+        core::array::IntoIter::new(arr).collect()
+    }
+}