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_typeTimeSortableData

ダミー オブジェクトを作成せずに効率的に検索するにはどうすればよいですか?

コメントからの更新:
もあります:find_if()ダミー オブジェクトを作成する手間を省きますが、O(n) の複雑さを犠牲にします。

4

1 に答える 1

3

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 or time_t or whatever GetTime() returns, and then the data_type could be the larger data.

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 に答える