Deque

A Deque is a container that imitates a traditional double-ended queue. It's designed for efficient pushes and pops from either the beginning or end, making it suitable for use as a queue or stack. However, it's not optimized for insertions or deletions from the middle.

💡

More information can be found in the API docs.

Deque operations

The main operations available for a Deque are push_back (opens in a new tab), push_front (opens in a new tab), pop_back (opens in a new tab), and pop_front (opens in a new tab). It is also possible to check the len (opens in a new tab)gth of the deque, get (opens in a new tab) an element by index, and iter (opens in a new tab)ate over the elements.

push_back: Adds an element to the end of the deque. O(1) time complexity.
push_front: Adds an element to the beginning of the deque. O(1) time complexity.
pop_back: Removes and returns the last element. Returns None if the deque is empty. O(1) time complexity.
pop_front: Removes and returns the first element. Returns None if the deque is empty. O(1) time complexity.
len: Returns the number of elements in the deque. O(1) time complexity.
is_empty: Returns true if the deque contains no elements. O(1) time complexity.
get: Retrieves an element by index. Returns None if the index is out of bounds. O(1) time complexity.
front: Returns a reference to the first element without removing it. Returns None if the deque is empty.
back: Returns a reference to the last element without removing it. Returns None if the deque is empty.
iter: Returns an iterator over the elements of the deque.

⚠️

The maximum capacity of a Deque is u32::MAX - 1 elements. Attempting to push more elements is considered Undefined Behavior.

Deque lifecycle

Creating a Deque doesn't immediately commit anything to storage. To add elements to the deque, you need to use the push_back or push_front methods.

Values in a Deque must implement the Serialize and Deserialize traits from the serde (opens in a new tab) crate to be stored.

Lifecycle example

use cw_storage_plus::Deque;
 
// Create a new deque. It doesn't exist in storage yet.
let deque: Deque<u32> = Deque::new("d");
assert_eq!(deque.len(&storage).unwrap(), 0);
 
// Add elements to the deque
deque.push_back(&mut storage, &2).unwrap();
deque.push_back(&mut storage, &3).unwrap();
deque.push_front(&mut storage, &1).unwrap();
 
// Check the length
assert_eq!(deque.len(&storage).unwrap(), 3);
 
// Remove elements
assert_eq!(deque.pop_back(&mut storage).unwrap(), Some(3));
assert_eq!(deque.pop_front(&mut storage).unwrap(), Some(1));
 
// Check the final state
assert_eq!(deque.len(&storage).unwrap(), 1);
assert_eq!(deque.get(&storage, 0).unwrap(), Some(2));

Usage examples

Using Deque as a queue

use cw_storage_plus::Deque;
 
let queue: Deque<String> = Deque::new("q");
 
// Enqueue elements
queue.push_back(&mut storage, &"first".to_string()).unwrap();
queue.push_back(&mut storage, &"second".to_string()).unwrap();
 
// Dequeue elements
assert_eq!(queue.pop_front(&mut storage).unwrap(), Some("first".to_string()));
assert_eq!(queue.pop_front(&mut storage).unwrap(), Some("second".to_string()));
assert_eq!(queue.pop_front(&mut storage).unwrap(), None);

Using Deque as a stack

use cw_storage_plus::Deque;
 
let stack: Deque<u32> = Deque::new("s");
 
// Push elements
stack.push_back(&mut storage, &1).unwrap();
stack.push_back(&mut storage, &2).unwrap();
stack.push_back(&mut storage, &3).unwrap();
 
// Pop elements
assert_eq!(stack.pop_back(&mut storage).unwrap(), Some(3));
assert_eq!(stack.pop_back(&mut storage).unwrap(), Some(2));
assert_eq!(stack.pop_back(&mut storage).unwrap(), Some(1));
assert_eq!(stack.pop_back(&mut storage).unwrap(), None);

Iterating over elements

use cw_storage_plus::Deque;
 
let deque: Deque<u32> = Deque::new("d");
 
deque.push_back(&mut storage, &1).unwrap();
deque.push_back(&mut storage, &2).unwrap();
deque.push_back(&mut storage, &3).unwrap();
 
let sum: u32 = deque.iter(&storage).unwrap().map(|r| r.unwrap()).sum();
assert_eq!(sum, 6);

Maintaining a log store

It is possible to use a Deque to maintain a store of log events or transaction records. This is useful when you want to keep a history of production level events to ease in debugging a deployed instance of a contract.

use cw_storage_plus::Deque;
use serde::{Serialize, Deserialize};
use cosmwasm_std::testing::*;
use cosmwasm_std::Addr;
 
#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
struct Log {
    block_height: u64,
    sender_addr: String,
    event: String,
}
 
// Initialize the Deque for storing logs
let logs: Deque<Log> = Deque::new("logs");
 
// Simulating contract execution context
let env = mock_env();
let info = message_info(&Addr::unchecked("sender"), &[]);
let event = "funds_transferred".to_string();
 
// Add a new log entry
logs.push_front(
    &mut storage,
    &Log {
        block_height: env.block.height,
        sender_addr: info.sender.to_string(),
        event: event.clone(),
    },
).unwrap();
 
// Optionally, limit the number of stored logs
const MAX_LOGS: u32 = 100;
if logs.len(&storage).unwrap() > MAX_LOGS {
    logs.pop_back(&mut storage).unwrap();
}
 
// Retrieve the most recent log
let latest_log = logs.get(&storage, 0).unwrap().unwrap();
assert_eq!(latest_log.event, "funds_transferred");

Map IndexedMap