Return to Revisions

Since you seem to be tryingy 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 standard library use these subtypes. Therefore, 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.

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

BinaryHeap<int> foo(8);

I know that enough 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 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 to avoid having to actually handle them). 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 an std::vector or an std::deque (or any conforming container).

Miscellaneous C++ stuff

It has been more than a year since the review, but it seems that it has some views, so I thought that it could be a good idea to complete it with some miscellaneous additional comments...

• You have template code in a .cpp file, this is really error-prone since templates are not compiled (their specializations are instantiated and compiled when needed). If you want to write a template library with separate interface and implementation, then put the interface in a .h file and include a .inl or .tpp file at the end of the header (these are the most common extensions for "implementation header files") with the implementation.

• You should const-qualify functions that do not alter the state of the class. For example, count (or size as I mentioned before) does not alter the heap and can be const-qualified to document that.

• Sometimes, your names should be more explicit. For example, template <class I> isn't explicit enough. It is easy to guess that it accepts iterators, but which kind of iterators? From the implementation, I think that it can accept forward iterators, so you should use names which reflect that fact:

    template <class ForwardIterator>
    int Heapify(ForwardIterator start, ForwardIterator end);