changing data in a priority_queue

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.

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

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

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).