collections - 在单个搜索中查找 BTreeSet 中更大和更低的键

Question

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

例如，给定集合 { "1", "3"}，搜索关键字是 "2" 那么答案应该是 ( “1”，“3”)。在不存在更低或更高值的情况下，应返回 None。

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

有没有一种方法可以像 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

不，没有办法在一次搜索中做到这一点； you need to call range twice .

关于增强 BTreeMap/BTreeSet 以拥有“游标”API 的讨论已经展开。最近，a pull request was opened to do so ，但它已关闭，因为人们认为应该就此类 API 的外观和工作方式进行更多讨论。

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

另见:

• How to get the lower bound and upper bound of an element in Rust BTreeSet?