Thread: Speed of iterating through STL containers

  1. #1

    Join Date
    May 2005
    Posts
    1,042

    Speed of iterating through STL containers

    Which is slower, in general, using std::iterators or using operator[], when available.

    e.g., say you have an std::vector<int> int_vector, you could loop through in a couple of different ways:

    PHP Code:

    for(int i 0int_vector.size(); i++)
    {
        
    int this_int int_vector[i]; //same as int_vector.at(i)
    }

    ...

    for(
    std::vector<int>::iterator ptr int_vector.begin(); ptr != int_vector.end(); ptr++)
    {
       
    int this_int = *ptr;

    Tests using both high and low resolution timers give inconsistent results. Which is typically seen as the "better" method to use? My guess is they're both ultimately pretty much the same thing under the hood.
    I'm not immature, I'm refined in the opposite direction.

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    For using vectors it should not matter. It's like using a pointer vs a subscript for looking through an array. Litterally, that's all you'd be doing.

    For deque I'd immagine iterators would be faster, because an itterator would have a pointer to the element itself, and not require the two levels of indirection as with operator[].
    Last edited by King Mir; 06-12-2006 at 03:23 PM.
    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.

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I'm inclined to believe iterators are faster due to the fact the [] operator makes a copy of the value, while the iterator type does not.
    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.

  4. #4
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    for a vector the two methods are pretty much equivalent. The second method is more generic (you could easily replace vector with list, if you felt it was a better choice), but the first is probably more readable to the average C++ programmer.

    As a minor nit, it's better not to call .size() as the loop condition (unless the size can change in the loop).
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  5. #5
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    in this case operator [] easier

    for (i = 0; i < nSize; ++i)
    [i]

    Kuphryn

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Uh, why is it easier?

    And I expect the average C++ programmer to be so familiar with iterators that it would be actually more intuitive to them than an index loop.

    Mario F. is wrong: [] does not make a copy. It returns a reference (const reference for const containers).

    Advantages of iterators:
    1) More universally applicable.
    2) Sometimes better debugging behaviour.
    3) Potentially easier to optimize for the compiler. But only potentially; making assumptions about optimization behaviour is rarely a good idea.

    Disadvantages:
    1) Tends to be a bit longer to type.

    One more thing: vector::at() and vector::operator[] are not the same! at() performs an additional index check and is thus slower, but safer.
    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

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> due to the fact the [] operator makes a copy of the value.
    No, it doesn't, it returns a reference.

    I'd use the iterators unless you never use any other standard containers or algorithms in your code since it would be more consistent. If you have mostly C-style code, the array syntax might be more consistent.

  8. #8
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Yes. I was actually just checking my sources. The responses seemed to go against my... *cough* theory. So I wanted to check back on what I believed I read about iterators compared to subscripting.

    I'm deeply wrong. I apologize
    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.

  9. #9

    Join Date
    May 2005
    Posts
    1,042
    As a minor nit, it's better not to call .size() as the loop condition (unless the size can change in the loop).
    Thank you, I did not know that!

    As a minor nit, it's better not to call .size() as the loop condition (unless the size can change in the loop).
    Wait, don't you mean unless the size is guaranteed to stay the same during the loop?
    Last edited by BobMcGee123; 06-12-2006 at 09:50 PM.
    I'm not immature, I'm refined in the opposite direction.

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    If there is a chance that the size of the container will change in the loop, then size() is actually protecting you, since it will return the current size. A fixed value won't update by itself. Though it is a good idea to cache the size in a variable if it isn't going to change.

  11. #11
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I test against size() all the time. If I'm going to use it a lot in a function, I stick the value in a temp variable and use it throughout the function.

    As far as the question I really don't think there is a major performance diff between the two methods. At least not one worth worrying about.

    I normally use iterators only when I have to such as map::find() and other STL functions requiring an iterator. Usually I use array subscript for everything else.

  12. #12
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Correct me if I'm wrong, but doesn't [] involve a multiplication (for objects of greater size than 1 at least)?
    Code:
    Array[i]
    would be assembled to using the address (each iteration):
    Code:
    Array + (TypeSize * i).
    While the iterator would just increment each iteration.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  13. #13
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    If you really want to be sure the best thing to do is to not guess, and write a program to measure. I did exactly that, and it turns out that [] is much faster than an iterator. Makes sense to me, that's what [] was supposed to do faster than anything else.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I did exactly that, and it turns out that [] is much faster than an iterator. Makes sense to me, that's what [] was supposed to do faster than anything else.
    According to BobMcGee123, "Tests using both high and low resolution timers give inconsistent results."

    It probably depends on the implementation, level of optimisation, exact usage etc. And doesnt really matter unless it is the performance bottleneck, which I find rather unlikely.
    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

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by Magos
    Correct me if I'm wrong, but doesn't [] involve a multiplication (for objects of greater size than 1 at least)?
    Yes, but
    1) The compiler might optimize that away by incrementing the counter by the byte size every iteration.
    2) The compiler might optimize it away by converting the whole loop to a pointer-increment loop.
    3) The compiler might optimize it away by using a specialized memory addressing instruction, which most CPUs (even RISC) have, and which typically are just as fast as the direct instructions.
    4) Since types are typically aligned at power-of-two-boundaries, the multiplication is just a shift anyway.

    So that's not going to make a real difference.

    citizen: Have you tested this in release mode? Debug iterators often have a lot of overhead.
    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. Noob STL question about Containers.
    By Swerve in forum C++ Programming
    Replies: 2
    Last Post: 03-15-2009, 12:02 PM
  2. Bit arrays with STL containers
    By Mario F. in forum C++ Programming
    Replies: 23
    Last Post: 07-03-2007, 09:50 AM
  3. stl containers allocation in heap or stack?
    By sawer in forum C++ Programming
    Replies: 9
    Last Post: 08-06-2006, 03:08 PM
  4. Pointer Elements & STL Containers :: STL
    By kuphryn in forum C++ Programming
    Replies: 2
    Last Post: 09-30-2002, 08:13 PM
  5. STL: element-wise addition of the contents of two containers
    By geophyzzer in forum C++ Programming
    Replies: 4
    Last Post: 06-26-2002, 06:17 PM