原文链接：

CTR51-CPP. Use valid references, pointers, and iterators to reference elements of a container

https://wiki.sei.cmu.edu/confluence/display/cplusplus/CTR51-CPP.+Use+valid+references%2C+pointers%2C+and+iterators+to+reference+elements+of+a+container

迭代器是指针的泛化，允许 C++ 程序可以在不同的数据结构 (容器) 以一种通用的方式运行。指针，引用和迭代器具有密切关系，在引用值时必须通过一个有效的迭代器，指针或者引用。任何时候存储一个指向一个容器内的元素的迭代器，引用或者指针都有风险，底层容器可能会被修改以致于已经存储的迭代器，指针或者引用失效。例如，当序列容器例如 std::vector 需要重新分配，已有的迭代器，指针和引用将会失效 [Kalev 99]。仅使用 有效指针 ，引用，或者迭代器来指向容器内的元素。

C++ 标准，[container.requirements.general]，第 12 段 [ISO/IEC 14882-2014] 陈述如下：

除非另有规定 (显式或者通过其他函数来定义一个函数)，调用一个容器的成员函数或者传递一个作为参数的容器到库函数不应该使指向该容器内对象的迭代器失效，或修改该容器内对象的值。

Iterators are a generalization of pointers that allow a C++ program to work with different data structures (containers) in a uniform manner [ISO/IEC 14882-2014]. Pointers, references, and iterators share a close relationship in which it is required that referencing values be done through a valid iterator, pointer, or reference. Storing an iterator, reference, or pointer to an element within a container for any length of time comes with a risk that the underlying container may be modified such that the stored iterator, pointer, or reference becomes invalid. For instance, when a sequence container such as std::vector requires an underlying reallocation, outstanding iterators, pointers, and references will be invalidated [Kalev 99]. Use only a valid pointer, reference, or iterator to refer to an element of a container.

The C++ Standard, [container.requirements.general], paragraph 12 [ISO/IEC 14882-2014] states the following:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

C++ 标准允许引用和指针对于同样的操作各自独立地失效，这可能导致一个失效的引用但是未失效的指针。然后，依赖这个却别使不安全的，因为指针指向的对象可能与预期的不同，即使指针是有效的。例如，检索一个指向容器内元素的指针，擦除这个元素 (当销毁底层对象时，引用失效)，然后在容器的相同位置插入一个新的元素，造成现存的指针现在指向一个有效但是不同的对象。所以，任何使一个指针或者一个引用失效的操作应该被当作会使指针和引用都失效来对待。

The C++ Standard allows references and pointers to be invalidated independently for the same operation, which may result in an invalidated reference but not an invalidated pointer. However, relying on this distinction is insecure because the object pointed to by the pointer may be different than expected even if the pointer is valid. For instance, it is possible to retrieve a pointer to an element from a container, erase that element (invalidating references when destroying the underlying object), then insert a new element at the same location within the container causing the extant pointer to now point to a valid, but distinct object. Thus, any operation that invalidates a pointer or a reference should be treated as though it invalidates both pointers and references.

以下容器函数会使迭代器，引用和指针在特定情况下失效。

The following container functions can invalidate iterators, references, and pointers under certain circumstances.

