Verschieben von Elementen aus einem assoziativen Container

Question

Just for fun, habe ich den einfachsten Sortieralgorithmus vorstellbar implementiert:

template<typename Iterator> 
void treesort(Iterator begin, Iterator end) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type element_type; 

    // copy data into the tree 
    std::multiset<element_type> tree(begin, end); 

    // copy data out of the tree 
    std::copy(tree.begin(), tree.end(), begin); 
} 

für meine Testdaten Es ist nur etwa 20-mal langsamer als std::sort :)

Als nächstes ich wollte die Performance mit Bewegung Semantik verbessern:

template<typename Iterator> 
void treesort(Iterator begin, Iterator end) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type element_type; 

    // move data into the tree 
    std::multiset<element_type> tree(std::make_move_iterator(begin), 
            std::make_move_iterator(end)); 
    // move data out of the tree 
    std::move(tree.begin(), tree.end(), begin); 
} 

aber das hat keinen Einfluss auf die Leistung in signifikanter Weise, obwohl ich bin Sortierung std::string s.

Dann erinnerte ich mich, dass assoziative Container von außen konstant sind, das heißt, std::move und std::copy wird hier das gleiche tun :(Gibt es eine andere Möglichkeit, die Daten aus dem Baum zu bewegen?

Answer 1

std::set und std::multiset nur const Zugriff auf ihre Elemente.Das bedeutet, Sie können nicht etwas aus dem Satz verschieben.Wenn Sie Elemente verschieben können (oder sie überhaupt ändern), könnten Sie das Set durch Ändern der Sortierreihenfolge der Elemente brechen. Also verbietet C++ 11 das.

Also Ihr Versuch, die 0 zu verwendenAlgorithmus wird nur den Kopierkonstruktor aufrufen.

Answer 2

Ich glaube, Sie könnten einen benutzerdefinierten Zuordner für die multiset zu verwenden (3. Vorlage Argument), die tatsächlich die Elemente in der destroy Methode zurück in den Container des Benutzers bewegt. Dann lösche jedes Element in der Menge und während seiner Zerstörung sollte es deine Schnur zurück zum ursprünglichen Behälter bewegen. Ich denke, dass der benutzerdefinierte Zuordner 2-Phasen-Konstruktion haben müsste (übergeben Sie den Begin-Iterator an Ihre treesort-Funktion übergeben, um als Mitglied zu halten, aber nicht während der Konstruktion, weil es standardmäßig konstruierbar sein muss).

Offensichtlich wäre dies bizarr und ist eine alberne Problemumgehung für eine pop Methode im Set/Multiset. Aber es sollte möglich sein.

Answer 3

Ich mag Daves Idee eines freaky Zuordners, der sich an die Quelle jedes konstruierten Objektes erinnert und automatisch auf Zerstörung zurückgreift, daran hätte ich nie gedacht!

Aber hier ist eine Antwort näher zu Ihrem ursprünglichen Versuch:

template<typename Iterator> 
void treesort_mv(Iterator begin, Iterator end) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type element_type; 

    // move the elements to tmp storage 
    std::vector<element_type> tmp(std::make_move_iterator(begin), 
            std::make_move_iterator(end)); 
    // fill the tree with sorted references 
    typedef std::reference_wrapper<element_type> element_ref; 
    std::multiset<element_ref, std::less<element_type>> tree(tmp.begin(), tmp.end()); 

    // move data out of the vector, in sorted order 
    std::move(tree.begin(), tree.end(), begin); 
} 

Dies ist ein multiset von Referenzen sortiert, so brauchen sie nicht aus dem Baum zu bewegen.

Wenn Sie jedoch in den ursprünglichen Bereich zurückkehren, sind die Zuweisungszuweisungen nicht unbedingt sicher für die Selbstzuweisung, also habe ich sie zuerst in einen Vektor verschoben, so dass sie nicht wieder dem ursprünglichen Bereich zugewiesen werden Selbstzuweisungen.

Dies ist marginal schneller als Ihre ursprüngliche Version in meinen Tests. Es verliert wahrscheinlich an Effizienz, weil es sowohl den Vektor als auch alle Baumknoten zuordnen muss. Das und die Tatsache, dass mein Compiler COW-Zeichenketten verwendet, um sich zu bewegen, ist sowieso nicht viel schneller als das Kopieren.