『Borrow』のコレクションの検索キーとしての活用方法について。

概要

セットやマップ (std の BTreeSet, HashSet, BTreeMap, HashMap など) の検索メソッドの引数には検索対象の参照型を渡すのが基本ではあるが、Borrow トレイトの性質を使った応用もできるようになっている。

基本

検索引数として、検索対象への参照型をそのまま渡す。

(&T は Borrow<T> を実装しているため同じ関数で対応可能。)

応用

検索引数として、検索対象から 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、両者の生成するハッシュ値が同じため。