Thread: STL's vector V.S. STL's set??

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    284

    STL's vector V.S. STL's set??

    Code:
    	int tmp[]={3,2,1,3,2,4,5,4,2};
    	vector<int> vc(tmp,tmp+9);
    	set<int> st(vc.begin(), vc.end());
    
    	vector<int>::iterator vit=vc.begin();
    	for(;vit<vc.end();it++) cout<<*it<<' '; // OK
    
    	set<int>::iterator sit=st.begin();
    	for(;sit<st.end();it++) cout<<*it<<' '; // Error
            for(;sit!=st.end();it++) cout<<*it<<' '; // OK
    Why '<' is forbidden for SET's iterator?

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Only random-access iterators can be compared using <, >, <=, or >= (this is to discourage their use for other types of iterators for which it would be horribly inefficient). For other types of iterators, you must use == and !=.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Many people will also tell you that you should be using != for a vector as well.
    Also, you should use preincrement on your iterators (++it) not (it++).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by robatino View Post
    Only random-access iterators can be compared using <, >, <=, or >= (this is to discourage their use for other types of iterators for which it would be horribly inefficient). For other types of iterators, you must use == and !=.
    It's a good idea to always use != even for iterators that support <. If you are doing generic programming (which you should strive for), you never know exactly what kind of iterator your code might be dealing with. So you should assume the lowest common denominator -- a forward iterator which supports == and != comparison, and not much else.

    For the same reasons, it's better to increment an iterator with pre-increment instead of post-increment, because again, you never know exactly what functionality an iterator provides, and pre-increment is more fundamental than post-increment.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    I used to think < in an integer loop required a subtraction and was less efficient than !=, and that this was why Stroustrup used != almost exclusively in his loops, until I realized that non-random access iterators weren't allowed to use <. Now I realize that < should be about as efficient as != for an integer loop (they both can be implemented by direct bit comparisons between integers), but I tend to use != anyway so I can write integer and iterator loops in the same way.

    Edit:

    > For the same reasons, it's better to increment an iterator with pre-increment instead of post-increment, because again, you never know
    > exactly what functionality an iterator provides, and pre-increment is more fundamental than post-increment.

    Looking at the table on page 551 of Stroustrup, I don't see any distinction made between pre- and post-increment with regard to being able to use them with iterators. I agree that it's a good habit to use pre-increment by default for efficiency reasons though.
    Last edited by robatino; 07-09-2007 at 02:12 PM.

  6. #6
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Post-increment has to create a copy of the incremented object; pre-increment doesn't.

    With todays processors, != and < should both be possible in one clock cycle.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    in one clock cycle
    It is too long for todays processors

    1 instruction per tick count? You are definitely waisting your CPU power for nothing
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by robatino View Post
    Looking at the table on page 551 of Stroustrup, I don't see any distinction made between pre- and post-increment with regard to being able to use them with iterators. I agree that it's a good habit to use pre-increment by default for efficiency reasons though.
    That's for STL iterators. When dealing with user-written iterators, the user is often a lazy horse and doesn't write the post-increment operator. So the best generic classes/functions will always use pre-increment unless post-increment is absolutely necessary for some reason.

    It's not really so much to do with efficiency -- modern inlining C++ compilers can usually completely optimize away the overhead of a post-increment, as long as the temporary value is not being used (e.g., in the increment phase of a for-loop).

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by brewbuck View Post
    That's for STL iterators. When dealing with user-written iterators, the user is often a lazy horse and doesn't write the post-increment operator.
    Then it's not a compliant iterator. The requirements on iterators say that post-increment must be present, even for the meanest input or output iterators, which you can't even copy and reuse. When concepts come in C++09, such half-iterators will be the first against the wall.

    Besides, with the Boost.Iterator library, there's no excuse for doing this. Just defined increment(), and the library does the rest for you.

    Or even if not using B.I, it's still an inexcusable laziness. Here, take this, copy and past, and correct the two type names.
    Code:
    const type operator ++(int) {
      type t(*this);
      ++*this;
      return t;
    }
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    Then it's not a compliant iterator. The requirements on iterators say that post-increment must be present, even for the meanest input or output iterators, which you can't even copy and reuse. When concepts come in C++09, such half-iterators will be the first against the wall.
    Who cares? If you're writing your own generics why limit yourself to only non-broken classes? It's trivial to use pre-increment in an algorithm instead of post-increment and you gain the ability to work with non-compliant code while still working fine with compliant code.

    Or even if not using B.I, it's still an inexcusable laziness.
    Maybe, but not all the code I want to use is mine.

  11. #11
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Quote Originally Posted by brewbuck View Post
    Quote Originally Posted by CornedBee
    Or even if not using B.I, it's still an inexcusable laziness.
    Maybe, but not all the code I want to use is mine.
    If the code you're using was written by a developer lazy enough to not implement both operators, where else might the developer have been lazy?
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  12. #12
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by pianorain View Post
    If the code you're using was written by a developer lazy enough to not implement both operators, where else might the developer have been lazy?
    By following this logic, any code with any flaw in it would have to be rejected.

    Are you trying to say that any class which acts somewhat like an iterator but happens not to have a post-increment operator is somehow deficient? Why does it matter if such a class doesn't fit the precise definition of "iterator?" That's no reason not to be able to use it in a generic method.

    My POINT which has been lost in standards trivia here, is that pre-increment is in many senses a more "generic" operation than post-increment, and should be preferred by default.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Are you trying to say that any class which acts somewhat like an iterator but happens not to have a post-increment operator is somehow deficient? Why does it matter if such a class doesn't fit the precise definition of "iterator?" That's no reason not to be able to use it in a generic method.
    hmm... what if the class did not implement operator++ at all, and instead used a next() member function? After all, it acts somewhat like an iterator but happens not to have a pre-increment operator and post-increment operator. Why does it matter if such a class doesn't fit the precise definition of "iterator?" That's no reason not to be able to use it in a generic method.

    My POINT which has been lost in standards trivia here, is that pre-increment is in many senses a more "generic" operation than post-increment, and should be preferred by default.
    I think the generic operation is increment. The question is by what interface is this increment made possible.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by laserlight View Post
    hmm... what if the class did not implement operator++ at all, and instead used a next() member function? After all, it acts somewhat like an iterator but happens not to have a pre-increment operator and post-increment operator. Why does it matter if such a class doesn't fit the precise definition of "iterator?" That's no reason not to be able to use it in a generic method.
    I understand your "whittling down" argument but it doesn't appear to have a base case At some point you have to accept that the classes you operate on conform to some specific interface, I just disagree with what that interface should be required to provide.

    I see no harm in writing generic methods that can operate on STL-conformant objects AS WELL AS certain classes of NON-conformant objects. As the writer of a generic method shouldn't it be up to me what kinds of types my code can correctly operate on?

    And anyway, is anybody seriously arguing AGAINST using pre-increment in favor of post-increment? My reasoning happens to be different than the usual efficiency argument, but the result is the same.

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I'm arguing against avoiding post-increment where it makes the code more understandable, just because some broken code might not provide it.

    By following this logic, any code with any flaw in it would have to be rejected.
    No. Only the code where the flaw is a result of willful ignorance or laziness. If the flaw is an honest mistake, correct it and move on.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need some help...
    By darkconvoy in forum C Programming
    Replies: 32
    Last Post: 04-29-2008, 03:33 PM
  2. SystemParametersInfo set wallpaper issues
    By A10 in forum Windows Programming
    Replies: 5
    Last Post: 03-14-2008, 07:39 PM
  3. Replies: 8
    Last Post: 01-18-2008, 04:06 AM
  4. Replies: 4
    Last Post: 01-13-2008, 02:14 AM
  5. My graphics library
    By stupid_mutt in forum C Programming
    Replies: 3
    Last Post: 11-26-2001, 06:05 PM