Как выполнить бинарный поиск в std :: multiset, не создавая объект key_type? - PullRequest
Новая
       62

Как выполнить бинарный поиск в std :: multiset, не создавая объект key_type?

0 голосов
/ 22 сентября 2010

У меня есть такой контейнер: 

// 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 objects ...

Как эффективно выполнять поиск без создания фиктивного объекта?

Обновление по комментариям:
Также имеется find_if():Это избавит меня от усилий по созданию фиктивного объекта, но за счет сложности O (n).

1 Ответ

3 голосов
/ 22 сентября 2010

Я полагаю, что если ваши ключи настолько дороги для создания, что вы беспокоитесь о создании временного фиктивного ключа, вы всегда можете изменить свой код, чтобы использовать вместо него std::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;
...