代码之家 › 专栏 › 技术社区 › foraidt

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

containers stl sorting c++

foraidt · 技术社区 · 17 年前

我有时间戳数据,我需要根据时间戳进行搜索,以获得与我的输入时间戳最接近的一个现有时间戳。
最好用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> 的并为其提供自定义比较函数。
之后我用 <算法> 的 等距 查找指定值的两个邻居 x 从这两个值中,我检查哪一个最接近然后我有了我最好的对手。

也许STL已经有了一个算法可以做到这一点,所以我没有在这里重新发明什么?

更新:线性与二进制搜索

我忘了提到我有很多数据要处理,所以我不想线性搜索。
我之所以用 排序() 这是因为它具有随机访问迭代器,而对于 地图 不允许 等距 以两倍对数复杂度进行搜索。

4 回复 | 直到 17 年前

Pieter 17 年前

对于这样的事情,我也会使用等距。

如果每次对向量使用sort(),最好使用映射(或集合),因为它总是自动排序,并使用成员equal_范围

但这取决于插入/查询/数据量。(尽管对于我查询时总是需要排序的东西,地图是我的第一选择,只有在有充分理由的情况下,我才会使用向量)

Mark Ransom 7 年前

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

Salman A 17 年前

根据您的用途,您可以进行简单的线性搜索,而不是排序。提出一个“距离”函数,循环跟踪到目前为止的最佳匹配及其距离。当你找到一个更好的匹配,忘记前一个,保持新的和它的距离。当你完成了所有的循环,你就拥有了你的对手。

这就是O(N*S),其中N是向量中的项数,S是搜索数。

您当前的方式是O((N+S)*LogN),如果搜索数量较小且有界,则该方式会更大。否则,排序/二进制搜索更好。

Waqas 15 年前

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

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

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

更新:线性与二进制搜索

`stl::vector` , `sort()` 和 `equal_range()`