Class Function Iterators References/Pointers Notes
std::deque
insert(), emplace_front(), emplace_back(), emplace(), push_front(), push_back() X X 在双端队列中间的插入操作使所有指向该队列的元素的迭代器和引用失效。尾部插入使所有迭代器失效但对该队列内元素的引用有效性没有影响。 An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque but has no effect on the validity of references to elements of the deque. ([deque.modifiers], paragraph 1)
erase(), pop_back(), resize() X X 对双端队列最后一个元素的擦除操作只会使尾后迭代器和所有指向被擦除元素的迭代器和引用失效。对双端队列第一个元素的擦除操作只使被擦除的元素失效。对双端队列非第一个及非最后一个元素的擦除操作尾后迭代器和所有指向该队列内元素的迭代器及引用失效。An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque. ([deque.modifiers], paragraph 4)
clear() X X 销毁容器内的所有元素使所有的容器内元素的引用，指针和迭代器失效。可能也会使尾后迭代器失效。Destroys all elements in the container. Invalidates all references, pointers, and iterators referring to the elements of the container and may invalidate the past-the-end iterator. ([sequence.reqmts], Table 100)
std::forward_list
erase_after(), pop_front(), resize() X X erase_after 可能只使指向被擦除元素的迭代器和引用失效。erase_aftershall invalidate only iterators and references to the erased elements. ([forwardlist.modifiers], paragraph 1)
remove(), unique() X X 只使指向被擦除元素的迭代器和引用失效。Invalidates only the iterators and references to the erased elements. ([forwardlist.ops], paragraph 12 & paragraph 16)
clear() X X 销毁容器内的所有元素使所有的容器内元素的引用，指针和迭代器失效。可能也会使尾后迭代器失效。Destroys all elements in the container. Invalidates all references, pointers, and iterators referring to the elements of the container and may invalidate the past-the-end iterator. ([sequence.reqmts], Table 100)
std::list
erase(), pop_front(), pop_back(), clear(), remove(), remove_if(), unique() X X Invalidates only the iterators and references to the erased elements. ([list.modifiers], paragraph 3 and [list.ops], paragraph 15 & paragraph 19)
clear() X X 销毁容器内的所有元素使所有的容器内元素的引用，指针和迭代器失效。可能也会使尾后迭代器失效。Destroys all elements in the container. Invalidates all references, pointers, and iterators referring to the elements of the container and may invalidate the past-the-end iterator. ([sequence.reqmts], Table 100)
std::vector
reserve() X X 在reserve() 之后，如果重分配发生，capacity() 将大于或者等于 reverse 的参数值，否则，将等于 capacity() 先前的值。重分配使所有指向序列元素的引用，指针和迭代器失效。After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens and is equal to the previous value of capacity() otherwise. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. ([vector.capacity], paragraph 3 & paragraph 6)
insert(), emplace_back(), emplace(), push_back() X X 如果新的尺寸值大于旧的容量值，会造成重分配。如果没有发生重分配，所有在插入位置之前的迭代器和引用依然保持有效。所有在插入位置之后的迭代器和引用将失效。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.modifiers], paragraph 1). All iterators and references after the insertion point are invalidated.
erase(), pop_back(), resize() X X 在擦除位置及之后的迭代器和引用失效。Invalidates iterators and references at or after the point of the erase. ([vector.modifiers], paragraph 3)
clear() X X 销毁容器内的所有元素使所有的容器内元素的引用，指针和迭代器失效。可能也会使尾后迭代器失效。Destroys all elements in the container. Invalidates all references, pointers, and iterators referring to the elements of the container and may invalidate the past-the-end iterator. ([sequence.reqmts], Table 100)
std::set, std::multiset, std::map, std::multimap
erase(), clear() X X 只使指向被擦除元素的迭代器和引用失效。Invalidates only iterators and references to the erased elements. ([associative.reqmts], paragraph 9)
std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap
erase(), clear() X X 只使指向被擦除元素的迭代器和引用失效。Invalidates only iterators and references to the erased elements. ([unord.req], paragraph 14)
insert(), emplace() X insert 和emplace成员不会对迭代器有效性造成影响，如果 (N+n) < z * B_，其中 N 是 insert 操作之前的容器元素个数， n是已插入元素的个数， B 是容器的桶个数，_z 是容器的最大负载因子 。The insert and emplace members shall not affect the validity of iterators if (N+n) < z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor. ([unord.req], paragraph 15)
rehash(), reserve() X 重哈希会使迭代器失效，改变元素间的顺序，改变元素所在的桶，但是不会使指向元素的指针或者引用失效。Rehashing invalidates iterators, changes ordering between elements, and changes which buckets the elements appear in but does not invalidate pointers or references to elements. ([unord.req], paragraph 9)
std::valarray resize() X 改变大小操作使所有指向数组元素的指针和引用失效。Resizing invalidates all pointers and references to elements in the array. ([valarray.members], paragraph 12)

