c++ - CPP :How to get the REAL element in a vector?

Question

我是 C++ 的新手，正在制作用 C++ 编写的哈夫曼树，但在生成树结构时遇到了麻烦。
这是我的代码:

    void Huffman::generateTree() {
        std::vector<Node> nodes;
        for (auto itr : freq) {
            nodes.push_back(*(new Node(itr.first, itr.second)));
        }
        while (nodes.size() > 1) {
            Node::sort(&nodes);
            Node leftNode = nodes.back();
            nodes.pop_back();
            Node rightNode = nodes.back();
            nodes.pop_back();
            Node newAnode = *new Node();
            newAnode.merge(&leftNode,&rightNode);
            nodes.push_back(newAnode);
        }
        root = &nodes.back();
        displayTree();
    }

最终合并为一个节点，但是左节点和右节点是错误的:
(出于调试目的，每个节点在创建时都有一个随机 ID，以便我发现问题。)

NODE freq26|id96
|-Left:
   NODE freq10|id17
   |-Left:
   |--ERROR:SELF freq10|id17
   |-Right:
      NODE freq16|id19
      |-Left:
         NODE freq10|id17
         |-Left:
         |--ERROR:SELF freq10|id17
         |-Right:
            NODE freq16|id19
            |-Left:
               NODE freq10|id17
               |-Left:
               |--ERROR:SELF freq10|id17
               |-Right:
                  NODE freq16|id19
...endless loop

就像输出一样，从第一个子节点开始，每个节点的左子节点都是它自己，右节点是另一个节点，但只有两个相互切换，最后循环。
我搜索并阅读了几篇关于此的帖子，我知道这可能是由 pop_back 引起的。和 push_back元素到 vector ，指针可能指向另一个元素，但我该如何解决呢？有没有办法在不受操作 vector 影响的 vector 中获取REAL元素？
这是我的节点的一些代码:

//header
    class Node {
    private:
        char value;
        int frequency;
        Node *left;
        Node *right;
        String code;
...
    class Huffman{
    private:
        Node * root;
        std::map<char,int> freq;// calculated frequency of data
        bool generated;
//source
    bool Node::sortMethod::operator()(const Node &nodeA, const Node &nodeB) {
        return nodeA.getFrequency() > nodeB.getFrequency();//getFrequency(): simply return node's frequency int
    }
    void Node::sort(std::vector<Node> *nodes) {
        std::sort(nodes->begin(), nodes->end(), sortMethod());
    }
    Node *Node::merge(Node *pLeft, Node *pRight) {
        left = pLeft;
        right = pRight;
        frequency = left->getFrequency() + right->getFrequency();
        return this;
    }

欢迎一切有帮助的，谢谢!

Answer 1

正如评论所暗示的那样，您需要停止认为 C++ 与 Java 相似，实际上并非如此。
C++ 中的对象具有明确的生命周期，并且该语言不会阻止您在对象不再存在后保留引用或指向对象的指针。
如果您希望某些东西比创建它的调用生命周期更长，则需要动态分配它，并且某些东西应该跟踪它的生命周期。默认为 std::unique_ptr ，当指针被销​​毁时，它会删除它所指向的内容。您可以通过移动 unique_ptr 来转让所有权。 .
不幸的是，您不能有效地拥有 std::priority_queue的 std::unique_ptr因为你不能移动 top , 和 pop不返回值。否则我会建议使用它而不是重新实现它。
我认为您不必在每个循环中对节点进行排序，因为合并的节点将始终具有最大的 frequency ，所以他们走在后面。

class Node;
// Aliases for types we will use
using NodePtr = std::unique_ptr<Node>;
using Nodes = std::vector<NodePtr>;

class Node {
private:
    char value;
    int frequency;
    NodePtr left;
    NodePtr right;
    std::string code;

    Node(char value, int frequency) : value(value), frequency(frequency) /*, code?*/{}
    Node(NodePtr left, NodePtr right) : /*value? ,*/ frequency(left->frequency + right->frequency), left(std::move(left)), right(std::move(right)) /*, code?*/{}
... 
};

// N.b. not members of Node
bool compareNodePtrs(const NodePtr & left, const NodePtr & right) {
    return left->getFrequency() > right->getFrequency();
}

void sortNodes(Nodes & nodes) {
    std::sort(nodes.begin(), nodes.end(), compareNodePtrs);
}

void Huffman::generateTree() {
    Nodes nodes;
    for (auto itr : freq) {
        nodes.emplace_back(std::make_unique<Node>(itr.first, itr.second));
    }
    sortNodes(nodes);
    while (nodes.size() > 1) {
        auto left = std::move(nodes.back());
        nodes.pop_back();
        auto right = std::move(nodes.back());
        nodes.pop_back();            
        nodes.emplace_back(std::move(left), std::move(right));
    }
    root = std::move(nodes.back());
    displayTree();
}