'std:: list:: sort ()` - pourquoi le passage soudain à la stratégie top-down?

update - VS2015 introduit les allocateurs non-par défaut constructibles et stateful, ce qui pose un problème lors de l'utilisation de listes locales comme cela a été fait avec l'approche ascendante antérieure. J'ai pu gérer ce problème en utilisant des pointeurs de noeuds au lieu de listes (voir ci-dessous) pour une approche ascendante.

Dans @sbi commentaire, il a demandé à l'auteur de haut en bas de l'approche, Stephan T. Lavavej, pourquoi le changement a été fait. La réponse de Stephan était "pour éviter la mémoire allocation par défaut et la construction d'allocateurs". La nouvelle approche descendante est plus lente que l'ancienne approche ascendante, mais elle n'utilise que des itérateurs (stockés de façon récursive sur la pile), n'utilise pas de listes locales et évite les problèmes liés aux allocateurs non-par défaut-constructibles ou stateful. La réponse de @T. C. va dans le détail à ce sujet.

en ce qui concerne la performance, s'il y a assez de mémoire, il serait généralement plus rapide de déplacer la liste vers un tableau ou un vecteur, trier, puis déplacer le trié tableau ou vecteur retour à la liste.

je suis capable de reproduire le problème (l'ancien sort ne compile pas, le nouveau fonctionne) basé sur une démo de @IgorTandetnik:

#include <iostream>
#include <list>
#include <memory>

template <typename T>
class MyAlloc : public std::allocator<T> {
public:
    MyAlloc(T) {}  // suppress default constructor

    template <typename U>
    MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {}

    template< class U > struct rebind { typedef MyAlloc<U> other; };
};

int main()
{
    std::list<int, MyAlloc<int>> l(MyAlloc<int>(0));
    l.push_back(3);
    l.push_back(0);
    l.push_back(2);
    l.push_back(1);
    l.sort();
    return 0;
}

---

j'ai remarqué ce changement en juillet 2016 et j'ai envoyé un courriel à P. J. Plauger au sujet de ce changement le 1er août 2016. Un extrait de sa réponse:

fait intéressant, notre registre des changements ne reflète pas ce changement. Que probablement signifie qu'il a été "suggéré" par l'un de nos plus grands clients et suis je sur la révision du code. Tout ce que je sais maintenant, c'est que le changement est venu vers l'automne 2015. Quand j'ai revu le code, le premier ce qui m'a frappé, c'est la ligne:

    iterator _Mid = _STD next(_First, _Size / 2);

qui, bien sûr, peut prendre un très longtemps pour une grande liste.

le code semble un peu plus élégant que ce que j'ai écrit au début de 1995(!), mais a certainement pire complexité temporelle. Cette version a été modélisée après L'approche par Stepanov, Lee, et Musser dans le STL original. Ils se trompent rarement dans le choix de leurs algorithmes.

je retourne maintenant à notre dernière bonne version connue du code original.

Je ne sais pas si le retour de P. J. Plauger au code original a traité la question du Nouvel allocateur, ou si ou comment Microsoft interagit avec Dinkumware.

pour une comparaison des méthodes du haut vers le bas par rapport aux méthodes du bas vers le haut, j'ai créé une liste liée avec 4 millions d'éléments, chacun consistant en un entier de 64 bits non signé, en supposant que je finirais par avoir une liste doublement liée de noeuds presque séquentiellement ordonnés (même s'ils seraient alloués dynamiquement), les rempli avec des nombres aléatoires, puis les triés. Les noeuds ne bougent pas, seul le lien est modifié, mais maintenant la traversée de la liste accède aux noeuds dans l'ordre aléatoire. J'ai ensuite rempli ces les noeuds ordonnés au hasard avec un autre ensemble de nombres aléatoires et les triés de nouveau. J'ai comparé l'approche descendante de 2015 avec l'approche ascendante antérieure modifiée pour correspondre aux autres changements apportés pour 2015 (sort() appelle maintenant sort() avec une fonction de comparaison prédicative, plutôt que d'avoir deux fonctions distinctes). Ce sont les résultats. mise à jour - j'ai ajouté une version basée sur le pointeur de noeud et j'ai aussi noté le temps pour simplement créer un vecteur à partir de la liste, le vecteur de tri, recopie.

sequential nodes: 2015 version 1.6 seconds, prior version 1.5  seconds
random nodes:     2015 version 4.0 seconds, prior version 2.8  seconds
random nodes:                  node pointer based version 2.6  seconds
random nodes:    create vector from list, sort, copy back 1.25 seconds

pour les noeuds séquentiels, la version précédente est seulement un peu plus rapide, mais pour les noeuds aléatoires, la version précédente est 30% plus rapide, et la version de pointeur de noeud 35% plus rapide, et la création d'un vecteur à partir de la liste, le tri du vecteur, puis la copie de retour est 69% plus rapide.

ci-dessous est le premier code de remplacement pour std:: list:: sort() j'ai utilisé pour comparer la méthode antérieure de bas en haut avec un petit tableau (_binlist[]) par rapport à l'approche descendante de VS2015 je voulais le la comparaison, pour être juste, j'ai donc modifié une copie de < liste >.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        if (2 > this->_Mysize())
            return;
        const size_t _MAXBINS = 25;
        _Myt _Templist, _Binlist[_MAXBINS];
        while (!empty())
            {
            // _Templist = next element
            _Templist._Splice_same(_Templist.begin(), *this, begin(),
                ++begin(), 1);
            // merge with array of ever larger bins
            size_t _Bin;
            for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty();
                ++_Bin)
                _Templist.merge(_Binlist[_Bin], _Pred);
            // don't go past end of array
            if (_Bin == _MAXBINS)
                _Bin--;
            // update bin with merged list, empty _Templist
            _Binlist[_Bin].swap(_Templist);
            }
            // merge bins back into caller's list
            for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++)
                if(!_Binlist[_Bin].empty())
                    this->merge(_Binlist[_Bin], _Pred);
        }

