Блог*

Forwarded from Технологический Болт Генона

4:19

Зачем MAX при открытии отправляет запрос к серверу Телеграма?
https://qna.habr.com/q/1408720

4:20

🤣32😁6❤2🤔2👍1

640 views12:16

#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;
}

👍10🤯3🤡1

848 viewsedited 14:25