在一次搜索中查找 BTreeSet 中的较大键和较小键

Question

我希望能够在 Rust 中找到BTreeSet严格低于和大于指定键的键。

例如，给定集合{ "1", "3" }，并且搜索关键字是，"2"那么答案应该是（"1", "3"）。在不存在较低值或较大值的情况下，None应返回。

range()我可以通过两次调用该方法来实现我正在寻找的结果BTreeSet。

有没有一种方法可以使用单个搜索来完成此操作，就像 C++ 中那样？C++std::set有一个双向迭代器：

// $CXX -std=c++17 less-than.c++ -o less-than && ./less-than

#include <cassert>
#include <optional>
#include <set>
#include <string>
#include <iostream>

using std::optional;
using std::pair;
using std::set;
using std::string;

pair<optional<string>, optional<string>> bounding_box(
    const set<string>& space,
    const string& point)
{
    if (space.empty()) { return {}; }

    optional<string> gt_bound;
    optional<string> lt_bound;

    const auto ge_bound_it = space.lower_bound(point);

    if (ge_bound_it != space.end()) {
        if (*ge_bound_it == point) {
            // lower_bound returned an equal point, use the next one
            // if it exists
            const auto gt_bound_it = std::next(ge_bound_it, 1);

            if (gt_bound_it != space.end()) {
                gt_bound = *gt_bound_it;
            }
        } else {
            gt_bound = *ge_bound_it;
        }

    }

    if (ge_bound_it != space.begin()) {
        lt_bound = *std::next(ge_bound_it, -1);
    }

    return {lt_bound, gt_bound};
}

int main() {
    {
        const auto box = bounding_box({"1", "3"}, "2");
        assert(box.first);
        assert(*box.first == "1");

        assert(box.second);
        assert(*box.second == "3");
    }

    {
        const auto box = bounding_box({"1", "3"}, "4");
        assert(box.first);
        assert(*box.first == "3");

        assert(!box.second);
    }

    {
        const auto box = bounding_box({"1", "3"}, "0");
        assert(!box.first);

        assert(box.second);
        assert(*box.second == "1");
    }

    {
        const auto box = bounding_box({"3", "3"}, "3");
        assert(!box.first);
        assert(!box.second);
    }

    {
        const auto box = bounding_box({"3", "4"}, "3");
        assert(!box.first);
        assert(box.second);
        assert(*box.second == "4");
    }

    {
        const auto box = bounding_box({}, "3");
        assert(!box.first);
        assert(!box.second);
    }
}

这个search方法有点热点，我想知道 Rust 中是否有一种惯用的方法来做到这一点。

Answer 1

不，没有办法在一次搜索中做到这一点；你需要打电话range两次。

已经有关于增强BTreeMap/BTreeSet拥有“光标”API 的讨论。最近，为此提出了一个拉取请求，但它被关闭了，因为人们认为应该对这样的 API 应该如何外观和工作进行更多讨论。

也许您会成为带头讨论此类 API 的人？

也可以看看：

• 如何获取 Rust BTreeSet 中元素的下界和上限？