c++ - 在 C++ 中插入优先级队列时如何解决段错误

Question

我一直在尝试用 C++ 创建霍夫曼树。我有一个自定义的霍夫曼节点类和一个霍夫曼树类，其头文件和源文件内容如下所示:

这是我的 main() 函数:

#include <iostream>         // Includes the input and output stream header file.
#include <string>           // Includes the string library.
#include <exception>            // Includes the exceptions header file.
#include "HuffmanNode.h"        // Includes the Huffman node class and all its respective components.
#include "HuffmanTree.h"        // Includes the Huffman tree class and all its respective components.
#include <fstream>          // Includes the file stream header file.

using namespace FOOBAR;     // Declare the use of my custom made namespace.

int main(int argc, char* argv[]) {
    std::string input_file, output_file;

    try {
        std::cout << "" << std::endl;
        input_file = std::string(argv[1]);  output_file = std::string(argv[2]);
        HuffmanTree my_huffman_tree = HuffmanTree(/*fptr compare*/);    
        my_huffman_tree.generateMap(input_file);
        my_huffman_tree.createHuffmanNodes();   
        std::cout << "" << std::endl;
    }
    catch(std::exception e) {
        std::cout << "" << std::endl;
        std::cout << "Error: " << e.what() << std::endl; // Print out the exact nature of the error.
        std::cout << "" << std::endl;
        exit(0);    // Terminate program execution.
    }
    return 0;
}

这是我的霍夫曼节点头文件:

// Preprocessor directives that guard against redeclaration should image_manipulator.h be defined elsewhere in the program
#ifndef HUFFMANNODE_H 
#define HUFFMANNODE_H

// These are the included header files that are required for the execution of the program.
#include <memory>

// This is my custom namespace for the program.
namespace FOOBAR {
    class HuffmanNode {
        private:
            char character; int frequency;      // These are the constituents of each node i.e. consists of a character as well as a frequency.
            std::shared_ptr<HuffmanNode> left_node, right_node; // Left and right attributes for my left and right nodes.
        public:

            HuffmanNode(char the_char, int the_frequency);      // Declaration of default constructor.
            HuffmanNode(int the_frequency);             // Declaration of default constructor.
            HuffmanNode(const HuffmanNode& rhs);            // Copy constructor.
            HuffmanNode(const HuffmanNode&& rhs);           // Move constructior.
            HuffmanNode & operator=(const HuffmanNode& rhs);    // Copy assignment operator.
            HuffmanNode && operator=(const HuffmanNode&& rhs);  // Move assignment operator.
            char getCharacter() const;              // Retrieve a key in the map.
            int getFrequency() const;               // retrieve a value in the map.
            std::shared_ptr<HuffmanNode> getLeftNode();     // Fetch the left node.
            std::shared_ptr<HuffmanNode> getRightNode();        // Fetch the right node.
            ~HuffmanNode();                     // Destructor.

            // Declare other methods to be used here. 
    };
}

#endif

这是我的霍夫曼节点源文件:

#include "HuffmanNode.h"

namespace CHRTIN006 {

    // This is the implementation one of the Huffman Node constructor method.   
    HuffmanNode::HuffmanNode(char the_char, int the_frequency) {
        HuffmanNode::character = the_char;  HuffmanNode::frequency = the_frequency;
    }

    // This is the implementation one of the Huffman Node constructor method.   
    HuffmanNode::HuffmanNode(int the_frequency) {
        HuffmanNode::frequency = the_frequency;
    }

    // This is the implementation of the Huffman Node copy constructor.
    HuffmanNode::HuffmanNode(const HuffmanNode &rhs) {
        HuffmanNode::character = rhs.HuffmanNode::character;
        HuffmanNode::frequency = rhs.HuffmanNode::frequency;
    }

    // This is the implementation of the Huffman Node move constructor.
    HuffmanNode::HuffmanNode(const HuffmanNode &&rhs) {

    }

    // This is the implementation of the Huffman Node copy assignment operator.
    HuffmanNode& HuffmanNode::operator=(const HuffmanNode &rhs) {
        if(this == &rhs) {
            return *this;
        }

        HuffmanNode::character = rhs.HuffmanNode::character;
        HuffmanNode::frequency = rhs.HuffmanNode::frequency;
        return *this; 
    }

    // This is the implementation of the Huffman Node move assignment operator. 
    HuffmanNode && HuffmanNode::operator=(const HuffmanNode &&rhs) {

    }

    // This method will return the key of an entry in the map.
    char HuffmanNode::getCharacter() const{
        return HuffmanNode::character;
    }

    // This method will return the value of an entry in the map.
    int HuffmanNode::getFrequency() const{
        return HuffmanNode::frequency;
    }

    // Retrieve the left most node of that particular branch.
    std::shared_ptr<HuffmanNode> HuffmanNode::getLeftNode() {
        return HuffmanNode::left_node;
    }

    // Retrieve the right most node of that particular branch.
    std::shared_ptr<HuffmanNode> HuffmanNode::getRightNode() {
        return HuffmanNode::right_node;
    }

    // This is the implementation of the Huffman Node destructor.   
    HuffmanNode::~HuffmanNode() {

    }
}

这是我的哈夫曼树类的头文件内容:

// Preprocessor directives that guard against redeclaration should HuffmanTree.h be defined elsewhere in the program.
#ifndef HUFFMANTREE_H 
#define HUFFMANTREE_H

