Snippet stash

Collections

std/collections

idioms/deref

too-many-lists

• Big O notation
• Плюсы и минусы, применение и назначение
• VecDeque Двухсторонняя очередь
• BinaryHeap Очередь с приоритетом max/min
• LinkedList Двусвязный список с собственными узлами
• std::collections::HashSet
• std::collections::HashMap
• std::collections::BTreeSet
• std::collections::btree_map::BTreeMap
• Параллельные коллекции
• Неизменяемые коллекции
  • crate im
  • Struct im::vector::Vector
  • Struct im::hashmap::HashMap

Знать как работает список, очередь, дерево и сложность их алгоритмов

Связные списки предпочтительнее массивов, когда:

• нужно, чтобы операции вставки и удаления выполнялись чрезвычайно быстро;
• не требуется произвольный доступ к данным;
• приходится вставлять или удалять элементы между других элементов;
• заранее не известно количество элементов (оно будет расти или уменьшится по ходу выполнения программы).

Массивы предпочтительнее связных списков, когда:

• нужен произвольный доступ к данным;
• нужен очень быстрый доступ к элементам;
• число элементов не изменяется во время выполнения программы, благодаря чему легко выделить непрерывное пространство памяти.

Граф (graph) аналогичен дереву. Разница состоит в том, что у него нет ни дочерних, ни родительских узлов (вершин) и, следовательно, нет корневого узла. Данные свободно организованы в виде узлов (вершин) и дуг (ребер) так, что любой узел может иметь произвольное число входящих и исходящих ребер. Это самая гибкая из всех структур, она используется для представления почти всех типов данных. Например, графы идеальны для социальной сети, где узлы — это люди, а ребра — дружеские связи.

Хеш-таблица (hash table) — это структура данных, которая позволяет находить элементы за O(1). Поиск занимает постоянное время вне зависимости от того, ищете вы среди 10 млн элементов или всего среди 10. В отличие от массива, его элементы хранятся не в упорядоченной последовательности. Позиция, занимаемая элементом в памяти, «волшебным образом» задается хеш-функцией. Это позволяет нам получать элементы немедленно. Заданное значение сначала пропускается через хеш-функцию. Она выдает точную позицию, где элемент должен находиться в памяти.

Big O notation

• 2n экспоненциальный
• n^2 квадратичный
• n линейный
• log(n) логарифмический

Квадратичная скорость при O^2 (т.е. 3n^2+5n+2) при которой если входные данные из 100 значений отработают за 1 секунду то при 200 входных данных это будет 4 секунды. Увеличивает в четыре раза т.е. квадратично. При увеличении n в 2 раза то время увеличивается в 4 раза

от быстрых к медленным:

log n => ^ n => n => n log n => n^2 => 2n

O(1) означает, что операция выполняется в постоянное время: для завершения будет выполнено одно и то же время независимо от размера структуры данных

O(n) означает, что операция выполняется в линейном времени: если вы удвоите размер вашей структуры данных, операция займет в два раза больше времени; если вы в четыре раза увеличите размер, это займет в четыре раза больше и т. д.

O(log n) означает, что операция выполняется в логарифмическом времени: для log2 , если вы удвоите размер вашей структуры данных, операция займет один шаг дольше; если вы в четыре раза увеличите размер, ему потребуется еще два шага; и так далее. Тем не менее структуры данных в этой библиотеке обычно работают в log 64 раз, а это значит, что вам нужно сделать свою структуру данных в 64 раза больше, чтобы потребоваться один дополнительный шаг, а в 4096 раз больше, чтобы потребовалось два шага.

O(n log n) - самая дорогая операция, которую вы увидите в этой библиотеке: это означает, что для каждого из n элементов в вашей структуре данных вам необходимо выполнить операции log n. В нашем случае, как отмечалось выше, это часто достаточно близко к O (n), что обычно не так плохо, как кажется, но даже O(n) не является дешевым, и стоимость все еще увеличивается логарифмически, если медленно, размер ваших данных увеличивается. O (n log n) в основном означает «вы уверены, что вам нужно это сделать?»

O(1)* означает «амортизированный O(1)», что означает, что операция обычно выполняется в постоянное время, но иногда будет дороже: например Vector::push_back вам даже не нужно думать о том, какую структуру данных использовать в любой конкретной ситуации, до того момента, когда вам нужно начать беспокоиться об оптимизации

Плюсы и минусы, применение и назначение

Vec или HashMap охватывают большинство случаев использования для общего хранения и обработки данных

• sequence Последовательности: Vec, VecDeque, LinkedList
• map: HashMap,BTreeMap
• set: HashSet,BTreeSet
• Разное: BinaryHeap

Про карты map

Карты - это сопоставление ключей со значениями, в которых наиболее распространенной операцией чтения является поиск значения, связанного с данным ключом. Карты могут иметь или не иметь определенного порядка. Любой заданный ключ может появляться только один раз внутри карты, а установка ключа на другое значение перезапишет предыдущее значение.

Про наборы set

Наборы представляют собой коллекции уникальных значений и могут иметь или не иметь определенный порядок. Их решающее свойство состоит в том, что любое заданное значение может существовать только один раз в заданном наборе.

Используйте, Vec когда

• Вы хотите собирать предметы, которые должны быть обработаны или отправлены в другом месте позже, и не заботятся о каких-либо свойствах сохраняемых фактических значений.
• Вам нужна последовательность элементов в определенном порядке и будет только добавляться к (или ближе) к концу.
• Вам нужен стек.
• Вы хотите изменить размер массива.
• Вам нужен массив, выделенный для кучи.

Используйте, VecDeque когда

• Вы хотите, Vec чтобы поддерживалась эффективная вставка на обоих концах последовательности.
• Вам нужна очередь.
• Вам нужна двойная очередь (deque).

Это необходимо для решения низкоуровневых задач, таких как планирование заданий ЦП, а также для моделирования реальной очереди - например, запросов на техническую поддерку, которые необходимо обрабатывать последовательно.

Используйте, LinkedList когда

• Вы хотите Vec ИЛИ VecDeque неизвестного размера, и терпеть не может амортизировать.
• Вы хотите эффективно разбить и добавить списки.
• Вы абсолютно уверены, что вы на самом деле, действительно, хотите дважды связанный список.

Используйте, HashMap когда

• Вы хотите связать произвольные ключи с произвольным значением.
• Вам нужен кеш.
• Вам нужна карта без дополнительной функциональности.

HashSet

Используйте, BTreeMap когда

• Вам нужна карта, отсортированная по ее ключам.
• Вы хотите, чтобы иметь возможность получать список заявок по требованию.
• Вас интересует, какая самая маленькая или самая большая пара ключ-значение.
• Вы хотите найти самый большой или самый маленький ключ, который меньше или больше чем что-то.

BTreeSet

Используйте, BinaryHeap когда

• Он сохраняет элемент с наибольшим значением впереди, но другие элементы располагаются в любом порядке.
• Вы хотите хранить кучу элементов, но только когда-либо хотите обработать «самый большой» или «самый важный» в любой момент времени.
• Вам нужна очередь приоритетов. (Некоторые языки называют это очередью приоритетов)
• Хороший способ использовать, a BinaryHeap — для коллекции дел, которые нужно сделать.

Итераторы iter, iter_mut и into_iter

iter предоставляет итератор неизменных ссылок на все содержимое коллекции в самом «естественном» порядке. Для коллекций последовательностей, например Vec, это означает, что элементы будут приведены в порядке возрастания индекса начиная с 0. Для упорядоченных коллекций, например BTreeMap, это означает, что элементы будут приведены в отсортированном порядке. Для неупорядоченных коллекций, например HashMap, элементы будут выдаваться в любом порядке, которое внутреннее представление сделало наиболее удобным.

VecMap

vec_map

используйте VecMap внутренне вместо a BTreeMap. Эта функция обеспечивает небольшое улучшение производительности

VecDeque Двухсторонняя очередь

struct.VecDeque

VecDeque удобен для работы с двухсторонними очередями.

• Для удаления и вставки с начала VecDeque значительно быстрее, чем Vec.
• Для удаления и вставки с конца разницы практически нет с Vec.
• Но у Vec очень медленно вставка в начало, а у VecDeque очень медленно вставка или удаление по индексу

VecDeque(произносится как «век-дек») — это Vec, оптимизированный для (т. е. хорошо справляющийся) pop (выталкивания) предметов как спереди, так и сзади. Rust имеет VecDeque, потому что Vecs отлично подходят для выталкивания сзади (последнего предмета), но не так хороши спереди. Когда вы используете .pop() на Vec, он просто снимает последний предмет справа, и больше ничего не перемещается. Но если вы удалите предмет из любого места внутри Vec, все предметы справа от него перемещаются на одну позицию влево.

Вы можете увидеть это в описании для .remove(): "Удаляет и возвращает элемент в позиции index внутри вектора, сдвиг всех элементов после него влево."

Минус VecDeque: Доступ по индексу аналогичен Vec (O(1)), но он менее оптимален для операций, связанных только с концом структуры данных, потому что в памяти используется кольцевой буфер, и операции могут быть чуть сложнее. VecDeque: Кольцевой буфер может быть избыточным, особенно если редко вставлять или удалять элементы с начала. Удаление из середины работает, но оно требует сдвига элементов, что делает операцию линейной по времени (O(n)), аналогично тому, как это происходит в Vec

• new
• with_capacity
• get
• get_mut
• swap - Перемещает элементы по индексам i и j
• capacity
• reserve_exact
• reserve
• try_reserve_exact
• try_reserve
• shrink_to_fit
• shrink_to
• truncate - Сокращает VecDeque по индексу отбрасывая остальные
• iter
• iter_mut
• as_slices - Возвращает пару срезов front и back
• as_mut_slices - Возвращает пару изменяемых срезов front и back
• len
• is_empty
• drain

use std::collections::VecDeque;
fn main(){
    let mut buf: VecDeque = VecDeque::with_capacity(10);
    // let mut buf = VecDeque::new();
    buf.push_front(1);;//push_front Добавляет элемент в начало
    buf.push_back(3);//push_back  Добавляет элемент в конец
    assert_eq!(buf.front(), Some(1));//back Предоставляет ссылку на первый элемент
    assert_eq!(3, *buf.back().unwrap());//back Предоставляет ссылку на последний элемент // back_mut изменяемая  ссылка
    assert_eq!(buf.pop_back(), Some(3)); //pop_back  Удаляет последний элемент из VecDequeи возвращает его, или Noneесли он пуст
    assert_eq!(buf.pop_front(), Some(1));//pop_front Удаляет первый элемент и возвращает его
}

