当我对一个向量进行洗牌时，指向其中一个元素的指针会发生什么？

Question

我有一个 std::vector<int> 和一个指向向量中一个元素的指针int*。假设指针指向第三个元素：pointer=&vector.at(2) 。如果我现在打乱了这个向量，指针还会指向同样的元素（第三个元素）吗？还是它将指向现在已经移动了的原来是第三个元素的新位置？

之后，我想让问题更加一般化：当向量扩展或缩小时，向量元素的指针和迭代器的行为如何？

- dani

---

指针是一个地址，一个内存位置。它指向其地址上的任何内容；除非指针本身被更改，否则它总是指向相同的地址。 - The Paramagnetic Croissant

花点时间思考一下指针是什么？指针是内存地址。无论你如何打乱向量，指针仍将指向相同的地址。 - Tony J

它们保持不变，这就是为什么它是一个问题的原因。 - iwolf

你不能在C++中移动对象。（虽然你可以有移动构造函数等，但这并不是在这个问题的上下文中“移动对象”的意思） - user253751

Answer 1

指针将继续指向同一个位置，因此当您洗牌时，它将指向已移动到您指定位置的任何元素。

当您扩展向量的大小时，所有现有的指针和迭代器都可能变得无效。当你洗牌时，它们仍然指向同一个位置，该位置通常会包含不同于洗牌之前的值。

缩小向量的大小将取决于您如何执行此操作。一种方法是创建一个临时向量作为当前向量的副本，交换两个向量，然后销毁临时向量（通常通过让它超出范围来隐式销毁）。如果您这样做，指针将指向临时向量，并在其被销毁时无效。

如果您使用shrink_to_fit，那么它（可能）不会使迭代器/指针无效，但可能没有任何效果（标准规定它是一个非绑定请求，并且不说它使迭代器/指针无效）。

- Jerry Coffin

---

“所有现有的指针和迭代器将变得无效”可能是正确的，但更准确的说法是“现有的指针和迭代器不能保证保持有效”。 - thang

@thang 这两个意思是相同的。 - philipxy

你如何在不使指针和迭代器失效的情况下实际使用 shrink_to_fit？ - T.C.

@T.C.：一些内存管理器可以直接在原地拆分已分配的块。其他管理器可能会忽略此请求--但无论如何，标准似乎都没有允许shrink_to_fit使迭代器失效的权限。 - Jerry Coffin

请参考LWG 2223中有关shrink_to_fit与迭代器失效问题的内容。 - dyp

Answer 2

如果现在对向量进行洗牌，那么指针还会指向同一个元素（第三个），还是会指向已移动的之前第三个元素的新位置？

洗牌元素只是通过数组中的各个“桶”进行复制/交换元素，而您的指针只是指向内存中的“该固定位置”。因此，它将继续指向数组中保持在第三个位置上的任何内容。

那么我想把问题再泛化一点：当向量扩展、缩小或洗牌时，指向向量元素的指针和迭代器会如何表现？

扩展：所有迭代器/引用/指针可能无效。

缩小：只要它们指向被移除的元素之前的元素，它们就会保持有效，除非您执行了shrink_to_fit。指向删除的元素的迭代器/指针显然是无效的。

洗牌：您正在移动元素而不会导致重新分配，因此迭代器和引用仍然有效。

请注意，所有这些信息通常都在大多数C++文档源中报告。

对于向量要记住的概念规则是，它们只是一个动态数组周围的盒子，而指向元素的迭代器和指针在概念上是相同的东西（实际上，std::vector<T>::iterator 可以是 T * 的 typedef）。引用也是指针的伪装。

如果一个操作可能需要重新分配数组（=数组需要增长，或者您明确要求它缩小），那么所有迭代器/指针/引用都将被失效。如果删除元素，则指向向量“概念末尾”后面的指针将指向无效的元素。如果大小保持不变，则不需要进行重新分配。

- Matteo Italia

Answer 3

如果向量在未调整大小的情况下被洗牌，则指针仍指向相同位置，该位置可能包含不同的元素。

