iterator - 使用 HashMap 实现类 SQL RIGHT OUTER JOIN 的迭代器适配器

Question

我正在尝试扩展 bluss 的 rust-itertools使用类似 SQL 的连接迭代器。我在 RIGHT OUTER JOIN 使用散列连接策略时遇到了一个特殊问题(该策略本身实际上非常简单)。

迭代器适配器结构采用 2 个输入迭代器，其中第二个(右侧)加载到 HashMap 中。迭代工作如下:

1. 左侧迭代器中的项目与 map 匹配 - 如果匹配则返回两个项目
2. 当左迭代器耗尽时，返回map中不匹配的值

问题 出在第二部分，我试图将 map 的值迭代器与 map 一起存储，以存储其迭代状态。但正如我在此 answer 中了解到的那样，使用rust 是不可能的。不幸的是，我不知道如何才能做到这一点。

这是 INNER JOIN 适配器的完整代码，它执行第一部分:

use std::collections::HashMap;
use std::hash::Hash;

pub struct HashJoinInner<I, K, V0, V1> where
    I: Iterator<Item=(K, V0)>,
    K: Hash + Eq,
    V1: Clone,
{
    left: I,
    right: HashMap<K, V1>,
}

impl<I, K, V0, V1> HashJoinInner<I, K, V0, V1> where
    I: Iterator<Item=(K, V0)>,
    K: Hash + Eq,
    V1: Clone,
{
    /// Create a `HashJoinInner` iterator.
    pub fn new<J>(l: I, r: J) -> Self
        where J: Iterator<Item=(K, V1)>
    {
        let mut hm: HashMap<K, V1> = HashMap::new();
        for (k, v) in r {
            hm.insert(k, v);
        }
        HashJoinInner {
            left: l,
            right: hm,
        }
    }
}

impl<I, K, V0, V1> Iterator for HashJoinInner<I, K, V0, V1> where
    I: Iterator<Item=(K, V0)>,
    K: Hash + Eq,
    V1: Clone,
{
    type Item = (V0, V1);

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.left.next() {
                Some((k0, v0)) => match self.right.get(&k0) {
                    Some(v1) => return Some((v0, Clone::clone(v1))),
                    None => continue,
                },
                None => return None,
            }
        }
    }
}

我将不胜感激。

Answer 1

您不能存储 Values 迭代器，因为它包含对 HashMap 的引用。如果您移动 map ，这些引用可能会变得无效。但是，您可以使用 into_iter 方法使用 HashMap。它拥有 HashMap 的所有值，并且可以移动到新结构中。

这是对您之前问题中的代码的调整。这还不是左连接或右连接。从使用一个迭代器完成到完成另一个迭代器的切换很复杂。

use std::collections::hash_map::{HashMap, IntoIter};
use std::hash::Hash;

struct Foo<K, V>
    where K: Hash + Eq,
          V: Clone,
{
    iter: IntoIter<K, (V, bool)>,
}

impl<K, V> Foo<K, V>
    where K: Hash + Eq,
          V: Clone,
{
    fn new<I>(it: I) -> Self
        where I: Iterator<Item=(K, V)>
    {
        let mut map = HashMap::new();
        for (k, v) in it {
            map.insert(k, (v, false));
        }
        Foo { iter: map.into_iter() }
    }
}

impl<K, V> Iterator for Foo<K, V>
    where K: Hash + Eq,
          V: Clone,
{
    type Item = V;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.iter.next() {
                Some((_, (v, false))) => return Some(v.clone()),
                Some(_) => continue,
                None => return None,
            }
        }
    }
}

fn main() {
    let it = (0..).zip("AB".chars());
    let foo = Foo::new(it);
    for v in foo {
        println!("{}", v);
    }
}

但是您不需要做任何这些来获得您想要的。您可以简单地创建一个 HashMap 并在迭代其他项目时检查它。我不小心创建了一个左外连接，但只需翻转参数即可获得右外连接。 ^_^

use std::collections::hash_map::HashMap;
use std::hash::Hash;

struct LeftOuterJoin<L, K, RV> {
    left: L,
    right: HashMap<K, RV>,
}

impl<L, K, RV> LeftOuterJoin<L, K, RV> 
    where K: Hash + Eq
{
    fn new<LI, RI>(left: LI, right: RI) -> Self
        where L: Iterator<Item=LI::Item>,
              LI: IntoIterator<IntoIter=L>,
              RI: IntoIterator<Item=(K, RV)>
    {
        LeftOuterJoin {
            left: left.into_iter(),
            right: right.into_iter().collect()
        }
    }
}

impl<L, K, LV, RV> Iterator for LeftOuterJoin<L, K, RV>
    where L: Iterator<Item=(K, LV)>,
          K: Hash + Eq,
          RV: Clone
{
    type Item = (K, LV, Option<RV>);

    fn next(&mut self) -> Option<Self::Item> {
        match self.left.next() {
            Some((k, lv)) => {
                let rv = self.right.get(&k);
                Some((k, lv, rv.cloned()))
            },
            None => None,
        }
    }
}

fn main() {
    let mut left = HashMap::new();
    left.insert(1, "Alice");
    left.insert(2, "Bob");

    let mut right = HashMap::new();
    right.insert(1, "Programmer");

    for (id, name, job) in LeftOuterJoin::new(left.into_iter(), right) {
        println!("{} ({}) is a {:?}", name, id, job);
    }
}