c – 在已排序的STL容器中查找给定键的“最佳匹配键”

发布时间：2020-12-16 04:56:56 所属栏目：百科来源：网络整理

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

问题

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

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

使用stl :: vector,sort()和equal_range()的方法

由于地图或集合只允许我找到完全匹配,我不会再使用其中一个.
所以现在我有一个向量附加数据的向量.在搜索之前我使用< algorithm>的sort()并为它提供自定义比较函数.
之后,我使用< algorithm>的equal_range()来查找指定值x的两个邻居.
从这两个值我检查哪一个最接近x然后我有我最好的匹配.

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

更新：线性与二进制搜索

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

解决方法

我会使用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)
{
    TimestampedDataSet::iterator upper = data.lower_bound(searchkey);
    if (upper == data.begin() || upper->m_timestamp == searchkey.m_timestamp)
        return upper;
    TimestampedDataSet::iterator lower = upper;
    --lower;
    if (upper == data.end() ||
            (searchkey.m_timestamp - lower->m_timestamp) < (upper->m_timestamp - searchkey.m_timestamp))
        return lower;
    return upper;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!