Struct dequemap::btreemap::DequeBTreeMap

pub struct DequeBTreeMap<K, V> { /* private fields */ }

Double-ended queue with Map feature.

DequeBTreeMap is a data structure that combines the functionality of a double-ended queue (Deque) and a map. It allows you to insert and remove key-value pairs from either end of the queue in a constant time, and provides map-like access to the values by their keys.

The implementation of DequeBTreeMap uses a BTreeMap to store the entries, and a VecDeque to store the indices in the order they were added to the map. This allows DequeBTreeMap to provide efficient O(log n) insertion, removal, and access operations. It also implements many common traits, such as Default, PartialEq, PartialOrd, Clone, and Debug.

DequeBTreeMap provides several methods for inserting and removing key-value pairs. The insert() method inserts a key-value pair into the map, and returns the old value if the key was already present. The push_back() and push_front() methods insert a key-value pair at the back or front of the queue, respectively, and return the old value if the key was already present.

DequeBTreeMap also provides the entry() method, which returns an Entry enum that represents either a vacant or occupied entry in the map. This can be used to insert or update values in the map while also managing the indices in the queue.

In addition, DequeBTreeMap provides methods for accessing and iterating over the entries in the map. The get() and get_mut() methods allow you to retrieve a reference to the value associated with a key, and the iter() and into_iter() methods return iterators over the entries in the map. DequeBTreeMap also implements the Index and IndexMut traits, which allow you to access and modify the values in the map using index syntax (e.g., map[key]).

Overall, DequeBTreeMap is a useful data structure for situations where you need to maintain the insertion order of the entries while also providing efficient access to the values by their keys.

One potential limitation of DequeBTreeMap is that it is not optimized for processing large batches of data with many duplicates. This is because the insert() method has a worst-case time complexity of O(n), where n is the number of entries in the map. This means that if you try to insert a large number of duplicate keys into the map, the performance may degrade significantly.

Additionally, DequeBTreeMap uses a BTreeMap internally, which means that the keys must implement the Ord trait. This means that the keys must have a total order and must be comparable using the <, >, <=, and >= operators. This may not always be desirable, depending on the types of keys you need to use with DequeBTreeMap.

Overall, while DequeBTreeMap is a useful data structure in many cases, it is important to consider its performance and limitations when deciding whether to use it in your own code.

When the element is present, the maximum time complexity is O(n). So it is not suitable for processing large batches of data with too many duplicates.

Here are some examples of using DequeBTreeMap in Rust code:

let mut map: DequeBTreeMap<String, i32> = DequeBTreeMap::new();

map.push_back("foo".to_string(), 42);

map.push_front("bar".to_string(), -1);

let old_value = map.insert("baz".to_string(), 123);

let value = map.get("baz");

for (key, value) in map.iter() {
println!("{}: {}", key, value);
}

The above content and some comments in the code are written by ChatGPT.

Implementations

impl<K, V> DequeBTreeMap<K, V>

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

impl<K, V> DequeBTreeMap<K, V>where K: Clone + Ord,

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated, and the old value is returned. The key is not updated, though; this matters for types that can be == without being identical.

pub fn push_back(&mut self, key: K, value: V) -> Option<V>

pub fn push_front(&mut self, key: K, value: V) -> Option<V>

pub fn entry(&mut self, key: K) -> Entry<'_, K, V>where K: Ord,

pub fn shrink_to_fit(&mut self)

pub fn capacity(&mut self) -> usize

impl<K, V> DequeBTreeMap<K, V>

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the given VecDeque. The collection may reserve more space to avoid frequent reallocations.

pub fn clear(&mut self)

pub fn remove(&mut self, k: &K) -> Option<V>where K: Ord,

pub fn get<Q>(&self, k: &Q) -> Option<&V>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

pub fn iter(&self) -> Iter<'_, K, V>

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn contains_key<Q>(&self, k: &Q) -> boolwhere K: Borrow<Q> + Ord, Q: Ord + ?Sized,

pub fn front(&self) -> Option<(&K, &V)>where K: Ord,

pub fn pop_front(&mut self) -> Option<(K, V)>where K: Ord,

pub fn back(&self) -> Option<(&K, &V)>where K: Ord,

pub fn pop_back(&mut self) -> Option<(K, V)>where K: Ord,

Trait Implementations

impl<K: Clone, V: Clone> Clone for DequeBTreeMap<K, V>

fn clone(&self) -> DequeBTreeMap<K, V>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for DequeBTreeMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for DequeBTreeMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K, V> Deserialize<'de> for DequeBTreeMap<K, V>where K: Deserialize<'de> + Ord + Clone, V: Deserialize<'de>,

Requires crate feature "serde"

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, K, V> Extend<(&'a K, &'a V)> for DequeBTreeMap<K, V>where K: Ord + Copy, V: Copy,

fn extend<T>(&mut self, iter: T)where T: IntoIterator<Item = (&'a K, &'a V)>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V> Extend<(K, V)> for DequeBTreeMap<K, V>where K: Ord + Clone,

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, const N: usize> From<[(K, V); N]> for DequeBTreeMap<K, V>where K: Ord + Clone,

fn from(items: [(K, V); N]) -> Self

Converts to this type from the input type.

impl<K, V> FromIterator<(K, V)> for DequeBTreeMap<K, V>where K: Ord + Clone,

fn from_iter<T>(iter: T) -> Selfwhere T: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<'a, K, Q, V> Index<&'a Q> for DequeBTreeMap<K, V>where K: Borrow<Q> + Ord, Q: Ord,

type Output = V

The returned type after indexing.

fn index(&self, key: &'a Q) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K: Ord, V> Index<usize> for DequeBTreeMap<K, V>

type Output = V

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K: Ord, V> IndexMut<usize> for DequeBTreeMap<K, V>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'de, K, V, E> IntoDeserializer<'de, E> for DequeBTreeMap<K, V>where K: IntoDeserializer<'de, E> + Ord, V: IntoDeserializer<'de, E>, E: Error,

type Deserializer = MapDeserializer<'de, <DequeBTreeMap<K, V> as IntoIterator>::IntoIter, E>

The type of the deserializer being converted into.

fn into_deserializer(self) -> Self::Deserializer

Convert this value into a deserializer.

impl<'a, K: Ord, V> IntoIterator for &'a DequeBTreeMap<K, V>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V> IntoIterator for DequeBTreeMap<K, V>where K: Ord,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Ord, V: Ord> Ord for DequeBTreeMap<K, V>

fn cmp(&self, other: &DequeBTreeMap<K, V>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Selfwhere Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Selfwhere Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere Self: Sized + PartialOrd,

Restrict a value to a certain interval.

impl<K: PartialEq, V: PartialEq> PartialEq for DequeBTreeMap<K, V>

fn eq(&self, other: &DequeBTreeMap<K, V>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: PartialOrd, V: PartialOrd> PartialOrd for DequeBTreeMap<K, V>

fn partial_cmp(&self, other: &DequeBTreeMap<K, V>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K, V> Serialize for DequeBTreeMap<K, V>where K: Serialize + Ord, V: Serialize,

fn serialize<T>(&self, serializer: T) -> Result<T::Ok, T::Error>where T: Serializer,

Serialize this value into the given Serde serializer.

impl<K: Eq, V: Eq> Eq for DequeBTreeMap<K, V>

impl<K, V> StructuralEq for DequeBTreeMap<K, V>

impl<K, V> StructuralPartialEq for DequeBTreeMap<K, V>