如果将向量调整为更大的大小，则认为指针已经“失效”，并且具有与未初始化指针相同的状态，即评估它或尝试通过它读取会导致未定义行为。

- M.M

---

你怎么能说指针可能会指向不同的元素，而不知道它的内容呢？想象一下一个只有3的向量... - Theolodis

@Theolodis，我觉得很不可能有人会洗牌一个只包含3的向量。 - M.M

Answer 4

地址不会改变，但存储在该地址的值会发生变化。

#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

- davepmiller

Answer 5

实际上，向量是一种连续缓冲区数据的代码维护。每个元素都以类似数组的方式相邻设置。

在实践中，当元素移动时，它们只是移动。指针指向该缓冲区中的位置，因此如果元素移动，则实际上指针最终会指向其他位置。

然而，C++标准更加严格。当迭代器失效时，指向该位置的引用和指针也失效了。有许多操作可以使迭代器失效，但逻辑上并没有改变数组实际上仍是同一个缓冲区的事实。例如，如果你 .erase 一个元素，则会使该位置及之后的每个迭代器失效。

实际上，元素的指针将指向列表中的下一个元素，但标准不能保证这一点。 std::shuffle 不会使任何迭代器失效。它只是改变存储在那里的值。因此，第 n 个元素的指针在实践和理论上仍将指向第 n 个元素。

当扩展向量时，如果将其扩展到 .capacity() 之外，则所有迭代器都将失效。在实践中，它实际上将数据移动到新位置，指针现在是悬空指针。

当您缩小向量（通过 .erase(it) 或 .erase(a,b)）时，所有第一个参数及之后的迭代器都将失效。这意味着对这些元素的引用和指针也失效了。在实践中，它们现在将指向链条“更下面”的元素（如果存在这样的元素），因为 .erase 都不会导致缓冲区重新分配，但标准不能保证这一点。

还有其他操作可以使迭代器失效。 .shrink_to_fit() 可以，vector<X>(vec).swap(vec) （C++03 版本的 shrink-to-fit）也可以，以及增加大小超过 .capacity() 的操作。

导致 .capcity() 改变的操作实际上会使您的指针在实践和理论上都失效（或使指针指向超出末尾的位置）。

- Yakk - Adam Nevraumont

---

你为什么要多次说“在实践中”？（理论上也是这样的） - M.M

在理论上，vec.erase(vec.begin()) 使向量中任何元素的所有指针无效。但实际上，它们仍然指向元素，但标准并没有讨论“现在指向下一个元素”的半无效状态。除了使用一种病态语言实现来标记指针失效外，我想不到会破坏它的实现方式。 - Yakk - Adam Nevraumont

不遵循标准的代码具有未定义行为。提及未定义行为的典型实现是误导性和不相关的。（你这样做的目的是什么？） - philipxy

@philipxy 我可以想到三个好的理由和一个中等的理由。首先，识别哪些错误需要小心，因为测试无法发现：即使未定义，知道期望的行为也能告诉您很多信息。其次，我可能是错的：虽然引用和迭代器可能会无效，但标准中的连续性保证和指针算术保证可能使指针更加明确定义！第三，在每个实现都必须以某种方式行事的情况下，未来的标准可能会强制执行它。第四，有时你只需要欺骗一下。 - Yakk - Adam Nevraumont

Answer 6

阅读您调用的每个函数的文档。如果您不知道何时以及如何调用它以及它的作用，那么为什么要使用它？

一般来说，您不能依赖于实现概念，例如地址或数组，并且不能依赖于测试程序。您必须阅读特定容器、迭代器和运算符的哪些元素是或不是无效的迭代器。

vector::shrink_to_fit使所有迭代器无效。 vector::resize到相同或更小的大小只使新大小之外的迭代器无效。 vector::resize到更大的大小使所有迭代器无效。

来自C++14标准[iterator.requirements.general]: 指针是迭代器。使已失效的迭代器解引用的效果是未定义的。

http://en.cppreference.com/w/cpp/container/vector

