从相同的向量中push_back元素是否安全?
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-closed.html#526解决了这个问题(或与它非常相似的东西)作为标准中的潜在缺陷:;
1)在执行该function期间,可以改变const引用所取的参数
例子:
鉴于std :: vector v:
v.insert(v.begin(),v [2]);
v [2]可以通过移动vector元素来改变
提议的决议是这不是一个缺陷:
vector :: insert(iter,value)是需要工作的,因为标准没有给它权限而不能工作。
是的,这是安全的,标准的库实现跳过这样做。
我相信实施者以某种方式将这个要求追溯到23.2 / 11,但我不知道如何,也找不到更具体的东西。 我能find的最好的是这篇文章:
http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771
检查libc ++和libstdc ++的实现,显示它们也是安全的。
标准保证你的第一个例子是安全的。 引用C ++ 11
[sequence.reqmts]
3在表100和101中,
X
表示序列容器类,a
表示包含typesT
元素的X
的值,…t
表示X::value_type
的左值或常量右值16表101 …
expression式
a.push_back(t)
返回typesvoid
操作语义附加t.
的副本t.
要求:T
应为CopyInsertable
入X
容器basic_string
,deque
,list
,vector
所以即使这不是微不足道的,实现必须保证在执行push_back
时不会使参考无效。
第一个例子是安全的,这是不明显的,因为最简单的push_back
实现将是首先重新分配vector,如果需要的话,然后复制引用。
但是,至less在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 ++是安全的 。
当需要重新分配内存时, 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. }
第一个版本绝对不安全:
通过调用标准库容器或string成员函数获得的迭代器上的操作可以访问基础容器,但不得修改它。 [注意: 特别是,使迭代器无效的容器操作与与该容器关联的迭代器上的操作发生冲突。 – 结束注意]
从第17.6.5.9节
请注意,这是关于数据竞赛的部分,人们通常会认为它与线程一起使用,但是实际的定义涉及到“发生在…之前”的关系,并且在push_back
的多个副作用之间没有看到任何顺序关系在这里起作用,即参照无效似乎不是被定义为有序复制构成新的尾部要素。
这是完全安全的。
在你的第二个例子中
v.reserve(v.size() + 1);
这是不需要的,因为如果vector超出它的大小,就意味着reserve
。
vector是负责这个东西,而不是你。
两者都是安全的,因为push_back将复制值,而不是参考。 如果你正在存储指针,就vector而言,它仍然是安全的,但是只要知道你的vector有两个元素指向相同的数据。
第23.2.1节一般容器要求
16
- a.push_back(t)追加t的副本。 要求:T应该是CopyInsertable到X.
- a.push_back(rv)追加rv的副本。 要求:T应该是MoveInsertable到X.
因此,push_back的实现必须确保插入v[0]
的副本 。 通过反例,假设一个在复制之前重新分配的实现,它不会附加v[0]
的副本,因此违反规范。
从23.3.6.5/1开始: 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.
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.
由于我们在最后插入, 如果vector没有resize,没有引用将会失效。 所以如果向量的capacity() > size()
那么它保证工作,否则保证是未定义的行为。