Hareketli elemanlar

Question

Sadece eğlence için, ben hayal basit sıralama algoritması uygulayan Ben hareket semantik ile performansını artırmak istedik:

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

Ama bu ben bile, önemli bir biçimde performans etkilemedi std::string s sıralama.

Sonra ilişkisel kaplar :(ağaçtan veri taşımak için başka bir yolu var mı? Yani std::move ve std::copy Burada da aynı şeyi yapacağız, dışarıdan sabittir hatırladım

Answer 1

std::set vesadece elemanlarına erişim sağlar const Bir şeyleri setin dışına taşıyamayacağınız anlamına gelir.Eğer öğeleri dışarı taşıyabiliyorsanız (veya hepsini değiştirdiğinizde), öğelerin sıralama düzenini değiştirerek seti bozabilirsiniz. Yani C++ 11 bunu yasaklıyor

0'ı kullanma girişiminizalgoritması sadece kopya kurucuyu çağırır.

Answer 2

multiset için kullanılacak özel bir ayırıcıyı kullanmanız gerektiğini (3. şablon argümanı), öğelerin gerçekte destroy yöntemini kullanıcının kasasına geri taşıdığını düşünebilirsiniz. Daha sonra setteki her bir elemanı siliniz ve imha sırasında dizinizi orijinal konteynere geri taşımalıdır. Özel ayırıcının 2 aşamalı bir yapıya sahip olması gerektiğini düşünüyorum (bunu, varsayılan olarak yapılandırılabilir olması gerektiğinden, yapım sırasında değil, bir üye olarak tutmak için treesort işlevinize geçirilen başlangıç ​​yineleyicisini iletin).

Açıkçası bu durum çok tuhaf olurdu ve set/multiset'te pop yöntemine sahip olmamanız için aptalca bir çözümdür. Ama mümkün olmalıydı.

Answer 3

Dave'in, her bir hareketin nesnenin kaynağını hatırlatan ve otomatik olarak yıkıma geri döndüğü garip bir aldatıcı fikrini seviyorum, bunu yapmayı hiç düşünmemiştim!

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

Bu referansların multiset sıralar, bu yüzden ağaçtan Taşınacak gerekmez:

Ama burada bir cevap daha yakın orijinal girişimine var.

Ancak, orijinal aralığa geri taşınırken, taşıma atamaları kendiliğinden atamak için zorunlu değildir, bu yüzden bunları önce bir vektöre taşıdım, böylece onları orijinal aralığa yeniden atadığınızda, kendini atamalar.

Bu, numaralı marjinal sınavlarımdaki orijinal versiyonundan daha hızlıdır. Muhtemelen verimliliği kaybeder, çünkü vektörü ve tüm ağaç düğümlerini ayırmak zorundadır. Bu ve derleyicimin COW dizelerini kullandığı gerçeği hareket etmekten çok daha hızlı değil.