Tuesday, April 21, 2009

C++ note: using a functor to help organise a vector of pointers

Suppose that some large structures need to be managed by using a heap. There is no limitation to the number of items, and therefore a vector is used to maintain the memory. Because they are organised in a heap, direct heap operation on the memory vector is slow. Therefore, another vector is used to store the indice.

template<cnode> myClass{
vector<cnode> memory;
vector<unsigned> indice;

Now the indice vector must store indice (unsigned) rather than pointers (CNode*). This is because when the memory vector is reallocated, the original pointers to the memory are invalid. Using pointer vectors will lead to segmentation-fault.

Pushing and popping heap operations can now be carried out on the indice. They should rely on node comparison. The standard node comparison function should read like:

// in myClass
bool less(const unsigned x, const unsigned y) { return memory[x] < memory[y]; }

The above code does not compile, because push_back and pop_back in std require a function with the signature less(x, y). A member function doesn't work. A solution is the functor.

struct CNodeLess {
const vector<CNode> *memory;
CNodeLess(const vector<CNode> &bm): memory(&bm) {}
bool operator()(const unsigned &x, const unsigned &y) { return (memory[x] < memory[y]); }

Now the class can have a member in CNodeLess that caches the memory, and provide the less(x,y) signature.