如何创建 BTreeSet 的子范围<(字符串、字符串、字符串)>？如何将边界元组转换为元组的边界？

Question

我正试图使用BTreeSet<(String, String, String)>来创建一个简单的内存"三重存储"。

准确地说：

type Entity = String;
type Attribute = String;
type Value = String;
type EAV = (Entity, Attribute, Value);
type EAVSet = BTreeSet<EAV>;

pub fn example_db() -> EAVSet {
let mut example: EAVSet = BTreeSet::new();
insert_strtup(&mut example, ("1", "type", "user"));
insert_strtup(&mut example, ("1", "user/name", "Arthur Dent"));
insert_strtup(&mut example, ("1", "user/age", "33"));
insert_strtup(&mut example, ("2", "type", "user"));
insert_strtup(&mut example, ("2", "user/name", "Ford Prefect"));
insert_strtup(&mut example, ("2", "user/age", "42"));
return example;
}

fn insert_strtup(db: &mut EAVSet, val: (&str, &str, &str)) -> () {
db.insert((val.0.to_string(), val.1.to_string(), val.2.to_string()));
}
pub fn example()  {
let db = example_db();
// How to customize this?
let range: (Bound<EAV>, Bound<EAV>) = (Bound::Unbounded, Bound::Unbounded);
for elem in eavt.range(range) {
println!("{:?}", elem);
}
}

我面临的问题是，我希望人们能够在集合中的一个子范围内迭代。然而，std::ops::Bound的简单用法是不可能的，因为我们存储了具有多个字段的元组。

我希望能够为以下所有内容构建范围查询：

