从同一向量中 push_back 一个元素是否安全？

Question

vector<int> v;
v.push_back(1);
v.push_back(v[0]);

如果第二个 push_back 导致重新分配内存，那么对于向量中第一个整数的引用将不再有效。所以这不安全吗？

vector<int> v;
v.push_back(1);
v.reserve(v.size() + 1);
v.push_back(v[0]);

这会使它更安全吗？

- Neil Kirk

---

注意：目前标准提案论坛正在讨论中。其中，有人提供了一个push_back的示例实现作为其中一部分。另一位发帖者指出了其中的一个错误，即它没有正确处理你所描述的情况。据我所知，没有其他人认为这不是一个错误。并不是说这是最终证明，只是一个观察结果。 - Benjamin Lindley

很抱歉，我不知道应该接受哪个答案，因为关于正确答案仍存在争议。 - Neil Kirk

第五个评论在https://dev59.com/CmMl5IYBdhLWcg3wJUIC#18647445下要求我对这个问题发表评论。目前回答中任何一个回答都说“是的，从同一向量后面添加元素是安全的”，我通过给每个这样的答案投赞成票来回答这个问题。 - Howard Hinnant

@BenVoigt: <耸肩> 如果您不同意标准的内容，或者即使您同意标准的内容，但认为其表述不够清晰，这总是一个选择：http://cplusplus.github.io/LWG/lwg-active.html#submit_issue 我自己也多次选择了这个选项。有时成功，有时失败。如果您想辩论标准的内容或应该如何表述，SO 不是一个有效的论坛。我们的对话没有规范性意义。但是通过上面的链接，您可以有机会产生规范性影响。 - Howard Hinnant

如果 push_back 导致向量达到其容量，向量将分配一个新的更大的缓冲区，复制旧数据，然后删除旧缓冲区。然后它将插入新元素。问题是，新元素是对刚刚被删除的旧缓冲区中数据的引用。除非 push_back 在删除之前复制该值，否则它将是一个错误的引用。 - Neil Kirk

Answer 1

看起来像是http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526中提到了这个问题（或类似的问题）可能是标准中的一个潜在缺陷：

1）通过const引用传递的参数可以在函数执行期间更改

例如：

给定std::vector v:

v.insert(v.begin(), v[2]);

v[2] 可能会被移动向量元素而发生变化

建议的解决方案是，这不是一个缺陷：

vector::insert(iter, value)需要正常工作，因为标准没有允许它不工作。

- Nate Kohl

---

我在17.6.4.9中找到了权限：“如果函数的参数具有无效值（例如函数域之外的值或指针用于其预期用途无效），则行为是未定义的。” 如果重新分配发生，则所有迭代器和元素的引用都将失效，这意味着传递给函数的参数引用也无效。 - Ben Voigt

我认为重点是实现负责进行重新分配，它有责任确保在初始定义输入的情况下行为是被定义的。由于规范明确指定push_back会复制，实现必须在释放之前缓存或复制所有值，可能会牺牲执行时间。由于在这个特定问题中没有留下外部引用，因此迭代器和引用无效也无所谓。 - OlivierD

我认为这应该是权威答案，Stephan T. Lavavej 在 Reddit 上也使用基本相同的论点提到了它。 - TemplateRex

“v.insert(v.begin(), v[2]);” 无法触发重新分配内存。那么这怎么回答这个问题呢？ - ThomasMcLeod

是的，显然它可以触发重新分配。您通过插入新元素来扩展向量的大小。 - Violet Giraffe

Answer 2

是的，它是安全的，并且标准库的实现会尽力确保其安全。

我相信实现者将这个要求追溯到23.2/11，但是我无法弄清楚具体细节，也找不到更确切的信息。最好的资料是这篇文章：

http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771

检查libc++和libstdc++的实现显示它们也是安全的。

- Sebastian Redl

---

这里真的需要一些后盾支持。 - chris

很有趣，我必须承认我从未考虑过这种情况，但确实似乎很难实现。对于 vec.insert(vec.end(), vec.begin(), vec.end())，它是否也适用？ - Matthieu M.

@MatthieuM。编号100的表格显示：“pre：i和j不是a的迭代器。” - Sebastian Redl

