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]);
这样安全吗?
看起来 http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-close.html#526 解决了这个问题(或与之非常相似的问题)作为潜在的缺陷标准:
1) const引用所带的参数可以在执行过程中改变 的功能
示例:
给定 std::vector v:
v.insert(v.begin(), v[2]);
v[2] 可以通过移动向量的元素来改变
提议的解决方案是这不是缺陷:
vector::insert(iter, value) 需要工作,因为标准 不允许它不工作。
是的,它是安全的,并且标准库实现克服了重重困难才做到了这一点。
我相信实施者会以某种方式将此要求追溯到 23.2/11,但我不知道如何实现,也找不到更具体的东西。我能找到的最好的就是这篇文章:
http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771
检查 libc++ 和 libstdc++ 的实现表明它们也是安全的。
该标准甚至可以保证您的第一个示例是安全的。引用 C++11
[序列.reqmts]
3 在表 100 和 101 中...
表示序列容器类,X
表示包含a
类型元素的X
的值,...T
表示左值或 const 右值t
X::value_type
16 表 101 ...
表达式
返回类型a.push_back(t)
操作语义 附加void
的副本 要求:t.
应将T
转换为CopyInsertable
。 容器X
、basic_string
、deque
、list
vector
因此,尽管这并不完全是微不足道的,但实现必须保证在执行
push_back
时不会使引用无效。
第一个示例是否安全并不明显,因为
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
...
}
}
这不是标准的保证,但作为另一个数据点,
v.push_back(v[0])
对于 LLVM 的 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.
}
第一个版本绝对不安全:
对调用标准库容器或字符串成员函数获得的迭代器的操作可以访问底层容器,但不得修改它。 [注意:特别是,使迭代器无效的容器操作与与该容器关联的迭代器上的操作发生冲突。 — 尾注]
来自第 17.6.5.9 节
请注意,这是关于数据竞争的部分,人们通常将其与线程结合起来......但实际的定义涉及“发生在”关系,并且我没有看到多个副作用之间的任何顺序关系
push_back
在这里发挥作用,即引用失效似乎没有被定义为相对于复制构造新尾元素的顺序。
完全安全。
在你的第二个例子中
v.reserve(v.size() + 1);
这是不需要的,因为如果向量超出其大小,它将意味着
reserve
。
Vector 负责这件事,而不是你。
这是一个很好的可视化,显示在重新分配发生之前在缓冲区中创建了最后一个元素。
两者都是安全的,因为push_back将复制值,而不是引用。如果您存储指针,就向量而言仍然是安全的,但只需知道向量的两个元素指向相同的数据即可。
因此,push_back 的实现必须确保插入第 23.2.1 节一般容器要求
16
- a.push_back(t) 追加 t 的副本。要求:T 应可复制插入到 X 中。
- a.push_back(rv) 附加 rv 的副本。要求:T 应可移动插入到 X 中。
v[0]
的副本。通过反例,假设一个实现在复制之前重新分配,它肯定不会附加
v[0]
的副本,因此违反了规范。Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.
由于我们在末尾插入,因此如果向量未调整大小,则任何引用都不会失效。因此,如果向量的
capacity() > size()
那么它就保证可以工作,否则它就保证是未定义的行为。