j'ai fait quelques changements mineurs. Le code original gardait la trace du maximum réel bin dans une variable nommée _Maxbin, mais le overhead dans la fusion finale est assez petit que j'ai enlevé le code associé à _Maxbin. Pendant la construction du tableau, la boucle interne du code original a fusionné dans un élément _Binlist [], suivi d'un swap en _Templist, ce qui semblait inutile. J'ai changé la boucle interne pour fusionner dans _Templist, il n'y a échange que lorsqu'un élément _binlist[] vide est trouvé.

ci-dessous est un remplacement basé sur un pointeur de noeud pour std::list::sort() que j'ai utilisé pour une autre comparaison. Cela élimine les problèmes liés à la répartition. Si une exception de comparaison est possible et se produit, tous les noeuds dans le tableau et la liste de température (pNode) devraient être annexés de nouveau à la liste originale, ou peut-être une exception de comparaison pourrait être traitée comme un moins que comparer.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        const size_t _NUMBINS = 25;
        _Nodeptr aList[_NUMBINS];           // array of lists
        _Nodeptr pNode;
        _Nodeptr pNext;
        _Nodeptr pPrev;
        if (this->size() < 2)               // return if nothing to do
            return;
        this->_Myhead()->_Prev->_Next = 0;  // set last node ->_Next = 0
        pNode = this->_Myhead()->_Next;     // set ptr to start of list
        size_t i;
        for (i = 0; i < _NUMBINS; i++)      // zero array
            aList[i] = 0;
        while (pNode != 0)                  // merge nodes into array
            {
            pNext = pNode->_Next;
            pNode->_Next = 0;
            for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++)
                {
                pNode = _MergeN(_Pred, aList[i], pNode);
                aList[i] = 0;
                }
            if (i == _NUMBINS)
                i--;
            aList[i] = pNode;
            pNode = pNext;
            }
        pNode = 0;                          // merge array into one list
        for (i = 0; i < _NUMBINS; i++)
            pNode = _MergeN(_Pred, aList[i], pNode);
        this->_Myhead()->_Next = pNode;     // update sentinel node links
        pPrev = this->_Myhead();            //  and _Prev pointers
        while (pNode)
            {
            pNode->_Prev = pPrev;
            pPrev = pNode;
            pNode = pNode->_Next;
            }
        pPrev->_Next = this->_Myhead();
        this->_Myhead()->_Prev = pPrev;
        }

    template<class _Pr2>
        _Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2)
        {
        _Nodeptr pDst = 0;          // destination head ptr
        _Nodeptr *ppDst = &pDst;    // ptr to head or prev->_Next
        if (pSrc1 == 0)
            return pSrc2;
        if (pSrc2 == 0)
            return pSrc1;
        while (1)
            {
            if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval))
                {
                *ppDst = pSrc2;
                pSrc2 = *(ppDst = &pSrc2->_Next);
                if (pSrc2 == 0)
                    {
                    *ppDst = pSrc1;
                    break;
                    }
                }
            else
                {
                *ppDst = pSrc1;
                pSrc1 = *(ppDst = &pSrc1->_Next);
                if (pSrc1 == 0)
                    {
                    *ppDst = pSrc2;
                    break;
                    }
                }
            }
        return pDst;
        }

comme alternative à la nouvelle VS2015 std::list: sort(), vous pouvez utiliser cette version autonome.

template <typename T>
void listsort(std::list <T> &dll)
{
    const size_t NUMLISTS = 32;
    std::list <T> al[NUMLISTS]; // array of lists
    std::list <T> tl;           // temp list
    while (!dll.empty()){
        // t1 = next element from dll
        tl.splice(tl.begin(), dll, dll.begin(), std::next(dll.begin()));
        // merge element into array
        size_t i;
        for (i = 0; i < NUMLISTS && !al[i].empty(); i++){
            tl.merge(al[i], std::less<T>());
        }
        if(i == NUMLISTS)       // don't go past end of array
            i -= 1;
        al[i].swap(tl);         // update array list, empty tl
    }
    // merge array back into original list
    for(size_t i = 0; i < NUMLISTS; i++)
        dll.merge(al[i], std::less<T>());
}

ou utilisez l'algorithme similaire gcc.