Comment faire une recherche binaire dans un multiset std :: sans construire un objet key_type?

Question

J'ai un récipient comme celui-ci:

// 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; 

Maintenant, si je veux obtenir le dernier objet de données avant que le temps t, je pourrais créer un objet factice et appelez upper_bound():

TimeSortableData dummy(t); 
TimeSortedData::const_iterator it = mySortedData.upper_bound(dummy); 
--it; 
// result = *it; 

Cela me donne complexité de recherche logarithmique.
En plus d'être maladroite, cette approche est problématique si un tel objet factice est très difficile à créer (par rapport aux performances d'exécution mais à l'effort de codage).

J'ai regardé std::multiset::key_comp mais je ne vois pas comment je pourrais l'utiliser ..
deux std::multiset::find() et std::binary_search() veux que je leur donne key_type, à savoir TimeSortableData objets ...

du conteneur Comment Je recherche efficacement sans avoir à créer un objet factice?

mise à jour des commentaires:
Il y a aussi find_if(): Il me épargner l'effort de créer un objet factice, mais au prix de O (n) complexité.

Answer 1

Je suppose que si vos clés sont si chères à construire que vous craignez de créer une clé factice temporaire, vous pouvez toujours changer votre code pour utiliser un std::multimap à la place. Laissez la clé être quelque chose de pas cher à construire, comme un entier ou time_t ou GetTime() renvoie, et puis le data_type pourrait être la plus grande des données.

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;