9

我知道使用“保留”来避免不必要的重新分配是一个好习惯（有效 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());
4

2 回答 2

7

如果什么时候v1你std::vector真的不需要它，因为编译器/stl 知道里面有多少项目v2（并且reserve在复制实际数据之前需要的数量本身）。

但是，对于一般情况，如果输入容器 ( ) 不知道有多少项目，并且您手头有数量reserve，则提前确定所需数量可能是有意义的。v1

于 2012-07-01T14:53:20.207 回答
7

是否调用reserve取决于：

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

让我们按顺序取 3 点。

1) 迭代器类型

该assign方法采用两个迭代器，它们至少必须符合InputIterator模型。问题是这个模型代表了纯粹的来源（比如来自网络的字节）：你可以从中消费两次。结果，给定两个InputIterator，如果不提取数据就无法计算它们之间的距离（除非您根本不想要数据，但这不是 assign 的目的），因此您不能先“保留”。

至少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);
    }
}
于 2012-07-01T16:05:04.427 回答