std クレートのセットやマップ (BTreeSet, HashSet, BTreeMap, HashMap) における検索系のメソッドについて。検索引数の型、検索対象の型、それから Borrow トレイト、それぞれの関係を紹介する。

具体例

代表的なメソッドについて、いくつか見てみる。

`BTreeMap::get`

以下はメソッドの宣言部分。


impl<K, V, A> BTreeMap<K, V, A>
where
    A: Allocator + Clone,
{
    // ... //

    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q> + Ord,
        Q: Ord + ?Sized,
    {
        // ... //
    }

    // ... //
}

検索引数の型 &Q と検索対象の型 K について。Q は K から Borrow を通して借用でき、かつ K と同じく Ord が必要。そして、Q を K から得る過程で、Ord による順序関係は変化してはならない (以下は rustdoc からの引用)。

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

`HashMap::get`

以下はメソッドの宣言部分。


impl<K, V, S> HashMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    // ... //

    pub fn get<Q>(&self, k: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        // ... //
    }

    // ... //
}

検索引数の型 &Q と検索対象の型 K について。Q は K から Borrow を通して借用でき、かつ K と同じく Eq + Hash が必要。そして、Q を K から得る過程で、Eq による同値関係と、Hash が生成する値は変化してはならない (以下は rustdoc からの引用)。

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

サンプル

基本編

検索対象は i32、検索引数はその参照型の &i32 を利用。


use std::collections::HashMap;

fn main() {
    let mut dict = HashMap::<i32, String>::new();
    dict.insert(0, "foo".to_string());
    dict.insert(1, "bar".to_string());
    dict.insert(2, "baz".to_string());

    let result = dict.get(&1);

    assert_eq!(result , Some(&"bar".to_string()));
}

応用編 1

キー型が String

検索対象は String、検索引数はそこから Borrow で得られる &str を利用。


use std::collections::HashMap;

fn main() {
    let mut dict = HashMap::<String, String>::new();
    dict.insert("Foo".to_string(), "foo".to_string());
    dict.insert("Bar".to_string(), "bar".to_string());
    dict.insert("Baz".to_string(), "baz".to_string());

    let result = dict.get("Bar");

    assert_eq!(result, Some(&"bar".to_string()));
}

応用編 2

キー型が Box

検索対象は Box<i32>、検索引数はそこから Borrow で得られる &i32 を利用。


use std::collections::HashMap;

fn main() {
    let mut dict = HashMap::<Box<i32>, String>::new();
    dict.insert(Box::new(0), "foo".to_string());
    dict.insert(Box::new(1), "bar".to_string());
    dict.insert(Box::new(2), "baz".to_string());

    let result = dict.get(&1);

    assert_eq!(result, Some(&"bar".to_string()));
}

応用編 3

キー型が独自型

検索対象は独自型 Key、検索引数はそこから Borrow で得られる &u32 を利用。


use std::{borrow::Borrow, collections::HashMap, hash::Hash};

fn main() {
    let mut dict = HashMap::<Key, String>::new();
    dict.insert(Key { id: 0 }, "foo".to_string());
    dict.insert(Key { id: 1 }, "bar".to_string());
    dict.insert(Key { id: 2 }, "baz".to_string());

    let result = dict.get(&1);

    assert_eq!(result, Some(&"bar".to_string()));
}

#[derive(PartialEq, Eq, Hash)]
struct Key {
    id: u32,
}

impl Borrow<u32> for Key {
    fn borrow(&self) -> &u32 {
        &self.id
    }
}

この検索が成立するのは、derive で自動実装される Hash、そして Key の Borrow<u32> から借用される &u32 の Hash、両者の生成するハッシュ値が同じため。

基本と応用

基本編

応用編

具体例

BTreeMap::get