Bu, bir std :: vektörünün içeriğini C++ 11'deki diğerinin sonuna taşımak için en etkili yöntem midir?

Question

vector::insert() ve std::copy() komutlarının fazladan ayırma gerektirdiğini düşünüyordum. Ancak, push_back() yeni oluşturulmuş bir öğe swap() ise, bu, içerilen türün varsayılan kurucu ile tahsis edilmediği sürece herhangi bir ayırmayı azaltacağını düşünüyorum.

Sorum tip std::string ait std::vector s için özel olarak aslında, ama burada belirtildiği gibi diğer türleri içerdiği için çalışması gerekir:

template <typename T> 
void appendMove(std::vector<T>& dst, std::vector<T>& src) 
{ 
    dst.reserve(dst.size() + src.size()) 
    for(std::vector<T>::iterator it = src.begin(); it != src.end(); ++it) 
    { 
     dst.push_back(std::vector<T>()); 
     std::swap(dst.end()[-1], *it); 
    } 
} 

ben haklı mıyım? Başka bir şey eksik miyim? Belki bunu yapmanın daha iyi bir yolu var mı?

Answer 1

Performans feragatnamesi: Profillemeyi kullanın.

performans hususlar:

• push_back vektörünün kapasitesi eleman eklemek için yeterli olup olmadığını her çağrı için kontrol etmek zorundadır. Derleyicinin, döngü içinde bu denetimden kaçınmak için yeterince akıllı olması olası değildir, yani, her döngü yinelemesi için, daha fazla optimizasyonu da engelleyebilecek olan, kontrol etmek zorunda olacaktır.
• reserve numaralı telefona çağrı yapılmazsa, push_back, hareket halindeyken vektörün kapasitesini, muhtemelen depolanan öğelerin hareket etmesine yol açacak döngüde birden çok kez ayarlaması gerekir.
• swapmove biraz farklıdır: hamle o dizi alır gibi GManNickG Açıklamalarda belirttiği
• gibi vector::insert, takmadan önce gerekli bellek, ayırabileceğiniz optimizasyonlar izin verebilir taşındı nesneler üzerinde daha az sıkı garantileri vardır eklenecek. Bu muhtemelen rasgele erişim yineleyicileri üzerinde bir uzmanlık gerektirecektir, çünkü onlar için std::difference O (1) 'dir (tüm çift yönlü yineleyiciler için uygulanabilir, ancak bu daha yavaş olabilir - iki döngü yineleme - değil rezerve). Aklıma

en etkili yolu kapasitesi kontrol olmadan (push_back yoluyla veya insert yoluyla ya) elemanları gerekli kapasiteyi ayıracağı daha sonra, etmektir.

Akıllı bir Standart Kitaplık uygulaması, insert numaralı telefonun içinde reserve numaralı telefonu arayabilir ve ekleme sırasında kapasitesini kontrol edemez. Bununla birlikte, bunun comply to the Standard olmasını kesinlikle bilmiyorum.

Kütüphanenizin (yorumlar) Andy Prowl 'ın versiyonu yeterince akıllı yeterli ise: Else

dst.insert(dst.end(), 
      std::make_move_iterator(src.begin()), 
      std::make_move_iterator(src.end()) ); 

, el insert çağırmadan önce reserve çağrısını yazabilir, ama bunu yapamazsınız (AFAIK) insert/iç kapasite kontrolleri o/w bir eleman ekleyin:

template < typename T, typename FwdIt > 
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst) 
{ 
    dst.reserve(dst.size() + std::distance(src_begin, src_end)); 
    // capacity checks might slow the loop inside `insert` down 
    dst.insert(dst.end(), src_begin, src_end); 
} 

Örnek:

int main() 
{ 
    std::vector<int> dst = { 0, 1, 2 }; 
    std::vector<int> src = { 3, 42 }; 

    append(std::make_move_iterator(src.begin()), 
      std::make_move_iterator(src.end()), 
      dst); 
} 

Farklı yineleyici türleri için append uygulamak için daha iyi olabilir:

template < typename T, typename FwdIt > 
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst, 
      std::forward_iterator_tag) 
{ 
    // let the vector handle resizing 
    dst.insert(dst.end(), src_begin, src_end); 
} 

template < typename T, typename RAIt > 
void append(RAIt src_begin, RAIt src_end, std::vector<T>& dst, 
      std::random_access_iterator_tag) 
{ 
    dst.reserve(dst.size() + (src_end - src_begin)); 
    dst.insert(dst.end(), src_begin, src_end); 
} 

template < typename T, typename FwdIt > 
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst) 
{ 
    append(src_begin, src_end, dst, 
      typename std::iterator_traits<FwdIt>::iterator_category()); 
} 

---

bir performans sorunu nedeniyle döngü içindeki kapasite kontrolleri oluşursa, gerekli ek unsurlar varsayılan-oluşturmaya çalışabilir ilk. Onlar (yani inşa edilmiş) mevcut zaman varacakları yere src nesneleri taşımak için operator[] kontrol-dışı veya basit yineleyicinızı kullanabilirsiniz:

template < typename T, typename RAIt > 
void append(RAIt src_begin, RAIt src_end, std::vector<T>& dst, 
      std::random_access_iterator_tag) 
{ 
    auto src_size = src_end - src_begin; 

    dst.resize(dst.size() + src_size); 

    // copy is not required to invoke capacity checks 
    std::copy(src_begin, src_end, dst.end() - src_size); 
    // ^this^ should move with the example provided above 
} 

---

Kolaylık sarıcı:

template < typename T, typename FwdIt > 
void append_move(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst) 
{ 
    append(std::make_move_iterator(src_begin), 
      std::make_move_iterator(src_end), 
      dst); 
}