collections - 一次搜索即可找到BTreeSet中的上下键

我希望能够在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中是否有惯用的方法来做到这一点。

最佳答案

不，无法通过单个搜索来执行此操作； you need to call range twice。

已经进行了有关增强BTreeMap/BTreeSet以具有“cursor” 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?