Réponse à la question

Histoire de la question

Avant C++20, le calcul de la moyenne arithmétique de deux entiers ou pointeurs nécessitait une implémentation manuelle, généralement via l'expression naïve (a + b) / 2. Cependant, cette approche invoque un comportement indéfini lorsque la somme dépasse la valeur maximale représentable par le type. std::midpoint a été normalisé dans C++20 au sein de l'en-tête <numeric> pour fournir une solution portable, constexpr et noexcept qui garantit des résultats corrects dans l'ensemble du domaine des types d'entiers et de pointeurs sans déclencher de dépassement d'entier signé.

Le problème

Le dépassement d'entier signé est un comportement indéfini en C++, même avec le mandat de complément à deux de C++20. Lors de la moyenne de deux grands entiers signés positifs (par exemple, proches de INT_MAX), leur somme déborde. De même, pour deux grands entiers négatifs, la somme peut sous-déborder. Bien que l'arithmétique des pointeurs ait également un comportement indéfini lors du dépassement, la différence entre deux pointeurs dans le même tableau est garantie de s'inscrire dans std::ptrdiff_t, éliminant le risque de débordement présent dans l'addition d'entiers. Le défi consiste à mettre en œuvre un algorithme d'average pour les entiers qui évite le débordement inhérent à l'addition tout en maintenant la justesse pour les entrées à signe mixte.

La solution

Pour les entiers signés, std::midpoint évite le débordement en convertissant les opérandes en leurs équivalents non signés avant la soustraction. Il calcule la moyenne comme a - (unsigned_type(a) - b) / 2 lorsque a > b, ou l'équivalent symétrique sinon. Cela exploite l'arithmétique modulo bien définie des types non signés pour calculer la moitié de la distance entre les nombres sans jamais créer une valeur intermédiaire dont la magnitude dépasse les entrées. Pour les pointeurs, l'implémentation utilise simplement first + (last - first) / 2, car la différence (last - first) est bien définie et représentable, et la division par deux garantit que l'addition subséquente reste dans la plage valide du tableau.

#include <numeric>
#include <limits>
#include <iostream>

int main() {
    int a = std::numeric_limits<int>::max() - 10;
    int b = std::numeric_limits<int>::max() - 2;
    
    // int naive = (a + b) / 2; // Comportement indéfini : débordement
    int safe = std::midpoint(a, b); // Bien défini : retourne max - 6
    
    int arr[] = {1, 2, 3, 4, 5};
    int* mid = std::midpoint(&arr[0], &arr[4]); // Pointe vers arr[2]
}

Situation de la vie réelle

Description du problème

Dans une plateforme de trading à haute fréquence, le système devait calculer le milieu temporel entre deux horodatages de commandes représentés sous forme de std::int64_t nanosecondes depuis l'époque Unix. Lors des tests de résistance proches de l'ouverture du marché, lorsque les horodatages approchaient INT64_MAX, le calcul hérité (t1 + t2) / 2 provoquait des plantages intermittents en raison du dépassement d'entier signé, corrompant la logique de file d'attente de priorité du moteur de correspondance de commandes.

Différentes solutions envisagées

Solution 1 : Utiliser des types de précision étendue intégrés L'équipe a envisagé de convertir en __int128_t pour le calcul intermédiaire, puis de reconvertir. Cette approche garantissait une arithmétique correcte sur les compilateurs pris en charge (GCC, Clang, MSVC). Cependant, elle manquait de portabilité pour les cibles embarquées respectant strictement C++17 et introduisait des régressions de performances subtiles sur les architectures 32 bits où l'émulation 128 bits est coûteuse.

