如何在 std::multiset 中进行二分搜索而不构造 key_type 对象?
我有一个像这样的容器:
// 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;
现在,如果我想获取时间 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) 复杂度。
I have a container like this:
// 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;
Now if I want to get the last data object before time t
, I could create a dummy object and call upper_bound()
:
TimeSortableData dummy(t);
TimeSortedData::const_iterator it = mySortedData.upper_bound(dummy);
--it;
// result = *it;
This gives me logarithmic search complexity.
Aside from looking clumsy, this approach is problematic if such a dummy object is very hard to create (not wrt. run-time performance but coding effort).
I've looked at std::multiset::key_comp
but I don't see how I could use it..
Both std::multiset::find()
and std::binary_search()
want me to give them the container's key_type
, i.e. TimeSortableData
objects...
How can I search eficiently without having to create a dummy object?
Update from comments:
There is also find_if()
: It would spare me the effort of creating a dummy object but at the price of O(n) complexity.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
我想,如果您的密钥构建起来非常昂贵,以至于您担心创建临时虚拟密钥,那么您可以随时更改代码以使用
std::multimap
代替。让键是构造起来很简单的东西,例如整数或 time_t 或任何GetTime()
返回的内容,然后data_type
可以是更大的数据。I suppose that if your keys are so expensive to construct that you worry about creating a temporary dummy key, you can always change your code to use an
std::multimap
instead. Let the key be something cheap to construct, such as an integer ortime_t
or whateverGetTime()
returns, and then thedata_type
could be the larger data.