在调用vector :: assign()之前调用vector :: reserve()会更好吗？

Question

我理解使用"保留"来避免不必要的重新分配是一种很好的做法(有效STL的第14项):

std::vector<int> v1;
v1.reserve(1000);

for (int i = 0; i < 1000; i++)
    v1.push_back(i);

调用assign时是否适用相同的规则？

std::vector<int> v2;
//v2.reserve(v1.size()); // Better to do this?
v2.assign(v1.begin(), v1.end());

Answer 1

在情况下,当v1是std::vector你并不真的需要它,因为编译器/ STL知道有多少项目是如何去那里的v2(并且将reserve所需要的量本身复制实际数据之前).

但是,对于一般情况,reserve如果输入容器(v1)不知道有多少项目,并且您手头有这个数字,那么事先对所需数量有意义.

Answer 2

是否打电话reserve取决于:

• 迭代器类型:对于输入迭代器,实现无法猜测大小
• 库的质量:它可能不适合"更好"的迭代器
• 性能是否值得降低可维护性

让我们按顺序拿3分.

1)迭代器类型

该assign方法需要两个必须至少符合InputIterator模型的迭代器.问题是这个模型代表纯粹的源(比如来自网络的字节):你可以消耗两次它的东西.结果,给定两个InputIterator,如果不提取数据就不可能计算它们之间的距离(除非您根本不想要数据,但这不是分配的内容),因此您不能先"保留".

这std::distance至少需要这个事实说明FowardIterator.

2)实施的质量

我不认为标准实际上要求"更好"的迭代器(至少建模ForwardIterator)执行assign两次遍历范围.在受内存带宽限制的计算中(想象一下读取磁带上的信息,倒带时间非常慢),这实际上会更昂贵.

但是,许多实现(例如libc ++,见下文)将专门化,assign以便在存在时ForwardIterator首先调用std::distance以在必要时保留适当数量的内存.

注意:顺便说一下,这同样适用于质量插入.

3)维护负担

我会注意到,尽管可能获益,但你(可能是在不知不觉中)在这里复制信息.

size_t size = std::distance(begin, end);

if (begin != end) ++begin; // new line

v.reserve(size);
v.assign(begin, end);

看看新行的外观突然使代码略微不正确？并不是说它不会起作用,但据称优化不再那么正确:你现在预留太多了!

就个人而言,我会相信我的标准库实现做正确的事情.写作他们的人比我更有经验.

如果它确实是您应用程序中确定的瓶颈,您可以随时尝试.只需编写一种reserve_and_assign方法,使其显而易见,并测量它是否更好.

供参考,这里是libc ++实现,在这里采取:

template <class _Tp, class _Allocator>
template <class _InputIterator>
typename enable_if
<
     __is_input_iterator  <_InputIterator>::value &&
    !__is_forward_iterator<_InputIterator>::value,
    void
>::type
vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
{
    clear();
    for (; __first != __last; ++__first)
        push_back(*__first);
}

template <class _Tp, class _Allocator>
template <class _ForwardIterator>
typename enable_if
<
    __is_forward_iterator<_ForwardIterator>::value,
    void
>::type
vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
{
    typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last);
    if (static_cast<size_type>(__new_size) <= capacity())
    {
        _ForwardIterator __mid = __last;
        bool __growing = false;
        if (static_cast<size_type>(__new_size) > size())
        {
            __growing = true;
            __mid =  __first;
            _VSTD::advance(__mid, size());
        }
        pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
        if (__growing)
            __construct_at_end(__mid, __last);
        else
            this->__destruct_at_end(__m);
    }
    else
    {
        deallocate();
        allocate(__recommend(static_cast<size_type>(__new_size)));
        __construct_at_end(__first, __last);
    }
}