0

我有一个这样的容器：

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

4

1 回答 1

3

我想如果您的密钥构建成本太高以至于您担心创建临时虚拟密钥，您可以随时更改代码以使用 anstd::multimap代替。让键是构造成本低的东西，例如整数或time_t任何GetTime()返回值，然后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;
于 2010-09-22T18:59:49.027 回答