Struct AllOne

pub struct AllOne { /* private fields */ }

双向链表 + 两个 HashMap

本实现使用 NonNull 封装裸指针，需要注意在删除节点或者 Drop 整个结构的时候需要用 Box::from_raw() 来释放内存。

• keys: HashMap<String, u32> 记录该数据结构内所有的 key 对应的值，以便用 O(1) 的时间查找 key
• index: HashMap<u32, NonNull<Node>> 记录该数据结构内所有 key 的值（作为 key）在链表结构里对应的节点的指针

Implementations

impl AllOne

&self means the method takes an immutable reference. If you need a mutable reference, change it to &mut self instead.

pub fn new() -> Self

Initialize your data structure here.

pub fn inc(&mut self, key: String)

Inserts a new key with value 1. Or increments an existing key by 1.

pub fn dec(&mut self, key: String)

Decrements an existing key by 1. If Key’s value is 1, remove it from the data structure.

pub fn get_max_key(&self) -> String

Returns one of the keys with maximal value.

pub fn get_min_key(&self) -> String

Returns one of the keys with Minimal value.

Trait Implementations

impl Debug for AllOne

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

Formats the value using the given formatter.

impl Default for AllOne

fn default() -> AllOne

Returns the “default value” for a type.

impl Drop for AllOne

fn drop(&mut self)

Must pop every node to drop allocated memory of nodes

impl Send for AllOne

impl Sync for AllOne