移动后的向量是否总是为空?

58

我知道通常标准对从中移动的值没有太多要求:

N3485 17.6.5.15 [lib.types.movedfrom]/1:

在C++标准库中定义的类型的对象可以被移动 (12.8)。移动操作可以被明确地指定或隐含地生成。除非另有规定,否则这些移动后的对象应该放在一个有效但未指定状态。

我没有找到任何关于vector的内容明确排除它不符合这个段落。然而,我无法想出一个合理的实现,导致vector不为空。

是否有一些标准方面的规定我漏掉了,还是类似于在C++03中将basic_string视为连续缓冲区?


1
我认为一个疯狂但合法的实现可能是 class vector<T> { private: T* m_data; size_type m_size; size_type m_capacity; bool m_this_owns_data; }; - aschepler
2
@aschepler:不,那是非法的。 - Puppy
我找不到关于向量的任何内容明确将其从该段落中排除。 “未指定”包括仅存在单个替代方案的情况。(因此,除非移动后存在对象进入无效状态的情况,在该引语中使用前缀“除非另有规定”是多余的)。 - Johannes Schaub - litb
@Yakk:是的。任何一个vector与另一个使用相同T的vector的存储别名都是非法的。 - Puppy
1
@BillyONeal:是的,我看了答案,当涉及到分配器时,标准相当复杂 :( - Mooing Duck
显示剩余2条评论
4个回答

82

我来晚了,提供一份额外的答案,因为我认为当前没有完全正确的答案。

问题:

一个被移动的vector是否总是为空?

回答:

通常情况下是空的,但并不总是空的。

具体细节:

vector没有像某些类型一样定义标准化的被移动状态(例如,unique_ptr在被移动后等于nullptr),但是vector的要求并不多。

答案取决于我们是谈论vector的移动构造函数还是移动赋值运算符。在后一种情况下,答案还取决于vector的分配器。


vector<T, A>::vector(vector&& v)

这个操作必须具有常数复杂度。这意味着没有其他选择,只能从v中窃取资源来构建*this,使v处于空状态。无论分配器A是什么,类型T是什么,都是如此。

所以对于移动构造函数,是的,被移动的vector将始终为空。虽然这并没有直接说明,但这是由于复杂度要求和没有其他实现方式导致的。


vector<T, A>&
vector<T, A>::operator=(vector&& v)

要求翻译为中文: 这里的内容相对复杂。有3个主要情况:

第一种情况:

allocator_traits<A>::propagate_on_container_move_assignment::value == true

(propagate_on_container_move_assignment评估为true_type)

在这种情况下,移动赋值运算符将销毁*this中的所有元素,使用*this的分配器释放容量,移动分配器,然后将内存缓冲区的所有权从v转移给*this。除了销毁*this中的元素外,这是O(1)复杂度操作。通常情况下(例如在大多数但不是所有的std::algorithms中),移动赋值的左侧在移动赋值之前具有empty() == true

注意:在C++11中,std::allocatorpropagate_on_container_move_assignmentfalse_type,但在C++1y(y == 4 we hope)中已更改为true_type

在第一种情况下,移出的vector将始终为空。

二:

allocator_traits<A>::propagate_on_container_move_assignment::value == false
    && get_allocator() == v.get_allocator()

(propagate_on_container_move_assignment的返回值为false_type,且这两个分配器相等)

在这种情况下,移动赋值运算符的行为类似于第一种情况,但有以下例外:

  1. 分配器不会被移动分配。
  2. 此情况与第三种情况之间的决策发生在运行时,而第三种情况需要更多的T,因此第二种情况也需要更多的T,即使第二种情况实际上并没有执行T的额外要求。

在第二种情况下,移动后的vector将始终为空。

第三种情况:

allocator_traits<A>::propagate_on_container_move_assignment::value == false
    && get_allocator() != v.get_allocator()

(propagate_on_container_move_assignment评估为false_type,且两个分配器不相等)
在这种情况下,实现无法移动分配器,也无法将任何资源从v转移到*this(资源是内存缓冲区)。在这种情况下,实现移动赋值运算符的唯一方法是有效地:
typedef move_iterator<iterator> Ip;
assign(Ip(v.begin()), Ip(v.end()));

也就是说,将v中的每个单独的T移动到*this中。如果*this中有可用的capacitysize,则assign可以重复使用它们。例如,如果*thisv具有相同的size,则实现可以将v中的每个T移动分配给*this。这需要TMoveAssignable的。请注意,MoveAssignable不需要T具有移动赋值运算符。复制赋值运算符也可以满足要求。MoveAssignable只是意味着T必须可以从rvalue T中进行分配。

如果*thissize不足够,则需要在其中构造新的T。这要求T是可MoveInsertable的。就我所知,对于任何明智的分配器,MoveInsertable归结为与MoveConstructible相同的事情,这意味着可以用右值T构造它(并不意味着存在T的移动构造函数)。
第三种情况中,移后的vector通常不会为空。它可能被移动了元素。如果这些元素没有移动构造函数,则这可能等效于复制赋值。但是,并没有强制要求这样做。实现者可以自由地执行v.clear(),使v为空。我不知道有哪个实现这样做,也不知道任何这样做的动机。但我没有看到任何禁止它的东西。

David Rodríguez报告说,在这种情况下,GCC 4.8.1调用v.clear(),导致v为空。libc++不会这样做,因此v不为空。两个实现都是符合规范的。


4
谢谢!简而言之,这是可能的,因为它没有被禁止并且该库是可定制的。 - Potatoswatter
3
Howard,我不相信“常数时间”要求会排除“短向量”“优化”的实现,至少只要元素的构造函数和析构函数是微不足道的。只要短向量有一个最大大小,复制操作就受到复制该大小所需时间的限制,这足以符合常数时间的要求。在这种情况下,即使移动构造函数也可能不会留下空向量。 - rici
3
@rici: [container.requirements.general]/p10/b6 要求除非另有规定,否则不得使容器的任何迭代器失效。vector没有其他规定。然而[string.require]/p6/pb1对string进行了澄清,注脚237进一步说明了这一点。所有这些的意图是禁止对vector进行“短字符串”优化,但允许对string进行优化。 - Howard Hinnant
2
实现者可以自由地做一些额外的工作并执行v.clear()[...] 我不知道是否有任何实现这样做。 GCC 4.8.1正是这样做的。 - David Rodríguez - dribeas
1
@rici:我认为在需要缓冲区所有权转移的情况下,源迭代器将成为目标迭代器。话虽如此,标准对此并不明确,如果调试实现禁止这种使用,我也不会感到惊讶。libc++调试模式(尚处于初期)允许使用这样的“移动”迭代器。在禁止缓冲区所有权转移的情况下,源中未完成的迭代器的行为是未指定的。libc++保持它们不变,而GCC 4.8.1则使它们无效。 - Howard Hinnant
显示剩余8条评论

5
虽然在一般情况下这可能不是一个明智的实现方式,但移动构造函数/赋值的有效实现只需从源中复制数据,保留源的原样。此外,对于赋值的情况,移动可以作为交换来实现,并且“已移动”容器可能包含“已移动到”容器的旧值。
如果使用了多态分配器(如我们所做的),并且分配器不被视为对象的“值”(因此,赋值永远不会改变实际使用的分配器),则实际上可以将移动实现为复制。在这种情况下,移动操作可以检测源和目标是否使用相同的分配器。如果它们使用相同的分配器,则移动操作可以直接从源中移动数据。如果它们使用不同的分配器,则目标必须复制源容器。

4
@DeadMG:这是关于迭代器失效的连续第二条评论,您能否解释一下您所指的特定点? - Matthieu M.
1
@BillyONeal:我不是100%确定。措辞特别将swap与分配器可能被更改的其他操作区分开来。23.2.1/7说明了分配器何时可以更改,并且它提到,除非分配器在交换时传播或两个对象中的分配器相同,否则swap是未定义的。 - David Rodríguez - dribeas
@DeadMG:看一下第99表,移动赋值的要求。它明确指出,目标容器中的元素可以从原始容器中的元素进行移动赋值,在这种情况下,原始容器将不再拥有这些元素。如果包含的元素没有移动赋值,则目标容器中的元素将被复制 - David Rodríguez - dribeas
@David:是的,这些规则表明分配器应用相同的操作。它们不允许交换分配器。 - Billy ONeal
@BillyONeal:我不确定我理解你的推理或者为什么你关心分配器被交换(除非你指的是答案第一段的最后一句话)。 - David Rodríguez - dribeas
显示剩余12条评论

4
在许多情况下,移动构造和移动赋值可以通过委托给swap来实现 - 尤其是如果没有涉及分配器。这样做有几个原因:
  • swap必须被实现
  • 开发人员效率更高,因为需要编写的代码更少
  • 运行时效率更高,因为总共执行的操作更少
以下是移动赋值的示例。在这种情况下,如果移动到的向量不为空,则移动源向量将不会为空。
auto operator=(vector&& rhs) -> vector&
{
    if (/* allocator is neither move- nor swap-aware */) {
        swap(rhs);
    } else {
        ...
    }
    return *this;
}

我认为这是不合法的,因为分配器要求。具体来说,这使得赋值运算符对allocator_traits<allocator_type>::propagate_on_container_swap::value敏感,而标准只允许它对allocator_traits<allocator_type>::propagate_on_container_move_assignment::value敏感。 - Billy ONeal
@BillyONeal:你是对的。然而,这个例子表明可以有有效的实现,交换数据结构,使得移动后的向量不为空。我已经更新了我的答案以尊重分配器特性。 - nosid
不,那仍然不起作用。propagate_on_container_move_assignment 要求分配器本身被移动赋值。你上面的例子交换了分配器,这是不允许的。 - Billy ONeal
at将是一个模板参数,不一定是std::allocator_traits。) - aschepler

