1
\$\begingroup\$

This heap will be used for A* search pathfinding in my 2D isometric game engine. It uses lambda functions (instead of std::less or std::greater) to allow me to dictate min-heap or max-heap more dynamically. It also uses lambda functions for FindByKey, ReplaceByKey, and RemoveByKey so that the search key can differ from the compare key (for example: sorting by priority, but searching by name).

Typical use:

typedef struct test_s {
    int priority;
    std::string name;
    test_s(): priority(rand() % 100), name("DEFAULT_TEST") {};
} test_t;

auto max = [](test_t & a, test_t & b) { return b.priority > a.priority; };
auto equls = [](test_t & a, std::string key) { return a.name == key; };
eHeap<test_t, decltype(max)> priorityQueue(max);
test_t * result;

priorityQueue.PushHeap(test_t());    
if (result = priorityQueue.FindByKey("DEFAULT_TEST", equls) != nullptr)
    printf("Found %s\n", result->name);
// etc

The primary data structure is a c-style array because I wanted the practice, so the heap arrangement only works on contiguous memory blocks. Dynamic memory allocation for the array occurs in block sizes given by the granularity as seen in Resize(const int newHeapSize) to reduce allocation overhead. The allocated memory is only freed on ClearAndResize(const int newHeapSize), ~eHeap(), or if the public Free() is called.

I've unit-tested this with POD types, std::string, and std::unique_ptr<int> and it executes all functions without issue.

Question: Are there any memory leak/corruption issues I'm not seeing?

#ifndef EVIL_HEAP_H
#define EVIL_HEAP_H

#include <new.h>        // std::move
#include <utility>      // std::swap

#define DEFAULT_HEAP_SIZE 1024
#define DEFAULT_HEAP_GRANULARITY 1024

//********************************************
//              eHeap
// The template compare function a user creates 
// dictates if this is a MaxHeap or a MinHeap.
// Does not allocate until a new element is added.
// This copies/moves pushed data, so changing 
// the source data will not affect this heap.
// This class only works with contiguous memory.
//*******************************************
template <class type, class lambdaCompare>
class eHeap {
public:

    typedef eHeap<type, lambdaCompare> heap_t;

                            eHeap() = delete;                                                           // disallow instantiation without lambdaCompare object      
                            eHeap(lambdaCompare & compare, const int initialHeapSize = DEFAULT_HEAP_SIZE);// relaced default constructor
                            eHeap(lambdaCompare & compare, const type * data, const int numElements);   // heapify copy constructor 
                            eHeap(lambdaCompare & compare, type * data, const int numElements);         // heapify move constructor 
                            eHeap(const eHeap<type, lambdaCompare> & other);                            // copy constructor
                            eHeap(eHeap<type, lambdaCompare> && other);                                 // move constructor
                            ~eHeap();                                                                   // destructor

    heap_t                  operator+(const eHeap<type, lambdaCompare> & other);                        // copy merge
    heap_t                  operator+(eHeap<type, lambdaCompare> && other);                             // move merge
    heap_t &                operator+=(const eHeap<type, lambdaCompare> & other);                       // copy meld
    heap_t &                operator+=(eHeap<type, lambdaCompare> && other);                            // move meld
    heap_t &                operator=(eHeap<type, lambdaCompare> other);                                // copy and swap assignement
    const type * const      operator[](const int index) const;                                          // debug const content access   

    const type * const      PeekRoot() const;
    void                    PushHeap(const type & data);
    void                    PushHeap(type && data);
    void                    PopRoot();
    void                    ReplaceRoot(const type & data);
    void                    ReplaceRoot(type && data);

    // DEBUG: universal/forwarding references
    template<typename DataMember, typename lambdaEquals>
    const type * const      FindByKey(DataMember && key, lambdaEquals & equals) const;  

    template<typename DataMember, typename lambdaEquals>
    bool                    RemoveByKey(DataMember && key, lambdaEquals & equals);

    template<typename DataMember, typename lambdaEquals>
    bool                    ReplaceByKey(DataMember && oldKey, type & newData, lambdaEquals & equals);

    template<typename DataMember, typename lambdaEquals>
    bool                    ReplaceByKey(DataMember && oldKey, type && newData, lambdaEquals & equals);

    int                     Size() const;
    bool                    IsEmpty() const;

