我当时以为vector::insert()and std::copy()命令需要额外的分配。但是,如果我push_back()是一个新创建的元素,那么swap()我认为这将减少任何分配,只要所包含的类型未使用默认构造函数分配即可。
vector::insert()
std::copy()
push_back()
swap()
我的问题实际上是专门针对std::vector的std::string,但应该适用于此处所述的其他包含的类型:
std::vector
std::string
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); } }
我对么?我还有其他东西吗?也许有更好的方法可以做到这一点?
性能免责声明:使用性能分析。
性能注意事项:
push_back
reserve
swap
move
vector::insert
std::difference
我能想到的最有效的方法是保留必要的容量,然后在不进行容量检查的情况下(通过push_back或通过insert)插入元素。
insert
一个智能的标准库实现可以对reserve内部进行调用,insert而无需在插入过程中检查容量。不过,我不太确定这是否符合标准。
如果您的图书馆足够聪明,那么Andy Prowl的版本(请参阅注释)就足够了:
dst.insert( dst.end(), std::make_move_iterator(src.begin()), std::make_move_iterator(src.end()) );
否则,您可以在调用reserve之前手动将调用写入insert,但是您不能(AFAIK)在不进行内部容量检查的情况下插入/附加元素:
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); }
例:
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 ); }
最好append为不同的迭代器类型实现:
append
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() ); }
如果由于循环内的容量检查而导致性能问题,则可以尝试首先默认构造所需的其他元素。当它们存在(即已构造)时,您可以使用非选中operator[]或简单的迭代器将src对象移动到其目的地:
operator[]
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 }
便利包装:
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 ); }