Return to Revisions

Since you try to mimic the style of STL containers (at least, that's what your comments say), there are several things you could improve:

STL containers subtypes

Most of the STL containers have subtypes. I am pretty sure that some parts of the library uses these subtypes. So, if you want your code to work with the generic algorithms, you better add those subtypes:

• value_type: probably be an alias for T, or std::vector<T>::value_type.
• size_type: in your case, it would be unsigned long since it is the type you use for the size of your heap. Generally, the type std::size_t is used for size_type though. The best solution in your case would be std::vector<T>::size_type
• reference: often T&.
• There are many other subtypes. Look at the documentation for std::vector and see which one you can take from the underlying std::vector and which one you better let alone (for example, you don't provide anything to work with iterators and you don't provide any mechanism for allocators).

Size of the heap

First of all, you have two functions to obtain the size of your heap, count and get_size, which is redundant. count is there so that your heap looks like an STL container, however, the standard method name to get the size of a container is size not count. There is no need for the function get_size: it is a duplicate, it does not conform to STL naming, and it does not even conform to the case of your other functions.

The fact that the size of your heap does not correspond to the size of the underlying std::vector is rather troubling. When I write this:

BinaryHeap<int> foo(8);

I know that the memory has been reserved for 8 elements, but I would expect the size to be 0. Moreover, if I write this:

BinaryHeap<int> foo(8);
foo.FindXtrma();

I then have no idea what my value will be since the size is 8 and I did not control the inserted values. Generally speaking, you probably should use implement size like this to avoid surprises:

size_type size() const
{
    return data_.size();
}

There are probably other things which could be improved: make your BinaryHeap more like a STL container by enabling a support for allocators for example (you could forward the allocator stuff directly to the underlying std::vector). Also, instead of a real container, you could try to make your BinaryHeap a container adapter (like std::stack or std::queue) so that it can use a std::vector or a std::deque (or any confirming container).