• 所有实体
• ID在范围CCD_ 3中的所有实体
• 实体CCD_ 4的所有字段
• 实体1的"user/age"字段的当前值(

到目前为止，我们想到的唯一想法是使用一个字符串键，我们知道它是一个比较低响应的事实。高于我们为"占位符"字段寻找的值。但这感觉很粗糙/容易出错，就像重新发明轮子一样。

有没有办法把(Bound<String>, Bound<String>, Bound<String>)变成Bound<(String, String, String)>？或者这里还有其他方法吗？

编辑：在Rust中过滤/查询多关键字btree索引显示了一种解决方案，即将所有值包装在有序枚举(Min, Exact(String), Max(中，但该解决方案需要更改BTreeSet中存储的值类型。这也感觉像是增加了内存开销，因为我们实际上从来没有在里面存储Exact(some_string)以外的任何东西。是否有其他方法不需要更改存储在BTreeSet中的值的类型？

Answer 1

由于Borrow总是返回一个引用(grrrrrrrr(，而Borrowed不一定是Copy，因此您可能能够依赖于sentinel内存地址？

请注意，由于不允许使用关联的static项，因此您可能需要为要使用的每种类型提供此代码的副本。

use std::borrow::Borrow;
use std::cmp::Ordering;
#[repr(transparent)]
pub struct StringWithMinMaxSentinel(String);
// must be static, not const, to ensure a constant memory address
pub static STRING_MIN_SENTINEL: StringWithMinMaxSentinel = StringWithMinMaxSentinel(String::new());
pub static STRING_MAX_SENTINEL: StringWithMinMaxSentinel = StringWithMinMaxSentinel(String::new());
impl Borrow<StringWithMinMaxSentinel> for String {
fn borrow(self: &String) -> &StringWithMinMaxSentinel {
unsafe { &*(self as *const String as *const StringWithMinMaxSentinel) }
}
}
impl PartialEq for StringWithMinMaxSentinel {
fn eq(&self, other: &Self) -> bool {
std::ptr::eq(self, other) || (!std::ptr::eq(self, &STRING_MIN_SENTINEL) && !std::ptr::eq(other, &STRING_MAX_SENTINEL) && !std::ptr::eq(other, &STRING_MIN_SENTINEL) && !std::ptr::eq(self, &STRING_MAX_SENTINEL) && self.0.eq(&other.0))
}
}
impl Eq for StringWithMinMaxSentinel {}
impl PartialOrd for StringWithMinMaxSentinel {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for StringWithMinMaxSentinel {
fn cmp(&self, other: &Self) -> Ordering {
if std::ptr::eq(self, other) {
Ordering::Equal
} else if std::ptr::eq(self, &STRING_MIN_SENTINEL) || std::ptr::eq(other, &STRING_MAX_SENTINEL) {
Ordering::Less
} else if std::ptr::eq(self, &STRING_MAX_SENTINEL) || std::ptr::eq(other, &STRING_MIN_SENTINEL) {
Ordering::Greater
} else {
self.0.cmp(&other.0)
}
}
}

Answer 2

我希望能够为以下所有内容构建范围查询：

all entities;
all entities with an ID in range x..y;
all fields of entity 1;
the current value of entity 1's "user/age" field).

是否有一种[其他]方法不需要改变存储在BTreeSet中的值？

给定上述约束条件，以下操作有效。由于所有东西都是字符串，所以范围使用字符串比较，意思是"字符串"；a"b"；表示以"0"开头的所有字符串；a"；。空字符串是一个自然的最小字符串值，但没有现成的最大字符串值，因此我们使用一个大的静态字符串。这当然一点也不好。这可能可以通过使用Option而不是String来改进，None值代表最大值，Some("(将是最小值。然后你还必须实现自己的比较。。。

use std::collections::BTreeSet;
use std::ops::Bound;
type Entity = String;
type Attribute = String;
type Value = String;
type EAV = (Entity, Attribute, Value);
type EAVSet = BTreeSet<EAV>;
pub fn example_db() -> EAVSet {
let mut example: EAVSet = BTreeSet::new();
insert_strtup(&mut example, ("1", "type", "user"));
insert_strtup(&mut example, ("1", "user/name", "Arthur Dent"));
insert_strtup(&mut example, ("1", "user/age", "33"));
insert_strtup(&mut example, ("2", "type", "user"));
insert_strtup(&mut example, ("2", "user/name", "Ford Prefect"));
insert_strtup(&mut example, ("2", "user/age", "42"));
insert_strtup(&mut example, ("11", "type", "user"));
insert_strtup(&mut example, ("11", "user/name", "Arthur Dent"));
insert_strtup(&mut example, ("11", "user/age", "33"));
insert_strtup(&mut example, ("12", "type", "user"));
insert_strtup(&mut example, ("12", "user/name", "Ford Prefect"));
insert_strtup(&mut example, ("12", "user/age", "42"));
return example;
}
fn insert_strtup(db: &mut EAVSet, val: (&str, &str, &str)) -> () {
db.insert((val.0.to_string(), val.1.to_string(), val.2.to_string()));
}
static MAX_STRING: &str = "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ";
pub fn main() {
let db = example_db();
// How to customize this?
let range: (Bound<EAV>, Bound<EAV>) = (Bound::Unbounded, Bound::Unbounded);
for elem in db.range(range) {
println!("{:?}", elem);
}
println!("tall entities with an ID in range "11"..="12":");
let range = (
Bound::Included(("11".to_string(), "".to_string(), "".to_string())),
Bound::Excluded(("120".to_string(), "".to_string(), "".to_string())),
);
for elem in db.range(range) {
println!("{:?}", elem);
}
println!("tall fields of entity 1:");
let range = (
Bound::Included(("1".to_string(), "".to_string(), "".to_string())),
Bound::Excluded(("10".to_string(), "".to_string(), "".to_string())),
);

for elem in db.range(range) {
println!("{:?}", elem);
}
println!("tthe current value of entity 1's "user/age" field:");
let range = (
Bound::Included(("1".to_string(), "user/age".to_string(), "".to_string())),
Bound::Excluded(("1".to_string(), "user/age".to_string(), MAX_STRING.to_string())),
);

for elem in db.range(range) {
println!("{:?}", elem);
}
}