我已经用C++编程好几年了，现在我已经在我的个人项目上工作了几个月。我不想和你分享细节，但我发现自己处于这样一种情况，即设计一些数据结构，使每个值都Map到一个唯一的、可变长度的区间或键值范围，这将是非常方便的。
因此，例如，调用一个具有区间[0，9）中任何键的函数将返回17，但是调用一个大于或等于9的键将返回另一个值，尽管在我的实际情况下，该值不一定是文字类型。类似于这样：
template <std::totally_ordered T>
struct Interval
{
T lower;
T upper;
};
template <std::totally_ordered KeyType, typename ValueType>
class IntervalTable
{
// Implementation here.
public:
ValueType& getValue(const KeyType& key);
};我可以想象有几种方法可以实现这一点，其中一些版本的数组或Map是最有可能的候选者，但我无法轻松地在网上找到已经存在的结构，我想知道是否有人知道一个众所周知的结构或解决方案，所以我不会花很多时间重新发明轮子。
2条答案
按热度按时间kyvafyod1#
你可以将你的间隔存储在
std::vector<std::pair<Interval<KeyType>, ValueType>>中，然后使用std::lower_bound来找到正确的间隔：Demo
添加健全性检查以避免重叠间隔，并确保
vector始终排序。ddrv8njm2#
Boost Interval Container Library或libinterval library-一种适用于您的用例的数据结构是区间树，因为它通过将数字行划分为区间并将这些区间存储在二叉搜索树中来工作。
在您的示例中，可以将键值对存储为间隔，每个间隔由Interval结构表示，就像您定义的那样。每个间隔的lower字段将是间隔的下限（包括），upper字段将是间隔的上限（不包括）。