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

Question

I recently run into this issues when implementing something. I have a custom Tree like struct which contains a value and a vector of children. When inserting child nodes, I expect them to come in a random order and I need to keep track of the last element inserted for some future operations. It turns out that if I save a pointer to the vector of the last node, after sorting the vector the pointer is still valid, but it now points to a completely different vector. Here is a minimal example:

#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;
}

I tried playing around with some custom std::swap implementations but I can't seem to change that behaviour. How can I make it so that after sorting, the pointer to the vector points to the same vector? At the moment, I perform an extra search after the sort to find the desired element.

Also could someone point me to some documentation that explains this behaviour?

Answer 1

After sort, the raw pointer node3_vec will still point the last Node in container. After the sort this will be a copy of node4 where a copy of node3 used to be before the sort.