std::vector是一个序列容器，封装了动态大小的数组。
元素被连续存储，这意味着元素不仅可以通过迭代器访问，还可以使用指向元素的普通指针的偏移量进行访问。

迭代器     随机访问迭代器

迭代器失效
swap, std::swap     永不失效
shrink_to_fit     总是失效
resize     如果向量更改了容量，则所有元素都会失效。 如果没有更改，则仅在插入点之后的元素失效。

http://en.cppreference.com/w/cpp/container/vector/resize

当调整大小到更小的尺寸时，向量容量不会减少，因为这样会使所有迭代器无效，而不仅仅是等效的pop_back()调用将会使它们无效的那些迭代器。

vector::shuffle之后，迭代器/指针不变，但解除引用会得到新值。

因为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

迭代器是其他迭代器类型的基本概念：输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器。迭代器可以被看作指针的抽象。 [...]

`- 类型为It的左值满足可交换性 [...]

http://en.cppreference.com/w/cpp/concept/ValueSwappable

如果满足以下条件，类型T就是ValueSwappable： 1. 类型T符合迭代器要求 2. 对于任何类型为T的可解引用对象x（即除了end迭代器之外的任何值），*x都符合Swappable要求。

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.

- philipxy

Answer 7

正如其他人所说，指针“指向”内存中的一个位置，而不管那里的内容是什么。实际上您可以做一些非常有趣的事情，比如有一个包含5个元素的数组，但打印出第6个位置的值，即使它不在数组的范围内。当您像array [5]这样访问一个长度为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;
}

这段代码的结果如下所示: 因此，我们可以看到指针实际上并没有改变其指向位置，但在内存中的该单元已被修改，所以解引用指针将产生不同的结果。

- Stevo

---

访问超出数组或向量大小的部分是未定义行为。你不能正确地说它会做任何特定的事情。 - philipxy

@Philipxy 是的，我认为那是一个合理的评论。我的意思只是尝试超出数组定义的区域不一定会被阻止，它会愉快地尝试使用单元格，无论成功与否。但如果这种说法是不正确的，请指出这种情况。我总是对学习更多感兴趣，然后我会相应地更新答案。 - Stevo

C/C++（等）标准定义了程序的行为，有些行为是未定义的。我们只能期望符合规定的行为。请阅读“as-if”规则。或者查看编程语言的规范和语义。请参考我之前的评论：你这样做的目的是什么？ - philipxy

@philipxy 我已经阅读完了你提供的未定义行为链接的第一页，并对接下来的两页非常感兴趣。As-if规则也是一个非常有趣的阅读材料，尽管在复制/移动的情况下它似乎有些滑稽可笑，但并不一定需要应用。非常感谢你提供这些信息的链接，虽然其中有一些概念对我来说还有些晦涩难懂，但真的非常有趣。我现在会根据所学内容编辑我的回答。 - Stevo

Answer 8

完全取决于“std::vector”是如何实现的。我不确定是否有任何保证。

编辑：我刚刚了解到，C++标准确实比我想象得严格得多（感谢philipxy）。它确实规定向量必须在内部像C数组一样运行。请参见

http://herbsutter.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/

“因此，如果你的实现符合至少C++03标准，就不要考虑其他的了。例如，如果你将std::vector实现为一个链表（不太可能），那么洗牌、缩小大小等操作将不起作用。如果“std::vector”在内部使用类似于“int []”来存储其元素（很可能），那么重新排列元素可能意味着您的指针现在指向的值与之前不同（Stevo试过）。如果在这种情况下调整向量的大小，则再次完全取决于内部实现。在这种情况下，调整大小可能会分配一个新的“int []”，并复制旧内容。在这种情况下，您的指针将指向未分配的内存，因此可能会发生所有混乱。如果你幸运的话（取决于实现），那么通过“小”的数量缩小或增大向量可能什么都不会发生（你的指针仍然有效）。总结：不要这样做;-)（使用指针，然后修改容器）。”

- Ingo Blackman

---

不，所有这些行为都是指定的。（请参见我的答案。） - philipxy