1

I'm writing a library that provides graphs for search algorithms.

Usually you want to rank nodes using a priority queue. Normally you want to search for an specific node in the queue and lower its key (when you find a better path to it).

Searching would be O(n) unless you know the index of the node (you can add it to the node structure). Adding the index to the Node requires that the queue is able to update the index when needed.

I'm having trouble writing a generic priority queue, because I need to know where to read and write the index of a node on this queue. Is there a way to do it?

The code might look like this

class SomeNode : Node {
 int indexA;
 int indexB;
}

template <typename N, ?? indexMember>
class Heap{
  update(N node, int key){
    //...
    node.indexMember = i;
  }
}

Heap<SomeNode, 'indexA'> heapA(cmp_A());
Heap<SomeNode, 'indexB'> heapB(cmp_B());

I'm asking here because I think that the design may need some rework rather than a probably missing feature

  • This is how to do it: stackoverflow.com/questions/11532130/… – Thomas Eding Jul 2 '15 at 16:08
  • @Thomas thanks, that is what I wanted to do. Should I mark this as a duplicate, or accept an answer from you explaining that in a little more detail for other people that get here? – Dietr1ch Jul 3 '15 at 0:36
1

Following the StackOverflow Question suggested by Thomas, the answer should look like this:

class SomeNode : Node {
 int indexA;
 int indexB;
}

template <typename N, int (N::*indexMember)>  // Note the *
class Heap{
  update(N node, int key){
    //...
    node.*indexMember = i;  // Also here
  }
}

Heap<SomeNode, &SomeNode::indexA> heapA(cmp_A());  // Note the ref to the member
Heap<SomeNode, &SomeNode::indexB> heapB(cmp_B());

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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