我有一个包含可排序数据类型的集合。我需要能够搜索到位于这个集合中两个未知点之间的所有元素。为了简单起见，我将使用一些伪代码来描述这一点。
set = {
(a, 0),
(a, 3),
(a, 8),
(b, 2),
(b, 5),
(c, 0)
}
实际上，我的代码实现如下
// This is highly simplified
template<typename A, typename B>
class overall_type {
public:
auto find(A min_a, A max_a) {
// Find all elements between (min_a, -oo) and (max_a, oo)
// How can I do this?
}
// A large number of other implementation details
private:
struct contained_type {
A data_a;
B data_b;
auto operator<(contained_type const& other) -> bool {
if (data_a < other.data_a) {
return true;
}
if (data_a > other.data_a) {
return false;
}
return data_b < other.data_b;
}
}
std::set<contained_type> internal_data;
}
我想查找范围(例如((b, -oo) <= e <= (b, oo)内的所有元素。由于我已经为我的数据类型实现了比较器，数据将按顺序放置在集合中，这意味着我只需要找到一个起点和一个终点。
我的问题是，我不能确定确切的起点是什么。在上面的例子中，最低的元素是(b, 1)，因此简单的find()操作是不够的。另一个限制是，我不知道数据中包含的任何类型元素的最小值，因为所有类型都是模板。相反，我需要能够使用不完整的数据进行搜索。
我也考虑过实现我自己的二进制搜索，但由于集合似乎不是随机访问的，所以在使用二进制搜索时我无法轻松做到这一点。
我考虑过的唯一替代方案是使用std::vector并在其上实现我自己的二进制搜索，并添加代码插入到正确的位置以保持其排序，然而，向量的隐藏意味着我无法满足项目最坏情况下的时间复杂性要求。
如果我忽略了一个明确的解决方案，我深表歉意——我所在的大学对STL的教学非常糟糕，所以可能有一个我根本没有听说过的数据结构，我的多次搜索都没有发现。
如何创建符合上述条件的解决方案？
也许是这样的。这依赖于std::set::equal_range等人在C++14中添加的执行异构搜索的能力，给定一个对不同类型的组合具有过载的比较器。
template<typename A, typename B>
class overall_type {
public:
auto find(A min_a, A max_a) {
return internal_data.equal_range(RangeCover{min_a, max_a});
}
private:
using contained_type = std::pair<A, B>;
struct RangeCover {
A& min_a;
A& max_a;
};
struct Compare {
using is_transparent = int;
bool operator()(contained_type const& l, contained_type const& r) const {
return l < r;
}
bool operator()(contained_type const& l, RangeCover const& r) const {
return l.first < r.min_a;
}
bool operator()(RangeCover const& l, contained_type const& r) const {
return l.max_a < r.first;
}
};
std::set<contained_type, Compare> internal_data;
};
演示
Compare使RangeCover的一个实例与具有该范围中第一个分量的contained_type的所有实例进行比较，忽略第二个分量。
如果有大量相等的data_a值，以下解决方案在性能上不是最优的，但它很简单，除了默认可构造之外，不需要任何特殊的类型B。如果添加透明比较以允许lower_bound()单独与A直接工作，那么它甚至不需要B是默认可构造的。
auto find(A min_a, A max_a) {
// Find all elements between (min_a, -oo) and (max_a, oo)
contained_type min_pair{min_a}; // data_b is default constructed
auto iter = internal_data.lower_bound(min_pair);
// linear search backward for true begin point
auto begin = iter;
for (; begin != internal_data.begin(); --begin) {
if (begin->data_a < min_a) {
++begin;
break;
}
}
// linear search forward for true end point
// [left as an exercise for the reader]
}