Pourquoi le passage soudain à une stratégie descendante dans std::list::sort()?

Dans Visual Studio 2015 (VS2015), Microsoft a modifié la stratégie de tri de std::list::sort() du tri par fusion ascendant traditionnel à une approche descendante. Ce changement a éliminé l'utilisation d'un tableau interne de listes et a adopté des itérateurs pour suivre les limites d'exécution triées dans la liste d'origine.

Raisons du changement

Stephan T. Lavavej , le développeur de l'approche descendante, a cité la nécessité d'éviter l'allocation de mémoire et la construction d'allocateurs autres que ceux par défaut. VS2015 a introduit des allocateurs qui n'étaient plus constructibles et avec état par défaut, ce qui posait des problèmes lors de l'utilisation de l'approche ascendante précédente.

Mise en œuvre de l'approche descendante

Le haut -down utilise un algorithme récursif qui divise récursivement la liste en moitiés jusqu'à ce qu'elle atteigne des cas de base où les listes sont vides ou contiennent un seul élément. La fonction _Sort partitionne la liste en trois segments : l'exécution gauche, l'exécution droite et l'itérateur de fin. La logique de fusion est effectuée à l'aide de std::list::splice pour déplacer les nœuds dans la liste d'origine, en maintenant la sécurité des exceptions. Cette approche répond aux problèmes d'allocation de mémoire, mais elle s'accompagne d'une pénalité de performances par rapport au tri par fusion ascendant d'origine. Pour les grandes listes avec des nœuds dispersés, l’approche descendante souffre d’une augmentation des échecs de cache, ce qui entraîne des temps d’exécution plus lents. Dans de tels cas, il peut être plus rapide de déplacer la liste vers un tableau ou un vecteur, de la trier et de créer une nouvelle liste à partir du tableau ou du vecteur trié.