Sign in to follow this  
harmon

changing data in a priority_queue

Recommended Posts

I have an STL priority queue full of nodes. These nodes have data in them, but I need to change some of that data after adding the node to the priority queue. Specifically, I am doing huffman compression and want to save the huffman code within each node. This can only be done after traversing the tree to each leaf node and then (hopefully) saving the code within the node. Only problem is that top() returns a const reference to the node. Any way to get around this? Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by harmon
I have an STL priority queue full of nodes. These nodes have data in them, but I need to change some of that data after adding the node to the priority queue. Specifically, I am doing huffman compression and want to save the huffman code within each node. This can only be done after traversing the tree to each leaf node and then (hopefully) saving the code within the node. Only problem is that top() returns a const reference to the node. Any way to get around this? Thanks.
I'm probably in over my head here, but I just thought I'd mention that in my A* implementation (which seems like a similar problem) I store indices to the nodes in the priority queue rather than the nodes themselves. The nodes are stored in a separate array in a fixed order. The data in the nodes can then be modified freely, the caveat being that if you change the sort term you have to remember to re-sort the corresponding index.

The indices themselves are sorted via a functor that is aware of the node array. I'm guessing that this method is also perhaps more efficient than sorting the nodes themselves.

This works fairly well for A*, but I don't know if it would be applicable to your situation.

Share this post


Link to post
Share on other sites
Thanks for the reply... I actually figured it out a different way. I did some research on "constness" and found that if I make the data member that I want to change "mutable" then I can change the mutable data even if the object I am accessing is const. For example:

mutable std::string code;

This data member will now be able to be changed even if it is within a const object

Share this post


Link to post
Share on other sites
Quote:
Original post by harmon
Thanks for the reply... I actually figured it out a different way. I did some research on "constness" and found that if I make the data member that I want to change "mutable" then I can change the mutable data even if the object I am accessing is const. For example:

mutable std::string code;

This data member will now be able to be changed even if it is within a const object

That's certainly one approach. Alternatively, you could just use a different data structure. Look into heaps, for instance [make_heap, push_heap, and pop_heap are all standard library functions].

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
Alternatively, you could just use a different data structure. Look into heaps, for instance [make_heap, push_heap, and pop_heap are all standard library functions].
Actually, I forgot to mention that I used the above functions rather than priority_queue in the A* implementation, primarily for greater control of memory allocation. In this case the underlying container is of course directly available, which solves the access problem you mention.

If speed is at all a concern however, sorting indices might still be a win in terms of efficiency. I realize this might require changing the implementation significantly though.

In any case, I'm not sure if this would be a good place to use the mutable keyword, for various reasons; if I were you I'd pursue one of the other alternatives mentioned instead. That's just me though (and I'm no expert on these topics).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this