#prog #rust #article
В стандартной библиотеке 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;
}