    // memory management
    size_t                  Allocated() const;
    void                    SetGranularity(const int newGranularity);
    void                    Free();
    void                    Resize(const int newHeapSize);
    void                    Clear();
    void                    ClearAndResize(const int newHeapSize);

private:

    void                    Allocate(const int newHeapSize);
    void                    Heapify();
    void                    SiftUp(const int index);
    void                    SiftDown(const int index);

private:

    type *                  heap;           
    lambdaCompare           compare;
    int                     numElements;
    int                     granularity;
    int                     heapSize;
};

//***************
// eHeap::eHeap
// default constructor
//*****************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare>::eHeap(lambdaCompare & compare, const int initialHeapSize) 
    : compare(compare),
      numElements(0),
      granularity(DEFAULT_HEAP_GRANULARITY),
      heapSize(initialHeapSize),
      heap(nullptr) 
{
}

//***************
// eHeap::eHeap
// heapify copy constructor
// only works on contiguous memory
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare>::eHeap(lambdaCompare & compare, const type * data, const int numElements) 
    : compare(compare),
      numElements(numElements),
      granularity(DEFAULT_HEAP_GRANULARITY)
{
    int mod;
    int i;

    mod = numElements % granularity;
    if (numElements > 0 && !mod) {
        heapSize = numElements;
    } else {
        heapSize = numElements + granularity - mod;
    }

    if (data == nullptr) {
        heap = nullptr;
        return;
    }
    heap = new type[heapSize];
    for (i = 0; i < numElements; i++)
        heap[i] = data[i];

    Heapify();
}

//***************
// eHeap::eHeap
// heapify move constructor
// only works on contiguous memory
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare>::eHeap(lambdaCompare & compare, type * data, const int numElements)
    : compare(compare),
    numElements(numElements),
    granularity(DEFAULT_HEAP_GRANULARITY)
{
    int mod;
    int i;

    mod = numElements % granularity;
    if (numElements > 0 && !mod) {
        heapSize = numElements;
    }
    else {
        heapSize = numElements + granularity - mod;
    }

    if (data == nullptr) {
        heap = nullptr;
        return;
    }
    heap = new type[heapSize];
    for (i = 0; i < numElements; i++)
        heap[i] = std::move(data[i]);

    Heapify();
}

//***************
// eHeap::eHeap
// copy constructor
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare>::eHeap(const eHeap<type, lambdaCompare> & other) 
    : compare(other.compare),
      numElements(other.numElements),
      granularity(other.granularity),
      heapSize(other.heapSize)
{
    int i;
    heap = new type[heapSize];
    for (i = 0; i < heapSize; i++)
        heap[i] = other.heap[i];
}

//***************
// eHeap::eHeap
// move constructor
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare>::eHeap(eHeap<type, lambdaCompare> && other) 
    : compare(other.compare),
      numElements(0),
      granularity(DEFAULT_HEAP_GRANULARITY),
      heapSize(DEFAULT_HEAP_SIZE),
      heap(nullptr) 
{
    std::swap(numElements, other.numElements);
    std::swap(granularity, other.granularity);
    std::swap(heapSize, other.heapSize);
    std::swap(heap, other.heap);
}

//***************
// eHeap::~eHeap
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare>::~eHeap() {
    Free();
}

//***************
// eHeap::operator+
// merge, copies originals
// DEBUG: cannot be const function because the invoked heapify copy constructor is not const
//****************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare> eHeap<type, lambdaCompare>::operator+(const eHeap<type, lambdaCompare> & other) {
    int sumElements; 
    int i, j;
    type * newData; 

    sumElements = numElements + other.numElements;
    if (!sumElements)
        return eHeap<type, decltype(compare)>(compare);

    newData = new type[sumElements];
    if (heap != nullptr) {
        for (i = 0; i < numElements; i++)
            newData[i] = heap[i];
    }
    if (other.heap != nullptr) {
        for (/*i == numElements,*/ j = 0; j < other.numElements; i++, j++)
            newData[i] = other.heap[j];
    }

    return eHeap<type, lambdaCompare>(compare, newData, sumElements);
}

