Recherche de la clé la plus adaptée & # 8221; pour une clé donnée dans un conteneur STL trié

Question

Problème

J'ai des données horodatées, que je dois rechercher en fonction de l'horodatage afin d'obtenir l'horodatage existant qui correspond à mon horodatage d'entrée le plus proche.
De préférence, cela devrait être résolu avec le STL. boost :: * ou stl :: tr1 :: * (à partir de VS9 avec Featurepack) sont également possibles.
Exemple de données horodatées:

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

Approche avec stl :: vector , sort () et equal_range ()

Etant donné qu'un map ou un set ne me permet que de trouver des correspondances exactes, je ne vais pas plus loin en utilisant l'un d'eux. Alors maintenant, j’ai un vecteur auquel j’ajoute des données au fur et à mesure de leur entrée. Avant de lancer la recherche, j’utilise < algorithme > pour sort () et fournissez-le avec une fonction de comparaison personnalisée.
Après cela, j’utilise le equal_range () de < algorithm > pour rechercher les deux voisins d’une valeur spécifiée x . À partir de ces deux valeurs, je vérifie laquelle est la plus proche de x , puis ma correspondance est la meilleure.

Bien que cela ne soit pas trop complexe, je me demande s’il existe des solutions plus élégantes à ce problème.
Peut-être que la STL a déjà un algorithme qui fait exactement cela, alors je ne réinvente pas quelque chose ici?

Mise à jour: recherche linéaire vs recherche binaire

J'ai oublié de mentionner que j'ai beaucoup de données à gérer, je ne souhaite donc pas avoir à effectuer de recherche linéaire.
La raison pour laquelle je trie un vecteur avec sort () est parce qu'il a des itérateurs à accès aléatoire, ce qui n'est pas le cas avec une carte . L'utilisation d'une map n'autorise pas equal_range () à effectuer une recherche avec une complexité deux fois logarithmique.
Est-ce que j'ai raison?

Answer 1

Je voudrais utiliser set :: lower_bound pour trouver la valeur correspondante ou supérieure, puis décrémenter l'itérateur pour vérifier la valeur inférieure suivante. Vous devez utiliser std :: set plutôt que std :: map car votre clé est incorporée à l'objet. Vous devrez fournir un foncteur comparant les membres de l'horodatage.

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

Je voudrais aussi utiliser equal_range pour une telle chose.

Si vous utilisez sort () à chaque fois sur votre vecteur, il pourrait être préférable d'utiliser une carte (ou un ensemble), car celle-ci est toujours triée automatiquement, et utilisez le membre equal_range

Mais cela dépend de la quantité d'insertions / requêtes / quantité de données. (bien que pour quelque chose qui doit toujours être trié quand je demande, une carte serait mon premier choix, et je n'utiliserais un vecteur que s'il y avait une très bonne raison)

Answer 3

En fonction de votre utilisation, vous pouvez effectuer une recherche linéaire simple au lieu d’un tri. Fournissez une "distance". fonction, boucle en gardant une trace de la meilleure correspondance à ce jour, et sa distance. Lorsque vous trouvez une meilleure correspondance, oubliez la précédente et gardez la nouvelle et sa distance. Lorsque vous avez tout parcouru, vous avez votre correspondance.

Cela correspond à O (N * S), où N représente le nombre d'éléments dans le vecteur et S le nombre de recherches.

Votre méthode actuelle est O ((N + S) * LogN), ce qui est supérieur si le nombre de recherches est petit et limité. Sinon, la recherche tri / binaire est préférable.

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