我有一个这样的容器:
// Sort functor
struct SortByTime :
std::binary_function<const TimeSortableData &, const TimeSortableData &, bool>
{
bool operator()(const TimeSortableData & a, const TimeSortableData & b) const
{
return a.GetTime() < b.GetTime();
}
};
// Container that sorts by time
typedef std::multiset<TimeSortableData, SortByTime> TimeSortedData;
现在,如果我想在 time 之前获取最后一个数据对象t
,我可以创建一个虚拟对象并调用upper_bound()
:
TimeSortableData dummy(t);
TimeSortedData::const_iterator it = mySortedData.upper_bound(dummy);
--it;
// result = *it;
这给了我对数搜索的复杂性。
除了看起来笨拙之外,如果这样的虚拟对象很难创建(不是运行时性能,而是编码工作),这种方法是有问题的。
我看过std::multiset::key_comp
但我不知道如何使用它。
两者都std::multiset::find()
希望std::binary_search()
我给他们容器key_type
,即TimeSortableData
对象...
如何在无需创建虚拟对象的情况下进行有效搜索?
评论更新:
还有find_if()
:它可以让我省去创建虚拟对象的工作,但代价是 O(n) 复杂性。