在已排序的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()接近

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

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

更新：线性与二进制搜索

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

Answer 1

我会使用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;
}

Answer 2

对于这样的事情，我也会使用equal_range。

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

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

Answer 3

根据您的使用情况，您可以进行简单的线性搜索而不是排序。提出一个“距离”功能，循环跟踪目前为止的最佳匹配及其距离。当你找到更好的匹配时，忘记前一个，并保持新的和它的距离。当你完成所有事情时，你就得到了你的匹配。

这可以是O（N * S），其中N是向量中的项目数，S是搜索数。

您当前的方式是O（（N + S）* LogN），如果搜索的数量很小且有界，则更大。否则排序/二进制搜索更好。

Answer 4

//the function should return the element from iArr which has the least distance from input
double nearestValue(vector<double> iArr, double input)
{
    double pivot(0),temp(0),index(0);
    pivot = abs(iArr[0]-input);
    for(int m=1;m<iArr.size();m++)
    {           
        temp = abs(iArr[m]-input);

        if(temp<pivot)
        {
            pivot = temp;
            index = m;
        }
    }

    return iArr[index];
}

void main()
{
    vector<double> iArr;

    srand(time(NULL));
    for(int m=0;m<10;m++)
    {
        iArr.push_back(rand()%20);
        cout<<iArr[m]<<" ";
    }

    cout<<"\nnearest value is: "<<lib.nearestValue(iArr,16)<<"\n";
}