Trovare & # 8220; la chiave di corrispondenza migliore & # 8221; per una determinata chiave in un contenitore STL ordinato

Question

Problema

Ho dei dati di data e ora, che devo cercare in base alla data e ora per ottenere quella più esistente che corrisponde al mio timestamp di input il più vicino.
Preferibilmente questo dovrebbe essere risolto con l'STL. boost :: * o stl :: tr1 :: * (da VS9 con Featurepack) sono anche possibili.
Esempio di dati con data e ora:

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

Approccio con stl :: vector , sort () e equal_range()

Dal momento che una map o set mi consente solo di trovare corrispondenze esatte, non ne uso più una di queste. Quindi ora ho un vettore al quale aggiungo i dati non appena arrivano. Prima di cercare uso il sort () < algoritmo > > e fornire una funzione di confronto personalizzata.
Dopodiché utilizzo < algoritmo > equal_range () per trovare i due vicini di un valore specificato x . Da questi due valori controllo quale è il più vicino a x e quindi ho la mia corrispondenza migliore.

Anche se questo non è troppo complesso, mi chiedo se ci siano soluzioni più eleganti a questo.
Forse l'STL ha già un algoritmo che fa esattamente questo, quindi non sto reinventando qualcosa qui?

Aggiornamento: ricerca lineare o binaria

Ho dimenticato di menzionare che ho un sacco di dati da gestire, quindi non voglio cercare in modo lineare.
Il motivo per cui sto ordinando un vettore con sort () è perché ha iteratori ad accesso casuale che non è il caso di una map . L'uso di una map non consentirebbe a equal_range () di effettuare una ricerca con complessità logaritmica doppia.
Ho ragione?

Answer 1

Userei set :: lower_bound per trovare il valore corrispondente o maggiore, quindi decrementerei l'iteratore per verificare il valore inferiore successivo. Dovresti usare std :: set piuttosto che std :: map poiché la tua chiave è incorporata nell'oggetto - dovrai fornire un funzione che confronta i membri del timestamp.

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

Vorrei usare equal_range anche per una cosa del genere.

Se stai usando sort () ogni volta sul tuo vettore, potrebbe essere meglio usare una mappa (o set), dato che è sempre ordinata automaticamente, e usa il membro equal_range

Ma ciò dipende dalla quantità di inserimenti / query / quantità di dati. (anche se per qualcosa che deve sempre essere ordinato quando eseguo una query, una mappa sarebbe la mia prima scelta e utilizzerei un vettore solo se ci fosse un motivo molto valido)

Answer 3

A seconda dell'utilizzo, è possibile eseguire una semplice ricerca lineare anziché un ordinamento. Vieni con una "distanza" funzione, loop through per tenere traccia della migliore corrispondenza finora e la sua distanza. Quando trovi una corrispondenza migliore, dimentica la precedente e mantieni la nuova e la sua distanza. Quando hai passato in rassegna tutto, hai la tua corrispondenza.

Questo risulta essere O (N * S) dove N è il numero di elementi nel vettore e S è il numero di ricerche.

Il tuo modo attuale è O ((N + S) * LogN) che è maggiore se il numero di ricerche è piccolo e limitato. In caso contrario, la ricerca ordinamento / binario è migliore.

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