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

Question

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

迭代器适配器结构体采用 2 个输入迭代器，其中第二个（右侧）被加载到 HashMap 中。迭代的工作原理如下：

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

问题在于第二部分，我尝试将地图的值迭代器与地图一起存储以存储其迭代状态。但正如我在这个答案中了解到的那样，这在铁锈中是不可能的。不幸的是我不知道如何才能做到这一点。

以下是 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. 如果您移动地图，这些参考可能会变得无效。但是，您可以使用该方法来HashMap使用into_iter。它拥有 的所有值，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);
    }
}

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

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);
    }
}