Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / Surprising STL problem Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Mystagogue

April 26, 2005, 01:29 PM

I have code like this:

  1.  
  2.     #include <list>
  3.    using namespace std;
  4.  
  5.     //...some method somewhere then has...
  6.     list<Shape*>::iterator pPointer = m_lstSubStates.begin();
  7.     list<Shape*>::iterator pEnd   = m_lstSubStates.end();
  8.     for (;pPointer < pEnd;++pPointer)
  9.     { ...}
  10.  

Which doesn't compile, due to complaints about the "less than" operator in the for loop. Complaints like:

------------------------------
c:myprojectsfoobar.cpp(2961): error C2784: 'bool std::operator

 
IronChefC++

April 26, 2005, 02:29 PM

The list container iterators are bidirectional iterators - they do not have an operator< defined. And even if they did, you certainly wouldn't want to use it in this situation. The loop conditional would run the remainder of the list to figure out each step if it was at the end. A simple traversal of all the nodes in the list would go from O(n) to O(n log n). That's a lot of wasted time for nothing.

The operator< is only defined for random access iterators. operator!= is defined for all iterator types. I'd suggest getting in the habit of using != for loops.

 
Thomas Mølhave

April 26, 2005, 03:11 PM

That would be O(n^2) for a complete list traversal using the naive way of doing "it1

 
IronChefC++

April 26, 2005, 06:20 PM

You are correct. That was ridiculously stupid of me.

 
Thomas M�lhave

April 27, 2005, 02:48 AM

well, shit happens :)

 
This thread contains 5 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.