1

我在其他回答中留下了这样的评论,但是还没来得及完全解释就匆忙离开了。移动自 vector 的结果必须始终为空,或者在移动赋值的情况下,必须为空或前一个对象的状态(即交换),否则无法满足迭代器失效规则,即移动不会使它们失效。考虑:

std::vector<int> move;
std::vector<int>::iterator it;
{
    std::vector<int> x(some_size);
    it = x.begin();
    move = std::move(x);
}
std::cout << *it;

在此,您可以看到迭代器失效确实暴露了移动的实现方式。为了使此代码合法,特别是迭代器保持有效的要求,阻止了实现执行复制、小型对象存储或任何类似的操作。如果进行了复制,则在可选项为空时会使迭代器无效,如果vector使用某种基于SSO的存储,则情况也是如此。基本上,唯一合理的可能实现方式是交换指针或简单地移动它们。
请仔细查看有关所有容器要求的标准引用。
X u(rv)    
X u = rv    

post: 在此构造之前,u应该等于rv的值

a = rv

a将等于rv在此赋值之前的值

迭代器有效性是容器的一部分价值。尽管标准没有直接明确说明这一点,但我们可以看到,例如:

begin()返回一个指向容器中第一个元素的迭代器。end()返回一个过容器末端的迭代器。如果容器为空,则begin() == end();