• clear
• contains
• front
• front_mut
• back
• back_mut
• pop_front
• push_front
• push_back
• pop_back
• swap_remove_back - Замена элемента по индексу на последний элемент
• swap_remove_front - Замена элемента по индексу на первый элемент
• insert
• remove
• split_off
• append
• retain
• resize

as_mut_slices(&mut self) -> (&mut [T], &mut [T])

fn main(){
// Возвращает пару срезов front и back
 let mut vector = VecDeque::new();
    vector.push_back(0);
    vector.push_back(1);
    vector.push_front(10);
    vector.push_back(9);
    vector.push_front(8);
    // ([0, 1, 10, 9, 8], []) если все вставлены в конец
    println!("{:?}",vector.as_mut_slices());// ([8, 10], [0, 1, 9])
}

get(&self, index: usize) -> Option<&T>

fn main(){
// Доступ по индексу
    let mut buf = VecDeque::new();
    buf.push_back(3);
    buf.push_back(4);
    buf.push_back(5);
    assert_eq!(buf.get(1), Some(&4));
}

insert(&mut self, index: usize, value: T)

fn main(){
 //  insert вставка по индексу, смещает все индексы больше вставленного
    use std::collections::VecDeque;

    let mut vec_deque = VecDeque::new();
    vec_deque.push_back('a');
    vec_deque.push_back('b');
    vec_deque.push_back('c');
    assert_eq!(vec_deque, &['a', 'b', 'c']);

    vec_deque.insert(1, 'd');
    assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
}

remove(&mut self, index: usize) -> Option<T>

fn main(){
 //  remove удаляет по индексу и возвращает элемент смещая оставшиеся элементы 
    use std::collections::VecDeque;
    let mut buf = VecDeque::new();
    buf.push_back(1);
    buf.push_back(2);
    buf.push_back(3);
    assert_eq!(buf, [1, 2, 3]);

    assert_eq!(buf.remove(1), Some(2));
    assert_eq!(buf, [1, 3]);
}

append(&mut self, other: &mut VecDeque<T>)

fn main(){
 //  append дополняет очередь
    let mut buf: VecDeque<_> = vec![1, 2].into_iter().collect();
    let mut buf2: VecDeque<_> = vec![3, 4].into_iter().collect();
    buf.append(&mut buf2);
    assert_eq!(buf, [1, 2, 3, 4]);
    assert_eq!(buf2, []);
}

BinaryHeap

📌

• Он сохраняет элемент с наибольшим значением впереди, но другие элементы располагаются в любом порядке.
• Вы хотите хранить кучу элементов, но только когда-либо хотите обработать «самый большой» или «самый важный» в любой момент времени.
• Вам нужна очередь приоритетов. (Некоторые языки называют это очередью приоритетов)
• Хороший способ использовать, a BinaryHeap — для коллекции дел, которые нужно сделать.

LinkedList Двусвязный список с собственными узлами

struct.LinkedList

wiki

Вы хотите эффективно разбить и добавить списки. Почти всегда лучше использовать Vec или VecDeque вместо LinkedList.

В общем, контейнеры на основе массивов быстрее, эффективнее с точки зрения памяти и лучше используют кэш ЦП. Допускает только последовательный доступ к элементам (нет доступа по индексу), но при этом дает возможность перемещения в обе стороны.

• new - Создает пустой LinkedList
• append - Перемещает все элементы из другого в конец списка
• iter - Итератор
• iter_mut - Изменяемый итератор
• is_empty - Проверка на пустоту
• len - Возвращает длину LinkedList
• clear - Удаляет все элементы из LinkedList
• contains - Наличие значения
• front - Ссылка на первый элемент
• front_mut - Изменяемая ссылка на первый элемент
• back - Последний элемент
• back_mut - Изменяемая ссылка на последний элемент
• push_front - Вставить в начало
• pop_front - Удалить с начала
• push_back - Вставить в конец
• pop_back - Удалить с конца
• drain_filter
• split_off - Разбивает список на два по заданному индексу

use std::time::{Duration, Instant};
use std::collections::LinkedList;
fn linked_remove(s:&mut usize,vec:&mut LinkedList){
    let mut ss = s.clone();
    while *s > 0 {
        *s-=1;
        vec.push_front(1);
    }
    let now = Instant::now();
    while ss > 0 {
        ss-=1;
        //vec.pop_front().unwrap();
        vec.pop_back().unwrap();
    }
    println!("{}", now.elapsed().as_secs());
}
fn main(){
   let mut vec:LinkedList = LinkedList::new();
   linked_remove(&mut s,&mut vec);
}

std::collections::HashSet

struct.HashSet

Если вам нужен, HashSet который выдает вам свои ключи по порядку, вы можете использовать BTreeSet

Требуется, чтобы ключи реализовывали Eq и Hash черты, хотя это часто может быть достигнуто при использовании

#[derive(PartialEq, Eq, Hash)]
k1 == k2 -> hash(k1) == hash(k2)

• new - Создание
• with_capacity - Создание с емкостью
• with_hasher - Создание с хешером
• with_capacity_and_hasher - Создание емкость с хешером
• hasher - Возвращает ссылку на набор BuildHasher
• capacity - Количество элементов без выделения новой памяти
• reserve - Резервирует емкость
• shrink_to_fit - Максимально уменьшает емкость комплекта
• shrink_to
• iter - Итератор
• difference - Разность
• symmetric_difference - Симметричная разность , только в одном map
• intersection - Общие значения
• union - Обьединение
• len - Возвращает количество элементов в наборе
• is_empty - Проверка на пустоту
• drain - Очищает набор, возвращая все элементы в итераторе
• clear - Удаляет набор, удаляя все значения
• contains - Возвращает true, если набор содержит значение.
• get - Возвращает ссылку на значение если оно есть
• is_disjoint - Проверка пересечения
• is_subset - Множество является подмножеством ?
• is_superset - Множество является надмножеством ?
• insert - Добавляет значение в набор
• replace - Добавляет значение в набор или заменяя совпавшее значение
• remove - Удаляет значение из набора
• take - Удаляет и возвращает значение в наборе
• retain - Сохраняет только элементы, заданные предикатом

Если вы вставляете значение, которое уже присутствует в HashSet (т.е. новое значение равно существующим, и оба они имеют одинаковый хеш), новое значение заменяет старое.

use std::collections::HashSet;
fn main() {
   #[derive(Hash, Eq, PartialEq, Debug)]
    struct Viking {
        name: String,
        power: usize,
    }

    let mut vikings = HashSet::new();
    // let viking_names: HashSet<&'static str> = [ "Einar", "Olaf", "Harald" ].iter().cloned().collect();

    vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
    vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
    vikings.insert(Viking { name: "Olaf".to_string(), power: 4 });
    vikings.insert(Viking { name: "Harald".to_string(), power: 8 });

    for x in &vikings {
        println!("{:?}", x);
    }

    let viking:Viking  = Viking { name: "Einar".to_string(), power: 9 };
    if vikings.contains(&viking) {
        println!("{:?}",vikings.get(&viking));// Some(Viking { name: "Einar", power: 9 })
    }
}

1. Принадлежность (x ∈ A) И Подмножество (A ⊆ B)

Принадлежность (x ∈ A) - элемент x принадлежит множеству A, если x находится внутри набора A.

use std::collections::HashSet;
fn main(){
    // let allowed: HashSet<_> = ["gmail.com", "yandex.ru"].into_iter().collect();
    let allowed = HashSet::from(["gmail.com", "yandex.ru"]);
    let domain = "gmail.com";

    if allowed.contains(domain) {
        println!("(domain ∈ allowed) - элемент domain принадлежит множеству allowed");
    }
    // Почему не массивы? Потому что в массиве → дубликаты возможны и алгоритм нахождения дольше
 
}

Подмножество A ⊆ B - множество A является подмножеством B, если каждый элемент A содержится в B.

Т.е. все элементы A входят в B. Это проверка “достаточности”.

use std::collections::HashSet;
fn main(){
    // Пользователь пытается выполнить действие, требующее набора прав:
    let required = HashSet::from(["read", "write"]);
    let user = HashSet::from(["read", "write", "delete"]);

    if user.is_superset(&required) {
        println!("(required ⊆ user)");// множество `required` является подмножеством `user`, т.е. все требования required содержатся в наборе user
    }
}

2. Операции над множествами

Пересечение (A ∩ B) - элементы, которые есть и в A, и в B. Нахождение общего.

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let a: HashSet<_> = [1, 7, 3, 1, 3, 3].into_iter().collect();
    let b: HashSet<_> = [3, 4, 7].into_iter().collect();
    
    let intersection: HashSet<_> = a.intersection(&b).cloned().collect();
    
    for x in &intersection {
        println!("{}", x); // 7, 3
    }

    Ok(())
}

Объединение (A ∪ B) - элементы, которые есть либо в A, либо в B (дубликатов нет).

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let a: HashSet<_> = [1, 7, 3, 1, 3, 3].into_iter().collect();
    let b: HashSet<_> = [3, 4, 7].into_iter().collect();
    
    let union: HashSet<_> = a.union(&b).cloned().collect();
 
    for x in &union {
        println!("{}", x); // 7, 3, 4, 1
    }

    Ok(())
}

Разность (A \ B) - элементы, которые есть в A, но НЕ в B.

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let a: HashSet<_> = [1, 7, 3, 1, 3, 3].into_iter().collect();
    let b: HashSet<_> = [3, 4, 7].into_iter().collect();
    
    // `(A \ B)` - элементы, которые есть в `A`, но НЕ в `B`
    let diff: HashSet<_> = a.difference(&b).cloned().collect();
 
    for x in &diff {
        println!("{}", x); // 1
    }

    // `(B \ A)` - элементы, которые есть в `B`, но НЕ в `A`
    let diff: HashSet<_> = b.difference(&a).cloned().collect();
 
    for x in &diff {
        println!("{}", x); // 4
    }

    Ok(())
}

Симметрическая разность (A △ B) - элементы, которые есть либо только в A, либо только в B, но не в обоих.

Это объединение минус пересечение: (A ∪ B) \ (A ∩ B)

Например: какие настройки изменились между конфигурациями

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    
    let user_state_1 = HashSet::from(["read", "write", "check" ]);
    let user_state_2 = HashSet::from(["read", "write", "delete"]);
    
    let sym: HashSet<_> = user_state_1.symmetric_difference(&user_state_2).cloned().collect();
 
    for x in &sym {
        println!("{}", x); // delete, check
    }
    
    // Или
    let union: HashSet<_> = user_state_1.union(&user_state_2).cloned().collect();
    let intersection: HashSet<_> = user_state_1.intersection(&user_state_2).cloned().collect();
    let sym: HashSet<_> = union.difference(&intersection).cloned().collect();
    
    for x in &sym {
        println!("{}", x); // delete, check
    }
 
    Ok(())
}