//***************
// eHeap::operator+
// merge, moves from originals
// DEBUG: cannot be const function because the invoked heapify move constructor is not const
//****************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare> eHeap<type, lambdaCompare>::operator+(eHeap<type, lambdaCompare> && other) {
    int sumElements;
    int i, j;
    type * newData;

    sumElements = numElements + other.numElements;
    if (!sumElements)
        return eHeap<type, decltype(compare)>(compare);

    newData = new type[sumElements];
    if (heap != nullptr) {
        for (i = 0; i < numElements; i++)
            newData[i] = std::move(heap[i]);
    }
    if (other.heap != nullptr) {
        for (/*i == numElements,*/ j = 0; j < other.numElements; i++, j++)
            newData[i] = std::move(other.heap[j]);
    }

    return eHeap<type, lambdaCompare>(compare, newData, sumElements);
}

//***************
// eHeap::operator+=
// meld, moves from source
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare> & eHeap<type, lambdaCompare>::operator+=(eHeap<type, lambdaCompare> && other) {
    int i;

    if (other.heap == nullptr)
        return *this;

    if (heap == nullptr) {
        Allocate(other.heapSize);
    } else if (numElements + other.numElements > heapSize) {
        Resize(heapSize + other.numElements);
    }

    for (i = 0; i < other.numElements; i++)
        heap[i + numElements] = std::move(other.heap[i]);

    numElements += other.numElements;
    Heapify();
    return *this;
}

//***************
// eHeap::operator+=
// meld, preserves source
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare> & eHeap<type, lambdaCompare>::operator+=(const eHeap<type, lambdaCompare> & other) {
    int i;

    if (other.heap == nullptr)
        return *this;

    if (heap == nullptr) {
        Allocate(other.heapSize);
    } else if (numElements + other.numElements > heapSize) {
        Resize(heapSize + other.numElements);
    }

    for (i = 0; i < other.numElements; i++)
        heap[i + numElements] = other.heap[i];

    numElements += other.numElements;
    Heapify();
    return *this;
}

//***************
// eHeap::operator=
// copy and swap assignement
//***************
template<class type, class lambdaCompare>
inline eHeap<type, lambdaCompare> & eHeap<type, lambdaCompare>::operator=(eHeap<type, lambdaCompare> other) {
    std::swap(numElements, other.numElements);
    std::swap(granularity, other.granularity);
    std::swap(heapSize, other.heapSize);
    std::swap(heap, other.heap);
    // DEBUG: lambdaCompare closure object swap is omitted because both eHeaps already contain relevant instances,
    // as well as to avoid invoking deleted default lambda constructor
    return *this;
}

//***************
// eHeap::operator[]
//***************
template<class type, class lambdaCompare>
inline const type * const eHeap<type, lambdaCompare>::operator[](const int index) const {
    return (heap == nullptr || index >= numElements || index < 0) ? nullptr : &heap[index];
}

//***************
// eHeap::PeekRoot
//***************
template<class type, class lambdaCompare>
inline const type * const eHeap<type, lambdaCompare>::PeekRoot() const {
    return heap == nullptr ? nullptr : &heap[0];
}

//***************
// eHeap::PushHeap
//***************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::PushHeap(const type & data) {
    if (heap == nullptr) {
        Allocate(heapSize);
    } else if (numElements + 1 >= heapSize) {
        Resize(heapSize + 1);
    }
    heap[numElements] = data;
    SiftUp(numElements);
    numElements++;
}

//***************
// eHeap::PeekRoot
// emplace and move
// assumes the given type has a move assignment operator
//***************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::PushHeap(type && data) {
    if (heap == nullptr) {
        Allocate(heapSize);
    } else if (numElements + 1 >= heapSize) {
        Resize(heapSize + 1);
    }
    heap[numElements] = std::move(data);
    SiftUp(numElements);
    numElements++;
}

//***************
// eHeap::PopRoot
//***************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::PopRoot() {
    if (heap == nullptr) {
        return;
    } else if (numElements == 1) {
        Clear();
        return;
    }
    numElements--;
    std::swap(heap[0], heap[numElements]);
    SiftDown(0);
}

//***************
// eHeap::ReplaceRoot
//***************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::ReplaceRoot(const type & data) {
    if (heap == nullptr) {
        PushHeap(data);
        return;
    } 
    heap[0] = data;
    SiftDown(0);
}

//***************
// eHeap::ReplaceRoot
// emplace and move
// assumes the given type has a proper move assignment operator
//***************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::ReplaceRoot(type && data) {
    if (heap == nullptr) {
        PushHeap(std::move(data));
        return;
    }
    heap[0] = std::move(data);
    SiftDown(0);
}

