Huffman coding comparison

[bearophile]

> I'd like it to also return the popped item, a ElementType!Range, is this possible?
> Popping one item out is one of the most common operations I have to perform on an heap.

I have read some pages, trying to understand why your pop doesn't return the item.

In a page I have read:
>Pop returns void for the sake of speed: SGI FAQ, and to prevent exceptions that may be thrown by the objects copy constructor.<


A quotation from this page:
http://www.sgi.com/tech/stl/FAQ.html
>Why do the pop member functions return void? All of the STL's pop member functions (pop_back in vector, list, and deque; pop_front in list, slist, and deque; pop in stack, queue, and priority_queue) return void, rather than returning the element that was removed. This is for the sake of efficiency. If the pop member functions were to return the element that was removed then they would have to return it by value rather than by reference. (The element is being removed, so there wouldn't be anything for a reference to point to.) Return by value, however, would be inefficient; it would involve at least one unnecessary copy constructor invocation. The pop member functions return nothing because it is impossible for them to return a value in a way that is both correct and efficient.<


Time ago I have suggested about a possible enum boolean value defined inside nonvoid functions, that is true/false if the function result is used or not:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=97424
So this value can be used with a static if to compute the result. So such functions are like templates, they get copied in two (generic function pointers have to refer to the nornal version of the function that computes and returns the result).

A simpler solution is to use two different names for two functions. The most common operation is to pop an item from a heap and then to use it. So the pop() can return the popped item. And then the heap can define another method that just pops the top item and doesn't return it, it can be named for example "drop", something similar to this (I don't know if this is right):

/**
Pops the largest element (according to the predicate $(D less))
and returns it.
 */
    ElementType!Range pop()
    {
        enforce(_length);
        auto tmp = _store.front;
        enforce(_length);
        if (_length > 1)
            swap(_store.front, _store[_length - 1]);
        --_length;
        percolateDown(_store[0 .. _length]);        
        return tmp;
    }
    
/**
Drops the largest element (according to the predicate $(D less)).
 */
    void drop()
    {
        enforce(_length);
        if (_length > 1)
            swap(_store.front, _store[_length - 1]);
        --_length;
        percolateDown(_store[0 .. _length]);
    }


Bye,
bearophile