一个std::basic_string 对象也是一个适用这条规则的容器。更多关于 std::basic_string 容器的特定信息，查看 STR52-CPP. Use valid references, pointers, and iterators to reference elements of a basic_string 。

A std::basic_string object is also a container to which this rule applies. For more specific information pertaining to std::basic_string containers, see STR52-CPP. Use valid references, pointers, and iterators to reference elements of a basic_string.

不合规代码示例 Noncompliant Code Example

在这个不合规的代码示例中，在首次调用 insert() 时，pos 就失效了， 下标循环迭代有未定义行为.。

In this noncompliant code example, pos is invalidated after the first call to insert(), and subsequent loop iterations have undefined behavior.

1
2
3
4
5
6
7
8
9
#include <deque>

void f(const double *items, std::size_t count) {
  std::deque<double> d;
  auto pos = d.begin();
  for (std::size_t i = 0; i < count; ++i, ++pos) {
    d.insert(pos, items[i] + 41.0);
  }
}

合规方案 (Updated Iterator) Compliant Solution (Updated Iterator)

在这个合规方案中，每次迭代，pos 被重新分配了有效的迭代器，避免了未定义行为。

In this compliant solution, pos is assigned a valid iterator on each insertion, preventing undefined behavior.

1
2
3
4
5
6
7
8
9
#include <deque>

void f(const double *items, std::size_t count) {
  std::deque<double> d;
  auto pos = d.begin();
  for (std::size_t i = 0; i < count; ++i, ++pos) {
    pos = d.insert(pos, items[i] + 41.0);
  }
}

合规方案 (Generic Algorithm) Compliant Solution (Generic Algorithm)

这个合规方案用通用标准模板库算法 std::transform() 替换了手写循环。std::transform() 的函数调用接受转换的元素范围，被转换值存储的位置 (这里是一个用于在 d 的起始位置插入这些值的 std::inserter 对象)，应用的转换函数 (这里是一个简单的 lambda 表达式)。

This compliant solution replaces the handwritten loop with the generic standard template library algorithm std::transform(). The call to std::transform() accepts the range of elements to transform, the location to store the transformed values (which, in this case, is a std::inserter object to insert them at the beginning of d), and the transformation function to apply (which, in this case, is a simple lambda).

1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <deque>
#include <iterator>

void f(const double *items, std::size_t count) {
  std::deque<double> d;
  std::transform(items, items + count, std::inserter(d, d.begin()),
                 [](double d) { return d + 41.0; });
}

风险评估 Risk Assessment

使用指向容器内元素的无效的引用，指针，或者迭代器将导致未定义行为。

Using invalid references, pointers, or iterators to reference elements of a container results in undefined behavior.

Rule Severity Likelihood Remediation Cost Priority Level
CTR51-CPP High Probable High P6 L2

Automated Detection

Tool Version Checker Description
Parasoft C/C++test img CERT_CPP-CTR51-a Do not modify container while iterating over it
PVS-Studio img V783

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

SEI CERT C++ Coding Standard STR52-CPP. Use valid references, pointers, and iterators to reference elements of a basic_string

Bibliography

[ISO/IEC 14882-2014] Clause 23, “Containers Library” Subclause 24.2.1, “In General”
[Kalev 1999] ANSI/ISO C++ Professional Programmer’s Handbook
[Meyers 2001] Item 43, “Prefer Algorithm Calls to Handwritten Loops”
[Sutter 2004] Item 84, “Prefer Algorithm Calls to Handwritten Loops”

SEI CERT C++ Coding Standard > SEI CERT C++ Coding Standard > button_arrow_left.png SEI CERT C++ Coding Standard > SEI CERT C++ Coding Standard > button_arrow_up.png SEI CERT C++ Coding Standard > SEI CERT C++ Coding Standard > button_arrow_right.png