CPP:How 获取向量中的 REAL 元素？

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

和输出一样，从第一个子节点开始，每个节点的左子节点是自己，右子节点是另一个节点，但只有两个相互切换，最后循环。

我搜索并阅读了一些关于此的 post 我知道这可能是由 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::unique_ptr 的 std::priority_queue，因为您无法移动 top，而 pop 不会 return 值。否则我会建议使用它而不是重新实现它。

我认为您不必在每个循环中对节点进行排序，因为合并后的节点总是最大的 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();
}

CPP:How 获取向量中的 REAL 元素？

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

c++

vector

huffman-code