3. Декартово произведение множеств

(ключ к JOIN, графам, отношениям, БД, моделям состояний)

A × B - взять каждый элемент A и скрестить со всеми B

A = {1, 2}
B = {x, y}

A × B = {(1, x), (1, y), (2, x), (2, y)}

fn main() -> std::io::Result<()> {
    
    let A = ["1","2"];
    let B = ["x","y"];
    
    for a in &A {
        for b in &B {
            print!("({a}, {b}) ");// (1, x) (1, y) (2, x) (2, y)
        }
    }
 
    Ok(())
}

difference<'a>(&'a self,other:&'a HashSet<T, S>)->Difference<'a,T,S>

fn main(){
// Разность
    let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
   // println!("{:?}",b); { 4, 2, 3}
// Разность a - b
    for x in a.difference(&b) {
        println!("{}", x); // Print 1
    }

    let diff: HashSet<_> = a.difference(&b).collect();
    assert_eq!(diff, [1].iter().collect());

// Обратите внимание, что разность не симметрична, 
// и `b - a` означает нечто другое:
    let diff: HashSet<_> = b.difference(&a).collect();
    assert_eq!(diff, [4].iter().collect());
}

symmetric_difference<'a>(&'a self,other:&'a HashSet<T,S>)->SymmetricDifference<'a,T,S>

fn main(){
// Симметричная разность   
// Уникальные значения А которых нет в В + наоборот уникальные значения В корорых нет в А

    let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();

    // Print 1, 4 in arbitrary order.
    for x in a.symmetric_difference(&b) {
        println!("{}", x);
    }

    let diff1: HashSet<_> = a.symmetric_difference(&b).collect();
    let diff2: HashSet<_> = b.symmetric_difference(&a).collect();

    assert_eq!(diff1, diff2);
    assert_eq!(diff1, [1, 4].iter().collect());
}

intersection<'a>(&'a self,other:&'a HashSet<T, S>)->Intersection<'a, T, S>

fn main(){
// Общие значения
    let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();

// печатает 2, 3 в произвольном порядке
    for x in a.intersection(&b) {
        println!("{}", x);
    }

    let intersection: HashSet<_> = a.intersection(&b).collect();
    assert_eq!(intersection, [2, 3].iter().collect());
}

is_disjoint(&self, other: &HashSet<T, S>) -> bool

fn main(){
// Проверка пересечения
    let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let mut b = HashSet::new();
    b.insert(1);
    // пересечение пустое ?
    assert_eq!(a.is_disjoint(&b), false);
    // аналогично
    let intersection: HashSet<_> = a.intersection(&b).collect();
    assert_eq!(intersection.is_empty(),false);
}

union<'a>(&'a self,other:&'a HashSet<T, S>)->Union<'a,T, S>

fn main(){
// Обьединение 
    let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();

    // Print 1, 2, 3, 4 in arbitrary order.
    for x in a.union(&b) {
        println!("{}", x);
    }

    let union: HashSet<_> = a.union(&b).collect();
    assert_eq!(union, [1, 2, 3, 4].iter().collect());
}

is_subset(&self,other: &HashSet<T, S>)->bool

fn main(){
    // Содержит по крайней мере все значения в self
    let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let mut set = HashSet::new();

    assert_eq!(set.is_subset(&sup), true);
    set.insert(2);
    assert_eq!(set.is_subset(&sup), true);
    set.insert(4);
    assert_eq!(set.is_subset(&sup), false);
}

is_superset(&self, other: &HashSet<T, S>) -> bool

fn main(){
    // если множество является надмножеством другого, то есть self содержит по крайней мере все значения в другом.
    let sub: HashSet<_> = [1, 2].iter().cloned().collect();
    let mut set = HashSet::new();

    assert_eq!(set.is_superset(&sub), false);

    set.insert(0);
    set.insert(1);
    assert_eq!(set.is_superset(&sub), false);

    set.insert(2);
    assert_eq!(set.is_superset(&sub), true);
}

replace(&mut self, value: T) -> Option<T>

fn main(){
// Добавляет значение в набор, заменяя существующее значение, если оно есть, которое равно заданному. Возвращает замененное значение.
    let mut set = HashSet::new();
    set.insert(Vec::::new());

    assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
    set.replace(Vec::with_capacity(10));
    assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
}

remove<Q: ?Sized>(&mut self, value: &Q) -> bool
    where
       T: Borrow<Q>,
       Q: Hash + Eq, 

fn main(){
// Удаляет значение из набора. Возвращает true, если значение присутствовало в наборе. 
    let mut set = HashSet::new();

    set.insert(2);
    assert_eq!(set.remove(&2), true);
    assert_eq!(set.remove(&2), false);
}

retain<F>(&mut self, f: F) 
where
    F: FnMut(&T) -> bool, 

fn main(){
// Сохраняет только элементы, заданные предикатом. 
    let xs = [1,2,3,4,5,6];
    let mut set: HashSet = xs.iter().cloned().collect();
    set.retain(|&k| k % 2 == 0);
    assert_eq!(set.len(), 3);
}

• union: получить все уникальные элементы в обоих наборах.

• difference: получить все элементы, которые находятся в первом наборе, но не второй.

• intersection: получить все элементы, которые находятся только в обоих наборах.

• symmetric_difference: получить все элементы, которые находятся в одном наборе или другом, но не оба.

use std::collections::HashSet;
fn main() {
    let mut a: HashSet = vec!(1i32, 2, 3).into_iter().collect();
    let mut b: HashSet = vec!(2i32, 3, 4).into_iter().collect();

    assert!(a.insert(4));
    assert!(a.contains(&4));

    // `HashSet::insert()` returns false if
    // there was a value already present.
    assert!(b.insert(4), "Value 4 is already in set B!");
    // FIXME ^ Comment out this line

    b.insert(5);

    // If a collection's element type implements `Debug`,
    // then the collection implements `Debug`.
    // It usually prints its elements in the format `[elem1, elem2, ...]`
    println!("A: {:?}", a);
    println!("B: {:?}", b);

    // Print [1, 2, 3, 4, 5] in arbitrary order
    println!("Union: {:?}", a.union(&b).collect::>());

    // This should print [1]
    println!("Difference: {:?}", a.difference(&b).collect::>());

    // Print [2, 3, 4] in arbitrary order.
    println!("Intersection: {:?}", a.intersection(&b).collect::>());
    // Print [1, 5]
    println!("Symmetric Difference: {:?}",
             a.symmetric_difference(&b).collect::>());
}

std::collections::HashMap

• struct.HashMap
• perf-book/hashing
• understanding-a-hash-table
• cheats.rs/#other-collections

• Вы хотите связать произвольные ключи с произвольным значением.
• Доступ по ключу
• Вам нужна карта без дополнительной функциональности.
• Если вам нужен, HashMap который выдает вам свои ключи по порядку, вы можете использовать BTreeMap
• Если вам нужен, HashMap который выдает значения по порядку используйте crate indexmap

Хеш-карты настолько популярны, потому что по большей части они обеспечивают время поиска O(1) и время удаления O(1)

Алгоритм хеширования по умолчанию в настоящее время является SipHash 1-3

Ключи могут быть логическими, целыми числами, строками или любым другим типом реализующим Eq и Hash черты, хотя это часто может быть достигнуто при использовании

#[derive(PartialEq, Eq, Hash)]
k1 == k2 -> hash(k1) == hash(k2)

fn main(){
 let solar_distance = HashMap::from([
    ("Mercury", 0.4),
    ("Venus", 0.7),
    ("Earth", 1.0),
    ("Mars", 1.5),
 ]);
}

Параллельный HashMap

crate dashmap
Самый быстрый для рабочих нагрузок общего назначения

crate flurry
Особенно хорошо подходит для рабочих нагрузок с интенсивным чтением.

Алгоритм хеширования можно заменить на ослабленной HashMap основе с использованием методов:

• default,
• with_hasher
• with_capacity_and_hasher

Многие альтернативные алгоритмы доступны на crates.io, например:

• в crate fnv.

method.with_hasher

crates.io/hasher...

hashing-functions

Использование быстрой хеш функции (не рекомендуется если есть угроза к DoS атакам)

use fnv::FnvHashMap;
fn main(){
    let mut map = FnvHashMap::default();
    map.insert(1, "one");
    map.insert(2, "two");
}

[dependencies]
ahash = "0.7.4"

use std::collections::HashMap;
fn main(){
    let h = HashMap;
}

IndexMap сохраняет порядок вставки

use std::collections::HashMap;
use indexmap::IndexMap;

fn main() {
    let mut hash_map = HashMap::new();
    hash_map.insert("a", 1);
    hash_map.insert("b", 2);
    hash_map.insert("c", 3);

    let mut index_map = IndexMap::new();
    index_map.insert("a", 1);
    index_map.insert("b", 2);
    index_map.insert("c", 3);

    println!("HashMap:");
    for (key, value) in &hash_map {
        println!("{}: {}", key, value); // Порядок может быть произвольным
    }

    println!("IndexMap:");
    for (key, value) in &index_map {
        println!("{}: {}", key, value); // Порядок сохраняется
    }
}

HashMap пожератель памяти

• vec = 64
• hash = 144

use std::collections::HashMap;
use peak_alloc::PeakAlloc;

#[global_allocator]
static PEAK_ALLOC: PeakAlloc = PeakAlloc;

fn main() {
    let current_mem_before = PEAK_ALLOC.current_usage_as_mb();
        println!("В настоящее время эта программа использует {} MB of RAM.", current_mem_before);
        let peak_mem_before = PEAK_ALLOC.peak_usage_as_gb();
        println!("Максимальная сумма, которая была использована {}\n\n", peak_mem_before);

    let mut vec: Vec = Vec::with_capacity(2048);
    //let mut map = HashMap::new();
    for i in 0..10000000{
        vec.push(i);
        //map.insert(i, i);
    }

    let current_mem_after = PEAK_ALLOC.current_usage_as_mb();
        println!("В настоящее время эта программа использует {} MB of RAM.", current_mem_after);
        let peak_mem_after = PEAK_ALLOC.peak_usage_as_gb();
        println!("Максимальная сумма, которая была использована {}", peak_mem_after);

    println!("Занимаемая память {}", peak_mem_after-peak_mem_before);// vec =  0.031250954
                                                                                                                       // hash = 0.59013176                                                                    
}

