Support different hash algorithms in into_group_map

[hcpl]

Motivation

Currently Itertools::into_group_map returns HashMap<K, V> which equals to HashMap<K, V, RandomState> with RandomState being https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html.

Supporting HashMap<K, V, S> where S: BuildHasher + Default will allow into_group_map to interoperate with hash maps that use other hash algorithms, e.g. FnvHashMap or FxHashMap.

Implementation issues

The problem is that naively adding an S: BuildHasher + Default type parameter like this:

src/group_map.rs

 #![cfg(feature = "use_std")]
 
 use std::collections::HashMap;
-use std::hash::Hash;
+use std::hash::{BuildHasher, Hash};
 use std::iter::Iterator;
 
 /// Return a `HashMap` of keys mapped to a list of their corresponding values.
 ///
 /// See [`.into_group_map()`](../trait.Itertools.html#method.into_group_map)
 /// for more information.
-pub fn into_group_map<I, K, V>(iter: I) -> HashMap<K, Vec<V>>
+pub fn into_group_map<I, K, V, S>(iter: I) -> HashMap<K, Vec<V>, S>
     where I: Iterator<Item=(K, V)>,
           K: Hash + Eq,
+          S: BuildHasher + Default,
 {
-    let mut lookup = HashMap::new();
+    let mut lookup = HashMap::default();
 
     for (key, val) in iter {
         lookup.entry(key).or_insert(Vec::new()).push(val);
     }
 
     lookup
}

src/lib.rs

@@ -60,7 +60,7 @@ use std::iter::{IntoIterator};
 use std::cmp::Ordering;
 use std::fmt;
 #[cfg(feature = "use_std")]
-use std::hash::Hash;
+use std::hash::{BuildHasher, Hash};
 #[cfg(feature = "use_std")]
 use std::fmt::Write;
 #[cfg(feature = "use_std")]
@@ -1956,9 +1956,10 @@ pub trait Itertools : Iterator {
     /// assert_eq!(lookup[&3], vec![13, 33]);
     /// ```
     #[cfg(feature = "use_std")]
-    fn into_group_map<K, V>(self) -> HashMap<K, Vec<V>>
+    fn into_group_map<K, V, S>(self) -> HashMap<K, Vec<V>, S>
         where Self: Iterator<Item=(K, V)> + Sized,
               K: Hash + Eq,
+              S: BuildHasher + Default,
     {
         group_map::into_group_map(self)
     }

will mess with type checking if the code relied on S = RandomState to be inferred.

Specifically, the above change breaks compilation of tests/quick.rs:

error[E0283]: type annotations required: cannot resolve `_: std::hash::BuildHasher`
   --> tests/quick.rs:913:61
    |
913 |         let lookup = a.into_iter().map(|i| (i % modulo, i)).into_group_map();
    |                                                             ^^^^^^^^^^^^^^

What's more, default type parameters are only supported on type definitions, but not on functions or methods: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=c8030e99c0e0f5908b130dbfe3e8c26d.

So I guess the only way out is to keep into_group_map as is (to support the default case) and add a new combinator which differs from the original as shown in the diff above.