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

Question

我知道使用"reserve"是一种很好的实践，以避免不必要的重新分配（见Effective 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());

- jpen

---

我不确定为什么它不会使用std::distance自动保留正确的内存。 - chris

Answer 1

是否需要调用reserve取决于以下几个方面：

• 迭代器类型：对于输入迭代器，实现无法猜测其大小
• 库的质量：可能不会针对“更好”的迭代器进行专门优化
• 性能是否值得降低可维护性

让我们按顺序来看这三个方面。 1）迭代器类型 assign方法接受至少符合InputIterator模型的两个迭代器。问题是，该模型表示纯源（例如来自网络的字节）：您可以从中消耗两次。 因此，给定两个InputIterator，不可能在不提取数据的情况下计算它们之间的距离（除非您根本不想要数据，但这不是assign的目的），因此您不能先“reserve”。

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

- Matthieu M.

Answer 2

如果v1是std::vector，你实际上并不需要它，因为编译器/STL知道在v2中会有多少项（并且在复制实际数据之前将reserve所需的数量）。

然而，对于通用情况，如果输入容器（v1）不知道有多少项，并且您有手头的数字，则提前reserve所需的数量可能是有意义的。

- Vlad

---

我的代码中有个拼写错误。我原本想写 v2.reserve(v1.size())。 - jpen

我不确定你的意思。你说的“在向量v1的情况下，你实际上并不需要它”，是指v1.reserve(1000)不需要吗？ - jpen

@jpen：是的，因为assign会自动完成它。 （这是针对v1是向量的情况。）刚刚编辑了答案以避免歧义。 - Vlad

你的意思是说 v2.reserve(v1.size()) 不需要吗？ - jpen

没错，reserve 没有意义。这里没有不必要的重新分配需要避免。当你调用 assign 时，它知道需要分配多少字节。 - David Schwartz