Vec 10000000 -------------------------------------------------
В настоящее время эта программа использует 0.00005054474 MB of RAM.
Максимальная сумма, которая была использована 0.000000049360096
+++
В настоящее время эта программа использует 64.00103 MB of RAM.
Максимальная сумма, которая была использована 0.031251002

HashMap 10000000 -------------------------------------------------
В настоящее время эта программа использует 0.00005054474 MB of RAM.
Максимальная сумма, которая была использована 0.000000049360096
+++
В настоящее время эта программа использует 144.00104 MB of RAM.
Максимальная сумма, которая была использована 0.07031352

Max value

use std::collections::HashMap;
fn main(){
    let mut  user_bets:HashMap = HashMap::new();
    user_bets.insert(1,200); user_bets.insert(3,300); user_bets.insert(7,100); user_bets.insert(2,20);

    let max_value = user_bets.iter().reduce(|a, b| {
       if a.1 >= b.1 { a } else { b }
    });
// или
    let max_value = user_bets.iter().max_by(|x, y| x.1.cmp(y.1)).unwrap();
    assert_eq!(Some((3, 300)),max_value);
}

Методы:

• new - Создает пустую HashMap
• with_capacity - Создает пустой HashMap с указанной емкостью.
• with_hasher - Создание с хэш-конструктором для хеш-ключей
• with_capacity_and_hasher - Создание с хешером и емкостью
• hasher - Возвращает ссылку BuildHasher
• capacity - Количество элементов без выделения новой памяти
• reserve - Резервирует емкость
• try_reserve
• shrink_to_fit - Максимально уменьшает емкость комплекта
• shrink_to
• keys - Итератор по ключам
• values - Итератор по значениям
• values_mut - Итератор по значениям с изменением
• iter - Итератор по пары ключ-значение
• iter_mut - Изменяемый итератор по пары ключ-значение
• entry - Получить состояние записи
• len - Количество элементов map
• is_empty - Проверка на пустоту
• drain - Очищает набор, возвращая все элементы в итераторе
• clear - Удаляет набор, удаляя все значения
• get - Возвращает ссылку на значение, соответствующее ключу
• get_key_value
• contains_key - Возвращает true, если набор содержит значение.
• get_mut - Возвращает измененную ссылку на значение по ключу
• insert - Вставляет пару ключ-значение в карту
• remove - Удаляет ключ с карты
• remove_entry - Удаляет ключ с карты , возвращает значение с ключом
• retain - Сохраняет только элементы, заданные предикатом

fn main(){
     use std::collections::HashMap;
    // let mut map: HashMap<&str, i32> = HashMap::new();
    let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
    map.insert("a", 1);  map.insert("b", 2);  map.insert("c", 3);

    if map.contains_key("key"){
        let x = map.get_mut("key").unwrap();  
        *x=*x+1;
     }else{
         map.insert("key",1);
     }

//contains_key(key) проверяет наличие ключа
    assert_eq!(map.contains_key("b"), true);
//get(key) Возвращает ссылку на значение, соответствующее ключу
    assert_eq!(map.get("b"), Some(&2));
    if let Some(x) = map.get_mut("b") {
        *x = 100;
    }
//keys() Итератор посещает все ключи в произвольном порядке.
    for key in map.keys() {
        println!("{}", key);
    }
//values() Итератор посещает все значения в произвольном порядке.
    for val in map.values() {
        println!("{}", val);
    }
    for val in map.values_mut() {
        *val = *val + 10;
    }
// проход по HashMap
    for (key, value) in &map {
        println!("{}: \"{}\"", key, value);
    }
    for (key, val) in map.iter() {
        println!("key: {} val: {}", key, val);
    }
    for (_, val) in map.iter_mut() {
        *val *= 2;
    }
    //remove(key) Удаляет ключ с карты, возвращая значение в ключе, если ключ был ранее в map
    map.insert("a", 1);
    assert_eq!(map.remove("a"), Some(&1));
    //remove_entry(key) Удаляет ключ с карты, возвращая сохраненный ключ и значение, если ключ был ранее в map.
    assert_eq!(map.remove_entry("b"), Some(( "b",2)));
}

HashMap Serialize Deserialize

