Jump to content
  • Advertisement
Sign in to follow this  
kirkd

STL Priority Queue

This topic is 4011 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to get a priority queue operating with some sample code (below), but I keep getting the following error on the line which declares the priority queue like this: priority_queue< vector< node >, greater<node> > q; Here's the error: main.cpp:124: error: no type named `value_type' in `struct std::greater<node>' This is example code I've pulled off the web, but I get the same error when using my code. Any idears?? -Kirk
//
// PQHUFF.CPP
//
// This program reads in all the characters from
// the file input.dat, then builds a Huffman
// encoding tree using an STL priority queue.  The
// resulting table is then printed out.
//
// If you have the HP version of the STL installed,
// you can build this program with Borland C++ 4.5
// using a command line like this:
//
//  bcc -ml -IC:\STL pqhuff.cpp
//
//
// Borland 4.x workarounds
//

#define __MINMAX_DEFINED
#pragma option -vi-

#include &lt;iostream.h&gt;
#include &lt;iomanip.h&gt;
#include &lt;fstream.h&gt;
#include &lt;vector.h&gt;
#include &lt;stack.h&gt;
#include &lt;cstring.h&gt;

//
// The node class is used to represent both leaf
// and internal nodes. leaf nodes have 0s in the
// child pointers, and their value member corresponds
// to the character they encode.  internal nodes
// don't have anything meaningful in their value
// member, but their child pointers point to
// other nodes.
//

struct node {
    int weight;
    unsigned char value;
    const node *child0;
    const node *child1;
//
// Construct a new leaf node for character c
//
    node( unsigned char c = 0, int i = -1 ) {
        value = c;
        weight = i;
        child0 = 0;
        child1 = 0;
    }
//
// Construct a new internal node that has
// children c1 and c2.
//
    node( const node* c0, const node *c1 ) {
        value = 0;
        weight = c0-&gt;weight + c1-&gt;weight;
        child0 = c0;
        child1 = c1;
    }
//
// The comparison operator used to order the
// priority queue.
//
    bool operator&lt;( const node &a ) const {
        return weight &lt; a.weight;
    }
    void traverse( string code = "" )  const;
};

//
// The traverse member function is used to
// print out the code for a given node.  It
// is designed to print the entire tree if
// called for the root node.
//

void node::traverse( string code ) const
{
    if ( child0 ) {
        child0-&gt;traverse( code + "0" );
        child1-&gt;traverse( code + "1" );
    } else {
        cout &lt;&lt; " " &lt;&lt; value &lt;&lt; "      ";
        cout &lt;&lt; setw( 2 ) &lt;&lt; weight;
        cout &lt;&lt; "     " &lt;&lt; code &lt;&lt; endl;
    }
}

//
// This routine does a quick count of all the
// characters in the input file.  I skip the
// whitespace.
//

void count_chars( int *counts )
{
    for ( int i = 0 ; i &lt; 256 ; i++ )
        counts[ i ] = 0;
    ifstream file( "input.dat" );
    if ( !file ) {
        cerr &lt;&lt; "Couldn't open the input file!\n";
        throw "abort";
    }
    file.setf( ios::skipws );
    for ( ; ; ) {
        unsigned char c;
        file &gt;&gt; c;
        if ( file )
            counts[ c ]++;
        else
            break;
   }
}

main()
{
    int counts[ 256 ];

    count_chars( counts );
    priority_queue&lt; vector&lt; node &gt;, greater&lt;node&gt; &gt; q;
//
// First I push all the leaf nodes into the queue
//
    for ( int i = 0 ; i &lt; 256 ; i++ )
        if ( counts[ i ] )
            q.push( node( i, counts[ i ] ) );
//
// This loop removes the two smallest nodes from the
// queue.  It creates a new internal node that has
// those two nodes as children. The new internal node
// is then inserted into the priority queue.  When there
// is only one node in the priority queue, the tree
// is complete.
//

    while ( q.size() &gt; 1 ) {
        node *child0 = new node( q.top() );
        q.pop();
        node *child1 = new node( q.top() );
        q.pop();
        q.push( node( child0, child1 ) );
    }
//
// Now I dump the results
//
    cout &lt;&lt; "Char  Symbol   Code" &lt;&lt; endl;
    q.top().traverse();
    return 1;
}



Share this post


Link to post
Share on other sites
Advertisement
You might take another look at the template parameters for priority_queue (documentation can be found here).

Share this post


Link to post
Share on other sites
Not sure if this is even on the right path, but if I change my operator< to read:

bool operator<( const SearchNode &sn ) const
{ return ( this->F() < sn.F() ); }

I start getting this error:

..\SearchNode.h:57: error: passing `const SearchNode' as `this' argument of `long int SearchNode::F()' discards qualifiers
..\SearchNode.h:57: error: passing `const SearchNode' as `this' argument of `long int SearchNode::F()' discards qualifiers


It seems the STL wants this type of declaration, but why am I not allowed to use it??

Share this post


Link to post
Share on other sites
Quote:
Original post by kirkd
Not sure if this is even on the right path, but if I change my operator< to read:

bool operator<( const SearchNode &sn ) const
{ return ( this->F() < sn.F() ); }

I start getting this error:

..\SearchNode.h:57: error: passing `const SearchNode' as `this' argument of `long int SearchNode::F()' discards qualifiers
..\SearchNode.h:57: error: passing `const SearchNode' as `this' argument of `long int SearchNode::F()' discards qualifiers


It seems the STL wants this type of declaration, but why am I not allowed to use it??
F() needs to be declared constant (read this if you're not sure why).

Were you able to fix the other problem?

Share this post


Link to post
Share on other sites
Having const trailing a method means that it guarantees it won't change anything internally. Is function F a const function? Otherwise, your const operator will be calling a non-const function, which isn't kosher. Declare F as const if need be, and if really need be, change some members to mutable. But that's usually a sign of bad design.

Edit: Too slow!

Share this post


Link to post
Share on other sites
Holy cow, that did the trick! I made F() const which is fine because it is an accessor function.

Thank you for your help, everyone!

-Kirk

Share this post


Link to post
Share on other sites
What is the Huffman tree used for?
I ask this because I needed one which was guaranteed to give the same results no matter which machine it ran on, yet stl pqueue does not give this behaviour. AS it is not defined if two nodes have the same value which will come to the head first.

Share this post


Link to post
Share on other sites
The article I extracted to code from is here: http://www.dogma.net/markn/articles/pq_stl/priority.htm

It was targeted toward data compression, but I was just looking for an example of how to declare the priority queue such that the lowest valued items is at the top. I'm applying it to graph search and coding the A* algorithm

-Kirk

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!