STL méthode "la plus proche"?

Question

Je cherche un tri STL qui renvoie l'élément "le plus proche" de la valeur cible si la valeur exacte n'est pas présente dans le conteneur. Il doit être rapide, donc essentiellement que je suis à la recherche d'une recherche binaire légèrement modifiée ... Je pourrais écrire, mais il semble que quelque chose qui devrait déjà exister ...

Answer 1

Voulez-vous dire les fonctions lower_bound/upper_bound ? Ceux-ci effectuent une recherche binaire et retournent l'élément le plus proche au-dessus de la valeur que vous recherchez. Clarification: Les versions globales de lower/upper_bound ne fonctionnent que si la gamme est triée, car elles utilisent une sorte de recherche binaire en interne. (Évidemment, les méthodes lower/upper_bound dans std :: map fonctionnent toujours). Vous avez dit dans votre question que vous cherchiez une sorte de recherche binaire, donc je suppose que la gamme est triée.

En outre, Ni le lower_bound ni le upper_bound ne renvoient le membre le plus proche. Si la valeur X que vous recherchez n'est pas un membre de la gamme, ils vont tous deux retourner le premier élément plus élevé que X. Sinon, lower_bound retournera la première valeur égale à X, upper_bound retournera la dernière valeur égale X.

Donc, pour trouver la valeur la plus proche, vous auriez à

• appel lower_bound
• si elle renvoie la fin de la plage, toutes les valeurs sont moins de X. Le dernier élément (c'est-à-dire le plus élevé) est le plus proche
• si elle renvoie le début de la plage, toutes les valeurs sont supérieures à X. Le premier élément (ie le plus bas) est le plus proche
• s'il renvoie un élément au milieu de la plage, vérifiez cet élément et l'élément précédent - celui qui est le plus proche de X est celui que vous cherchez

Answer 2

Vous recherchez donc un élément dont la distance minimale est de k?

Utilisez std::transform pour transformer chaque x en x-k. L'utilisation std::min_element avec une fonction de comparaison qui renvoie abs(l) < abs(r). Puis ajoutez k sur le résultat. EDIT: Vous pouvez également utiliser std::min_element avec une fonction de comparaison abs(l-k) < abs(r-k) et éliminer le std::transform.

EDIT2: Ceci est bon pour les conteneurs non triés. Pour les conteneurs triés, vous voulez probablement la réponse de Nikki.

Answer 3

Si vos données ne sont pas triées, utilisez std::min_element avec un foncteur de comparaison qui calcule votre distance.

Answer 4

Si le conteneur est déjà trié (comme le laisse entendre), vous devriez pouvoir utiliser std::upper_bound et l'élément directement avant de savoir qui est le plus proche:

// Untested. 
template <class Iter, class T> 
Iter closest_value(Iter begin, Iter end, T value) 
{ 
    Iter result = std::upper_bound(begin, end, value); 
    if(result != begin) 
    { 
     Iter lower_result = result; 
     --lower_result; 
     if(result == end || ((value - *lower_result) < (*result - value))) 
     { 
      result = lower_result; 
     } 
    } 

    return result; 
} 

Si le conteneur ne sont pas triées, utilisez min_element avec un prédicat comme déjà suggéré.