When extracting an element in a vector using vector.front(), the element's pointer points to itself.

[expnext]

Describe the issue

When fetching the first Node from std::vector using vector.front(), it is found that the parent pointer of the first Node points to itself.

Simple Source Code

#include <iostream>
#include <vector>
class Node {
public:
    double time;
    double x;
    double y;
    double f;
    Node* parent;
    Node() = default;
    Node(const Node& other) = default;
    Node(double time, double x, double y, double f, Node* parent = nullptr) :time(time), x(x), y(y), f(f), parent(parent) {};
    bool operator<(const Node& other) const { return f < other.f; };
    ~Node() = default;
};
using Nodes = std::vector<Node>;
int main()
{
    Node root = Node(0, 0, 0, 10);
    Nodes open{};
    open.push_back(root);
    Node current{0,0,0,0};
    for (int i = 0; i < 5; ++i) {
        current = open.front();
        open.erase(open.begin());
        std::cout << i << ":" << std::endl;
        for (auto [x, y] : std::vector<std::pair<double, double>>{ {-1,0},{0,1},{1,0},{0,-1} }) {
            Node succ = Node(current.time + 1, current.x + x, current.y + y, current.f + 1, &current);
            std::cout << succ.parent << std::endl;
            std::cout << succ.parent->parent << std::endl;
            std::cout << std::endl;
            open.push_back(succ);
        }
    }
    return 0;
}

Expected behavior

When fetching the first Node from std::vector using vector.front(), the parent pointer of the first Node points to Node.parent.

STL version

```
Microsoft Visual Studio Community 2022 (64-bit) - Current
Version 17.12.3
/std:c++latest
```

[frederick-vs-ja]

What did you mean by "the first Node"?

current is modified in the loop (by current = open.front()), which makes current.parent points to current later. I'm not seeing anything wrong.

[expnext]

Simple Source Code

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
class Node {
public:
    double time;
    double x;
    double y;
    double f;
    Node* parent;
    Node() = default;
    Node(const Node& other) = default;
    Node(double time, int x, int y, double f, Node* parent = nullptr) :time(time), x(x), y(y), f(f), parent(parent) {};
    bool operator<(const Node& other) const { return f < other.f; };
    ~Node() = default;
};
using Nodes = std::vector<Node>;
bool findInList(std::pair<double,double> coord, const std::vector<std::pair<double,double>>& list) {
    for (auto & it : list) {
        if (fabsf(it.first - coord.first) < 0.001) {
            if (fabsf(it.second - coord.second) < 0.001) {
                return true;
            }
        }
    }
    return false;
}
bool compareNode(const Node* a, const Node* b) {
    return a->f < b->f;
}
int main()
{
    // use open
    auto root = Node(0, 0, 0, 10);
    Nodes open{};
    open.push_back(root);
    std::vector<std::pair<double,double>> close;
    Node current_node {};
    // use open ptr
    std::vector<Node*> open_ptrs;
    open_ptrs.push_back(&root);
    Node* current_ptr {};
    for (int i = 0; i < 5; ++i) {
        // use open
        std::sort(open.begin(), open.end());
        current_node = open.front();
        open.erase(open.begin());
        // use open ptr
        std::sort(open_ptrs.begin(), open_ptrs.end(), compareNode);
        current_ptr = open_ptrs.front();
        open_ptrs.erase(open_ptrs.begin());
        std::cout << i << ":" << std::endl;
        for (auto [x, y] : std::vector<std::pair<double, double>>{ {-1,0},{0,1},{1,0},{0,-1} }) {
            // use open
            Node succ = Node(current_node.time + 1, current_node.x + x, current_node.y + y, current_node.f + 1, &current_node);
            if (findInList(std::pair<double,double>(current_node.x + x, current_node.y + y), close)) {
                continue;
            }
            close.emplace_back(current_node.x + x, current_node.y + y);
            std::cout << succ.parent << std::endl;
            std::cout << succ.parent->parent << std::endl;
            std::cout << std::endl;
            open.emplace_back(succ);
            // use open ptr
            Node* succ_ptr = new Node(current_ptr->time+1, current_ptr->x + x, current_ptr->y + y, current_ptr->f + 1, current_ptr);
            std::cout << "use ptr:" << std::endl;
            std::cout << succ_ptr->parent << std::endl;
            std::cout << succ_ptr->parent->parent << std::endl;
            std::cout << std::endl;
            open_ptrs.emplace_back(succ_ptr);
        }
    }
    /*
    for (auto& node_ptr : open_ptrs) {
        delete node_ptr;
    }
    */
    return 0;
}

Quesition

What I want is the element with the smallest f-value in open, and when I use std::vector<Node>, when looping i=1, assuming current_node=Node(1,0,-1,11,0x5ffd50), 0x5ffd50 points to a Node(1,0,-1,11,0x5ffd50), i.e. current_node.parent = current.parent->parent. That's what I'm talking about pointing to itself. However, when I use std::vector<Node*>, * current_ptr=Node(1,0,-1,11,0x5ffdc0), points to Node(0,0,0,10,NULL), and that's what I want. Why do I get the correct result with std::vector<Node*>, but I get the wrong result with std::vector<Node>.

[expnext]

What did you mean by "the first Node"?

current is modified in the loop (by current = open.front()), which makes current.parent points to current later. I'm not seeing anything wrong.

open.front() is used in order to get the element with the smallest f-value.

[frederick-vs-ja]

This is probably unrelated to vector. Note that current_node is a single object which outlives the outer loop.

When using std::vector<Node>, your code stored pointer to current_node in new nodes, and assigned current_node with new nodes later. As a result, the value current_node.parent became &current_node later. When using std::vector<Node*>, your code assigned current_ptr with pointer to certain nodes, which didn't modify existing nodes.