我现在正在点赞，因为这也是我的回忆，但需要提供参考资料。 - bames53

你使用的版本中是否包含“除非另有规定（无论是明确规定还是通过其他函数定义来规定），调用容器成员函数或将容器作为库函数的参数不会使该容器中的对象的迭代器失效或更改值。”？但是，vector.push_back 确实有另外的规定。"如果新大小大于旧容量，则导致重新分配."并且（在 reserve 函数中）"重新分配会使所有引用、指针和迭代器都失效，这些引用、指针和迭代器指向序列中的元素." - Ben Voigt

Answer 3

标准保证即使是你的第一个示例也是安全的。引用C++11：

[sequence.reqmts]

3 在表100和101中... X表示序列容器类，a表示包含类型为T的元素的X的值，t表示X::value_type的左值或常数右值

16 表101... 表达式 a.push_back(t) 返回类型 void 操作语义 追加t的副本。 要求：T必须能够CopyInsertable到X中。 容器 basic_string、deque、list、vector 所以即使它并不是完全琐碎的，实现也必须保证在执行push_back时不会使引用无效。

- Angew is no longer proud of SO

---

我不明白这怎么能保证安全。 - jrok

“@Angew: 它完全使 't' 无效，唯一的问题是在复制之前还是之后。你最后一句话肯定是错误的。” - Ben Voigt

客户端无需在整个调用过程中保持先决条件，只需确保在调用开始时满足该条件。 - bames53

@barnesпјҡжҲ‘дёҚеҗҢж„ҸгҖӮдҫӢеҰӮпјҢдҪ жҳҜеҗҰеңЁеЈ°з§°std::for_eachеҝ…йЎ»еңЁиҢғеӣҙзҡ„еҮҪж•°еҜ№иұЎдҪҝз»“жқҹиҝӯд»ЈеҷЁж— ж•Ҳж—¶д»Қ然иғҪеӨҹе·ҘдҪңпјҹ е®ғеҰӮдҪ•еҸ‘зҺ°ж–°зҡ„жңүж•Ҳз»“жқҹиҝӯд»ЈеҷЁпјҹ еңЁи°ғз”Ёжңҹй—ҙпјҢжӮЁеҝ…йЎ»зЎ®дҝқж»Ўи¶іеүҚжҸҗжқЎд»¶гҖӮ - Ben Voigt

那是个好观点，但我相信传递给for_each的函数对象要求不使迭代器失效。我找不到关于for_each的参考资料，但在一些算法文本中看到类似“op和binary_op不应使迭代器或子���围失效”的字眼。 - bames53

Answer 4

第一个示例看起来并不安全，因为push_back的最简实现是在需要时首先重新分配向量，然后复制引用。

但至少在Visual Studio 2010中似乎是安全的。它的push_back实现会特殊处理向量中推送元素的情况。 代码结构如下：

void push_back(const _Ty& _Val)
    {   // insert element at end
    if (_Inside(_STD addressof(_Val)))
        {   // push back an element
                    ...
        }
    else
        {   // push back a non-element
                    ...
        }
    }

- Johan Råde

---

我想知道规格是否要求这个是安全的。 - Nawaz

根据标准，它不需要是安全的。然而，可以以安全的方式实现它。 - Ben Voigt

@BenVoigt 我会说这是必须要安全的（请看我的回答）。 - Angew is no longer proud of SO

@BenVoigt 在您传递引用时，它是有效的。 - Angew is no longer proud of SO

@Angew：那还不够。你需要传递一个在调用期间保持有效的引用，而这个引用却不行。 - Ben Voigt

Answer 5

这并不是标准的保证，但作为另一个数据点，v.push_back(v[0]) 在LLVM 的 libc++中是安全的。 libc++ 的 std::vector::push_back 在需要重新分配内存时调用 __push_back_slow_path。

void __push_back_slow_path(_Up& __x) {
  allocator_type& __a = this->__alloc();
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), 
                                                  size(), 
                                                  __a);
  // Note that we construct a copy of __x before deallocating
  // the existing storage or moving existing elements.
  __alloc_traits::construct(__a, 
                            _VSTD::__to_raw_pointer(__v.__end_), 
                            _VSTD::forward<_Up>(__x));
  __v.__end_++;
  // Moving existing elements happens here:
  __swap_out_circular_buffer(__v);
  // When __v goes out of scope, __x will be invalid.
}