//***************
// eHeap::FindByKey
// search keys can differ from compare keys
// returns pointer to the first match regardless of duplicates
// returns nullptr if key not found
//***************
template<class type, class lambdaCompare>
template<typename DataMember, typename lambdaEquals>
inline const type * const eHeap<type, lambdaCompare>::FindByKey(DataMember && key, lambdaEquals & equals) const {
    int i;

    for (i = 0; i < numElements; i++) {
        if (equals(heap[i], std::forward<DataMember>(key)))
            return &heap[i];
    }
    return nullptr;
}

//***************
// eHeap::RemoveByKey
// search keys can differ from compare keys
// returns false if key not found
//****************
template<class type, class lambdaCompare>
template<typename DataMember, typename lambdaEquals>
inline bool eHeap<type, lambdaCompare>::RemoveByKey(DataMember && key, lambdaEquals & equals) {
    int i;

    for (i = 0; i < numElements; i++) {
        if (equals(heap[i], std::forward<DataMember>(key))) {
            std::swap(heap[i], std::move(heap[numElements - 1]));
            numElements--;
            SiftDown(i);
            return true;
        }
    }
    return false;
}

//***************
// eHeap::ReplaceByKey
// search keys can differ from compare keys
// returns false if key not found
// DEBUG: instead of explicit IncreaseKey and DecreaseKey
//***************
template<class type, class lambdaCompare>
template<typename DataMember, typename lambdaEquals>
inline bool eHeap<type, lambdaCompare>::ReplaceByKey(DataMember && oldKey, type & newData, lambdaEquals & equals) {
    int i;

    for (i = 0; i < numElements; i++) {
        if (equals(heap[i], std::forward<DataMember>(oldKey))) {
            heap[i] = newData;
            if (i > 0 && compare(heap[(i - 1) / 2], heap[i])) {
                SiftUp(i);
            } else {
                SiftDown(i);
            }
            return true;
        }
    }
    return false;
}

//***************
// eHeap::ReplaceByKey
// emplace and move
// search keys can differ from compare keys
// returns false if item not found
//****************
template<class type, class lambdaCompare>
template<typename DataMember, typename lambdaEquals>
inline bool eHeap<type, lambdaCompare>::ReplaceByKey(DataMember && oldKey, type && newData, lambdaEquals & equals) {
    int i;

    for (i = 0; i < numElements; i++) {
        if (equals(heap[i], std::forward<DataMember>(oldKey))) {
            heap[i] = std::move(newData);
            if (i > 0 && compare(heap[(i - 1) / 2], heap[i])) {
                SiftUp(i);
            } else {
                SiftDown(i);
            }
            return true;
        }
    }
    return false;
}

//***************
// eHeap::Size
// returns number of elements in the heap
//***************
template<class type, class lambdaCompare>
inline int eHeap<type, lambdaCompare>::Size() const {
    return numElements;
}

//***************
// eHeap::IsEmpty
// returns true for numElements == 0
//***************
template<class type, class lambdaCompare>
inline bool eHeap<type, lambdaCompare>::IsEmpty() const {
    return numElements == 0;
}

//***************
// eHeap::Heapify
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::Heapify() {
    int i;

    // DEBUG: start at the element just above the last leaf child and work upwards
    for (i = numElements / 2; i > 0; i--)
        SiftDown(i - 1);
}

//***************
// eHeap::SiftUp
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::SiftUp(const int index) {
    int parent;
    int child;

    if (heap == nullptr)
        return;

    for (child = index; child > 0; child = parent) {
        parent = (child - 1) / 2;
        if (!compare(heap[parent], heap[child]))
            return;

        std::swap(heap[parent], heap[child]);
    }
}

//***************
// eHeap::SiftDown
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::SiftDown(const int index) {
    int parent;
    int child;

    if (heap == nullptr || numElements <= 1)
        return;

    // DEBUG: a right child's existence (child + 1) implies that a left child exists, but not vis versa
    for (parent = index, child = 2 * parent + 1; child < numElements; child = 2 * parent + 1) {
        if (child + 1 < numElements && compare(heap[child], heap[child + 1]))
            child++;
        if (!compare(heap[parent], heap[child]))
            return;

        std::swap(heap[parent], heap[child]);
        parent = child;
    }
}

//***************
// eHeap::Allocate
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::Allocate(const int newHeapSize) {
    Free();
    heapSize = newHeapSize;
    heap = new type[heapSize];                  
    memset(heap, 0, heapSize * sizeof(type));
}

