Forum Mjukvara Programmering och digitalt skapande Tråd Inlägg

C++ Priority_queue med pekare

1
Skriv svar
Permalänk
Medlem
●

C++ Priority_queue med pekare

Tja! Har en kurs i C++ och algoritmer där vi har fått i uppgift att göra en Huffman-kodning. När vi ska bygga trädstrukturen för att koda tecknen så ska vi använda oss utav en priority_queue.

Min tanke var att lagra HuffmanNoders pekare i denna kö. Såhär ser en HuffmanNod ut.
Den har även en överlagrad < operator.

 HuffmanNode::HuffmanNode(int character, int count, HuffmanNode* zero, HuffmanNode* one) {
    this->character = character;
    this->count = count;
    this->zero = zero;
    this->one = one;
}

Vi har en frekvenstabell som innehåller tecknet som nyckel och antalet förekomster som värde.

HuffmanNode* buildEncodingTree(const map<int, int> &freqTable) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, HuffmanNode> prio_que;
    for(auto const& element:freqTable){
        prio_que.push(new HuffmanNode(element.first,element.second));
    }
    treeBuilder(prio_que);
    return prio_que.top();
}

Denna kodsnutt ger ett fel i STL som säger:

/usr/include/c++/4.8/bits/stl_heap.h:313: error: no match for call to '(HuffmanNode) (HuffmanNode*&, HuffmanNode*&)'
*(__first + (__secondChild - 1))))
^

Hur ska man implementera för att det inte ska bli ett sånt här fel? Är det fel att lagra pekare? Bör jag istället bara lagra Noder?

Mvh
Dalgren

Visa signatur

Crosshair IV | 1055T @ 3.2 GHz | 4 GB Corsair dominator | Corsair H50 | Fractal Design R3 | 2x PowerColor 6950 2GB | Corsair HX 750W

Redigera
Citera flera Citera
Permalänk
Datavetare ★
●

Av minst två anledningar bör du lagra noder "by value" i stället för att spara pekare:

  1. roten till felet du nu fått är inte uppenbart för dig, risken är överhängande att du t.ex. orsakar minnesläckor eller andra fel

  2. din HuffmanNode har ett väldigt litet tillstånd, en av sakerna som gör C++ väldigt effektivt är hur det kan hantera "by value" typer + det är mycket enklare att resonera kring C++ program som har sina element "by value"

Det är möjligt att använda pekare, men då prioritetsköer måste kunna jämföra element för att sortera dem så måste du i det läget skapa en "proxy" typ som i stort sett bara finns där för att ge pekare-till-T egenskap av en typ som går att jämföra. Jämförelsen ska vara baserad på tillståndet av T, inte dess pekarvärde.

Har inte testat detta, men något åt det här hållet skulle vara möjligt

#include <vector>
#include <queue>
#include <map>
#include <memory>

using namespace std;

class HuffmanNode
{
        int character;
        int count;              // frequency of 'character'                                
public:
        friend class HuffmanNodePtr;
        HuffmanNode (int chr, int cnt) : character(chr), count(cnt) { }
};

// Proxy class to make it possible to compare pointer-to-HuffmanNode based on state
class HuffmanNodePtr
{
        unique_ptr<HuffmanNode> ptr;
public:
        HuffmanNodePtr (HuffmanNode * p) : ptr(p) { }

        bool operator<(const HuffmanNodePtr & rhs) const
        {
                return ptr->count < rhs.ptr->count;
        }

        operator HuffmanNode * () const
        {
                return ptr.get();
        }
};

HuffmanNode *
buildEncodingTree(const map<int, int> &freqTable)
{
        priority_queue<HuffmanNodePtr> prio_que;

        for (auto &element: freqTable)
        {
                // The "new Huf..." should really be replaced with                         
                // make_unque<HuffmanNode>(...), but requires C++14                        
                prio_que.push (new HuffmanNode(element.first, element.second));
        }
        //treeBuilder(prio_que);                                                           
        return prio_que.top();
}
Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Redigera
Citera flera Citera
1
Skriv svar