Quick Question about the Efficiency of the STL

This is a discussion on Quick Question about the Efficiency of the STL within the C++ Programming forums, part of the General Programming Boards category; Hi, Suppose I have the following code segment: Code: std::vector<float> X(5, 1.0); std::vector<float>::iterator IterX; for(IterX = X.begin(); IterX != X.end(); ...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    25

    Quick Question about the Efficiency of the STL

    Hi,

    Suppose I have the following code segment:

    Code:
    std::vector<float> X(5, 1.0);
    std::vector<float>::iterator IterX;
    for(IterX = X.begin(); IterX != X.end(); IterX++) {
    std::cout << *Iter << " ";
    }
    and the following code segment:

    Code:
    std::vector<float> X(5, 1.0);
    for(int i = 0; i < 5; i++) {
    std::cout << X.at(i) << " ";
    }
    Which segment would be more efficient in terms of performance? I don't know how at() is implemented in the STL, but my guess would be that each time at() is called, the compiler internally creates an interator and iterates it the required number of times before dereferencing it. But I am not sure, because the book I am reading does say that std::vector<> provides fast random access to its elements.

    Can anyone here please help me?

    *****

    Note: this is not homework! I am not in school.

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,577
    My guess is it depends on the implementation. You can actually test this if you create big enough containers
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    A vector uses contiguous memory, so the at probably just uses the index multiplied by the size of the type to figure out how far in memory to go. The iterator implementation probably includes a pointer that is incremented each time.

    The at() might also be slower due to range-checking, although you could ask the same question about operator[] versus an iterator to avoid the range-checking complication.

    Bottom line is that it really depends on the implementation (except for the range-checking part), so you should do timing tests on your platform if you really need to know. In reality it probably doesn't matter at all. I would use the iterator in case I decided to change the container to something else later.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,821
    http://www.sgi.com/tech/stl/complexity.html
    A lot of the STL has statements about how complex (in relative terms) various actions are.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    I have found STL to be very fast as long as you do not do a lot of inserting, sorting, etc. So far my system is handling 12500 trees in a vector, rendering terrain with shaders, and a load of other tasks and I still get over 250 FPS.

    For the power it brings, STL is definitely worth the very small performance hit.

  6. #6
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    If your STL implementation happens to cache it's size, you're in luck, all you need to worry about would be the processor pipelining the wrong set of instructions in the range checking code.

    I'm guessing iterators are faster; with subscripts you may need to do a multiplication (or at least, a shift) for each access, while iterators (if using pointers) will only require an increment (ie. an addition).

    It is possible to optimize the iterator version by caching the end of the array in a second iterator; how much performance benefit this will bring is beyond me.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >but my guess would be that each time at() is called, the compiler internally
    >creates an interator and iterates it the required number of times before dereferencing it.
    Why would it do that when a simple range check is sufficient?
    Code:
    reference at ( size_type sub )
    {
      if (sub < 0 || sub >= size() )
        throw out_of_range ( "Invalid subscript" );
    
      return (*this)[sub];
    }
    My best code is written with the delete key.

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by Prelude
    Why would it do that when a simple range check is sufficient?
    Or an even simpler check? (size_type is required to be unsigned)
    Code:
    reference at ( size_type sub )
    {
      if (sub >= size() )
        throw out_of_range ( "Invalid subscript" );
    
      return (*this)[sub];
    }
    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

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >(size_type is required to be unsigned)
    Gah! Brain fart. Thanks for the correction.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. quick question
    By Unregistered in forum C++ Programming
    Replies: 5
    Last Post: 07-22-2002, 05:44 AM
  2. Quick Question Regarding Pointers
    By charash in forum C++ Programming
    Replies: 4
    Last Post: 05-04-2002, 12:04 PM
  3. Quick Question on File Names and Directories
    By Kyoto Oshiro in forum C++ Programming
    Replies: 4
    Last Post: 03-29-2002, 02:54 AM
  4. * quick question *
    By SavesTheDay in forum C Programming
    Replies: 3
    Last Post: 03-27-2002, 06:58 PM
  5. Quick question: exit();
    By Cheeze-It in forum C Programming
    Replies: 6
    Last Post: 08-15-2001, 06:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21