//***************
// eHeap::Allocated
// returns the total memory allocated 
//**************
template<class type, class lambdaCompare>
inline size_t eHeap<type, lambdaCompare>::Allocated() const {
    return heap == nullptr * heapSize * sizeof(type);
}

//***************
// eHeap::SetGranularity
// adjust the amount by which the heap will
// expand when it runs out of memory
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::SetGranularity(const int newGranularity) {
    granularity = newGranularity;
}

//***************
// eHeap::Free
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::Free() {
    if (heap != nullptr) {
        delete[] heap;
        heap = nullptr;
    }
    numElements = 0;
}

//***************
// eHeap::Resize
// increase heap size
// and expand available memory
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::Resize(const int newHeapSize) {
    type * oldHeap;
    int mod;
    int newSize;
    int i;

    if (newHeapSize <= heapSize)
        return;

    mod = newHeapSize % granularity;
    if (!mod)
        newSize = newHeapSize;
    else
        newSize = newHeapSize + granularity - mod;

    if (heap == nullptr) {
        heapSize = newSize;
        return;
    }

    oldHeap = heap;
    heap = new type[newSize];
    for (i = 0; i < heapSize; i++)
        heap[i] = std::move(oldHeap[i]);

    delete[] oldHeap;
    heapSize = newSize;
}

//***************
// eHeap::Clear
// reset numElements retain allocated memory to be overwritten
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::Clear() {
    // DEBUG: memsetting the contents of a 
    // std::unique_ptr or std::string will cause a leak
    // because its destructor cannot deallocate its original pointer
//  if (heap != nullptr) {
//      memset(heap, 0, heapSize * sizeof(type));
        numElements = 0;
//  }
}

//***************
// eHeap::ClearAndResize
// reset all data and free allocated memory
// set the new heap size to be allocated when the next element is added
//**************
template<class type, class lambdaCompare>
inline void eHeap<type, lambdaCompare>::ClearAndResize(const int newHeapSize) {
    Free();
    heapSize = newHeapSize;
}

#endif /* EVIL_HEAP_H */
\$\endgroup\$
1
  • \$\begingroup\$ It uses lambda functions (instead of std::lesser or std::greater) Not really true. You templatize the comparator function (which is good). So you can use any functor like object here. Note: A lambda is just syntactic sugar for creating an anonymous class behind the curtain. \$\endgroup\$ Dec 2, 2016 at 20:42

1 Answer 1

3
\$\begingroup\$

I've unit-tested this with POD types, std::string, and std::unique_ptr<int> and it executes all functions without issue.

Nice to see you again! :)

As with your deque from last time, I think your coding style is very good but the actual design is a bit questionable. (Less so than last time, though.) Consider:

template<typename DataMember, typename lambdaEquals>
const type * const FindByKey(DataMember&& key, lambdaEquals& equals) const;  

eHeap<std::string, std::less<>> myHeap;
const std::string *it1 = myHeap.FindByKey("hello", std::equal<>);
const std::string *it2 = myHeap.FindByKey("world", std::equal<>);
const std::string *it3 = myHeap.FindByKey("foo", std::equal<>);

Notice that the type DataMember in the first two calls is const char (&)[6], because the thing we're perfect-forwarding is an lvalue of type const char[6]; and in the third call is const char (&)[4].

If I were designing the API, I'd provide simply

template<typename lambdaPredicate>
const type * const FindByKey(lambdaPredicate& equals) const;  

eHeap<std::string, std::less<>> myHeap;
const std::string *it1 = myHeap.FindByKey([](auto&& x){ return x == "hello"; });
const std::string *it2 = myHeap.FindByKey([](auto&& x){ return x == "world"; });
const std::string *it3 = myHeap.FindByKey([](auto&& x){ return x == "foo"; });

Now the caller doesn't have to worry about things like "is the DataMember the first or second argument to lambdaEquals?" or "does DataMember secretly have to bear some relationship to type?" or anything like that. The only parameter the caller needs to worry about is the predicate, which is an opaque lambda type that clearly can do whatever it wants.

Notice that the type lambdaPredicate is a different type in all three of the calls here. So we have a little bit more template explosion, maybe; but it'll all be inlined anyway.

Also, at this point, we've got something that's very close to the standard algorithm std::find_if. So we might like to get rid of the member-function algorithm and just provide a pair of member functions to create iterators into the unordered elements of the heap:

