c++ - std::vector 在增长时会调用交换函数吗？总是或仅适用于某些类型？

Question

据我所知，我可以使用向量 ( std::vector< std::vector<int> >) 的向量，这将非常有效，因为在内部元素不会被复制，而是交换，这要快得多，因为不包括内存缓冲区的复制。我对吗？

究竟什么时候std::vector使用交换功能？我在C++ 标准中找不到任何关于它的信息。它是否在缓冲区重新分配期间发生？

我做了一些测试来找出它，但我失败了。我的自定义数据类型的交换函数根本没有被调用。

编辑：这是我的测试程序。

score 8 · Accepted Answer

我没有支持此声明的链接，但据我所知，与 Microsoft C++ 一起分发的 STL 实现使用一些内部非标准魔术注释将vector（和其他 STL 集合）标记为具有性能交换所以vector<vector<>>不会复制内部向量但交换它们。直到 VC9，也就是说，在 VC10 中，它们将切换到右值引用。我认为你不应该像没有交叉编译器那样标记你自己的类，而且你的代码只能在特定的编译器版本上工作。

编辑：我快速查看了<vector>VC9 中的标题并发现了这一点：

    // vector implements a performant swap
template <class _Ty, class _Ax>
    class _Move_operation_category<vector<_Ty, _Ax> >
    {
    public:
        typedef _Swap_move_tag _Move_cat;
    };

只是为了实验，你可以尝试为你自己的类型专门化这个类，但正如我所说，这是特定于 STL 版本的，它会在 VC10 中消失

score 3 · Accepted Answer

std::vector 传统上在增长时将元素复制构造到新内存中，然后销毁旧值。然而，在即将到来的具有右值引用和移动语义的 C++0x 中，std::vector 可以将元素移动到新内存中。这效率要高得多。如果您有一个字符串向量或其他一些昂贵的复制数据，那么移动构造它们基本上只是将指针复制到保存的数据并将源对象标记为空。与复制和销毁相比，这非常便宜，并且有效地解决了可移动构造类型的代价高昂的向量重新分配问题。这几乎是您描述的交换优化，内置于语言中。

score 3 · Accepted Answer

我认为不允许使用矢量swap（由 ADL 发现）。我可以找到并没有明确禁止，但是对vector的值类型的要求是CopyConstructible和Assignable。这些都没有swap作为有效操作（甚至是可选操作），也没有任何标准方法来确定交换是否过载。可能它可以使用std::swap（或特殊化，如果存在）在适当的地方，因为它对其参数有相同的要求：CopyConstructible 和 Assignable（以及命名空间 std 中函数的 UDT 的特殊化必须实现泛型模板的定义行为）。但是，这对重新分配没有帮助，因为您必须构造一些“空”对象来交换，并且当标准没有时，vector 不能仅仅决定其值类型应该是默认可构造的自己的权限不需要那个。

我认为可以合理地假设，如果您的类型 T 不需要某个操作，那么即使编译器以某种方式从心理上确定它存在，它也不会执行。在 C++ 中，仅仅因为某些东西定义了正确的函数来实现接口并不意味着它声称实现了该接口的语义。直到您在需要语义的上下文中传递它，您才声称函数的行为符合接口的预期。标准对vector的值类型没有要求表现良好swap，所以vector的实现不能假设仅仅因为swap被定义就优于operator=.

这只是我对规范意图的解释，不过，无论哪种方式，我都找不到任何确定的东西。

23.2.4.3/4 给出了一个线索。在谈到时erase，它说：“T 的赋值运算符被称为次数等于向量中删除元素之后的元素数”。因此 vector 被明确禁止swap用于在擦除后向前移动向量的末尾：它必须使用operator=. 我认为这是一个强烈的暗示，即作者的期望是operator=用于所有内容，否则他们不会如此粗心，以至于swap在不需要默认构造函数的情况下实际上可以使用它的情况下禁止。

我还看到了你和 jdv 描述的微软的观点，即对于容器的容器，交换可以带来很大的好处。只要“模板魔法”不会干扰格式良好的 C++ 程序，提供类型告诉向量交换的方法的实现就没有错。

例如，他们可能有一个名称中带有双下划线的类型特征模板。使用该名称的效果是实现定义的，所以所有的赌注都没有了。C++ 标准没有说明 std::vector 在专门化该模板的程序中的行为方式。在程序中使用保留名称后，实现可以定义要使用的向量operator=，swap或aubergine用于所有标准关心。

score 1 · Accepted Answer

标准是怎么说的，我也不知道。stl 中的默认设置是复制，如果您大量编辑向量的向量，这并不好玩。

但是，您想要的行为是在 Visual C++ 中的 TR1 实现中实现的，可作为 VS2008 的更新（TR1 是 C++ 0x 标准的前奏）。与许多其他编译器供应商一样，他们从 Dinkumware 购买他们的 stl 实现，因此您可以期望看到它出现在其他编译器上。请参阅http://msdn.microsoft.com/en-us/library/bb982198.aspx。

如果您使用 GCC，这对您毫无用处，但这里可能还有其他人可以告诉您。

[编辑] 编辑后继续阅读，我发现微软声称 swap() 优化是他们的功能，而不是 dinkimware 的。至少我是这样阅读这篇博文的：http: //blogs.msdn.com/vcblog/archive/2008/01/08/qa-on-our-tr1-implementation.aspx

score 1 · Accepted Answer

基本上，您是在询问执行以下操作时会发生什么：

vector<int> v;
v.reserve(100);

我们可以看看 libstdc++ 在这种情况下做了什么作为一个例子。

template<typename _Tp, typename _Alloc> void vector<_Tp, _Alloc>::reserve(size_type __n) {
    if (__n > this->max_size())
        __throw_length_error(__N("vector::reserve"));
    if (this->capacity() >= __n)
        return;

    const size_type __old_size = size();
    pointer __tmp = _M_allocate_and_copy(__n,
        _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start),
        _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish));
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
    _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
    this->_M_impl._M_start = __tmp;
    this->_M_impl._M_finish = __tmp + __old_size;
    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
}

这里重要的调用是_M_allocate_and_copy

template<typename _ForwardIterator> pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last) {
    pointer __result = this->_M_allocate(__n);
    std::__uninitialized_copy_a(__first, __last, __result, _M_get_Tp_allocator());
    return __result;
}

这里重要的调用是std::__uninitialized_copy_a

template<typename _InputIterator, typename _ForwardIterator, typename _Allocator> _ForwardIterator __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _Allocator& __alloc) {
    _ForwardIterator __cur = __result;
    for (; __first != __last; ++__first, ++__cur)
        __alloc.construct(&*__cur, *__first);
    return __cur;
}

这是调用构造。如您所见，它使用的是复制构造函数。

void construct ( pointer p, const_reference val ) {
    new ((void*)p) T (val);
}

因此，当发生重新分配时，向量中的每个元素都会调用复制构造函数。

score 0 · Accepted Answer

不幸的是，在讨论 C++ 0x 标准时忽略了使用交换函数。

我认为交换应该是语言级别已知的基本功能。它解决了向语言添加右值引用的许多原因。

从函数返回 std::vector 或从临时分配可以使用交换而不是复制。容器可以使用它来优化重新分配。

唉。:(

score -2 · Accepted Answer

当你有一个相当大的向量并且你想释放它时，你可以使用交换函数将它与一个空向量交换。这是使用 STL 容器时释放内存空间的一种非常有效的方法。

c++ - std::vector 在增长时会调用交换函数吗？总是或仅适用于某些类型？

7 回答 7

Related

Reference