Lines
66.54 %
Functions
75.81 %
Branches
100 %
use alloc::borrow::ToOwned;
use alloc::vec::{self, Vec};
use core::alloc::Layout;
use core::borrow::Borrow;
use core::cmp::Ordering;
use core::fmt::{self, Debug};
use core::iter::{FusedIterator, Peekable};
use core::ops::{Deref, DerefMut};
use core::{mem, slice};
use crate::Sort;
/// An ordered Key/Value map.
///
/// This type is similar to [`BTreeMap`](alloc::collections::BTreeMap), but
/// utilizes a simpler storage model. Additionally, it provides a more thorough
/// interface and has a [`merge_with()`](Self::merge_with) function.
/// This type is designed for collections with a limited number of keys. In
/// general, this collection excels when there are fewer entries, while
/// `HashMap` or `BTreeMap` will be better choices with larger numbers of
/// entries. Additionally, `HashMap` will perform better if comparing the keys
/// is expensive.
#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct Map<Key, Value>
where
Key: Sort<Key>,
{
fields: Vec<Field<Key, Value>>,
}
impl<Key, Value> Default for Map<Key, Value>
#[inline]
fn default() -> Self {
Self::new()
/// Returns a heuristic guessing the size that should be allowed to be scanned
/// sequentially.
/// This uses the key and value types's layout to calculate based on multiple
/// cache line widths. Magic numbers are a code smell, but I'm not sure how else
/// to tune this heuristic based on the information available at compile time.
const fn scan_limit<Key, Value>() -> usize {
let field_layout = Layout::new::<Field<Key, Value>>();
let align = field_layout.align();
let aligned = ((field_layout.size() + (align - 1)) / align) * align;
if aligned == 0 {
return 1;
let scan_limit = 128 / aligned;
if scan_limit > 16 {
16
} else if scan_limit < 4 {
4
} else {
scan_limit
#[test]
fn scan_limit_tests() {
// Small sizes seem better to narrow down via binary search up until ~16
// elements.
assert_eq!(scan_limit::<u8, ()>(), 16);
// Test a mid-point of the heuristic.
assert_eq!(scan_limit::<u64, u64>(), 8);
// Large field sizes only scan chunks of 4.
assert_eq!(scan_limit::<(u128, u128), (u128, u128)>(), 4);
impl<Key, Value> Map<Key, Value>
const SCAN_LIMIT: usize = scan_limit::<Key, Value>();
/// Returns an empty map.
#[must_use]
pub const fn new() -> Self {
Self { fields: Vec::new() }
/// Returns a map with enough memory allocated to store `capacity` elements
/// without reallocation.
pub fn with_capacity(capacity: usize) -> Self {
Self {
fields: Vec::with_capacity(capacity),
/// Returns the current capacity this map can hold before it must
/// reallocate.
pub fn capacity(&self) -> usize {
self.fields.capacity()
/// Inserts `key` and `value`. If an entry already existed for `key`, the
/// value being overwritten is returned.
pub fn insert(&mut self, key: Key, value: Value) -> Option<Field<Key, Value>> {
let field = Field::new(key, value);
match self.find_key_mut(&field.key) {
Ok(existing) => Some(mem::replace(existing, field)),
Err(insert_at) => {
self.fields.insert(insert_at, field);
None
/// Inserts an entry with `key` only if the map does not already contain
/// that key.
/// If an existing key is found, `Some(key)` is returned. If an existing key
/// isn't found, `value()` will be called, a new entry will be inserted, and
/// `None` will be returned.
/// This is similar to using [`Map::entry`], except this function does not
/// require that `Key` implement [`ToOwned`].
pub fn insert_with(&mut self, key: Key, value: impl FnOnce() -> Value) -> Option<Key> {
match self.find_key_index(&key) {
self.fields.insert(insert_at, Field::new(key, value()));
Ok(_) => Some(key),
/// Returns true if this object contains `key`.
pub fn contains<SearchFor>(&self, key: &SearchFor) -> bool
Key: Sort<SearchFor>,
SearchFor: ?Sized,
self.find_key_index(key).is_ok()
/// Returns the value associated with `key`, if found.
pub fn get<SearchFor>(&self, key: &SearchFor) -> Option<&Value>
self.get_field(key).map(|field| &field.value)
/// Returns a mutable value associated with `key`, if found.
pub fn get_mut<SearchFor>(&mut self, key: &SearchFor) -> Option<&mut Value>
self.get_field_mut(key).map(|field| &mut field.value)
/// Returns the field associated with `key`, if found.
pub fn get_field<SearchFor>(&self, key: &SearchFor) -> Option<&Field<Key, Value>>
self.find_key(key).ok()
/// Returns the a mutable reference to the field associated with `key`, if
/// found.
pub fn get_field_mut<SearchFor>(&mut self, key: &SearchFor) -> Option<&mut Field<Key, Value>>
self.find_key_mut(key).ok()
/// Returns the [`Field`] at the specified `index`, or None if the index is
/// outside of the bounds of this collection.
pub fn field(&self, index: usize) -> Option<&Field<Key, Value>> {
self.fields.get(index)
/// Returns a mutable reference to the [`Field`] at the specified `index`,
/// or None if the index is outside of the bounds of this collection.
pub fn field_mut(&mut self, index: usize) -> Option<&mut Field<Key, Value>> {
self.fields.get_mut(index)
/// Removes the value associated with `key`, if found.
pub fn remove<SearchFor>(&mut self, key: &SearchFor) -> Option<Field<Key, Value>>
let index = self.find_key_index(key).ok()?;
Some(self.remove_by_index(index))
/// Removes the field at `index`.
/// # Panics
/// This function will panic if `index` is outside of the bounds of this
/// collection.
pub fn remove_by_index(&mut self, index: usize) -> Field<Key, Value> {
self.fields.remove(index)
/// Returns the number of fields in this object.
pub fn len(&self) -> usize {
self.fields.len()
/// Returns true if this object has no fields.
pub fn is_empty(&self) -> bool {
self.fields.is_empty()
/// Returns an [`Entry`] for the associated key.
pub fn entry<'key, SearchFor>(
&mut self,
key: impl Into<SearchKey<'key, Key, SearchFor>>,
) -> Entry<'_, 'key, Key, Value, SearchFor>
Key: Sort<SearchFor> + Borrow<SearchFor>,
SearchFor: ToOwned<Owned = Key> + ?Sized + 'key,
let key = key.into();
match self.find_key_index(key.as_ref()) {
Ok(index) => Entry::Occupied(OccupiedEntry::new(self, index)),
Err(insert_at) => Entry::Vacant(VacantEntry::new(self, key, insert_at)),
fn find_key<SearchFor>(&self, search_for: &SearchFor) -> Result<&Field<Key, Value>, usize>
self.find_key_index(search_for)
.map(|index| &self.fields[index])
fn find_key_mut<SearchFor>(
search_for: &SearchFor,
) -> Result<&mut Field<Key, Value>, usize>
.map(|index| &mut self.fields[index])
fn find_key_index<SearchFor>(&self, search_for: &SearchFor) -> Result<usize, usize>
// When the collection contains `Self::SCAN_LIMIT` or fewer elements,
// there should be no jumps before we reach a sequential scan for the
// key. When the collection is larger, we use a binary search to narrow
// the search window until the window is 16 elements or less.
let mut min = 0;
let field_count = self.fields.len();
let mut max = field_count;
loop {
let delta = max - min;
if delta <= Self::SCAN_LIMIT {
for (relative_index, field) in self.fields[min..max].iter().enumerate() {
let comparison =
<Key as crate::Sort<SearchFor>>::compare(&field.key, search_for);
return match comparison {
Ordering::Less => continue,
Ordering::Equal => Ok(min + relative_index),
Ordering::Greater => Err(min + relative_index),
};
return Err(max);
let midpoint = min + delta / 2;
<Key as crate::Sort<SearchFor>>::compare(&self.fields[midpoint].key, search_for);
match comparison {
Ordering::Less => min = midpoint + 1,
Ordering::Equal => return Ok(midpoint),
Ordering::Greater => max = midpoint,
/// Returns an iterator over the fields in this object.
pub fn iter(&self) -> Iter<'_, Key, Value> {
self.into_iter()
/// Returns an iterator over the fields in this object, with mutable access.
pub fn iter_mut(&mut self) -> IterMut<'_, Key, Value> {
/// Returns an iterator over the keys in this object.
pub fn keys(&self) -> Keys<'_, Key, Value> {
Keys(self.fields.iter())
/// Returns an iterator over the values in this object.
pub fn values(&self) -> Values<'_, Key, Value> {
Values(self.fields.iter())
pub fn values_mut(&mut self) -> ValuesMut<'_, Key, Value> {
ValuesMut(self.fields.iter_mut())
/// Returns an iterator returning all of the values contained in this
/// object.
pub fn into_values(self) -> IntoValues<Key, Value> {
IntoValues(self.fields.into_iter())
/// Merges the fields from `self` and `other` into a new object, returning
/// the updated object.
/// * If a field is contained in `other` but not contained in `self`,
/// `filter()` is called. If `filter()` returns a value, the returned
/// value is inserted into the new object using the original key.
/// * If a field is contained in both `other` and `self`, `merge()` is
/// called with mutable access to a clone of the value from `self` and a
/// reference to the value from `other`. The `merge()` function is
/// responsible for updating the value if needed to complete the merge.
/// The merged value is inserted into the returned object.
/// * If a field is contained in `self` but not in `other`, it is always
/// cloned.
/// ```rust
/// use kempt::Map;
/// let a: Map<&'static str, usize> = [("a", 1), ("b", 2)].into_iter().collect();
/// let b: Map<&'static str, usize> = [("a", 1), ("c", 3)].into_iter().collect();
/// let merged = a.merged_with(&b, |_key, b| Some(*b), |_key, a, b| *a += *b);
/// assert_eq!(merged.get(&"a"), Some(&2));
/// assert_eq!(merged.get(&"b"), Some(&2));
/// assert_eq!(merged.get(&"c"), Some(&3));
/// ```
pub fn merged_with(
mut self,
other: &Self,
filter: impl FnMut(&Key, &Value) -> Option<Value>,
merge: impl FnMut(&Key, &mut Value, &Value),
) -> Self
Key: Clone,
Value: Clone,
self.merge_with(other, filter, merge);
self
/// Merges the fields from `other` into `self`.
/// value is inserted into `self` using the original key.
/// called with mutable access to the value from `self` and a reference to
/// the value from `other`. The `merge()` function is responsible for
/// updating the value if needed to complete the merge.
/// * If a field is contained in `self` but not in `other`, it is ignored.
/// let mut a: Map<&'static str, usize> = [("a", 1), ("b", 2)].into_iter().collect();
/// a.merge_with(&b, |_key, b| Some(*b), |_key, a, b| *a += *b);
/// assert_eq!(a.get(&"a"), Some(&2));
/// assert_eq!(a.get(&"b"), Some(&2));
/// assert_eq!(a.get(&"c"), Some(&3));
pub fn merge_with(
mut filter: impl FnMut(&Key, &Value) -> Option<Value>,
mut merge: impl FnMut(&Key, &mut Value, &Value),
) where
let mut self_index = 0;
let mut other_index = 0;
while self_index < self.len() && other_index < other.len() {
let self_field = &mut self.fields[self_index];
let other_field = &other.fields[other_index];
match Key::compare(&self_field.key, &other_field.key) {
Ordering::Less => {
// Self has a key that other didn't.
self_index += 1;
Ordering::Equal => {
// Both have the value, we might need to merge.
other_index += 1;
merge(&self_field.key, &mut self_field.value, &other_field.value);
Ordering::Greater => {
// Other has a value that self doesn't.
let Some(value) = filter(&other_field.key, &other_field.value) else {
continue;
self.fields
.insert(self_index, Field::new(other_field.key.clone(), value));
if other_index < other.fields.len() {
// Other has more entries that we don't have
for field in &other.fields[other_index..] {
let Some(value) = filter(&field.key, &field.value) else {
self.fields.push(Field::new(field.key.clone(), value));
/// Returns an iterator that returns all of the elements in this collection.
/// After the iterator is dropped, this object will be empty.
pub fn drain(&mut self) -> Drain<'_, Key, Value> {
Drain(self.fields.drain(..))
/// Clears the contents of this collection.
/// This does not return any allocated memory to the OS.
pub fn clear(&mut self) {
self.fields.clear();
/// Resizes this collection to fit its contents exactly.
/// This function will reallocate its internal storage to fit the contents
/// of this collection's current size. If the allocation is already the
/// correct size, this is a no-op.
pub fn shrink_to_fit(&mut self) {
self.fields.shrink_to_fit();
/// Resizes this collection to be able to hold `min_capacity`.
/// If the length of this collection is larger than `min_capacity`, this
/// function will behave identically to
/// [`shrink_to_fit()`](Self::shrink_to_fit).
pub fn shrink_to(&mut self, min_capacity: usize) {
self.fields.shrink_to(min_capacity);
/// Returns an iterator that yields [`Unioned`] entries.
/// The iterator will return a single result for each unique `Key` contained
/// in either `self` or `other`. If both collections contain a key, the
/// iterator will contain [`Unioned::Both`] for that key.
/// This iterator is guaranteed to return results in the sort order of the
/// `Key` type.
pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, Key, Value> {
Union {
left: self.iter().peekable(),
right: other.iter().peekable(),
/// Returns an iterator that yields entries that appear in both `self` and
/// `other`.
/// The iterator will return a result for each `Key` contained in both
/// `self` and `other`. If a particular key is only found in one collection,
/// it will not be included.
pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, Key, Value> {
Intersection {
/// Returns an iterator that yields entries that appear in `self`, but not
/// in `other`.
/// The iterator will return a result for each `Key` contained in `self` but
/// not contained in `other`. If a `Key` is only in `other` or is in both
/// collections, it will not be returned.
pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, Key, Value> {
Difference {
impl<'a, SearchFor, Key, V> core::ops::Index<&'a SearchFor> for Map<Key, V>
type Output = V;
fn index(&self, index: &'a SearchFor) -> &Self::Output {
self.get(index).expect("key not found")
impl<'a, SearchFor, Key, V> core::ops::IndexMut<&'a SearchFor> for Map<Key, V>
fn index_mut(&mut self, index: &'a SearchFor) -> &mut Self::Output {
self.get_mut(index).expect("key not found")
/// A key provided to the [`Map::entry`] function.
/// This is a [`Cow`](alloc::borrow::Cow)-like type that is slightly more
/// flexible with `From` implementations. The `Owned` and `Borrowed` types are
/// kept separate, allowing for more general `From` implementations.
#[derive(Debug)]
pub enum SearchKey<'key, Owned, Borrowed>
Borrowed: ?Sized,
/// A borrowed key.
Borrowed(&'key Borrowed),
/// An owned key.
Owned(Owned),
impl<'key, K> From<K> for SearchKey<'key, K, K> {
fn from(value: K) -> Self {
SearchKey::Owned(value)
impl<'key, Key, Borrowed> From<&'key Borrowed> for SearchKey<'key, Key, Borrowed>
fn from(value: &'key Borrowed) -> Self {
SearchKey::Borrowed(value)
impl<'key, Key, Borrowed> SearchKey<'key, Key, Borrowed>
Key: Borrow<Borrowed>,
Borrowed: ToOwned<Owned = Key> + ?Sized,
fn as_ref(&self) -> &Borrowed {
match self {
SearchKey::Borrowed(key) => key,
SearchKey::Owned(owned) => owned.borrow(),
fn into_owned(self) -> Key {
SearchKey::Borrowed(key) => key.to_owned(),
SearchKey::Owned(owned) => owned,
impl<Key, Value> Debug for Map<Key, Value>
Key: Debug + Sort<Key>,
Value: Debug,
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut s = f.debug_map();
for Field { key, value } in self {
s.entry(key, value);
s.finish()
impl<'a, Key, Value> IntoIterator for &'a Map<Key, Value>
type IntoIter = Iter<'a, Key, Value>;
type Item = &'a Field<Key, Value>;
fn into_iter(self) -> Self::IntoIter {
Iter(self.fields.iter())
impl<'a, Key, Value> IntoIterator for &'a mut Map<Key, Value>
type IntoIter = IterMut<'a, Key, Value>;
type Item = (&'a Key, &'a mut Value);
IterMut(self.fields.iter_mut())
impl<Key, Value> IntoIterator for Map<Key, Value>
type IntoIter = IntoIter<Key, Value>;
type Item = Field<Key, Value>;
IntoIter(self.fields.into_iter())
impl<Key, Value> FromIterator<(Key, Value)> for Map<Key, Value>
fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self {
let iter = iter.into_iter();
let mut obj = Self::with_capacity(iter.size_hint().0);
// Insert out of order, then sort before returning.
for (key, value) in iter {
obj.fields.push(Field::new(key, value));
obj.fields.sort_unstable_by(|a, b| a.key().compare(b.key()));
obj
/// A field in an [`Map`].
#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct Field<Key, Value> {
key: Key,
/// The value contained in this field.
pub value: Value,
impl<Key, Value> Field<Key, Value> {
/// Returns a new field with `key` and `value`.
pub fn new(key: Key, value: Value) -> Self {
Self { key, value }
/// Returns the key of this field.
pub fn key(&self) -> &Key {
&self.key
/// Converts this field into its key.
pub fn into_key(self) -> Key {
self.key
/// Returns this field as the contained key and value.
pub fn into_parts(self) -> (Key, Value) {
(self.key, self.value)
/// The result of looking up an entry by its key.
pub enum Entry<'a, 'key, Key, Value, BorrowedKey>
BorrowedKey: ?Sized,
/// A field was found for the given key.
Occupied(OccupiedEntry<'a, Key, Value>),
/// A field was not found for the given key.
Vacant(VacantEntry<'a, 'key, Key, Value, BorrowedKey>),
impl<'a, 'key, Key, Value, BorrowedKey> Entry<'a, 'key, Key, Value, BorrowedKey>
/// Invokes `update()` with the stored entry, if one was found.
pub fn and_modify(mut self, update: impl FnOnce(&mut Value)) -> Self {
if let Self::Occupied(entry) = &mut self {
update(&mut *entry);
/// If an entry was not found for the given key, `contents` is invoked to
/// populate the entry. A mutable reference to the entry's value is
/// returned.
pub fn or_insert_with(self, contents: impl FnOnce() -> Value) -> &'a mut Value
Key: Borrow<BorrowedKey>,
BorrowedKey: ToOwned<Owned = Key>,
Entry::Occupied(entry) => entry.into_mut(),
Entry::Vacant(entry) => entry.insert(contents()),
/// If an entry was not found for the given key, `value` is inserted into
/// the entry. A mutable reference to the entry's value is returned.
pub fn or_insert(self, value: Value) -> &'a mut Value
Entry::Vacant(entry) => entry.insert(value),
/// If this entry is vacant, it is populated with `Value::default()`. A
/// mutable reference to the entry's value is returned.
/// This function does not change the entry if it is present.
pub fn or_default(self) -> &'a mut Value
Value: Default,
#[allow(clippy::unwrap_or_default)] // This is the implementation of said function...
self.or_insert_with(Value::default)
/// An entry that exists in an [`Map`].
pub struct OccupiedEntry<'a, Key, Value>
object: &'a mut Map<Key, Value>,
index: usize,
impl<'a, Key, Value> OccupiedEntry<'a, Key, Value>
fn new(object: &'a mut Map<Key, Value>, index: usize) -> Self {
Self { object, index }
fn field(&self) -> &Field<Key, Value> {
&self.object.fields[self.index]
fn field_mut(&mut self) -> &mut Field<Key, Value> {
&mut self.object.fields[self.index]
/// Converts this entry into a mutable reference to the value.
/// This is different from `DerefMut` because the `DerefMut` extends the
/// lifetime to include `self`. This function extracts the reference with
/// the original lifetime of the map.
pub fn into_mut(self) -> &'a mut Value {
&mut self.object.fields[self.index].value
&self.field().key
/// Replaces the contents of this field with `value`, and returns the
/// existing value.
pub fn replace(self, value: Value) -> Value {
core::mem::replace(self.into_mut(), value)
/// Removes the entry from the map, and returns the value.
pub fn remove(self) -> Field<Key, Value> {
self.object.fields.remove(self.index)
impl<'a, Key, Value> Deref for OccupiedEntry<'a, Key, Value>
type Target = Value;
fn deref(&self) -> &Self::Target {
&self.field().value
impl<'a, Key, Value> DerefMut for OccupiedEntry<'a, Key, Value>
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.field_mut().value
/// A vacant entry in an [`Map`].
pub struct VacantEntry<'a, 'key, Key, Value, BorrowedKey>
key: SearchKey<'key, Key, BorrowedKey>,
insert_at: usize,
impl<'a, 'key, Key, Value, BorrowedKey> VacantEntry<'a, 'key, Key, Value, BorrowedKey>
Key: Borrow<BorrowedKey> + Sort<Key>,
BorrowedKey: ToOwned<Owned = Key> + ?Sized,
fn new(
) -> Self {
object,
key,
insert_at,
/// Returns a reference to the key being inserted.
pub fn key(&self) -> &BorrowedKey {
self.key.as_ref()
/// Inserts `key` and `value` at this location in the object.
/// This function panics if `key` does not match the original order of the
/// key that was passed to [`Map::entry()`].
pub fn insert(self, value: Value) -> &'a mut Value
self.object
.fields
.insert(self.insert_at, Field::new(self.key.into_owned(), value));
&mut self.object.fields[self.insert_at].value
/// An iterator over the [`Field`]s in an [`Map`].
pub struct Iter<'a, Key, Value>(slice::Iter<'a, Field<Key, Value>>);
impl<'a, Key, Value> Iterator for Iter<'a, Key, Value> {
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
fn count(self) -> usize
Self: Sized,
self.0.count()
fn last(self) -> Option<Self::Item>
self.0.last()
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.0.nth(n)
impl<'a, Key, Value> ExactSizeIterator for Iter<'a, Key, Value> {
fn len(&self) -> usize {
self.0.len()
impl<'a, Key, Value> DoubleEndedIterator for Iter<'a, Key, Value> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back()
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
self.0.nth_back(n)
impl<'a, Key, Value> FusedIterator for Iter<'a, Key, Value> {}
/// An iterator over mutable [`Field`]s contained in an [`Map`].
pub struct IterMut<'a, Key, Value>(slice::IterMut<'a, Field<Key, Value>>);
impl<'a, Key, Value> Iterator for IterMut<'a, Key, Value> {
let field = self.0.next()?;
Some((&field.key, &mut field.value))
self.0.last().map(|field| (&field.key, &mut field.value))
self.0.nth(n).map(|field| (&field.key, &mut field.value))
impl<'a, Key, Value> ExactSizeIterator for IterMut<'a, Key, Value> {
impl<'a, Key, Value> DoubleEndedIterator for IterMut<'a, Key, Value> {
self.0
.next_back()
.map(|field| (&field.key, &mut field.value))
.nth_back(n)
impl<'a, Key, Value> FusedIterator for IterMut<'a, Key, Value> {}
/// An iterator that returns all of the elements of an [`Map`] while
/// freeing its underlying memory.
pub struct IntoIter<Key, Value>(vec::IntoIter<Field<Key, Value>>);
impl<Key, Value> Iterator for IntoIter<Key, Value> {
impl<Key, Value> ExactSizeIterator for IntoIter<Key, Value> {
impl<Key, Value> DoubleEndedIterator for IntoIter<Key, Value> {
impl<Key, Value> FusedIterator for IntoIter<Key, Value> {}
/// An iterator over the keys in an [`Map`].
pub struct Keys<'a, Key, Value>(slice::Iter<'a, Field<Key, Value>>);
impl<'a, Key, Value> Iterator for Keys<'a, Key, Value> {
type Item = &'a Key;
self.0.next().map(Field::key)
self.0.last().map(Field::key)
self.0.nth(n).map(Field::key)
impl<'a, Key, Value> ExactSizeIterator for Keys<'a, Key, Value> {
impl<'a, Key, Value> DoubleEndedIterator for Keys<'a, Key, Value> {
self.0.next_back().map(Field::key)
self.0.nth_back(n).map(Field::key)
impl<'a, Key, Value> FusedIterator for Keys<'a, Key, Value> {}
/// An iterator converting a [`Map`] into a series of owned keys.
pub struct IntoKeys<Key, Value>(vec::IntoIter<Field<Key, Value>>);
impl<Key, Value> Iterator for IntoKeys<Key, Value> {
type Item = Key;
self.0.next().map(Field::into_key)
self.0.last().map(Field::into_key)
self.0.nth(n).map(Field::into_key)
impl<Key, Value> ExactSizeIterator for IntoKeys<Key, Value> {
impl<Key, Value> DoubleEndedIterator for IntoKeys<Key, Value> {
self.0.next_back().map(Field::into_key)
self.0.nth_back(n).map(Field::into_key)
impl<Key, Value> FusedIterator for IntoKeys<Key, Value> {}
/// An iterator over the values contained in an [`Map`].
pub struct Values<'a, Key, Value>(slice::Iter<'a, Field<Key, Value>>);
impl<'a, Key, Value> Iterator for Values<'a, Key, Value> {
type Item = &'a Value;
Some(&field.value)
self.0.last().map(|field| &field.value)
self.0.nth(n).map(|field| &field.value)
impl<'a, Key, Value> ExactSizeIterator for Values<'a, Key, Value> {
impl<'a, Key, Value> DoubleEndedIterator for Values<'a, Key, Value> {
self.0.next_back().map(|field| &field.value)
self.0.nth_back(n).map(|field| &field.value)
impl<'a, Key, Value> FusedIterator for Values<'a, Key, Value> {}
/// An iterator over mutable values contained in an [`Map`].
pub struct ValuesMut<'a, Key, Value>(slice::IterMut<'a, Field<Key, Value>>);
impl<'a, Key, Value> Iterator for ValuesMut<'a, Key, Value> {
type Item = &'a mut Value;
Some(&mut field.value)
self.0.last().map(|field| &mut field.value)
self.0.nth(n).map(|field| &mut field.value)
impl<'a, Key, Value> ExactSizeIterator for ValuesMut<'a, Key, Value> {
impl<'a, Key, Value> DoubleEndedIterator for ValuesMut<'a, Key, Value> {
self.0.next_back().map(|field| &mut field.value)
self.0.nth_back(n).map(|field| &mut field.value)
impl<'a, Key, Value> FusedIterator for ValuesMut<'a, Key, Value> {}
/// An iterator returning all of the values contained in an [`Map`] as its
/// underlying storage is freed.
pub struct IntoValues<Key, Value>(vec::IntoIter<Field<Key, Value>>);
impl<Key, Value> Iterator for IntoValues<Key, Value> {
type Item = Value;
Some(field.value)
self.0.last().map(|field| field.value)
self.0.nth(n).map(|field| field.value)
impl<Key, Value> ExactSizeIterator for IntoValues<Key, Value> {
impl<Key, Value> DoubleEndedIterator for IntoValues<Key, Value> {
self.0.next_back().map(|field| field.value)
self.0.nth_back(n).map(|field| field.value)
impl<Key, Value> FusedIterator for IntoValues<Key, Value> {}
/// An iterator that removes all of the [`Field`]s of an [`Map`].
/// When this iterator is dropped, the underlying [`Map`] will be empty
/// regardless of whether the iterator has been fully exhausted.
pub struct Drain<'a, Key, Value>(vec::Drain<'a, Field<Key, Value>>);
impl<'a, Key, Value> Iterator for Drain<'a, Key, Value> {
impl<'a, Key, Value> ExactSizeIterator for Drain<'a, Key, Value> {
impl<'a, Key, Value> DoubleEndedIterator for Drain<'a, Key, Value> {
impl<'a, Key, Value> FusedIterator for Drain<'a, Key, Value> {}
/// An iterator that yields [`Unioned`] entries for two [`Map`]s.
/// The iterator will return a single result for each unique `Key` contained in
/// either map. If both collections contain a key, the iterator will contain
/// [`Unioned::Both`] for that key.
/// This iterator is guaranteed to return results in the sort order of the `Key`
/// type.
pub struct Union<'a, K, V>
K: Sort,
left: Peekable<Iter<'a, K, V>>,
right: Peekable<Iter<'a, K, V>>,
impl<'a, K, V> Iterator for Union<'a, K, V>
type Item = Unioned<'a, K, V>;
if let Some(left) = self.left.peek() {
if let Some(right) = self.right.peek() {
match left.key().compare(right.key()) {
Ordering::Less => Some(Unioned::left(self.left.next().expect("just peeked"))),
Ordering::Equal => Some(Unioned::both(
self.left.next().expect("just peeked"),
self.right.next().expect("just peeked"),
)),
Some(Unioned::right(self.right.next().expect("just peeked")))
Some(Unioned::left(self.left.next().expect("just peeked")))
self.right.next().map(Unioned::right)
(self.left.len(), Some(self.left.len() + self.right.len()))
/// A unioned entry from a [`Union`] iterator. An entry can be from the left,
/// right, or both maps.
pub enum Unioned<'a, K, V> {
/// The `self`/left map contained this key/value pair.
Left {
/// The key of the entry.
key: &'a K,
/// The value of the entry.
value: &'a V,
},
/// The `other`/right map contained this key/value pair.
Right {
/// Both maps contained this `key`.
Both {
/// The value of the `self`/left entry.
left: &'a V,
/// The value of the `other`/right entry.
right: &'a V,
impl<'a, K, V> Unioned<'a, K, V> {
/// If `self` is [`Unioned::Both`] `merge` will be called to produce a
/// single value. If `self` is either [`Unioned::Left`] or
/// [`Unioned::Right`], the key/value will be returned without calling
/// `merge`.
/// fn merge(a: &Map<String, u32>, b: &Map<String, u32>) -> Map<String, u32> {
/// a.union(b)
/// .map(|unioned| {
/// unioned
/// .map_both(|_key, left, right| *left + *right)
/// .into_owned()
/// })
/// .collect()
/// }
/// let mut a = Map::new();
/// a.insert(String::from("a"), 1);
/// a.insert(String::from("b"), 1);
/// a.insert(String::from("c"), 1);
/// let mut b = Map::new();
/// b.insert(String::from("b"), 1);
/// let merged = merge(&a, &b);
/// assert_eq!(merged.get("a"), Some(&1));
/// assert_eq!(merged.get("b"), Some(&2));
pub fn map_both<R>(self, merge: impl FnOnce(&'a K, &'a V, &'a V) -> R) -> EntryRef<'a, K, V>
R: Into<OwnedOrRef<'a, V>>,
Unioned::Left { key, value } | Unioned::Right { key, value } => EntryRef {
value: OwnedOrRef::Ref(value),
Unioned::Both { key, left, right } => EntryRef {
value: merge(key, left, right).into(),
fn both(left: &'a Field<K, V>, right: &'a Field<K, V>) -> Self {
Self::Both {
key: left.key(),
left: &left.value,
right: &right.value,
fn left(field: &'a Field<K, V>) -> Self {
Self::Left {
key: field.key(),
value: &field.value,
fn right(field: &'a Field<K, V>) -> Self {
Self::Right {
/// A reference to a key from a [`Map`] and an associated value.
pub struct EntryRef<'a, K, V> {
pub key: &'a K,
/// The associated value of this key.
pub value: OwnedOrRef<'a, V>,
impl<'a, K, V> EntryRef<'a, K, V> {
/// Returns the owned versions of the contained key and value, cloning as
/// needed.
pub fn into_owned(self) -> (K, V)
K: Clone,
V: Clone,
(self.key.clone(), self.value.into_owned())
/// An owned value or a reference to a value of that type.
/// This type is similar to [`alloc::borrow::Cow`] except that it does not
/// require that the contained type implement `ToOwned`.
pub enum OwnedOrRef<'a, K> {
/// An owned value.
Owned(K),
/// A reference to a value.
Ref(&'a K),
impl<'a, K> OwnedOrRef<'a, K> {
/// Converts the contained value into an owned representation, cloning only
/// if needed.
pub fn into_owned(self) -> K
OwnedOrRef::Owned(owned) => owned,
OwnedOrRef::Ref(r) => r.clone(),
impl<K> From<K> for OwnedOrRef<'_, K> {
Self::Owned(value)
impl<'a, K> From<&'a K> for OwnedOrRef<'a, K> {
fn from(value: &'a K) -> Self {
Self::Ref(value)
/// An iterator that yields entries that appear in two maps.
/// The iterator will return a result for each `Key` contained in both maps. If
/// a particular key is only found in one collection, it will not be included.
pub struct Intersection<'a, K, V>
impl<'a, K, V> Iterator for Intersection<'a, K, V>
type Item = (&'a K, &'a V, &'a V);
let left = self.left.peek()?;
let right = self.right.peek()?;
let _skipped = self.left.next();
let left = self.left.next().expect("just peeked");
let right = self.right.next().expect("just peeked");
return Some((left.key(), &left.value, &right.value));
let _skipped = self.right.next();
(0, Some(self.left.len().min(self.right.len())))
/// An iterator over the difference between two [`Map`]s.
/// This iterator will return a result for each `Key` contained in `self` but
pub struct Difference<'a, K, V>
impl<'a, K, V> Iterator for Difference<'a, K, V>
type Item = (&'a K, &'a V);
return Some((left.key(), &left.value));
let _left = self.left.next();
let _right = self.right.next();
(0, Some(self.left.len()))