Ruchome elementy spośród asocjacyjną kontenera

Question

Tak dla zabawy, mam wdrożony algorytm Najprostszym sortowania można sobie wyobrazić:

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); 
} 

To tylko około 20 razy wolniej niż std::sort na przetwarzanie moich danych testu :)

Następny, chciałem poprawić wydajność z semantyki ruch:

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); 
} 

Ale to nie miało wpływu na wydajność w znaczący sposób, chociaż jestem sortowanie std::string s.

Wtedy przypomniałem sobie, że kontenery asocjacyjne są stałe z zewnątrz, czyli std::move i std::copy zrobi to samo tutaj :(Czy jest jakiś inny sposób, aby przenieść dane z drzewa?

Answer 1

std::set i std::multiset zapewniają tylko dostęp do ich elementów, co oznacza, że ​​nie można przenieść czegoś z zestawu.Jeśli można przenieść elementy (lub zmodyfikować je w ogóle), można złamać zestaw, zmieniając kolejność sortowania elementów. Więc C++ 11 zabrania tego:

Twoja próba użycia 0 Algorytmpo prostu wywoła konstruktor kopiowania.

Answer 2

Wydaje mi się, że można wykonać niestandardowy przydział dla użytkownika multiset do użycia (trzeci argument szablonu), który faktycznie przenosi elementy z jego metody destroy z powrotem do kontenera użytkownika. Następnie usuń każdy element z zestawu, a podczas jego niszczenia powinien przenieść twój ciąg z powrotem do oryginalnego pojemnika. Myślę, że niestandardowy alokator musiałby mieć konstrukcję dwufazową (przekazać iteratorowi przekazanemu do funkcji treesort jako element członkowski, ale nie podczas konstrukcji, ponieważ musi być domyślnie skonstruowany).

Oczywiście byłoby to dziwaczne i niemądre obejście dla braku metody pop w zestawie/multiset. Ale powinno być możliwe.

Answer 3

Podoba mi się pomysł Dave'a na dziwaczny przydział, który pamięta źródło każdego poruszonego obiektu i automatycznie cofa się przed zniszczeniem, nigdy bym tego nie pomyślał!

Ale tutaj jest odpowiedź bliżej oryginalnej próbie:

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); 
} 

ta sortuje multiset odniesień, więc nie muszą być przeniesione z drzewa.

Jednak po powrocie do pierwotnego zakresu przypisania przesunięć niekoniecznie są bezpieczne do samodzielnego przypisania, więc najpierw przeniosłem je do wektora, tak że po ponownym przypisaniu ich do pierwotnego zakresu nie będzie self-assignments.

To jest minimalnie szybsza niż wersja oryginalna w moich testach. Prawdopodobnie traci wydajność, ponieważ musi przydzielić wektor, a także wszystkie węzły drzewa. To i fakt, że mój kompilator używa ciągów COW tak, że przenoszenie nie jest dużo szybsze niż kopiowanie.