使用HashMap实现类似SQL的RIGHT OUTER JOIN的迭代器适配器 [英] An iterator adaptor implementing an SQL-like RIGHT OUTER JOIN using a HashMap
问题描述
我正在尝试扩展bluss的 rust-itertools 具有类似SQL的联接迭代器.我在使用哈希联接策略时遇到了RIGHT OUTER JOIN的特殊问题(该策略本身非常简单).
I'm trying to extend bluss's rust-itertools with SQL-like join iterators. I encountered a particular problem with RIGHT OUTER JOIN using a hash join strategy (the strategy itself is actually very simple).
迭代器适配器结构接受2个输入迭代器，其中第二个(右侧)被加载到HashMap中.迭代的工作方式如下:
The iterator adaptor struct takes 2 input iterators of which the second (the right) is loaded into the HashMap. The iteration works as follows:
- 左侧迭代器中的项目与地图匹配-如果匹配，则返回两个项目
- 左侧迭代器用尽后，从地图返回不匹配的值
问题是第二部分，我尝试将地图的Values迭代器与地图一起存储以存储其迭代状态.但是，正如我在此> ，因此不会生锈. 不幸的是，我不知道该怎么办.
The problem is with the second part where I tried to store the map's Values iterator along with the map to store its iteration state. But as I learned in this answer, it's not possible in rust. Unfortunately I have no idea how it could be done otherwise.
这是INNER JOIN适配器的完整代码，它完成了第一部分:
Here is the complete code for the INNER JOIN adaptor, which does the first part:
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,
}
}
}
}
我将不胜感激.
推荐答案
您无法存储Values迭代器，因为它包含对HashMap的引用.如果您移动地图，这些参考可能会失效.但是，您可以使用into_iter方法消费 HashMap.它拥有HashMap的所有值，并且可以移动到新结构中.
You cannot store the Values iterator because it contains references to the HashMap. These references could become invalid if you move the map. However, you can consume the HashMap using the into_iter method. That owns all the values of the HashMap and can be moved into a new struct.
这是前面问题中的代码调整.这还不是左联接或右联接.从使用一个迭代器完成到结束另一个迭代器的转换是很复杂的.
Here's a tweaking of your code from the earlier question. This isn't yet a left or right join. There's complexity about the switch from being done with one iterator to finishing off the other iterator.
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);
}
}
但是，您无需执行任何操作即可获得所需的内容.您可以简单地创建一个哈希图，并在迭代其他项时对其进行检查.我无意中创建了一个左外部联接，但是只需翻转参数即可获得一个右外部联接. ^ _ ^
However you don't need to do any of that to get what you want. You can simply create a hashmap and check it as you iterate over the other item. I accidentally created a left outer join, but just flip the arguments to get a right outer join. ^_^
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);
}
}
这篇关于使用HashMap实现类似SQL的RIGHT OUTER JOIN的迭代器适配器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
