gpt4 book ai didi

c++ - 如何在不构造 key_type 对象的情况下在 std::multiset 中进行二进制搜索?

转载 作者:行者123 更新时间:2023-11-28 01:10:19 28 4
gpt4 key购买 nike

我有一个这样的容器:

// 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) 的复杂性。

最佳答案

我想如果您的 key 的构建成本如此之高以至于您担心创建一个临时的虚拟 key ,您可以随时更改您的代码以使用 std::multimap 代替。让 key 是构造成本较低的东西,例如整数或 time_tGetTime() 返回的任何内容,然后 data_type 可以是更大的数据。

typedef std::multimap<time_t, TimeSortableData> TimeSortedData;
TimeSortedData mySortedData;

...

time_t dummy = [whatever];
TimeSortedData::const_iterator it = mySortedData.upper_bound(dummy);
if (it != mySortedData.begin()) --it; // Check that iterator isn't at beginning
result = it->second;

关于c++ - 如何在不构造 key_type 对象的情况下在 std::multiset 中进行二进制搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3772640/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com