I have a vector of millions of points that I have to sort based on their distance from the camera, in order to do that i created the following simple function object:

class PointSorter
{
public:
  PointSorter()
  {
    points = NULL;
  }

  // !!! copy constructor called all the time during std::sort !!!
  PointSorter(const PointSorter& other)
  {
    points = other.points;
    printf("object copied");
  }

  PointSorter(std::vector\* pvec==NULL)
  {
    points = pvec;
  }

  bool operator()(const unsigned int&a, const unsigned int&b)
  {
     return (\*points)\[a\].z() < (\*points)\[b\].z();
  }

  std::vector\* points;
};

then later on I do a simple

PointSorter sorter(&mypoints);
// std::vector indices;
std::sort( indices.begin(), indices.end(), sorter );

this sorts the indices of my points well, the only concern is that I discovered that the object "sorter" is being copied all the time during std::sort, this shurely impact negatively the sorting performance which is already quite poor for millions of points since I have to achieve interactive frame rates for my 3d program. Does anyone know how to pass a custom sorter object (which is not a static function) that is copied once and used all the way throughout the sorting? Regards, Michele

Thanks to all the replies, it turned out that a easier way of optimizing such code is to make the data structures as cache friendly as possible making the nodes smaller and careful allocation, so one can forget about iterative traversal for another bit...

In theory I would also do as you say, but when you actually try to translate it into practice everything becomes much more foggy, especially the management of the 2 functions "do_something_before()" and "do_soemthing_after()".

I already saw that example of wikipedia, unfortunately it is for a binary tree meanwhile I would need a more general N-ary tree and with operations on the node performed before and after visiting the children. I thought there would be a "text-book" solution to this but it seems that this is a much more complex problem than I expected...

I have a tree data structure that I use for my scene graph that I traverse each frame to update 20.000 nodes, I am currently doing the typical recursive traversal but probably it would be quicker if I converted the recursive traversal in an iterative one, does anyone have any hint on how to do that? Here is how my data structure looks like:

class Node
{
public:

... some data ...

std::vector Children;
};

void do_something_before(Node*)
{
...
}

void do_something_after(Node*)
{
...
}

// function to translate into an iterative one

void traverse(Node* node)
{
do_something_before(node);

for(int i=0; iChildren.size(); ++i )
traverse(node->Children[i]);

do_something_after(node);
}

Thanks