在已排序的STL容器中查找给定键的"最佳匹配键"

Question

问题

我有时间戳数据,我需要根据时间戳进行搜索,以获得与我最接近的输入时间戳匹配的现有时间戳.
优选地,这应该用STL解决.boost ::*或stl :: tr1 ::*(来自带有Featurepack的VS9)也是可能的.
带时间戳的数据示例:

struct STimestampedData
{
 time_t m_timestamp; // Sorting criterion
 CData m_data;       // Payload
}

接近stl::vector,sort()和equal_range()

既然a map或者set只允许我找到完全匹配,我就不会再使用其中一种了.所以现在我有一个我vector在其中添加数据的地方.在搜索之前我使用<algorithm>'s sort()并为它提供自定义比较功能.
之后我用<algorithm>'s equal_range()来查找指定值的两个邻居x.从这两个值我检查哪一个最接近x,然后我有我最好的匹配.

虽然这不是太复杂,但我想知道是否有更优雅的解决方案.
也许STL已经有了一个完全正确的算法,所以我不会在这里重新发明一些东西？

更新:线性与二进制搜索

我忘了提到我有很多数据要处理,所以我不想要线性搜索.
我正在对向量进行排序的原因sort()是因为它具有随机访问迭代器,而不是a的情况map.使用a map将不允许equal_range()以两次对数复杂度进行搜索.
我对么？

Answer 1

对于这样的事情,我也会使用equal_range.

如果你每次在vector上使用sort(),最好使用map(或set),因为它总是自动排序,并使用成员equal_range

但这取决于插入/查询/数据量.(虽然在我查询时总是需要排序的东西,地图将是我的第一选择,如果有一个很好的理由我只会使用矢量)

Answer 2

我会使用set :: lower_bound来查找匹配或更大的值,然后递减迭代器以检查下一个较低的值.您应该使用std :: set而不是std :: map,因为您的密钥嵌入在对象中 - 您需要提供一个比较时间戳成员的仿函数.

struct TimestampCompare
{
    bool operator()(const STimestampedData & left, const STimestampedData & right) const
    {
        return left.m_timestamp < right.m_timestamp;
    }
};
typedef std::set<STimestampedData,TimestampCompare> TimestampedDataSet;

TimestampedDataSet::iterator FindClosest(TimestampedDataSet & data, STimestampedData & searchkey)
{
    if (data.empty())
        return data.end();
    TimestampedDataSet::iterator upper = data.lower_bound(searchkey);
    if (upper == data.end())
        return --upper;
    if (upper == data.begin() || upper->m_timestamp == searchkey.m_timestamp)
        return upper;
    TimestampedDataSet::iterator lower = upper;
    --lower;
    if ((searchkey.m_timestamp - lower->m_timestamp) < (upper->m_timestamp - searchkey.m_timestamp))
        return lower;
    return upper;
}