fn main(){
    // Serialize
    let mut map: HashMap> = HashMap::with_capacity(1000);
    // ....
    let s_string = serde_json::to_string(&map).unwrap();// Serialize
    let mut f = File::open("src/helper/data_serialize/sample.json")?;//открыть/создать
    f.write_all(s_string.as_bytes())?;// запись в файл
     
    // Deserialize
    let mut f = std::fs::File::open("src/helper/data_serialize/sample.json")?;
    let mut lookup: HashMap = serde_json::from_reader(&mut f).unwrap();
    let keys:Vec = lookup.keys().map(|k|k.to_owned()).collect();
    let mut map: HashMap> = HashMap::new();
    for key in keys {
        let (k, v) = lookup.remove_entry(&key).unwrap();
        let vector:Vec = v.as_array().unwrap().iter().map(|v|v.as_str().unwrap().to_owned()).collect();
        map.insert(k, vector);
    }
    println!(""serialized = {:#?}"", map);                                                                                                                                                                                               
}

Получение value по значению для Copy типов

вызывая copied для получения Option<i32> вместо Option<&i32>

use std::collections::HashMap;
fn main(){
    let mut scores = HashMap::new();
    let team_name = String::from("Blue");
    let score = scores.get(&team_name).copied().unwrap_or(0);
}

Создание HashMap из среза через collect. Возвращаемый тип из map (key, value)

fn main(){
    let mut vars: [&str; 3] = ["ENV_VAR_THREE", "ENV_VAR_TWO", "ENV_VAR_ONE"];
    let vars_map: HashMap = vars
        .into_iter()
        .map(|&var| {
            env::var_os(var)
                .ok_or((var.to_uppercase(), String::from("")))
                .and_then(|value| {
                    if !value.is_empty() {
                        Ok((
                            var.to_uppercase(),
                            value.into_string().unwrap_or(String::from("")),
                        ))
                    } else {
                        Ok((var.to_uppercase(), String::from("")))
                    }
                })
                .unwrap_or((var.to_uppercase(), String::from("")))
    })
    .collect();
}

Быстрый способ создать HashMap

use std::collections::HashMap;

#[derive(Clone,Copy,Debug)]
struct Matrix{
    pub size:usize,

}
impl Matrix {
    fn new(size:usize  )->Self{
        Self{size }
    }
}
fn main(){
    let raw = vec![1; 9000000];

    let now = Instant::now();
    let mut buf_matrix: HashMap = HashMap::new();
    for (index,v) in  raw.iter().enumerate() {
        buf_matrix.insert( index, Matrix::new(index));
    }
    println!("Time Only Hash ={}s\n", now.elapsed().as_secs());// 10 sec

    let now = Instant::now();
    let mut buf_matrix:Vec<(usize,Matrix)> = Vec::new();
    for (index,v) in  raw.iter().enumerate() {
        buf_matrix.push((index, Matrix::new(index)));
    }
    //buf_matrix.sort_unstable_by(|a, b| a.0.cmp(&b.0));
     let buf_matrix: HashMap = buf_matrix
        .iter()
        .map(|t|t.0)
        .zip(buf_matrix.iter().map(|t|t.1))
        .collect::>();
     println!("Time Vec to Hash ={}s\n", now.elapsed().as_secs());// 6 sec

     for (k,v) in buf_matrix.iter().take(5){
          println!("k={} v={}", k,v.size);
      }
     println!("len={}", buf_matrix.len());

}

insert(&mut self, k: K, v: V) -> Option<V>

use std::collections::HashMap;
fn main(){
// При вставке нового значение возвращается None
// в случае вставки существующего ключа значение перезаписывается и возвращается старое значение
    let mut map = HashMap::new();
    assert_eq!(map.insert(37, "a"), None);
    assert_eq!(map.is_empty(), false);

    map.insert(37, "b");
    assert_eq!(map.insert(37, "c"), Some("b"));
    assert_eq!(map[&37], "c");
}

retain<F>(&mut self, f: F) Сохраняет только элементы, заданные предикатом

fn main(){
    let mut map: HashMap = (0..8).map(|x|(x, x*10)).collect();
    map.retain(|&k, _| k % 2 == 0);
    assert_eq!(map.len(), 4);
}

entry(&mut self, key: K) -> Entry<K, V> есть ключ или нет ключа. Получает соответствующую запись соответствующего ключа на карте для манипуляций на месте.

entry().or_insert()

HashMap реализует Entry API

method.entry

// манипулирования содержимого map условно на наличии ключа или нет

• std::collections::hash_map::Entry
  • Occupied(OccupiedEntry<'a, K, V>) - занятая запись
  • Vacant(VacantEntry<'a, K, V>) - свободная

Struct std::collections::hash_map::VacantEntry

Struct std::collections::hash_map::OccupiedEntry

fn main(){
// map.entry() возвращает Enum Entry означающий есть ключ или нет ключа
    let mut map: HashMap<&str, u32> = HashMap::new();
    match map.entry("poneyland") {
        Entry::Occupied(object_OccupiedEntry) => { println!("Значение {}",object_OccupiedEntry.get());},
        Entry::Vacant(object_VacantEntry) =>  println!("Ключ {}",object_VacantEntry.key())
    };

// или короче
// entry().or_insert() Если entry вернуло Vacant то вставка иначе вернет Occupied с объектом
    map.entry("poneyland").or_insert(12);// Entry(VacantEntry("poneyland"))

    *map.entry("poneyland").or_insert(12)+=10;// Entry(OccupiedEntry { key: "poneyland", value: 12 })

// entry().or_insert_with вставка при отсутствии ключа с помощью замыкания
    // map.entry("poneyland").or_insert_with(|| 100);

// entry().key() возвращает ключ
    println!("{:?}", map.entry("poneyland").key()); // poneyland


//  entry().and_modify() в случае (Occupied) присутствия ключа изменяет значение через замыкание
    map.entry("poneyland")
        .and_modify(|e| { *e += 1 })
        .or_insert(12);
    assert_eq!(map["poneyland"], 13);
    
//  вставляет значение по умолчанию для типа, если для текущего ключа не существует записи
// entry().or_default() не пашет вместо нее
    map.entry("poneyland").or_insert_with(Default::default);
}

Vacant(VacantEntry<'a, K, V>)

struct.VacantEntry

fn main(){
// Vacant(VacantEntry<'a, K, V>) свободная запись
// key()  insert(value) into_key()
    let mut map: HashMap<&str, u32> = HashMap::new();

    if let Entry::Vacant(object_VacantEntry) = map.entry("poneyland"){

        // VacantEntry.key()
         println!("Ключ {} свободен",object_VacantEntry.key());

        // VacantEntry.insert(value) вставка значения с созданным ключем.После это расходуется VacantEntry
        let value = object_VacantEntry.insert(12);
        println!("value:{:?}",value);// value:12

        // VacantEntry.into_key() расходует ключ если небыло вставки до этого
        //let key = object_VacantEntry.into_key();
        //println!("key:{}",key);
    };
}

Occupied(OccupiedEntry<'a, K, V>)

struct.OccupiedEntry

fn main(){
//  Occupied(OccupiedEntry<'a, K, V>) существующая запись
// key() remove_entry() get_mut() get() insert() remove() into_mut()
let mut map: HashMap<&str, u32> = HashMap::new();
  map.entry("poneyland").or_insert_with(Default::default);

  if let Entry::Occupied(mut object_OccupiedEntry) = map.entry("poneyland"){

// OccupiedEntry.key()
      println!("Ключ {} занят",object_OccupiedEntry.key());

// OccupiedEntry.remove_entry() удаляет ключ с карты
      //object_OccupiedEntry.remove_entry();

 // OccupiedEntry.get() возвращает изменяемую ссылку на значение
      *object_OccupiedEntry.get_mut()+=10;

// OccupiedEntry.get() возвращает ссылку на значение
     println!("object_OccupiedEntry:{:?}",object_OccupiedEntry.get());

// OccupiedEntry.insert(value) Устанавливает значение записи и возвращает старое значение записи.
      let value = object_OccupiedEntry.insert(12);
      println!("value:{:?}",value);// value:10

// OccupiedEntry.remove() удаляет значение и возвращает его
      let value = object_OccupiedEntry.remove();
      println!("value:{:?}",value);// value:12
  }
  
  //OccupiedEntry.into_mut() преобразует в изменяемую ссылку на значение
  if let Entry::Occupied(object_OccupiedEntry) = map.entry("poneyland"){
      *object_OccupiedEntry.into_mut()+=10;
  }
}

use std::collections::HashMap;

// Eq requires that you derive PartialEq on the type.
#[derive(PartialEq, Eq, Hash)]
struct Account<'a>{
    username: &'a str,
    password: &'a str,
}
struct AccountInfo<'a>{
    name: &'a str,
    email: &'a str,
}
type Accounts<'a> = HashMap, AccountInfo<'a>>;

fn try_logon<'a>(accounts: &Accounts<'a>,
        username: &'a str, password: &'a str){
    println!("Username: {}", username);
    println!("Password: {}", password);
    println!("Attempting logon...");

    let logon = Account {
        username: username,
        password: password,
    };
    match accounts.get(&logon) {
        Some(account_info) => {
            println!("Successful logon!");
            println!("Name: {}", account_info.name);
            println!("Email: {}", account_info.email);
        },
        _ => println!("Login failed!"),
    }
}
fn main(){
    let mut accounts: Accounts = HashMap::new();
    let account = Account {
        username: "j.everyman",
        password: "password123",
    };
    let account_info = AccountInfo {
        name: "John Everyman",
        email: "j.everyman@email.com",
    };
    accounts.insert(account, account_info);
    try_logon(&accounts, "j.everyman", "psasword123");
    try_logon(&accounts, "j.everyman", "password123");
}

remove insert get

use std::collections::HashMap;
fn call(number: &str) -> &str {
    match number {
        "798-1364" => "We're sorry, the call cannot be completed as dialed. Please hang up and try again.",
        "645-7689" => "Hello, this is Mr. Awesome's Pizza. My name is Fred. What can I get for you today?",
        _ => "Hi! Who is this again?"
    }
}
fn main() {
    let mut contacts = HashMap::new();
    contacts.insert("Daniel", "798-1364");
    contacts.insert("Ashley", "645-7689");
    contacts.insert("Katie", "435-8291");
    contacts.insert("Robert", "956-1745");

    // Takes a reference and returns Option<&V>
    match contacts.get(&"Daniel") {
        Some(&number) => println!("Calling Daniel: {}", call(number)),
        _ => println!("Don't have Daniel's number."),
    }

    // `HashMap::insert()` returns `None`
    // if the inserted value is new, `Some(value)` otherwise
    contacts.insert("Daniel", "164-6743");

    match contacts.get(&"Ashley") {
        Some(&number) => println!("Calling Ashley: {}", call(number)),
        _ => println!("Don't have Ashley's number."),
    }

    contacts.remove(&"Ashley");

    // `HashMap::iter()` returns an iterator that yields
    // (&'a key, &'a value) pairs in arbitrary order.
    for (contact, &number) in contacts.iter() {
        println!("Calling {}: {}", contact, call(number));
    }
}

std::collections::BTreeSet

struct.BTreeSet

Сортированный набор

Если вам нужен, HashSet который выдает вам свои ключи по порядку, вы можете использовать BTreeSet

Методы:

• new - Создает новый BTreeSet
• range - Создает итератор из диапазона
• difference - Разность
• symmetric_difference - Симметричная разность , только в одном map
• intersection - Общие значения
• union - Обьединение
• clear - Удаляет набор, удаляя все значения
• contains - Возвращает true, если набор содержит значение.
• get - Возвращает ссылку на значение в наборе
• is_disjoint - Проверка пересечения
• is_subset - Множество является подмножеством ?
• is_superset - Множество является надмножеством ?
• insert - Добавляет значение к набору
• replace - Добавляет значение в набор или заменяя совпавшее значение
• remove - Удаляет значение из набора
• take - Удаляет и возвращает значение в наборе
• append - Перемещение значений
• split_off - Разделяет коллекцию на две по заданному ключу
• iter - Итератор
• len - Размер
• is_empty - Проверка на пустоту

use std::collections::BTreeSet;
fn main() {
    let mut books:BTreeSet<&str> = BTreeSet::new();
   // let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();

// Add some books.
    books.insert("A Dance With Dragons");
    books.insert("To Kill a Mockingbird");
    books.insert("The Odyssey");
    books.insert("The Great Gatsby");

// Check for a specific one.
    if !books.contains("The Winds of Winter") {
        println!("We have {} books, but The Winds of Winter ain't one.", books.len());
    }

// Remove a book.
    books.remove("The Odyssey");

// Iterate over everything.
    for book in &books {
        println!("{}", book);
    }
}

std::collections::btree_map::BTreeMap

struct.BTreeMap

• сортированный map для быстрого поиска значений
• самая маленькая или самая большая пара ключ-значение
• сравнение ключей

В частности, каждый элемент хранится в отдельном узле, выделенном кучей.

Если вам нужен, HashMap который выдает вам свои ключи по порядку, вы можете использовать BTreeMap

Ключи сортируются автоматиески

fn main(){
// Сохраняется порядок сортировки
    let mut a:BTreeMap = BTreeMap::new();
    a.insert(10, "a");
    a.insert(2, "b");
    a.insert(3, "c");
    println!("{:?}",a);// {2: "b", 3: "c", 10: "a"}

    let mut a = BTreeMap::new();
    a.insert("d", 1);
    a.insert("c", 1);
    a.insert("a", 1);
    println!("{:?}",a);// {"a": 1, "c": 1, "d": 1}
}

Методы:

• new - Создает новый пустой BTreeMap с разумным выбором для B
• clear - Очищает map, удаляя все значения
• get - Возвращает ссылку на значение, соответствующее ключу.
• get_key_value
• contains_key - Возвращает true, если map содержит значение по ключу
• get_mut - Возвращает измененную ссылку на значение, по ключу
• insert - Вставляет пару ключ-значение в карту
• remove - Удаляет ключ с карты
• append - Слияние с перемещением
• range - Создает итератор из диапазона
• range_mut - Изменчивый диапазон (от и до не включая) по значениям
• entry - Получить состояние записи
• split_off - Разделяет коллекцию на две по заданному ключу.
• iter - Получает итератор по элементам карты, отсортированным по ключу
• iter_mut - Получает измененный итератор по элементам карты, отсортированным по ключу
• keys - Получает итератор по ключам карты в отсортированном порядке
• values - Получает итератор по значениям карты в порядке по ключу
• values_mut - Получает изменчивый итератор по значениям карты в порядке по ключу
• len - Возвращает количество элементов на карте
• is_empty - Проверка на пустоту

fn main(){
   let mut map = BTreeMap::new();
    // let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter().map(|&s| (s, 0)).collect();

    if ! map.is_empty() {
        map.len()
    }

// Ключом может быть любая заимствованная форма типа ключа карты, но порядок в заимствованной форме должен соответствовать порядку по типу ключа.

 //insert(value) Вставляет пару ключ-значение в карту.
   // Если на карте не было этого ключа, возвращается None.
   // Если на карте действительно присутствовал этот ключ, значение обновляется, и возвращается старое значение.
    assert_eq!(None,map.insert(1, "a"));
    assert_eq!(Some("a"),map.insert(1, "c"));
   // map.insert("a", 1); ключи одного типа

// remove(key) Удаляет ключ с карты, возвращая значение в ключе, если ключ был ранее на карте.
    assert_eq!(map.remove(&1), Some("c"));

// contains_key(key) проверяет существование значения для ключа
    if map.contains_key(&1) == true {
        // get() Возвращает ссылку на значение, Option
        if let Some(v) = map.get(&1){
            println!("{}",v);
        }
        //  Возвращает измененную ссылку на значение,Option
        if let Some(x) = map.get_mut(&1) {
            *x = "b";
        }
    }

    //clear() Очищает карту, удаляя все значения.
    if !map.is_empty(){
        map.clear();
    }
}

entry(&mut self, key: K) -> Entry<K, V> проверяет если или нет значения

or_insert - иначе вставить и вернуть &mut

fn main(){
    let mut count: BTreeMap<&str, usize> = BTreeMap::new();

    // подсчитайте количество вхождений букв в векторе
    for x in vec!["a","b","a","c","a","b"] {
        *count.entry(x).or_insert(0) += 1;
    }
}

Когда пользователь вызывает map.entry(&key), карта будет искать ключ, а затем выдаст вариант Entry перечисления:

Если Vacant(entry), ключ не был найден. В этом случае единственной допустимой операцией является insert значение в записи. Когда это будет сделано, вакантная запись будет потреблена и преобразована в изменяемую ссылку на значение, которое было вставлено. Это позволяет дополнительно манипулировать значением, превышающим время жизни самого поиска. Это полезно, если сложная логика должна выполняться над значением независимо от того, было ли значение только что вставлено.

Если Occupied(entry), то ключ был найден. В этом случае пользователь имеет несколько вариантов: они могут get, insert или remove значение занимаемой записи. Кроме того, они могут преобразовать занятую запись в изменяемую ссылку на ее значение, обеспечивая симметрию свободному insert случаю.

use std::collections::btree_map::BTreeMap;
fn main(){
    let mut count = BTreeMap::new();
    let message = "she sells sea shells by the sea shore";
    // Подсчитывает количество одинаковых символов
    for c in message.chars() {
        *count.entry(c).or_insert(0) += 1;
    }
    assert_eq!(count.get(&'s'), Some(&8));

    println!("Number of occurrences of each character");
    for (char, count) in &count {
        println!("{}: {}", char, count);
    }
// Number of occurrences of each character
//  : 7 a: 2 b: 1 e: 7 h: 4 l: 4 o: 1 r: 1 s: 8 t: 1 y: 1
}

keys(&'a self) -> Keys<'a, K, V>

fn main(){
// Получает итератор по ключам карты в отсортированном порядке.
    let mut a = BTreeMap::new();
    a.insert(2, "b");
    a.insert(1, "a");

    let keys: Vec<_> = a.keys().cloned().collect();
    assert_eq!(keys, [1, 2]);
}

values(&'a self) -> Values<'a, K, V>

values_mut(&mut self) -> ValuesMut<K, V>

fn main(){
// Получает изменчивый итератор по значениям карты в порядке по ключу
    let mut a = BTreeMap::new();
    a.insert(1, String::from("hello"));
    a.insert(2, String::from("goodbye"));

    for value in a.values_mut() {
        value.push_str("!");
    }

    let values: Vec = a.values().cloned().collect();
    assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
}

iter(&self) -> Iter<K, V>

iter_mut(&mut self) -> IterMut<K, V>

fn main(){
//iter_mut  Получает измененный итератор по элементам карты, отсортированным по ключу
    let mut map = BTreeMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    for (key, value) in map.iter_mut() {
        if key != &"a" {
            *value += 10;
        }
    }
}

split_off<Q>(&mut self, key: &Q) -> BTreeMap<K, V>

fn main(){
// Разделяет коллекцию на две по заданному ключу.
    let mut a = BTreeMap::new();
    a.insert(1, "a");
    a.insert(2, "b");
    a.insert(3, "c");
    a.insert(17, "d");
    a.insert(41, "e");

    let b = a.split_off(&3);

    println!("{:?}",b );// {3: "c", 17: "d", 41: "e"}
    println!("{:?}",a );// {1: "a", 2: "b"}
}

append(&mut self, other: &mut BTreeMap<K, V>)

fn main(){
// append(BTreeMap) перемещает значения затирая совпавшие ключи, источник расходуется
    let mut a = BTreeMap::new();
    a.insert(10, "a");
    a.insert(2, "b");
    a.insert(3, "c");

    let mut b = BTreeMap::new();
    b.insert(3, "d");//
    b.insert(4, "e");
    b.insert(5, "f");

    a.append(&mut b);
    println!("{:#?}",a);
}

range<T, R>(&self, range: R) -> Range<K, V>

fn main(){
// Создает итератор из диапазона
    // паникует если srart > end или start == end
    use std::collections::BTreeMap;
    use std::ops::Bound::Included;

    let mut map = BTreeMap::new();
    map.insert(3, "a");
    map.insert(5, "b");
    map.insert(8, "c");
    for (&key, &value) in map.range((Included(&4), Included(&8))) {
        println!("{}: {}", key, value);
    }
    assert_eq!(Some((&5, &"b")), map.range(4..).next());
}

range_mut<T, R>(&mut self, range: R) -> RangeMut<K, V>

fn main(){
// Изменчивый диапазон (от до не включая ) по значениям
    let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
        .map(|&s| (s, 0))
        .collect();

    for (name, balance) in map.range_mut("B".."Cheryl") {
        *balance += 100;
        println!("{} => {}", name, balance);
    }
}

tracking-the-inebriation-of-customers-at-a-bar

use std::collections::btree_map::BTreeMap;
fn main(){
    // У клиента бара измерен уровень алкоголя в крови
    struct Person { blood_alcohol: f32 }

   // Все заказы, сделанные в баре, по идентификатору клиента.
    let orders = vec![1,2,1,2,3,4,1,2,2,3,4,1,1,1];

   // Наши клиенты.
    let mut blood_alcohol = BTreeMap::new();

    for id in orders {
        // Если мы видим этого клиента впервые, инициализируйте его
        // без алкоголя в крови. В противном случае просто извлеките их.
        let person = blood_alcohol.entry(id).or_insert(Person { blood_alcohol: 0.0 });

        // Снизьте уровень алкоголя в крови. Заказ и распитие пива занимают время!
        person.blood_alcohol *= 0.9;

        // Проверьте, достаточно ли они трезвы, чтобы выпить еще пива.
        if person.blood_alcohol > 0.3 {
            // Слишком пьян...  
            println!("Sorry {}, I have to cut you off", id);
        } else {
            // еще пива
            person.blood_alcohol += 0.1;
        }
    }
}

значения типажи-объекты

use std::collections::BTreeMap;
use std::fmt;
use std::fmt::Debug;

#[derive(Debug)]
struct S1(i32);

#[derive(Debug)]
struct S2<'a >(&'a str);

trait ST{
    fn test(&self)->String;
}

impl ST for S1{
    fn test(&self)->String{
        self.0.to_string()
    }
}
impl <'a >ST for S2<'a >{
    fn test(&self)->String{
        self.0.to_string()
    }
}
impl fmt::Debug for dyn ST {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", self.test())
    }
}
/*impl std::fmt::Display for S1 {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}",self.0 )
    }
}
impl <'a >std::fmt::Display for S2<'a > {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", self.0 )
    }
}*/
fn main(){
    let mut a:BTreeMap<&str,&dyn ST> = BTreeMap::new();
    a.insert("s1", &S1(14));
    a.insert("s3", &S2("18"));
    a.insert("s2", &S2("19"));
    println!("\n\n{:?}",a);// {"s1": "14", "s2": "19", "s3": "18"}
}

Ключи структуры должны реализовать PartialOrd

use std::collections::BTreeMap;
#[derive(Eq,Debug)]
struct A(i32);

use std::cmp::Ordering;
// Что бы знать как сортировать ключи
impl Ord for A {
    fn cmp(&self, other: &A) -> Ordering {
        self.0.cmp(&other.0)
    }
}
impl PartialOrd for A {
    fn partial_cmp(&self, other: &A) -> Option {
        Some(self.cmp(other))
    }
}
impl PartialEq for A {
    fn eq(&self, other: &A) -> bool {
        self.0 == other.0
    }
}
fn main(){
    let mut a:BTreeMap = BTreeMap::new();
    a.insert(A(14),"a14");
    a.insert(A(18),"a18");
    a.insert(A(2),"a2");

    println!("{:?}",a);// {A(2): "a2", A(14): "a14", A(18): "a18"}
}

Параллельные коллекции

• rustcamp/3_5_collections
• Аарон Турон: свобода от блокировок без сборки мусора
• Степан Глава: Lock-free Rust: Crossbeam в 2019 году
• Википедия: Неблокирующий алгоритм
• crate lockfree
• crate crossbeam
• crate rayon

Когда вам нужно работать с одной и той же коллекцией из нескольких потоков, наиболее распространенный и очевидный способ - разместить ее за каким-либо примитивом синхронизации (например Arc<RwLock<VecDeque<T>>>, например). Однако это слишком плохо для широкого использования коллекции.

Вот почему существуют параллельные коллекции: они позволяют использовать коллекцию из нескольких потоков без явной синхронизации и обеспечивают эффективный механизм синхронизации под капотом (обычно с использованием алгоритмов без блокировки).

Они позволяют безопасно и эффективно выполнять параллельные операции над элементами коллекции без необходимости вручную управлять потоками или синхронизацией.

lockfree

crossbeam

Экосистема Rust имеет ящики crossbeam и lockfree, которые обеспечивают эффективную реализацию без блокировки для некоторых коллекций, обычно используемых в параллельном контексте.

Ключевые особенности параллельных коллекций:

Безопасность в многопоточном режиме: Параллельные коллекции должны быть безопасными для использования в многозадачности. Это означает, что операции над коллекциями не должны вызывать гонок данных или других проблем с синхронизацией.

Параллельные операции: Такие коллекции поддерживают параллельное выполнение операций над своими элементами, таких как map, filter, reduce, for_each и другие. Это позволяет эффективно использовать многоядерные процессоры.

Оптимизация: Параллельные коллекции часто используют разделение работы между потоками, что позволяет значительно ускорить выполнение операций, которые могут быть параллельно обработаны.

Структуры данных для многопоточности

Структуры данных для многопоточности

• dashmap

  • Потокобезопасный HashMap с быстрым доступом.
  • Хорош для in-memory KV-хранилища с многопоточностью.

• evmap

  • HashMap с lock-free обновлениями.
  • Подходит, если нужны частые чтения и редкие записи.

crate rayon

Примеры библиотек для параллельных коллекций в Rust: crate rayon — это одна из самых популярных библиотек для параллельного программирования в Rust. Она предоставляет параллельные итераторы для стандартных коллекций, таких как Vec, HashMap и других.

В этом примере par_iter позволяет обрабатывать элементы вектора в параллельных потоках. Это позволяет использовать все ядра процессора и значительно ускорить операции, такие как преобразования коллекций, фильтрация или агрегация данных.

use rayon::prelude::*;
fn main() {
    let data: Vec = (1..=10_000).collect();
    
    // Параллельная обработка: умножаем каждый элемент на 2
    let results: Vec = data.par_iter() // Используем параллельный итератор
                               .map(|&x| x * 2)
                               .collect();
    println!("{:?}", results);
}

Неизменяемые (immutable) коллекции

Поскольку коллекции в im неизменяемы, они могут быть безопасно использованы в многопоточном приложении, если правильно управлять параллельностью.

crate im

crate rpds

Неизменяемые коллекции, преимущество - исключение случайной мутации данных

• use hashmap::HashMap;
• use hashset::HashSet;
• use ordmap::OrdMap;
• use ordset::OrdSet;
• use vector::Vector;

Неизменяемые коллекции (также известные как «постоянные структуры данных») - это коллекции, которые сохраняют интерфейс и поведение его изменяемых аналогов, но имеют другую внутреннюю реализацию, которая позволяет каждой части кода работать с собственной копией всей коллекции и не беспокоиться о случайной смене элементов для других. Ключевой особенностью является неявная дедупликация данных. Это неизбежно сказывается на производительности, поэтому неизменяемая коллекция имеет другие гарантии производительности, чем изменяемые.

В экосистеме Rust есть crate im и crate rpds, которые обеспечивают неизменяемые реализации для некоторых коллекций.

crate im — это библиотека, предоставляющая неизменяемые (immutable) коллекции для Rust. Она реализует структуры данных, которые поддерживают функциональный стиль программирования и гарантируют неизменяемость, что означает, что данные не изменяются после их создания, и любые операции с ними возвращают новые коллекции вместо модификации исходных.

Основная цель im — предоставить эффективные и безопасные структуры данных, которые позволяют работать с данными, не нарушая принципов неизменности, что особенно полезно в многозадачных и многопоточном программировании. Цель этой библиотеки - обеспечить безопасный выбор по умолчанию для наиболее распространенных видов структур данных, позволяя отложить тщательное размышление о правильной структуре данных для работы, пока вам не придётся искать оптимизацию. Структурное разделение памяти копий неразделяемых структур данных , при копии память не выделяется.

Благодаря Rc подсчету ссылок на ссылки, клонирование структуры данных становится ленивой операцией: первоначальный клон мгновенно, и по мере изменения клонированной структуры данных он будет клонировать фрагменты только там, где вы их меняете, так что, если вы измените всю вещь, вы в конечном итоге выполнили полный клон.

fn main(){
    let mut name1 = "name1".to_string();
    let mut name2 = "name2".to_string();
    let mut vec = vector![name1,name2];
    let   vec_clone = vec.clone();
    // Данные будут склонированны т.е. появится реальная выделенная память только если их изменить (ленивое клонирование на запись Cow)
    *vec.get_mut(0).unwrap()="name3".to_string();
    println!("{} {}",vec.get(0).unwrap(),vec_clone.get(0).unwrap());

    //let new_vec:Vector = vec.update(0, "name3".to_string());
    //println!("{}",new_vec.get(0).unwrap());

    // Как Cow  
    use std::borrow::Cow;
    let mut v:Vec=vec![name1,name2];
    let v1 = Cow::Borrowed(&v);
    let mut v2 = Cow::Borrowed(&v);
    v2.to_mut()[0]="name2".to_string();
    println!("{} {}",v1[0],v2[0]);
}

Методы Struct im::vector::Vector

• new - Построить пустой вектор
• singleton - Построить вектор с одним значением
• len - Получить длину вектора
• is_empty - Проверка на пустоту
• iter - Итератор
• iter_mut - Изменчивый Итератор
• get - Получите ссылку на значение индекса в векторе.
• get_mut - Получите изменчивую ссылку на значение индекса в векторе.
• front - Получите первый элемент вектора.
• front_mut - Получите первый изменчивый элемент вектора.
• head - Получите первый элемент вектора.
• back - Получите последний элемент вектора.
• back_mut - Получите последний изменчивый элемент вектора.
• last - Получить последний элемент вектора.
• index_of - Получить индекс данного элемента в векторе
• contains - Проверьте, присутствует ли данный элемент в векторе.
• update - Создание нового вектора с заменой значения по индексу
• set - Обновляет значение по индексу
• swap - Меняет местами значения
• push_front - Вставка в начало Time: O(1)
• push_back - Вставка в конец Time: O(1)
• pop_front - Удаление с начала Time: O(1)
• pop_back - Удаление с конца Time: O(1)
• append - Добавьте другой вектор в конец текущего вектора.
• retain - Фильтрация по предикату
• split_at - Разделяет вектор на два по индексу
• split_off - Отделяет часть вектора по индексу оставляя левую часть в вект.
• skip - Новый вектор с пропуском count элементов
• take - Новый вектор из первых count элементов
• truncate - Усечение вектора до заданного размера.
• insert - Вставка в позицию, дорогая операция (лучше комбинировать split)
• remove - Удалите элемент из вектора по позиции, дорогая операция
• clear - Очистка вектора
• binary_search_by - Двоичный поиск сортированного вектора
• binary_search - Двоичный поиск сортированного вектора для элемента
• binary_search_by_key - Двоичный поиск сортированного вектора
• insert_ord - Вставляет значение в отсортированный вектор Time: O(log n)
• sort - Сортировка вектора как и обычный вектор. Time: O(n log n)
• sort_by - Сортировка вектора с помощью функции компаратора

#[macro_use] // для vector![1, 2, 3, 4, 5];
extern crate im;
use im::vector::Vector;
use std::time::{Duration, Instant};

fn main() {
    let mut s: usize = 100000000;
    let mut vec: Vector = Vector::new();
    im_vector_remove(&mut s, &mut vec);
}

//push_front 13
//push_back 13
fn im_vector_add(s:&mut usize,vec:&mut Vector){
let now = Instant::now();
    while *s > 0 {
        *s-=1;
       //vec.push_back(1);
       vec.push_front(1);
    }
    println!("{}", now.elapsed().as_secs());
}
// pop_front 13
//pop_back 14
fn im_vector_remove(s:&mut usize,vec:&mut Vector){
        let mut ss = s.clone();
        while *s > 0 {
                *s-=1;
                vec.push_back(1);
        }
        let now = Instant::now();
        while ss > 0 {
                ss-=1;
                 vec.pop_front().unwrap();
                //vec.pop_back().unwrap();
        }
        println!("{}", now.elapsed().as_secs());
}

singleton(a: A) -> Self

fn main(){
    //singleton(value)  Построить вектор с одним значением
    let mut v = Vector::singleton(88);
     v.push_back(76);
    println!("{:?}",v);// [88, 76]
}

iter_mut(&mut self) -> IterMut<A>

fn main(){
    let mut v = Vector::new();
    for i in 0..10 {
       v.push_back(i);
    }
    //println!("{:?}",v);// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    // Изменчивый итератор
    for n in v.iter_mut(){
      *n+=10;
      print!("{} ",n);// 10 11 12 13 14 15 16 17 18 19
    }
}

fn get(&self, index: usize) -> Option<&A>

fn main(){
    let vec = vector!["Joe", "Mike", "Robert"];
    assert_eq!(Some(&"Robert"), vec.get(2));
    assert_eq!(None, vec.get(5));
}

get_mut(&mut self, index: usize) -> Option<&mut A>

fn main(){
    // get_mut(index) Изменчивое значение
    let mut v:Vector = Vector::singleton("one".to_string());
    v.push_back("three".to_string());

    *v.get_mut(1).unwrap()="two".to_string();
    println!("{:?}",*v.get(1).unwrap());
}

index_of(&self, value: &A) -> Option<usize>

fn main(){
// Получить индекс данного элемента в векторе.
    let mut vec = vector![1, 2, 3, 4, 5];
    assert_eq!(Some(2), vec.index_of(&3));
}

update(&self, index: usize, value: A) -> Self

fn main(){
// Создание нового вектора с заменой значения по индексу
    let mut vec = vector![1, 2, 3];
    let new_vec:Vector = vec.update(1, 5);
    assert_eq!(vector![1, 5, 3], new_vec);
}

set(&mut self, index: usize, value: A)

fn main(){
// Обновляет значение по индексу
    let mut vec = vector![1, 2, 3, 4, 5];
    vec.set(1,20);
    assert_eq!(&20,vec.get(1).unwrap());
}

swap(&mut self, i: usize, j: usize)

fn main(){
// Меняет местами значения
    let mut vec = vector![1, 2, 3, 4, 5];
    vec.swap(0,4);
    assert_eq!(&5,vec.get(0).unwrap());
}

split_at(self, index: usize) -> (Self, Self)

fn main(){
// Разделяет вектор на два по индексу
    let mut vec = vector![1, 2, 3, 7, 8, 9];
    let (mut left,right) = vec.split_at(3);// [1, 2, 3] [7, 8, 9]
    let vec = vector![4, 5, 6];
    left.append(vec);
    left.append(right);// [1, 2, 3, 4, 5, 6, 7, 8, 9]
    assert_eq!(vector![1, 2, 3, 4, 5, 6, 7, 8, 9], left);
}

skip(&self, count: usize) -> Self

fn main(){
// Новый вектор с пропуском count элементов
    let mut vec:Vector = vector![1, 2, 3, 7, 8, 9].skip(3);
    assert_eq!(vector![7, 8, 9], vec);
}

take(&self, count: usize) -> Self

fn main(){
// Новый вектор из первых count элементов
    let mut vec:Vector = vector![1, 2, 3, 7, 8, 9].take(3);
    assert_eq!(vector![1, 2, 3], vec);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       
}

• binary_search(&self, value: &A) -> Result<usize, usize>
• binary_search_by<F>(&self, f: F) -> Result<usize, usize>
• binary_search_by_key<B, F>(&self, b: &B, f: F) -> Result<usize, usize>

fn main(){
    //Двоичный поиск сортированного вектора для данного элемента.
    let mut vec:Vector<&str> = vector!["d","b","a","c"];
    vec.sort_by(|left, right| left.cmp(right));
    println!("Index:{}",vec.binary_search(&"d").unwrap());
    assert_eq!(3,vec.binary_search(&"d").unwrap());
    assert_eq!(3,vec.binary_search_by(|val|val.cmp(&"d")).unwrap());

    //Двоичный поиск выполняет этот отсортированный срез с функцией извлечения ключа
    let mut vec:Vector<(&str,i32)> = vector![("d",4),("b",40),("a",5),("c",41)];
    vec.sort_by(|left, right| left.0.cmp(right.0));
    println!("vec:{:?}",vec);// ("a", 5), ("b", 40), ("c", 41), ("d", 4)
    println!("Index:{}",vec.binary_search_by_key(&"d", |&(a,b)| a).unwrap());// Index:3
}

insert_ord(&mut self, item: A)

fn main(){
    //Вставляет значение в отсотрированный вектор Time: O(log n)
    let mut vec = vector![1, 2, 3, 7, 8, 9];
    vec.insert_ord(5);
    vec.insert_ord(4);
    vec.insert_ord(0);
    vec.insert_ord(10);
    assert_eq!(vector![0,1, 2, 3, 4, 5, 7, 8, 9,10], vec);

    let mut vec:Vector = Vector::new();
    vec.insert_ord(5);
    vec.insert_ord(4);
    vec.insert_ord(0);
    vec.insert_ord(10);
    assert_eq!(vector![0,4, 5,10], vec);
}

fn sort_by<F>(&mut self, cmp: F)

fn main(){
    let mut vec = vector![3, 2, 5, 4, 1];
    vec.sort_by(|left, right| left.cmp(right));
    assert_eq!(vector![1, 2, 3, 4, 5], vec)
}

Методы Struct im::hashmap::HashMap

struct.HashMap

• new - Создание пустой HashMap или hashmap!
• singleton - Построить хэш-карту с одним отображением
• is_empty - Проверка на пустоту
• len - Размер
• with_hasher - Создание HashMap используя хашер
• hasher - Получить ссылку на карту BuildHasher
• new_from - Создание HashMap,используя текущюю хэш-карту с хешером
• iter - Итератор
• iter_mut - Изменчивый итератор
• keys - Итератор по ключам
• values - Итератор по значениям
• get - Значение по ключу
• get_mut - Изменчивое значение по ключу
• contains_key - Проверка наличия ключа в хэш-карте
• insert - Вставка значения
• remove - Удаление возврат ключа и значения
• remove_with_key - Удаление возврат ключа
• entry - Получить состояние Entry
• update - Обновление ключа или вставка
• update_with - Обновление ключа или вставка через замыкание
• update_with_key - Обновление ключа или вставка через замыкание
• update_lookup_with_key - Обновление ключа или вставка через замыкание
• alter - Обновление через замыкание
• without - Создание с исключением ключа
• extract - Удаление ключа с возвратом
• extract_with_key- Удаление ключа с возвратом
• union - Объединение
• union_with - Объединение через замыкание при дубле ключей
• union_with_key - Объединение через замыкание при дубле ключей
• unions - Объединение
• unions_with - Объединение через замыкание при дубле ключей
• unions_with_key - Объединение через замыкание при дубле ключей
• difference - Разность , уникальные ключи
• difference_with - Разность через замыкание при дубле
• difference_with_key - Разность через замыкание при дубле
• intersection - Общие значения
• intersection_with - Общие значения через замыкание при дубле
• intersection_with_key - Общие значения через замыкание при дубле
• is_submap_by - Проверка вхождения карты в другую карту
• is_proper_submap_by - Проверка вхождения другой карты в текущую
• is_submap - Проверка вхождения карты в другую карту
• is_proper_submap - Проверка вхождения другой карты в текущую

#[macro_use] // для hashmap!
extern crate im;
use im::hashmap::HashMap;
fn main() {
    // let map = HashMap::singleton(123, "onetwothree");
    //let mut map = hashmap!{123 => "onetwothree"};
    let mut map:HashMap = HashMap::::new();
    //let mut map:HashMap = map.new_from();

    for i in map.iter(){
      println!("Key={} value={}",i.0,i.1);
    }

    if map.is_empty() {
      map.insert(123, "hello");
    }
    //iter
    for i in map.iter_mut(){
      *i="new str";
      println!("{:?}",i);
    }
    // keys() values()
    let keys: Vec<_> = map.keys().cloned().collect();
    println!("{:?}",keys);
    let values: Vec<&str> = map.values().cloned().collect();
    println!("{:?}",values);

    // get(key) get_mut(key)
    *map.get_mut(&123).unwrap()="hello";
    assert_eq!(map.get(&123),Some(&"hello"));

    // contains_key(key) 
    // remove(key)
    if map.contains_key(&123){
     let value:&str = map.remove(&123).unwrap();
     assert_eq!("hello",value);
    }
    //remove_with_key(key)
    map.insert(123, "hello");
    let value:(i32,&str) = map.remove_with_key(&123).unwrap();
    assert_eq!((123,"hello"),value);
}

iter() - Итератор

// возвращает несколько Users по их идентификаторам;
fn getUsersByIDs(&self, vec: Vec<usize>) -> Option<HashMap<usize, User<'u>>> {
    let map: HashMap<usize, User<'u>> = self.users
        .iter()
        .filter(|ref value| vec.contains(&value.1.getID()))
        .cloned()
        .collect::<HashMap<usize, User>>();
    Some(map)
}
//возвращает IDs Users, которых nickname содержит заданную строку (функция поиска)
fn getIDsUserByNickname(&self, nickname: &str) -> Option<Vec<usize>> {
    let nickname = nickname.to_lowercase();
    let nickname: &str = nickname.as_str();
    let map: HashMap<usize, User<'u>> = self.users
        .iter()
        .filter(|ref value| value.1.getNickname().to_lowercase().contains(nickname))
        .cloned()
        .collect::<HashMap<usize, User>>();
    Some(map.keys().cloned().collect::<Vec<usize>>())
}

fn main(){
    // entry(key)
    *map.entry(123).or_insert("hello")="new str";
    assert_eq!(Some(&"new str"),map.get(&123));

    // update(key,value)
    let map:HashMap = map.update(123,"hello");
    assert_eq!(Some(&"hello"),map.get(&123));

     // update_with(key,value,F) Если есть ключ 123 тогда значение дает F
    let map:HashMap = map.update_with(123,"hello",|k,v| "hello 2" );
     assert_eq!(Some(&"hello 2"),map.get(&123));
     
    //update_lookup_with_key(key,value,F)
    let (old_value,map) = map.update_lookup_with_key(123,"hello 2",|k,v,oldV| "hello 3" );
    assert_eq!(Some("hello 2"),old_value);
    assert_eq!(Some(&"hello 3"),map.get(&123));

    // alter(F,key)
    let mut map:HashMap = map.alter( |oldV|{Some("hello")} ,123);
    assert_eq!(Some(&"hello"),map.get(&123));

    // without(key)
    map.insert(124, "hello 2");
    let map:HashMap = map.without(&123);
    assert_eq!(hashmap!{124 => "hello 2"},map);

    //extract(key)
     let (v,map) = map.extract(&124).unwrap();
     assert_eq!(v, "hello 2" );
     assert_eq!(map, HashMap::::new());
}

fn main(){
    // extract_with_key(key)
    let mut map:HashMap = HashMap::::new();
     map.insert(123, "hello");
    let value:(i32,&str,HashMap::) = map.extract_with_key(&123).unwrap();
    assert_eq!(123,value.0);// old key
    assert_eq!("hello",value.1);// old value
    assert!(value.2.is_empty());// current map

    // union(map)
    let map1 = hashmap!{1 => 1, 3 => 3};
    let map2 = hashmap!{2 => 2, 3 => 4};
    assert_eq!(hashmap!{1 => 1, 2 => 2, 3 => 3}, map1.union(map2));

    // union_with(map,F) сами решаем какое значение при совпадении брать
    let map1 = hashmap!{1 => 1, 3 => 3};
    let map2 = hashmap!{2 => 2, 3 => 4};
     assert_eq!(hashmap!{1 => 1, 2 => 2, 3 => 4}, map1.union_with(map2,|v1,v2|{ v2}));

    // union_with_key(map,F) сами решаем какое значение при совпадении брать , ключ в помощь
    let map1 = hashmap!{1 => 1, 3 => 3};
    let map2 = hashmap!{2 => 2, 3 => 4};
    assert_eq!(hashmap!{1 => 1, 2 => 2, 3 => 4},map1.union_with_key(map2,|k,v1,v2|{v2 }));

    // unions(core::iter::IntoIterator)
    // https://doc.rust-lang.org/nightly/core/iter/trait.IntoIterator.html
    let map1 = hashmap!{1 => 1, 3 => 3};
    let map2 = hashmap!{2 => 2};
    assert_eq!(hashmap!{1 => 1, 2 => 2, 3 => 3}, HashMap::unions(vec![map1, map2]));

    // unions_with(core::iter::IntoIterator, F) unions_with_key(core::iter::IntoIterator, F)
    let map1 = hashmap!{1 => 1, 3 => 3};
    let map2 = hashmap!{1 => 10,2 => 2};
    assert_eq!(hashmap!{1 => 10, 2 => 2, 3 => 3},  HashMap::unions_with(vec![map1, map2],|v1,v2|{v2}));
    //assert_eq!(hashmap!{1 => 10, 2 => 2, 3 => 3},  HashMap::unions_with_key(vec![map1, map2],|k,v1,v2|{v2}));

    // difference(map)
    let map1 = hashmap!{1 => 1, 3 => 4};
    let map2 = hashmap!{2 => 2, 3 => 5};
    assert_eq!(hashmap!{1 => 1, 2 => 2}, map1.difference(map2));

    // difference_with(map,F) difference_with_key(map,F)
    let map1 = hashmap!{1 => 1, 3 => 4};
    let map2 = hashmap!{2 => 2, 3 => 5};
    // assert_eq!(hashmap!{1 => 1, 2 => 2}, map1.difference_with(map2,|v1,v2|{None}));
    assert_eq!(hashmap!{1 => 1, 2 => 2, 3 => 5}, map1.difference_with(map2,|v1,v2|{Some(v2)}));
    //assert_eq!(hashmap!{1 => 1, 2 => 2, 3 => 5}, map1.difference_with_key(map2,|k,v1,v2|{Some(v2)}));
}

fn main(){
    // intersection(map) intersection_with(map) intersection_with_key(map)
    let map1 = hashmap!{1 => 1, 2 => 2};
    let map2 = hashmap!{2 => 3, 3 => 4};
    //assert_eq!(hashmap!{2 => 2}, map1.intersection(map2)); 
    //assert_eq!(hashmap!{2 => 2}, map1.intersection_with(map2,|v1,v2|{v1}));
    assert_eq!(hashmap!{2 => 3}, map1.intersection_with_key(map2,|k,v1,v2|{v2}));

    // is_submap_by(map,F) map2 полностью входит в map1 (ключи и значения их равны)
    let map1 = hashmap!{1 => 1, 2 => 2, 3 => 8 ,5 => 5};
    let map2 = hashmap!{2 => 2, 3 => 8 };
    if map2.len() <= map1.len(){
     assert!(map2.is_submap_by(map1,|v1,v2|{ v2==v1}));
    }

    // is_proper_submap_by(map,F) map2 полностью входит в map1 (ключи и значения их равны)
    // должен иметь меньше ключей
    let map1 = hashmap!{1 => 1, 2 => 2, 3 => 8 ,5 => 5};
    let map2 = hashmap!{2 => 2, 3 => 8,5 => 5};
    if map2.len() < map1.len(){
     assert!(map2.is_proper_submap_by(map1,|v1,v2|{ v2==v1}));
    }

    // is_submap(map)  map2 полностью входит в map1 (ключи и значения их равны)
    let map1 = hashmap!{1 => 1, 2 => 2, 3 => 8 ,5 => 5};
    let map2 = hashmap!{2 => 2, 3 => 8,5 => 5};
    if map2.len() <= map1.len(){
     assert!(map2.is_submap(map1));
    }
    //is_proper_submap(map) map2 полностью входит в map1 (ключи и значения их равны)
    // должен иметь меньше ключей
    let map3 = hashmap!{1 => 1, 2 => 2};
    let map4 = hashmap!{1 => 1, 2 => 2};
    assert!(!map3.is_proper_submap(map4));
}