当我打乱它时，指向向量中元素的指针会发生什么？
What happens to a pointer that points to an element in a vector when I shuffle it?
我有一个 std::vector<int> 和一个指针 int* 指向向量中的一个元素。假设指针指向第三个元素：pointer=&vector.at(2)。如果我现在打乱向量，它会仍然指向同一个元素（第三个）还是指向新的位置，以前是第三个的元素现在已经移动了？
之后，我想让这个问题更笼统一些：当向量被扩展或缩小时，指向向量中元素的指针和迭代器的行为如何？
如果矢量在没有调整大小的情况下被打乱，那么指针仍然指向相同的位置，该位置可能包含不同的元素。
如果将向量的大小调整为更大，则指针被称为 "invalidated" 并且它具有与未初始化指针相同的状态，即评估它或尝试读取它会导致未定义的行为。
指针将继续指向相同的位置，因此当您随机播放时，它会指向已移动到您指定位置的任何元素。
当您扩展向量的大小时，向量中的所有现有指针和迭代器都会变得无效。当您洗牌时，它们会继续指向相同的位置，该位置（通常）包含与洗牌前不同的值。
减小矢量的大小将取决于您的具体操作方式。一种方法是创建一个临时向量作为当前向量的副本，交换两者，然后销毁临时向量（通常是隐式地，让它超出范围）。如果你这样做，指针将进入临时，并在它被销毁时失效。
如果您使用 shrink_to_fit，那（可能）不会使 iterators/pointers 无效，但可能没有任何效果（标准指定它是一个非约束性请求，并且没有说明任何关于它的无效 iterators/pointers).
If I now shuffle the vector, will it still point to the same element (the third) or will it point the the new location where the used-to-third element has moved?
洗牌元素只是 copying/swapping 个元素通过数组中的各种 "buckets" 的问题，而您的指针只指向 "that fixed position in memory"。因此，它会一直指向数组中第三个位置的任何内容。
Then I like to make the question a little bit more general: How do pointer and iterators to elements in a vector behave when the vector is expanded, reduced or shuffled?
展开：全部iterators/references/pointers可能失效
减少：只要它们指向那些被删除之前的元素，它们将保持有效除非你做一个shrink_to_fit。 Iterators/pointers您删除的元素显然无效。
已打乱：您正在移动内容而不会导致重新分配，因此迭代器和引用仍然有效。
请注意，大多数 C++ 文档源中通常都会报告所有这些内容。
要记住向量的概念规则是它们只是动态数组周围的一个框，迭代器和指向元素的指针在概念上是相同的（实际上，std::vector<T>::iterator 可以是 typedef 对于 T *）。这同样适用于引用（伪装的指针）。
如果一个操作可能需要重新分配数组（=数组需要增长，或者您明确要求它收缩），那么所有 iterators/pointers/references 都将失效。如果删除元素，则指向向量 "conceptual end" 之后的指针将指向无效元素。如果大小保持不变，则不需要重新分配。
地址不会改变，但存储在该地址的值会。
#include <iostream>
#include <algorithm>
static void print_vec(const std::vector<int>& v) {
for (int i = 0; i < v.size(); ++i) {
std::cout << "Value: " << v.at(i) << " Address: " << &v.at(i) << std::endl;
}
}
static void shuffle_vec(std::vector<int>& v) {
auto engine = std::default_random_engine{};
std::shuffle(v.begin(), v.end(), engine);
}
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
std::cout << "Before Shuffle: " << std::endl;
print_vec(v);
shuffle_vec(v);
std::cout << "After Shuffle: " << std::endl;
print_vec(v);
return 0;
}
输出：
Before Shuffle:
Value: 1 Address: 0x16eb320
Value: 2 Address: 0x16eb324
Value: 3 Address: 0x16eb328
Value: 4 Address: 0x16eb32c
Value: 5 Address: 0x16eb330
After Shuffle:
Value: 3 Address: 0x16eb320
Value: 1 Address: 0x16eb324
Value: 5 Address: 0x16eb328
Value: 4 Address: 0x16eb32c
Value: 2 Address: 0x16eb330
实际上，向量是代码维护的连续数据缓冲区。每个元素都以类似数组的方式与下一个元素相邻设置。
当元素四处移动时，实际上，它们只是四处移动。指针指向该缓冲区中的位置，因此如果元素移动，实际上指针最终会指向其他地方。
不过，C++标准更为严格。当迭代器失效时，指向该位置的引用和指针也会失效。有许多操作可以使迭代器无效，这些操作在逻辑上不会改变数组实际上将成为同一缓冲区的事实。例如，如果您 .erase 一个元素，它会使该位置和之后的每个迭代器失效。
实际上，指向元素的指针最终会指向列表中的 "next" 元素，但标准并不保证这一点。
std::shuffle 不会使任何迭代器失效。它只是更改存储在那里的值。因此，指向第 n 个元素的指针在实践中和理论上仍将指向第 n 个元素。
扩展向量时，如果扩展超过.capacity()，所有迭代器都会失效。实际上它实际上将数据移动到一个新的位置，指针现在是悬挂指针。
减少时（通过.erase(it) 或.erase(a,b)），第一个参数处或之后的所有迭代器都将失效。这意味着对这些元素的引用和指针也将失效。实际上，它们现在将引用元素 "further down the chain"（如果存在此类元素），因为 .erase 都不会导致您的缓冲区重新分配，但标准不保证这一点。
还有其他操作可以使迭代器无效。 .shrink_to_fit() 可以，vector<X>(vec).swap(vec)（C++03 版本的收缩以适应）和 .reserve() 以及超出 .capacity() 大小的操作。
导致 .capcity() 改变的操作实际上会使您的指针在实践和理论上无效（或使指针指向末尾之外的指针）。
正如人们提到的，指针 "pointing" 指向内存中的某个位置，而不管那里的内容如何。实际上，您可以做一些非常有趣的事情，例如拥有一个包含 5 个元素的数组，但打印出位置 6 的值，即使它不在您的数组范围内。当你只声明它的长度为 5 个元素时，通过使用 array[5] 之类的东西访问数组，你最终会得到未定义的行为，本质上意味着可能会发生各种各样的事情，每个 运行 都可能返回完全不同的东西。请参阅下面 philipxy 的评论，以获取深入研究此概念的一些非常有用的链接。
因此，除了这些，您可以测试这里的一些代码，以实际看到这种效果。
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> values (5);
for (int i = 0; i < 5; i++)
values[i] = i;
for (int i = 0; i < 5; i++)
cout << values[i] << " ";
//Initialise the pointer so that it is pointing at the first element in vector
int* pointer = &values[0];
//By incrementing, we expect it to be pointing at the second element, which should be 1
pointer++;
cout << endl << "Pointer " << *pointer << endl;
//Reverse the order of the vector
reverse(values.begin(), values.end());
for (int i = 0; i < 5; i++)
cout << values[i] << " ";
cout << endl << "Pointer " << *pointer << endl;
return 0;
}
这段代码的结果是：
所以我们可以看到指针实际上并没有改变它指向的位置，但是内存中的那个单元格已经改变了，所以取消引用指针会产生不同的结果。
完全取决于"std::vector"的实现方式。我不确定是否有任何保证。
编辑：我刚刚了解到，C++ 标准确实比我想象的要严格得多（感谢 philipxy）。它确实指定 vector 必须在内部表现得像 C 数组。参见
http://herbsutter.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/
所以忘记其余的，至少如果你有一个至少符合 C++03 的实现。
例如，如果您将 std::vector 实现为链表（不太可能），那么改组、减小大小等将不会执行任何操作。
如果 "std::vector" 在内部使用类似 "int []" 的东西来存储它的元素（可能），那么重新排列元素可能意味着你的指针现在将指向一个与之前不同的值（什么Stevo 尝试过）。
如果在这种情况下调整向量的大小，那么它又完全取决于内部实现。调整大小 可能 分配新的 "int []" 并复制旧内容。在这种情况下，您的指针将指向现在未分配的内存，因此所有破坏都可能会崩溃。
如果你很幸运（取决于实现），那么将矢量缩小或增加 "small" 数量可能不会做任何事情（你的指针仍然有效）。
总结：不要那样做 ;-)（使用指针然后修改容器）。
阅读您调用的每个函数的文档。如果您不知道何时、如何调用它以及它的作用，那么您为什么要使用它？
一般来说，您不能依赖地址或数组等实现概念，也不能依赖测试程序。对于特定容器、迭代器和运算符的哪些元素，您必须阅读迭代器何时无效或未无效。
vector::shrink_to_fit 使所有迭代器失效
vector::resize 相同或更小会使超过新大小的迭代器完全无效
vector::resize 变大会使所有迭代器失效
来自 C++14 标准 [iterator.requirements.general]:
[P]ointers are iterators. The effect of dereferencing an iterator that
has been invalidated is undefined.
http://en.cppreference.com/w/cpp/container/vector
std::vector is a sequence container that encapsulates dynamic size arrays.
The elements are stored contiguously, which means that elements can be
accessed not only through iterators, but also using offsets on regular
pointers to elements.
iterator RandomAccessIterator
Iterator invalidation
swap, std::swap Never
shrink_to_fit Always
resize If the vector changed capacity, all of them.
If not, only those after the insertion point.
http://en.cppreference.com/w/cpp/container/vector/resize
Vector capacity is never reduced when resizing to smaller size because
that would invalidate all iterators, rather than only the ones that
would be invalidated by the equivalent sequence of pop_back() calls.
在 vector::shuffle iterators/pointers 之后没有变化，但对新值取消引用。
因为 shuffle 使用 swap 而迭代器不变：
http://en.cppreference.com/w/cpp/algorithm/random_shuffle
template< class RandomIt, class URNG >
void shuffle( RandomIt first, RandomIt last, URNG&& g );
RandomIt must meet the requirements of ValueSwappable and
RandomAccessIterator.
http://en.cppreference.com/w/cpp/concept/Iterator
Iterator is the base concept used by other iterator types:
InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator,
and RandomAccessIterator. Iterators can be thought of as an
abstraction of pointers.
[...]
`- lvalues of type It satisfy Swappable
[...]
http://en.cppreference.com/w/cpp/concept/ValueSwappable
Type T is ValueSwappable if
1) Type T satisfies the Iterator requirements
2) For any dereferencable object x of type T (that is, any value other
than the end iterator), *x satisfies the Swappable requirements.
http://en.cppreference.com/w/cpp/concept/Swappable
using std::swap;
swap(u, t);
After the call, the value of t is the value held by u before the call,
and the value of u is the value held by t before the call.
我有一个 std::vector<int> 和一个指针 int* 指向向量中的一个元素。假设指针指向第三个元素：pointer=&vector.at(2)。如果我现在打乱向量，它会仍然指向同一个元素（第三个）还是指向新的位置，以前是第三个的元素现在已经移动了？
之后，我想让这个问题更笼统一些：当向量被扩展或缩小时，指向向量中元素的指针和迭代器的行为如何？
如果矢量在没有调整大小的情况下被打乱，那么指针仍然指向相同的位置，该位置可能包含不同的元素。
如果将向量的大小调整为更大，则指针被称为 "invalidated" 并且它具有与未初始化指针相同的状态，即评估它或尝试读取它会导致未定义的行为。
指针将继续指向相同的位置，因此当您随机播放时，它会指向已移动到您指定位置的任何元素。
当您扩展向量的大小时，向量中的所有现有指针和迭代器都会变得无效。当您洗牌时，它们会继续指向相同的位置，该位置（通常）包含与洗牌前不同的值。
减小矢量的大小将取决于您的具体操作方式。一种方法是创建一个临时向量作为当前向量的副本，交换两者，然后销毁临时向量（通常是隐式地，让它超出范围）。如果你这样做，指针将进入临时，并在它被销毁时失效。
如果您使用 shrink_to_fit，那（可能）不会使 iterators/pointers 无效，但可能没有任何效果（标准指定它是一个非约束性请求，并且没有说明任何关于它的无效 iterators/pointers).
If I now shuffle the vector, will it still point to the same element (the third) or will it point the the new location where the used-to-third element has moved?
洗牌元素只是 copying/swapping 个元素通过数组中的各种 "buckets" 的问题，而您的指针只指向 "that fixed position in memory"。因此，它会一直指向数组中第三个位置的任何内容。
Then I like to make the question a little bit more general: How do pointer and iterators to elements in a vector behave when the vector is expanded, reduced or shuffled?
展开：全部iterators/references/pointers可能失效
减少：只要它们指向那些被删除之前的元素，它们将保持有效除非你做一个shrink_to_fit。 Iterators/pointers您删除的元素显然无效。
已打乱：您正在移动内容而不会导致重新分配，因此迭代器和引用仍然有效。
请注意，大多数 C++ 文档源中通常都会报告所有这些内容。
要记住向量的概念规则是它们只是动态数组周围的一个框，迭代器和指向元素的指针在概念上是相同的（实际上，std::vector<T>::iterator 可以是 typedef 对于 T *）。这同样适用于引用（伪装的指针）。
如果一个操作可能需要重新分配数组（=数组需要增长，或者您明确要求它收缩），那么所有 iterators/pointers/references 都将失效。如果删除元素，则指向向量 "conceptual end" 之后的指针将指向无效元素。如果大小保持不变，则不需要重新分配。
地址不会改变，但存储在该地址的值会。
#include <iostream>
#include <algorithm>
static void print_vec(const std::vector<int>& v) {
for (int i = 0; i < v.size(); ++i) {
std::cout << "Value: " << v.at(i) << " Address: " << &v.at(i) << std::endl;
}
}
static void shuffle_vec(std::vector<int>& v) {
auto engine = std::default_random_engine{};
std::shuffle(v.begin(), v.end(), engine);
}
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
std::cout << "Before Shuffle: " << std::endl;
print_vec(v);
shuffle_vec(v);
std::cout << "After Shuffle: " << std::endl;
print_vec(v);
return 0;
}
输出：
Before Shuffle:
Value: 1 Address: 0x16eb320
Value: 2 Address: 0x16eb324
Value: 3 Address: 0x16eb328
Value: 4 Address: 0x16eb32c
Value: 5 Address: 0x16eb330
After Shuffle:
Value: 3 Address: 0x16eb320
Value: 1 Address: 0x16eb324
Value: 5 Address: 0x16eb328
Value: 4 Address: 0x16eb32c
Value: 2 Address: 0x16eb330
实际上，向量是代码维护的连续数据缓冲区。每个元素都以类似数组的方式与下一个元素相邻设置。
当元素四处移动时，实际上，它们只是四处移动。指针指向该缓冲区中的位置，因此如果元素移动，实际上指针最终会指向其他地方。
不过，C++标准更为严格。当迭代器失效时，指向该位置的引用和指针也会失效。有许多操作可以使迭代器无效，这些操作在逻辑上不会改变数组实际上将成为同一缓冲区的事实。例如，如果您 .erase 一个元素，它会使该位置和之后的每个迭代器失效。
实际上，指向元素的指针最终会指向列表中的 "next" 元素，但标准并不保证这一点。
std::shuffle 不会使任何迭代器失效。它只是更改存储在那里的值。因此，指向第 n 个元素的指针在实践中和理论上仍将指向第 n 个元素。
扩展向量时，如果扩展超过.capacity()，所有迭代器都会失效。实际上它实际上将数据移动到一个新的位置，指针现在是悬挂指针。
减少时（通过.erase(it) 或.erase(a,b)），第一个参数处或之后的所有迭代器都将失效。这意味着对这些元素的引用和指针也将失效。实际上，它们现在将引用元素 "further down the chain"（如果存在此类元素），因为 .erase 都不会导致您的缓冲区重新分配，但标准不保证这一点。
还有其他操作可以使迭代器无效。 .shrink_to_fit() 可以，vector<X>(vec).swap(vec)（C++03 版本的收缩以适应）和 .reserve() 以及超出 .capacity() 大小的操作。
导致 .capcity() 改变的操作实际上会使您的指针在实践和理论上无效（或使指针指向末尾之外的指针）。
正如人们提到的，指针 "pointing" 指向内存中的某个位置，而不管那里的内容如何。实际上，您可以做一些非常有趣的事情，例如拥有一个包含 5 个元素的数组，但打印出位置 6 的值，即使它不在您的数组范围内。当你只声明它的长度为 5 个元素时，通过使用 array[5] 之类的东西访问数组，你最终会得到未定义的行为，本质上意味着可能会发生各种各样的事情，每个 运行 都可能返回完全不同的东西。请参阅下面 philipxy 的评论，以获取深入研究此概念的一些非常有用的链接。
因此，除了这些，您可以测试这里的一些代码，以实际看到这种效果。
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> values (5);
for (int i = 0; i < 5; i++)
values[i] = i;
for (int i = 0; i < 5; i++)
cout << values[i] << " ";
//Initialise the pointer so that it is pointing at the first element in vector
int* pointer = &values[0];
//By incrementing, we expect it to be pointing at the second element, which should be 1
pointer++;
cout << endl << "Pointer " << *pointer << endl;
//Reverse the order of the vector
reverse(values.begin(), values.end());
for (int i = 0; i < 5; i++)
cout << values[i] << " ";
cout << endl << "Pointer " << *pointer << endl;
return 0;
}
这段代码的结果是：
所以我们可以看到指针实际上并没有改变它指向的位置，但是内存中的那个单元格已经改变了，所以取消引用指针会产生不同的结果。
完全取决于"std::vector"的实现方式。我不确定是否有任何保证。
编辑：我刚刚了解到，C++ 标准确实比我想象的要严格得多（感谢 philipxy）。它确实指定 vector 必须在内部表现得像 C 数组。参见
http://herbsutter.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/
所以忘记其余的，至少如果你有一个至少符合 C++03 的实现。
例如，如果您将 std::vector 实现为链表（不太可能），那么改组、减小大小等将不会执行任何操作。
如果 "std::vector" 在内部使用类似 "int []" 的东西来存储它的元素（可能），那么重新排列元素可能意味着你的指针现在将指向一个与之前不同的值（什么Stevo 尝试过）。
如果在这种情况下调整向量的大小，那么它又完全取决于内部实现。调整大小 可能 分配新的 "int []" 并复制旧内容。在这种情况下，您的指针将指向现在未分配的内存，因此所有破坏都可能会崩溃。
如果你很幸运（取决于实现），那么将矢量缩小或增加 "small" 数量可能不会做任何事情（你的指针仍然有效）。
总结：不要那样做 ;-)（使用指针然后修改容器）。
阅读您调用的每个函数的文档。如果您不知道何时、如何调用它以及它的作用，那么您为什么要使用它？
一般来说，您不能依赖地址或数组等实现概念，也不能依赖测试程序。对于特定容器、迭代器和运算符的哪些元素，您必须阅读迭代器何时无效或未无效。
vector::shrink_to_fit 使所有迭代器失效
vector::resize 相同或更小会使超过新大小的迭代器完全无效
vector::resize 变大会使所有迭代器失效
来自 C++14 标准 [iterator.requirements.general]:
[P]ointers are iterators. The effect of dereferencing an iterator that has been invalidated is undefined.
http://en.cppreference.com/w/cpp/container/vector
std::vectoris a sequence container that encapsulates dynamic size arrays.
The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets on regular pointers to elements.iterator RandomAccessIterator
Iterator invalidation
swap, std::swapNever
shrink_to_fitAlways
resizeIf the vector changed capacity, all of them. If not, only those after the insertion point.
http://en.cppreference.com/w/cpp/container/vector/resize
Vector capacity is never reduced when resizing to smaller size because that would invalidate all iterators, rather than only the ones that would be invalidated by the equivalent sequence of
pop_back()calls.
在 vector::shuffle iterators/pointers 之后没有变化，但对新值取消引用。
因为 shuffle 使用 swap 而迭代器不变：
http://en.cppreference.com/w/cpp/algorithm/random_shuffle
template< class RandomIt, class URNG > void shuffle( RandomIt first, RandomIt last, URNG&& g );RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator.
http://en.cppreference.com/w/cpp/concept/Iterator
Iterator is the base concept used by other iterator types: InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, and RandomAccessIterator. Iterators can be thought of as an abstraction of pointers. [...]
`- lvalues of type It satisfy Swappable [...]
http://en.cppreference.com/w/cpp/concept/ValueSwappable
Type T is ValueSwappable if
1) Type T satisfies the Iterator requirements
2) For any dereferencable object x of type T (that is, any value other than the end iterator), *x satisfies the Swappable requirements.
http://en.cppreference.com/w/cpp/concept/Swappable
using std::swap; swap(u, t);After the call, the value of t is the value held by u before the call, and the value of u is the value held by t before the call.