// These are the included header files that are required for the execution of the program.
#include <queue>        // For building the huffman tree.
#include "HuffmanNode.h"    // Includes the Huffman Node header file.
#include <unordered_map>    // Header file for my map that is going to store the respective frequencies of each letter.
#include <memory>       // For making use of smart pointers.    
#include <vector>       // For making use of vectors within the program.
#include <functional>       // For including the comparison method in the constructor of the queue.

// This is my custom namespace for the program.
namespace FOOBAR {
    class HuffmanTree {     // This is where my Huffman tree class starts.

        public:     // Objects an variables declared under this specifier are treated as being public.
            // Going to be used to determine how to order entries in the queue.
            typedef bool (*fptr)(const HuffmanNode&, const HuffmanNode&);       
            bool compare(const HuffmanNode& node_a, const HuffmanNode& node_b); /////////////////////////////

            HuffmanTree(/*fptr compare*/);          // Default constructor.
            HuffmanTree(const HuffmanTree& rhs);        // Copy constructor.
            HuffmanTree(const HuffmanTree&& rhs);       // Move constructior.
            HuffmanTree& operator=(const HuffmanTree& rhs); // Copy assignment operator.
            HuffmanTree&& operator=(const HuffmanTree&& rhs);   // Move assignment operator.
            ~HuffmanTree();                 // Destructor.

            // This method is going to count the number of occurrences of each letter.
            void generateMap(std::string file); 

            // Create Huffman nodes and populate them in the priority queue.
            void createHuffmanNodes();
            // Declare other methods to be used here.

        private:    // Objects an variables declared under this specifier are treated as being private. 
            std::shared_ptr<HuffmanNode> root_node; // The root node for the Huffman tree.
            std::unordered_map<char, int> my_map;   // Map containing the respective frequencies of each letter.
            std::unordered_map<char, int>::iterator my_iterator;    // Iterator for indexing every element in my map.
            // This is the queue that is going to have entries of my shared pointers.
            std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, fptr> my_queue;
    };      // This is where my Huffman tree class ends.
}           // End of namespace.

#endif



This is the source file for my Huffman Tree class:

#include "HuffmanTree.h"
#include <fstream>
#include <iostream>
#include <boost/lexical_cast.hpp>   // Includes the lexical cast functionlaity from the boost library.

namespace FOOBAR {

    // This is the implementation of the Huffman Tree default constructor method.   
    HuffmanTree::HuffmanTree(/*fptr compare*/) /*: my_queue(compare)*/  {
        root_node = nullptr;
    }

    // This is the implementation of the Huffman Tree copy constructor.
    HuffmanTree::HuffmanTree(const HuffmanTree& rhs) {
        root_node = rhs.root_node;
    }

    // This is the implementation of the Huffman Tree move constructor.
    HuffmanTree::HuffmanTree(const HuffmanTree&& rhs) {

    }

    // This is the implementation of the Huffman Tree copy assignment operator.
    HuffmanTree& HuffmanTree::operator=(const HuffmanTree& rhs) {
        if(this == &rhs) {
            return *this;
        }
        root_node = rhs.root_node;
        return *this;
    } 

    // This is the implementation of the Huffman Tree move assignment operator. 
    HuffmanTree&& HuffmanTree::operator=(const HuffmanTree&& rhs) {

    } 

    // This is the implementation of the compare method that is going to be used to determine how to order entries in the queue.
    bool compare(const HuffmanNode& node_a, const HuffmanNode& node_b) { ////////////////////////////////////////
        if(node_a.getFrequency() > node_b.getFrequency()) {
            return true;
        }
        else  {
            return false;
        }
    }

    // This method is going to count the number of occurrences of each letter.
    void HuffmanTree::generateMap(std::string file) {
        std::ifstream input_stream(file);   std::string line = "";
        if(input_stream.fail()) {
            std::cerr << "Error: Could not open the file specified." << std::endl; // Print this error message.
        }

        else {
            while(std::getline(input_stream, line)) {
                for(int i = 0; i < line.length(); i++) {
                    char my_character = line.at(i);
                    my_iterator = HuffmanTree::my_map.find(my_character);
                    if(my_iterator == my_map.end()) {
                        HuffmanTree::my_map.insert(std::make_pair(my_character, 1));
                    }
                    else {
                        my_iterator -> second++;
                    }
                }                   
            }       
        }   
    }

    void HuffmanTree::createHuffmanNodes() {
        for(my_iterator = my_map.begin(); my_iterator != my_map.end(); ++my_iterator) {
            HuffmanNode some_huffman_node = HuffmanNode(boost::lexical_cast<char>(my_iterator -> first), boost::lexical_cast<int>(my_iterator -> second));      
            //my_queue.push(some_huffman_node); <---- Causes Segfault error
        }
    }

    // This is the implementation of the Huffman Tree destructor.   
    HuffmanTree::~HuffmanTree() {
        HuffmanTree::root_node = nullptr;
    }
}

可以使用任何输入文本。

但是当我尝试推送一个新创建的 huffman 节点时，我收到以下错误:

Makefile:32: 目标“运行”的配方失败 make: * [run] 段错误(核心转储)**

过去3天我一直卡在这部分。有人可以帮我吗？提前谢谢你。

Answer 1

您正在使用:

std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, fptr> my_queue;
                                                           ^^^

fptr 只是一个typedef，来自

typedef bool (*fptr)(const HuffmanNode&, const HuffmanNode&);

这是段错误的根本原因。

取而代之的是，使用比较对象更容易观察:

struct CompareHuffmanNode {
    bool operator()(HuffmanNode& n1, HuffmanNode& n2)
    {
      return n1.getFrequency() > n2.getFrequency();
    }
};

并将您的priority_queue声明为

std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, CompareHuffmanNode> my_queue;