＆＃8220;最適なキーの検索＆＃8221;ソートされたSTLコンテナ内の特定のキーに対して

Question

問題

タイムスタンプ付きのデータがあり、入力タイムスタンプに最も近い既存のタイムスタンプを取得するために、タイムスタンプに基づいて検索する必要があります。
できればこれはSTLで解決する必要があります。 boost :: *またはstl :: tr1 :: *（VS9 with Featurepack）も可能です。
タイムスタンプ付きデータの例：

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

stl :: vector 、 sort（）、および equal_range（）

によるアプローチ

map または set では完全に一致するもののみを検索できるため、これらのいずれかを使用することはできません。 これで、入ってくるデータを追加する vector ができました。検索する前に、＆lt; algorithm＆gt; の sort（）カスタム比較関数を提供します。
その後、＆lt; algorithm＆gt; の equal_range（）を使用して、指定された値 x の2つの近傍を見つけます。 これら2つの値から、どちらが x に最も近いかを確認し、最適な一致を取得します。

これはそれほど複雑ではありませんが、よりエレガントな解決策があるのではないかと思います。
STLには既にそれを行うアルゴリズムが既にあるので、ここで何かを再発明するつもりはないのでしょうか。

更新：線形検索とバイナリ検索

処理するデータが非常に多いことを忘れていたので、直線的に検索する必要はありません。
sort（）でベクターをソートしているのは、 map には当てはまらないランダムアクセス反復子があるためです。 map を使用すると、 equal_range（）が2倍の対数複雑度で検索を実行できなくなります。
私は正しいですか？

Answer 1

set :: lower_boundを使用して一致する値以上の値を見つけ、イテレータをデクリメントして次に低い値をチェックします。キーはオブジェクトに埋め込まれているため、std :: mapではなくstd :: setを使用する必要があります。タイムスタンプメンバーを比較するファンクターを提供する必要があります。

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を使用します。

ベクターで毎回sort（）を使用している場合は、マップ（またはセット）を使用することをお勧めします。これは常に自動的にソートされ、メンバー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";
}