Thread: Whoa, are reverse iterators slower and should I really care?

Hello All,

I have some code where I need to iterate backwards through a vector.

I thought about writing this with random access iterators and just subtracting one until I got to the beginning but then I looked it up and there are STL implemented reverse iterators so I just used those and they work perfectly for my needs.

But I looked up if they were slower and the google searches seem to indicate yes.

Granted, I'm only reverse iterating through like 4 elements at a maximum but I'm doing it quite a bit so I'm just curious, should I even care about using reverse iterators just long as they do the job properly?

Gah, that is sooooo not what I wanted to hear. I love the STL and I'm convinced that there's no set of C++ programmers superior to them. Well, my code works and it's A LOT faster than it used to be anyway.

I try to follow the mantra that if you try to over-optimize like this then you're a bad programmer because more often than not, a superior algorithm using slower containers is faster than a slow algorithm using faster containers. It's like doing something intelligently in a slightly slower way vs doing something stupid in a faster way.

Oh well. I'll look into it but I don't think reverse iterators will be an issue.

C++ (\STL) containers are generally associated with a set of algorithms, though.
So, be careful when choosing your type of container.
The differences are often significant in terms of complexity.

For example, std::map implements some sort of balanced tree and std::unordered_map acts like a hash table.

What was it, I'm using these reverse iterators to add nodes from a graph to a stack for iterative traversal. My real code looks like this :

Code:

void search_tree(tree *root, particle *p, vector<tree*> & leaves) {


   set<tree*> visited;


   stack<tree*> traversal;
   traversal.push(root);


   while (!traversal.empty()) {


      tree *curr = traversal.top();


      if (!visited.insert(curr).second) {


         traversal.pop();
         continue;
      }


      if (curr->del == 0) {


         if (inside_tetra(curr->t, p) == -1) {


            traversal.pop();
            continue;
         }


         if (curr->children.empty()) {


            leaves.push_back(curr);
            traversal.pop();
            continue;
         } else {


            //for (auto it = curr->children.end(); it < curr->children.end(); ++it)
               //traversal.push(*it);


            for (auto it = curr->children.crbegin(); it != curr->children.crend(); ++it)
               traversal.push(*it);


            continue;
         }
      } else if (curr->del == 1) {


         //for (auto it = curr->children.begin(); it < curr->children.end(); ++it)
            //traversal.push(*it);


         for (auto it = curr->children.crbegin(); it != curr->children.crend(); ++it)
            traversal.push(*it);


         continue;
      }
   }


   return;
}

I only decided to add the children in reverse order because the way my code works, the way in which children are processed matters for the output and I was trying to make sure my iterative solution matches exactly to my recursive implementation which I've been using as a reference. The outputs match though. I was just trying to optimize the code.

The reverse loop looks suspicious to me.
For a DFS, the correct order should not need a reverse loop.

Are you sure your recursive solution isn't searching the subtrees recursively out of order?

It needs to be in reverse because I'm using a stack which is last in, first out. So when I add the elements in the same order my recursive implementation searches, I need to put them on the stack in reverse order, if that makes sense.

Basically, with my graph, each node stores its children in a vector. My recursive implementation started from the beginning to the end. But when I use a stack and I push() elements in that order, it starts with the last child first so I push() the elements in reverse order so the first child is pop'd first.

The thing is, my code is triangulating points in space and does subsequent repairs. It is order sensitive and I was just trying to maintain consistency with previous incarnations even though it'd technically be irrelevant, mathematically.

I tested the different orders using both small and large point sets and they were largely similar though.

Originally Posted by MutantJohn

It needs to be in reverse because I'm using a stack which is last in, first out. So when I add the elements in the same order my recursive implementation searches, I need to put them on the stack in reverse order, if that makes sense.

Basically, with my graph, each node stores its children in a vector. My recursive implementation started from the beginning to the end. But when I use a stack and I push() elements in that order, it starts with the last child first so I push() the elements in reverse order so the first child is pop'd first.

Well, the recursive version uses a stack as well (the call stack) in almost the exact same way.

So, if your recursive function is giving output in an order reverse to the one you have with a normal loop, the recursive version has some bug.

I have implemented a lot of graph search algorithms, but never seen one where you have to put elements in reverse order because you have a stack!
A stack reverses it by its very nature, as you said.

Okay, I'm sorry to spam this topic with my own jibber jabber but I know why the differences arose between using reverse and forward orders.

You're right, my traversal can be done in any order.

Basically, my code searches this tree for appropriate leaves and collects them. It then processes them in a totally separate function.

But then I do conditional repairs and that's when the order really matters.

So, repairing entries in different orders yields different results.

To get a better idea of what I'm talking about, I'm mapping the insertion history of a tetrahedral mesh to a graph where each leaf is a valid element of the mesh. When I insert a point, I need to find all the leaves that contain the point. I collect those.

I then insert that point into each collected leaf in a separate function. Here, the order still doesn't matter. The tetrahedra can be collected and fracture in any order.

However and this is the key difference, the repair sequence for that new fracture set is order dependent. For example, I have 3 repair routines. 2-to-3, 3-to-2 and 4-to-4 where 2 tetrahedra are swapped for 3 good ones, etc.

Here, the order really does matter because the way in which you repair a tetrahedron can cause subsequent repairs or it can prevent others so that's why I had to feed everything in reverse order so that way it would match the normal repair set I had before due to how the nature of the stack works.

Sorry if this is too much but you got me thinking and I think I can justify the behavior of my code and considering that the differing outputs are small, even for something like 10,000 vertices being triangulated compared to 512 (both forwards and backwards yield relatively the same number of tetrahedra and repairs) so I think my code is performing properly. Feeding the elements in a reverse order is a completely arbitrary choice done by me, I guess, just to prove to myself that my code is behaving as it was when it was recursive.

Granted, I'm using all of this for a Voronoi tessellation which should always be the same no matter how the Delauny triangulation was constructed so we'll see if I'm right or not. I'm fairly confident though. I really hope so. Sometimes there are situations where you can't do any repairs so we'll see...