对自定义元素向量进行排序时的意外（至少对我而言）行为

Question

我最近运行在实施某事时遇到了这个问题。我有一个自定义的树状结构，其中包含一个值和一个子向量。插入子节点时，我希望它们以随机顺序出现，并且我需要跟踪最后插入的元素以用于将来的某些操作。事实证明，如果我保存指向最后一个节点的向量的指针，在对向量进行排序后指针仍然有效，但它现在指向一个完全不同的向量。这是一个最小的例子：

#include <iostream>
#include <vector>
#include <algorithm>

struct Node {
    int value;
    std::vector<Node> nxt;

    bool operator<(const Node& other) {
        return value < other.value;
    }
    /* Having this custom swap function doesn't make a difference
    *friend void swap(Node& lhs, Node& rhs) {
    *    std::swap(lhs.value, rhs.value);
    *    lhs.nxt.swap(rhs.nxt);
    *}
    */
};


int main() {
    Node node1;
    node1.value = 1;
    Node node2;
    node2.value = 2;
    Node node3;
    node3.value = 3;
    Node node4;
    node4.value = 4;

    std::vector<Node> container;
    container.push_back(node2);
    container.push_back(node1);
    container.push_back(node4);
    container.push_back(node3);
    std::vector<Node>* node3_vec = &container.back().nxt;
    node3_vec->push_back(node1);
    std::cout << "Address of the vector: " << node3_vec << std::endl;
    std::cout << "Size of the vector: " << node3_vec->size() << std::endl;

    std::sort(container.begin(), container.end());

    std::cout << "Address of the vector post sort: " << node3_vec << std::endl;
    std::cout << "Size of the vector post sort: " << node3_vec->size() << std::endl;

    //Inside the container
    std::cout << "Value of the node inside the container: " << container[2].value << std::endl;
    std::cout << "Address of the vector: " << &container[2].nxt << std::endl;
    std::cout << "Size of the vector: " << container[2].nxt.size() << std::endl;
    return 0;
}

我试过一些自定义 std::swap 实现，但我似乎无法改变这种行为。我怎样才能使排序后指向向量的指针指向同一个向量？目前，我在排序后执行额外的搜索以找到所需的元素。

也有人可以向我指出一些解释此行为的文档吗？

Answer 1

每当您保存指针时，您就是在内存中保存下一个向量所在的地址。如果您对容器进行排序，元素将四处移动，并且另一个元素将在该地址结束。

就像你记得你的朋友住在街上的 4 号房子一样。然后你让街上的每个人都搬家，让他们保持秩序。

很可能会有其他人住在 4 号房，但不是您的朋友！

我不确定是否有关于此的任何文档，因为这是预期的！

Answer 2

在sort之后，原始指针node3_vec仍将指向container中的最后一个Node。在 sort 之后，这将是 node4 的副本，其中 node3 的副本曾经在排序之前。

对自定义元素向量进行排序时的意外（至少对我而言）行为

Unexpected (for me at least) behaviour when sorting a vector of custom elements

c++

sorting

swap

stdvector