Solution 2 : Conversion arithmétique non signée La conversion des deux horodatages en std::uint64_t, la réalisation de la moyenne et le retour en arrière ont été proposés. Bien que cela évite le débordement pour des valeurs positives, cela produit des résultats définis par l'implémentation lorsqu'il s'agit d'horodatages historiques (valeurs négatives sous la représentation signée) car la conversion non signée de valeurs négatives donne de grandes magnitudes positives (retour arrière en complément à deux), rendant la moyenne mathématiquement incorrecte pour les calculs à travers zéro.

Solution 3 : Ramification manuelle avec vérifications de dépassement La mise en œuvre d'une fonction personnalisée vérifiant les signes des opérandes et utilisant conditionnellement a + (b - a)/2 ou des manipulations bit à bit a été envisagée. Cela fournissait une justesse mais ajoutait une surcharge de ramification et de complexité. Maintenir cette logique à travers plusieurs domaines numériques (coordonnées, prix, horodatages) violait le principe DRY et introduisait le risque d'erreurs de maintenance.

Solution 4 : Adopter C++20 std::midpoint La mise à niveau de la chaîne d'outils vers C++20 et l'utilisation de std::midpoint ont fourni une abstraction sans surcharge qui traitait correctement tous les cas limites, y compris les entrées à signe mixte et les valeurs proches des limites du domaine entier.

Solution choisie et résultat

L'équipe a sélectionné Solution 4, migrant la couche de calcul vers C++20. Ce changement a éliminé les plantages de dépassement en production, réduit le code de 200 lignes de utilitaires mathématiques sûrs personnalisés, et amélioré la localité du cache en supprimant la logique de ramification. Les tests de régression ont confirmé des performances identiques à l'approche naïve sur x86-64, avec l'avantage supplémentaire de l'évaluation constexpr pour des constantes à temps de compilation.

Ce que les candidats manquent souvent

Question 1 : Pourquoi la conversion d'entiers signés en types non signés est-elle insuffisante pour un calcul de milieu générique ?

Réponse Bien que l'arithmétique non signée se couvre modulo 2^N et évite le dépassement, convertir un entier signé négatif en non signé donne une grande valeur positive (par exemple, -1 devient UINT_MAX). Faire la moyenne d'un horodatage négatif et positif via l'arithmétique non signée donne un résultat proche du milieu de la plage non signée, pas la moyenne signée correcte. std::midpoint préserve le signe et arrondit correctement vers le premier argument lorsque la différence est impair, en gérant le bit de signe correctement sans dépendre du retour arrière non signé pour le résultat final.

Question 2 : Sous quelle contrainte spécifique du modèle d'objet l'std::midpoint pour les pointeurs invoque-t-il un comportement indéfini ?

Réponse std::midpoint nécessite que les deux pointeurs pointent vers des éléments du même objet tableau (ou un au-delà du dernier élément). Si les pointeurs se réfèrent à différents tableaux ou à de la mémoire non liée, le comportement est indéfini car l'expression last - first (utilisée en interne) est seulement définie pour des pointeurs à l'intérieur du même tableau. C'est une distinction subtile par rapport au midpoint entier ; les candidats supposent souvent que cela fonctionne comme une simple moyenne numérique et manquent les exigences strictes de l'aliasing et du modèle d'objet pour l'arithmétique des pointeurs.

Question 3 : Comment std::midpoint se comporte-t-il différemment pour les types à virgule flottante par rapport aux entiers, en particulier en ce qui concerne les valeurs NaN ?

Réponse Pour les types à virgule flottante, std::midpoint empêche le dépassement et le sous-dépassement dans la somme (qui pourraient produire une infinité ou un zéro incorrect) en utilisant une stratégie définie par l'implémentation, souvent équivalente à a/2 + b/2. Crucialement, si l'un des arguments est NaN, std::midpoint renvoie NaN. Si un argument est une infinité positive et l'autre une infinité négative, il renvoie NaN (indéterminé), tandis que le midpoint entier débordait simplement ou retournait. Les candidats supposent souvent qu'il effectue une simple arithmétique sans prendre en compte les règles de propagation des valeurs spéciales IEEE 754.