我在想 vector::insert()
和 std::copy()
命令需要额外的分配。但是,如果我 push_back()
一个新创建的元素然后 swap()
它我认为这会减少任何分配,只要包含的类型没有分配默认值构造函数。
我的问题实际上专门针对 std::string
类型的 std::vector
,但应该适用于此处所述的其他包含类型:
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
必须在每次调用时检查 vector 的容量是否足以插入元素。编译器不太可能聪明到可以避免循环内的检查,也就是说,对于每次循环迭代,它都必须检查,这也可能会阻止进一步的优化。- 如果之前没有调用
reserve
,push_back
必须随时调整 vector 的容量,可能在循环中多次,这会导致移动已经存储的元素。 swap
与move
略有不同:move 对移动的对象没有那么严格的保证,这可能允许优化- 作为GManNickG在评论中指出,
vector::insert
可以在插入之前保留必要的内存,因为它可以插入整个范围。这可能需要对随机访问迭代器进行专门化,因为它们的std::difference
在 O(1) 中(它可以应用于所有双向迭代器,但这可能会更慢 - 两次循环迭代 -比不保留)。
我能想到的最有效的方法是保留必要的容量,然后插入元素(通过 push_back
或通过 insert
)而不进行容量检查。
智能标准库实现可以在 insert
中调用 reserve
并且在插入期间不检查容量。我不完全确定这会 comply to the Standard , 不过。
如果您的图书馆足够聪明,Andy Prowl的版本(见评论)就足够了:
dst.insert( dst.end(),
std::make_move_iterator(src.begin()),
std::make_move_iterator(src.end()) );
否则,您可以在调用 insert
之前手动编写对 reserve
的调用,但您不能(据我所知)插入/附加没有内部容量检查的元素:
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
可能会更好:
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 对象移动到它们的目的地:
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 );
}
关于c++ - 这是在 C++11 中将一个 std::vector 的内容移动到另一个的末尾的最有效方法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16599164/