任何实际上从源代码的元素移动而不是交换内存的实现都将是有缺陷的,因此我建议任何标准措辞说否则都是有缺陷的-最重要的是因为标准实际上在这一点上并不非常清楚。这些引用来自N3691。


2
为什么它总是必须为空?源向量不能先将其指针移动到目标向量(从而保持无效保证),然后再向自身添加一个或多个元素吗?(从头开始使用新缓冲区)。虽然在发布程序中这不是明智的行为,但我想象这是程序错误查找器的有用部分,它试图查找依赖于“关于标准库移动构造函数的不正确假设”的程序错误。那么这是否在任何地方明确指定了呢? - Johannes Schaub - litb
3
我本以为 move = std::move(x); 会使 it 失效。你似乎在暗示 it 现在是指向 move 的第一个元素的迭代器。但我在标准中找不到任何支持这两种情况的依据。 - aschepler
3
@DeadMG: 你遇到了迭代器失效。你指的是哪条规则?swap和移动赋值有不同的特定要求。移动赋值的要求明确说明,如果分配器在移动赋值时没有传播,则可以移动赋值(注意元素,而不是容器的数据结构)。这与任何要求迭代器仍然有效且引用目标容器的规则相矛盾。 - David Rodríguez - dribeas
2
@DeadMG: 迭代器有效性 不是容器的的一部分。借用你自己的例子:C outer; C::iterator it; { C inner; it=inner.end(); swap(outer,inner); } /* it? */。块完成后,it可能有效也可能无效。C a = ...; C b = a; C::iterator it = b.begin(); b.reserve(b.size()*2); assert(a==b);然而迭代器已经失效了... - David Rodríguez - dribeas
4
@DeadMG说:在进行reserve()操作期间,std::vector不会改变,但迭代器将失效。具有不同容量、相同大小和完全相同顺序的元素集的两个向量相等vector<int> a = f(),b = a; 迭代器it = b.begin(); b.reserve(2*a.size()); reserve()操作不会改变b,但它肯定会使迭代器失效。 - David Rodríguez - dribeas
显示剩余16条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接