c ++中有范围图吗？

Question

在 c++ 中，unordered_map 和 map 是从映射中搜索键的好工具。

我可以建一个map，key是date，value是double（或者我自定义的struct）

但我想要一个范围映射，这意味着键是一个范围，例如：

#inlcude <map>
m[20190101] =3;
m[20201201] = 4.
cout << m[20200101]; // i want this can return me 3. because 20200101 is
// lower-close to 20190101

我该如何实现？

Answer 1

std::map 将数据存储在二叉树中，因此您可以轻松找到大于或等于 than/greater 的值的最接近键 upper_bound 和 lower_bound 方法

m.lower_bound(k): returns 指向第一个键不小于 k 的元素的迭代器，如果找不到这样的元素，则 m.end() 。
m.upper_bound(k)：returns 指向第一个键大于 k 的元素的迭代器，如果找不到这样的元素，则 m.end()。

然后您可以递减迭代器（如果它不等于 begin()）以找到下一个更小的元素。

所以对于你的例子：

auto it = m.upper_bound(20200101);
if (it != m.begin())
    std::cout << *--it;
else
    std::cout << "no key <= 20200101";

Answer 2

早在 2013/2014 年，我创建了一个 range_map 容器 class 模板，该模板模仿了 C++ 标准库的容器 class 模板。 range_map 的每个项目都存储在名为 range_map_item 的 class 模板中，该模板具有 3 个字段：左边界、右边界和存储的项目。（仅供参考，一切都在 beneficii 命名空间中。）它在很大程度上像 std::map 一样工作，但不会环绕它。我创建了自己的 rb-tree 来管理其内容。

范围的工作方式如下。每个键覆盖一个范围，如下所示：

[左绑定，右绑定)

意思是，左边界是范围的一部分，但右边界不是。

范围不能完全重叠，也就是说你不能有 2 个范围，这是正确的：

左 1 < 左 2 < 右 1 < 右 2

如果 2 个范围重叠，一个必须完全是另一个的子范围。

迭代器通过范围边界，而不是范围本身。它可以告诉您它当前是指向左边界还是右边界。

我已经用它做了很多测试。我已经能够创建 BMP 文件，该文件是通过迭代 range_map 并在其中放置随机范围并显示结果而创建的。好像基本能用，但我不能保证100%能用，而且我已经5年多没碰过它了。

它没有相关文档，但与它交互所需的函数的工作方式与对应的 C++ 标准库容器类似。我最常使用 emplace()。您可以只将左边界、右边界和项目传递给它。（仅供参考，“encaps”参数用于确定是否要封装预先存在的项目，如果这些项目恰好是您想要 enter/create 的项目的子范围。）您也可以在 emplace() 上使用分段构造. （多亏了我在网上找到的一个博客，它教会了我如何设置它。）

这是去图书馆的link。您应该将它保存在“beneficii”子文件夹中，并将该子文件夹放在您的包含目录或项目目录或其他目录中。编译器可以在何处搜索包含文件。该库是 header-only，因此没有 linking 问题。

这里是link下载地址：

https://drive.google.com/file/d/1SlBvIqnXwfJfsWv6yJsTm9SfutVok21U/view?usp=sharing

c ++中有范围图吗？

is there range map in c++?

c++

stl

unordered-map