const type *unordered_begin() const { return heap; }
const type *unordered_end() const { return heap + heapSize; }

eHeap<std::string, std::less<>> myHeap;
const std::string *it1 = std::find_if(myHeap.unordered_begin(), myHeap.unordered_end(), [](auto&& x){ return x == "hello"; });

If we're providing const iterators, should we also provide non-const iterators?

type *unordered_begin() { return heap; }
type *unordered_end() { return heap + heapSize; }

Probably not. We don't want to give the user the ability to modify or reorder the heap's elements on the fly; that could break the heap invariant.


typedef eHeap<type, lambdaCompare> heap_t;

Did you know that you can use the name of the template itself as a class-name inside the definition of the template? That is, you could just use eHeap in all the places you're currently using heap_t, and the compiler would know that you're talking about eHeap<type, lambdaCompare>.

In any event, heap_t probably shouldn't be a public member typedef, should it?


const type * const      operator[](const int index) const;

Of the four consts on that line, two are redundant — even harmful. Prefer to write

const type *operator[](int index) const;

It doesn't matter for primitive types like int and type *, but if the parameter or the return value were class types, the added const would have made a difference:

X foo();
const X bar();

X x;
x = foo();  // move assignment
x = bar();  // copy assignment, since `const X` can't be moved-from — oops!

I prefer always to write the generic-safe version, even for primitive types, so that neither I nor the readers who come after me need to worry about whether this type is primitive or not — it's just obviously safe, and the reader doesn't need to expend mental effort on it.


int i;
// ...
for (i = 0; i < heapSize; i++)
    heap[i] = other.heap[i];

For the same reason, I write ++i even when i++ is just as fast for integers. (Well, in that case, it's also because the verb comes first in English. "Increment i" reads better than "i, increment".)

C++ isn't C89; you should never declare an uninitialized variable if you can possibly help it. Write:

for (int i = 0; i < heapSize; ++i)
    heap[i] = other.heap[i];

The line I // ...ed above was heap = new type[heapSize];. Why on earth are you using manual memory management in this class? Remember the Rule of Zero.

Use std::vector<type> heap; and get rid of the heapSize member variable (because you have heap.size() for that now). This not only protects you against memory leaks (e.g. consider what happens if one of those copy-assignments throws an exception) — it will also make your code more efficient, because the vector will track its own capacity separately from its length, and use geometric resizing to make sure that a sequence of O(n) calls to PushHeap results in only O(lg n) reallocations, instead of O(n) reallocations. It will also make your source code shorter, because you can get rid of those Allocate() and Resize() functions.

You can also get rid of all your special member functions (as the Rule of Zero suggests), which will shorten the code even more.


Finally, you might not be aware that even make_heap, push_heap and pop_heap are available as standard library functions!

The one heap-related function that I wish were available in the STL that currently isn't available is basically your ReplaceRoot, which pops the top element and then also pushes the provided element onto the heap in a single operation (which, as you noticed, can be done more efficiently than just a pop plus a push).


I have a "heap_span" on my GitHub that's similar to this code but doesn't even use a vector for storage; it just provides a view onto a sequence of elements allocated by the caller. It might or might not interest you. :)

\$\endgroup\$
2
  • \$\begingroup\$ I will never implement a template again without those test cases @Quuxplusone :) Am I wrong that grouping variables from largest to smallest at the top of a function helps the compiler align them in memory in a more cache-friendly way? Does that only apply in class/struct declarations? If so, is the popular consensus that distributing them make it equally readable? I read through your heap_span, its a great example for a lot of the noexcept, perfect forwarding, and memory footprint reduction I ought to integrate in my future code. I enjoyed how you did in 200 lines what took me 700. \$\endgroup\$
    – TOM__
    Dec 4, 2016 at 1:00
  • 1
    \$\begingroup\$ "Am I wrong that grouping variables from largest to smallest at the top of a function helps the compiler align them in memory in a more cache-friendly way?" — Yup. It matters for class/struct members because those actually correspond to storage layout; but inside a function, the local variables will be stored in registers or even further optimized away. If I say int f() { int x = 42; int y = x + 7; return y; }, then most likely the compiler won't allocate any space for either x or y, because it can figure out that I mean simply int f() { return 49; }. \$\endgroup\$ Dec 4, 2016 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.