- Nate Kohl

---

复制不仅需要在释放现有存储之前进行，而且需要在移动现有元素之前进行。我想现有元素的移动是在__swap_out_circular_buffer中完成的，在这种情况下，此实现确实是安全的。 - Ben Voigt

@BenVoigt：说得好，你确实正确，移动操作发生在__swap_out_circular_buffer内部。（我已经添加了一些注释来说明这一点。） - Nate Kohl

Answer 6

第一个版本绝对不安全：

通过调用标准库容器或字符串成员函数获得的迭代器上的操作可能会访问底层容器，但不得修改它。[注意：特别是，使迭代器无效的容器操作与与该容器相关联的迭代器上的操作冲突。 —注] 来自17.6.5.9节

请注意，这是关于数据竞争的部分，人们通常将其与线程一起考虑... 但实际定义涉及“发生在”关系，并且我没有看到push_back的多个副作用之间存在任何排序关系，即引用失效似乎未被定义为相对于复制构造新尾元素有序。

- Ben Voigt

---

应该理解这是一条注释而不是规则，因此它解释了前述规则的后果...并且对于引用来说，这些后果是相同的。 - Ben Voigt

v[0]的结果不是一个迭代器，同样地，push_back()也不接受一个迭代器。所以，从语言法律的角度来看，你的论点是无效的。抱歉。我知道大多数迭代器都是指针，并且使迭代器失效的原因和使引用失效的原因基本相同，但你引用的标准部分与现在的情况无关。 - cmaster - reinstate monica

-1. 这是完全无关的引用，而且根本没有回答问题。委员会表示 x.push_back(x[0]) 是安全的。 - Nawaz

Answer 7

它是完全安全的。

在您的第二个示例中，您有

v.reserve(v.size() + 1);

这并不是必要的，因为如果向量超出其大小，它将暗示使用reserve。

向量负责这些事情，而不是你。

- Zaffy

Answer 8

两者都是安全的，因为push_back会复制值而不是引用。如果您正在存储指针，则就向量而言仍然是安全的，但请知道您的向量将有两个元素指向相同的数据。

第23.2.1节通用容器要求

16

• a.push_back(t) 追加t的副本。 要求：T必须可复制插入到X中。
• a.push_back(rv) 追加rv的副本。 要求：T必须可移动插入到X中。

因此，push_back的实现必须确保插入v[0]的副本。通过反例，假设在复制之前重新分配的实现，它不一定会追加v[0]的副本，因此违反规格。

- OlivierD

---

push_back 会 调整 向量的大小，在一个简单的实现中，这将在复制发生之前 使引用无效。因此，除非您可以从标准中支持此操作，否则我认为它是错误的。 - Konrad Rudolph

“this”是指第一个还是第二个例子？ push_back 将值复制到向量中；但是（就我所看到的而言），这可能发生在重新分配之后，此时它试图复制的引用已不再有效。 - Mike Seymour

push_back 通过引用接收其参数。 - bames53

@OlivierD：为了使第一个版本工作，它必须（1）分配新空间（2）复制新元素（3）移动构造现有元素（4）销毁已移动的元素（5）按照那个顺序释放旧存储。 - Ben Voigt

@BenVoigt，如果容器完全忽略该属性，为什么还需要一个类型是CopyInsertable呢？ - OlivierD

Answer 9

来自23.3.6.5/1：如果新大小大于旧容量，则会导致重新分配。如果没有重新分配，插入点之前的所有迭代器和引用仍然有效。

由于我们是在末尾插入，如果向量未调整大小，则不会使任何引用无效。因此，如果向量的capacity() > size()，则保证可以工作；否则，保证是未定义的行为。

- Mark B

---

我相信规范实际上保证了这在任何情况下都能工作。不过我还在等待一个参考。 - bames53

问题中没有提到迭代器或迭代器安全。 - OlivierD

@OlivierD 迭代器部分在这里是多余的：我对引文中的“references”部分感兴趣。 - Mark B

它实际上是有保证安全的（请参见我的答案，push_back的语义）。 - Angew is no longer proud of SO