В стандартной библиотеке Rust есть несколько ассоциативных контейнеров:
HashMap, HashSet, BTreeMap и BTreeSet. Часто на практике в качестве ключей в них хранятся строки — String. Требовать от пользователя для поиска значение типа String неудобно и чревато проблемами в производительности. Потому у этих структур данных есть API, позволяющие использовать для поиска ключи других, "похожие" на те, что хранятся в контейнере.Возьмём в качестве примера HashMap::get:
fn get<Q>(&self, k: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
Как видно из кода, тип для поиска (
Q) не обязан совпадать с типом хранимых ключей (K), но на K есть ограничение K: Borrow<Q>. Трейт Borrow выглядит таким образом:trait Borrow<Borrowed>
where
Borrowed: ?Sized,
{
fn borrow(&self) -> &Borrowed;
}
В процессе поиска значения на хранимых ключах вызывается метод
<K as Borrow<Q>>::borrow, и результат возвращаемого значения сравнивается со значением, переданным в get. Именно благодаря этому API (и реализациям в std, разумеется) коллекцию HashMap<String, Thing> можно индексировать значениями типа &str.Но у этого API есть недостаток. Именно, оно требует, чтобы предоставляемое значение было ссылкой и чтобы из ссылки на ключ можно было получить ссылку на
Q. Это ограничивает применимость API. Если, например, в мапе в качестве ключей хранятся (String, String), то логичный невладеющий эквивалент для индексации (&str, &str) не будет работать, потому что это кортеж ссылок, а не ссылка.В короткой статье Borrowed tuple indexing for HashMap рассказывается, как с некоторым количеством бойлерплейта можно обойти это ограничение.
Для сравнения, hashbrown (поверх которого сделаны мапы в std) от подобных ограничений не страдает, поскольку там в API используется более гибкий трейт Equivalent:
trait Equivalent<K>
where
K: ?Sized,
{
fn equivalent(&self, key: &K) -> bool;
}