Code shared from the Rust Playground

playground.rs

use std::collections::*;
use std::rc::Rc;
use std::cell::RefCell;

pub type AccountPK = u64;
pub type Transaction = u64;
pub type TxPool = HashMap<AccountPK, Vec<Transaction>>;

// Compiler will optimize this wrapper out.
// Using Rc+RefCell to workaround GATs https://users.rust-lang.org/t/unconstrained-lifetime-parameter-for-impl/27995/4
#[derive(Clone)]
pub struct Group{
 pub key: AccountPK,
 pub transactions: Rc<RefCell<Vec<Transaction>>>
}

impl Iterator for Group {
    type Item = Transaction;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.transactions.borrow_mut().pop()
    }
}

impl Group {
    pub fn new(key: AccountPK,transactions: Vec<Transaction>) -> Self {
        Self{
        key,
        transactions:Rc::new(RefCell::new(transactions))
        }
    }
    
    pub fn is_empty(&self) -> bool {
        self.transactions.borrow().is_empty()
    }
}

pub struct PoolGroupIterator<'a> {
    pool: &'a mut TxPool,
    sorted_groups: LinkedList<Group>,
}

impl<'a> PoolGroupIterator<'a> {
    pub fn new(pool: &'a mut TxPool) -> Self {
        Self {
            pool,
            sorted_groups: Default::default(),
        }
    }
}

impl<'a> Iterator for PoolGroupIterator<'a> {
    type Item = Group;
    fn next(&mut self) -> Option<Self::Item> {
        let Self {pool, sorted_groups} = self;
        let next_group_key = pool.keys().next().cloned();
        match next_group_key {
            Some(key) => {
                let mut group = pool.remove(&key.clone()).expect("Just checked existence");
                group.sort_by_key(|a| std::cmp::Reverse(*a));
                sorted_groups.push_front(Group::new(key.clone(), group));
                Some(sorted_groups.front().expect("Just pushed").clone())
            }
            None => {
                loop {
                    match sorted_groups.pop_front() {
                        None => break None,  // All transactions were processed.
                        Some(sorted_group) => if sorted_group.is_empty() {
                            continue;
                        } else {
                            sorted_groups.push_back(sorted_group);
                            break Some(sorted_groups.back_mut().expect("Just pushed").clone());
                        }
                    }
                }
            }
        }
    }
}

impl<'a> Drop for PoolGroupIterator<'a> {
    fn drop(&mut self) {
        let Self {pool, sorted_groups} = self;
        while let Some(sorted_group) = sorted_groups.pop_front() {
            let Group{key, transactions} = sorted_group;
            pool.insert(key, Rc::try_unwrap(transactions).expect("Should be the last reference").replace(Vec::new()));
        }
    }
}

fn validate(tx: u64) -> bool {
    tx % 2 == 1
}

pub fn main() {
    let mut pool = HashMap::new();
    pool.insert(1, vec![2,1]);
    pool.insert(0, vec![1]);
    pool.insert(2, vec![3]);
    for mut group in PoolGroupIterator::new(&mut pool) {
        loop {
            match group.next() {
                Some(t) => if validate(t) {
                    println!("{}", t);
                    break;
                }
                None => {
                    break;
                }
            }
        }
    }
}