Vector iterators
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: Vector iterators

  1. #1
    Join Date
    May 2012
    Posts
    57

    Vector iterators

    C++ beginner learning how to use vectors.

    I see that there are 3 ways to iterate through a vector.

    Code:
    Method 1:
    for(vector<int>::iterator it = myVect.begin(); it != myVect.end(); it++)
        cout << *it << ' ';
    
    Method 2:
    for (vector<int>::size_type i = 0;  i < myVect.size();  i++)
        cout << myVect[i] << ' ';
    
    Method3:
    for (unsigned i = 0;  i < myVect.size();  i++)
        cout << myVect[i] << ' ';
    If my craps program will:
    - only ever use the same vector container,
    - will have a maximum of 50 elements,
    - will only ever be compiled using VC++ 2010 Express,

    can I just use method-3 safely? If not, why not?
    And actually, with only 50 elements max, couldn't I use "int i = 0" in the for statement instead of unsigned?

    Just trying to understand it all.
    Thanks,
    Raptor

  2. #2
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Vector iterators

    Quote Originally Posted by raptor88 View Post
    C++ beginner learning how to use vectors.

    I see that there are 3 ways to iterate through a vector.

    Code:
    Method 1:
    for(vector<int>::iterator it = myVect.begin(); it != myVect.end(); it++)
        cout << *it << ' ';
    
    Method 2:
    for (vector<int>::size_type i = 0;  i < myVect.size();  i++)
        cout << myVect[i] << ' ';
    
    Method3:
    for (unsigned i = 0;  i < myVect.size();  i++)
        cout << myVect[i] << ' ';
    If my craps program will:
    - only ever use the same vector container,
    - will have a maximum of 50 elements,
    - will only ever be compiled using VC++ 2010 Express,

    can I just use method-3 safely? If not, why not?
    And actually, with only 50 elements max, couldn't I use "int i = 0" in the for statement instead of unsigned?

    Just trying to understand it all.
    Thanks,
    Raptor
    Your mistake is assuming that you know the future.

    Write the code once so that regardless of what your future plans are, the code will compile without error or warning or have run time issues. No good programmer says "I'm using such-and-such compiler, have only n items now,.." etc., and then writes code that reflects that. They write the code once, and regardless of whatever happens a month, a year, two years, etc. down the road, the code still works.

    Secondly, there are other ways to iterate through a vector or any other container. One of these ways is to use the for_each() algorithm function. Using that function would have used the more efficient pre-increment instead of the less efficient post-increment of the iterator in your first example:
    Code:
    for(vector<int>::iterator it = myVect.begin(); it != myVect.end();  ++it)
        cout << *it << ' ';
    Note the change to pre-increment. However the for_each() would have automatically corrected that instead of you having to do it.

    Also, if your goal is to just use cout in a loop, a std::copy is all you need:
    Code:
    #include <algorithm>
    #include <iostream>
    #include <iterator>
    //...
    std::copy(myVect.begin(), myVect.end(), std::ostream_iterator<int>(std::cout, "  "));
    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 28th, 2012 at 11:40 PM.

  3. #3
    Join Date
    May 2012
    Posts
    57

    Re: Vector iterators

    Quote Originally Posted by Paul McKenzie View Post
    Your mistake is assuming that you know the future.
    I put my question in that form to simplify what I was trying to ask. My basic question was whether Method-3 should always work under the conditions I set. Just trying to understand how vector iterators work. So should Method-3 always work under those conditions?

    I assume methods 1 and 2 will always work under any conditions. Is that right?

    Secondly, there are other ways to iterate through a vector or any other container. One of these ways is to use the for_each() algorithm function. Using that function would have used the more efficient pre-increment instead of the less efficient post-increment of the iterator in your first example:
    Thanks for the tip about using a for_each() function. I didn't know about that.
    Why does pre-increment work faster than post-increment?
    Would it make much difference iterating through only 50 elements?


    Also, if your goal is to just use cout in a loop, a std::copy is all you need:
    Code:
    #include <algorithm>
    #include <iostream>
    #include <iterator>
    //...
    std::copy(myVect.begin(), myVect.end(), std::ostream_iterator<int>(std::cout, "  "));
    I'll not be using cout in a loop. My craps program will be using SFML with no console. Just used cout in the 3 methods to keep things simple. But again, thanks for the tip about using std::copy. I'll learn how to use that too.

    Thanks,
    Raptor

  4. #4
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,976

    Re: Vector iterators

    I assume you prefer method 3 because "it is less typing". Don't let that EVER be a reason to write code in any form or way. Make your code readable, and readable by others.
    If you need to type more to make something more readable/standard then that is the right thing to do.


    with C++11, option 1 can be shortened.

    Code:
    for(auto it = myVect.begin(); it != myVect.end(); ++it)
        cout << *it << ' ';

  5. #5
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Vector iterators

    Quote Originally Posted by raptor88 View Post
    My basic question was whether Method-3 should always work under the conditions I set.
    You can take any piece of C++ code, regardless of what it does, and make it work exclusively with compiler X, Y, or Z. When you try it with Visual Studio Express 2010, did it work? If it did, then it worked for that compiler. However, how do you know that Service Pack X of Visual Express 2010 will make the code you have now faulty or uncompilable? What if you want to get Visual Studio 2012, and the code no longer works correctly?

    The problem with the general question of "if I have compiler X, and did things this way in C++, would it work?" is as I stated. That piece of code that happens to work for compiler X may not work for compiler X, version 2.0, 3.0, 4.0, etc. (assuming you're using version 1.0).

    One classic case of this is assuming that vector::iterators (since we're talking about iterators) were really simple pointers underneath the hood. The Visual C++ 6.0 compiler was the most popular C++ compiler of the late 1990's, and a lot of code that used vectors used shortcuts in the code, assuming that vector iterators were really pointers. This saved typing the whole "iterator" keyword, or saved creating a typedef, and saved having to declare types correctly.

    Then here comes Visual Studio .NET, 2002, 2003, 2005, etc., and guess what? All of that C++ code that was created with Visual 6.0 that assumed vector iterators were pointers no longer compiled! Do you know how many Internet sites still have faulty Visual C++ vector/iterator code, all because the author was using Visual C++ 6.0 and took that fatal shortcut? The ironic thing is that if the coder using Visual C++ 6.0 didn't take shortcuts, and instead declared the vector::iterator correctly, used the correct types, assumed that vector iterators were not pointers, etc. that the code would have still worked using Visual C++ 6.0 and in any future version of Visual Studio.

    So if you came to the Non-Visual C++ forum and asked "if I used iterators this way by assuming it is a pointer, and I'm using Visual C++ 6.0, and..."), then yes, the code would "work". But are you really learning correct coding? So please learn from this classic mistake -- never code something because it's "easier", "less typing", etc. Always write correct code with the future in mind -- if you know you're taking shortcuts because right now your compiler accepts it, don't take that shortcut.

    In addition, many "Lint" tools and compilers where some warnings are considered errors would reject your Method 3. A size_t is a size_t, and may not be an unsigned int, causing the lint tool to report an error, or the compiler to not generate object code.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 29th, 2012 at 01:35 PM.

  6. #6
    Join Date
    May 2012
    Posts
    57

    Re: Vector iterators

    Quote Originally Posted by OReubens View Post
    I assume you prefer method 3 because "it is less typing". Don't let that EVER be a reason to write code in any form or way. Make your code readable, and readable by others.
    If you need to type more to make something more readable/standard then that is the right thing to do.
    Actually no, I'm not preferring method-3 because of less typing. Method-2 uses "vector<int>::size_type" in place of Method-3's "unsigned" which is not that much more typing.

    Code:
    Method 2:
    for (vector<int>::size_type i = 0;  i < myVect.size();  i++)
    
    Method3:
    for (unsigned i = 0;  i < myVect.size();  i++)
    I'm just trying to understand vector iterators better and it's curious to me how Method-3 works fine. All 3 methods compile and run error free in my tests, though the actual for loops in my tests are more complex.

    Ok, forget about Method-3. Is Method-2 an accepted method and OK to use?


    with C++11, option 1 can be shortened.

    Code:
    for(auto it = myVect.begin(); it != myVect.end(); ++it)
        cout << *it << ' ';
    Thanks for another tip. However, looking at the pre-increment, won't the first element in the for loop be skipped?

    Thanks,
    Raptor
    Last edited by raptor88; November 29th, 2012 at 04:06 PM.

  7. #7
    Join Date
    May 2012
    Posts
    57

    Re: Vector iterators

    Quote Originally Posted by Paul McKenzie View Post
    You can take any piece of C++ code, regardless of what it does, and make it work exclusively with compiler X, Y, or Z. When you try it with Visual Studio Express 2010, did it work? If it did, then it worked for that compiler. However, how do you know that Service Pack X of Visual Express 2010 will make the code you have now faulty or uncompilable? What if you want to get Visual Studio 2012, and the code no longer works correctly?

    The problem with the general question of "if I have compiler X, and did things this way in C++, would it work?" is as I stated. That piece of code that happens to work for compiler X may not work for compiler X, version 2.0, 3.0, 4.0, etc. (assuming you're using version 1.0). .... snip ....

    Understand. Going back to your previous post, why is pre-increment faster than post-increment? And won't pre-increment skip the first element in the for loop?

    Thanks,
    Raptor

  8. #8
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,315

    Re: Vector iterators

    Quote Originally Posted by raptor88
    why is pre-increment faster than post-increment?
    Because a typical implementation of post-increment does more work than pre-increment, and in fact it might even call pre-increment. Of course, after compiler optimisation, it may be that they both result in the same code generated, so it would be more accurate to say that post-increment is not faster than pre-increment, and may be slower.

    Quote Originally Posted by raptor88
    And won't pre-increment skip the first element in the for loop?
    No as the increment is in a statement on its own.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  9. #9
    Join Date
    May 2012
    Posts
    57

    Re: Vector iterators

    Quote Originally Posted by laserlight View Post
    Because a typical implementation of post-increment does more work than pre-increment, and in fact it might even call pre-increment. Of course, after compiler optimisation, it may be that they both result in the same code generated, so it would be more accurate to say that post-increment is not faster than pre-increment, and may be slower.


    No as the increment is in a statement on its own.
    I wrote a test program and yes, pre-increment doesn't skip the first element. Goggling shows that a for loop works like a while loop with the increment occurring at the end of the loop. Also learned why a pre-increment can be faster but never slower than post-increment depending on the compiler.

    Thanks for helping out,
    Raptor
    Last edited by raptor88; December 1st, 2012 at 01:35 PM.

  10. #10
    Join Date
    May 2012
    Posts
    57

    Re: Vector iterators. How do they work with strings in a struct?

    A new question regarding vectors and iterators.

    I declared a struct that contains integers and one string. Then I instantiated a vector to hold the structs and set the total number of structs. My actual struct is pretty large so here's a sample to keep things simple:

    Code:
    struct MyStruct
    {
        int a
        int b
        string c
    }
    
    vector<MyStruct> myVect[8];
    
    for(vector<MyStruct>::size_type i = 0;  i < myVect.size();  ++i)
    {
        // do something.
    }
    Although I did not show it in the code above to keep things simple, I initialized the members of the struct and the strings are variable lengths. Also I know it's possible to use "push_back" to add elements to the vector but I have a reason why I need to establish the total size of the vector at time of instantiation. Also, my actual code compiles and works so that's not an issue.

    MY QUESTION:
    When I instantiated myVect with 8 elements, how did the compiler know how much memory to reserve and how to lay things out in memory AT THE TIME OF INSTANTIATION, when I initialized the structs in the vector with variable length strings AFTER the instantiation was done?

    Then how does incrementing the iterator "i" by only +1 each time work when each struct is effectively variable length in size? What are the actual mechanics involved?

    Thanks,
    Raptor
    Last edited by raptor88; December 1st, 2012 at 02:10 PM.

  11. #11
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,315

    Re: Vector iterators

    I note that this creates an array of 8 vector<MyStruct> objects:
    Code:
    vector<MyStruct> myVect[8];
    If you really wanted a vector of 8 MyStruct objects, then it should have been:
    Code:
    vector<MyStruct> myVect(8);
    Quote Originally Posted by raptor88
    When I instantiated myVect with 8 elements, how did the compiler know how much memory to reserve and how to lay things out in memory AT THE TIME OF INSTANTIATION, when I initialized the structs in the vector with variable length strings AFTER the instantiation was done?
    The memory used is for the MyStruct objects with the empty string members. If you change the string members later, more memory might be allocated at that later point.

    Quote Originally Posted by raptor88
    Then how does incrementing the iterator "i" by only +1 each time work when each struct is effectively variable length in size?
    Each MyStruct object has the same size with respect to sizeof. Anyway, the concept of an (input) iterator abstracts away this consideration, i.e., you just need to know that incrementing the iterator causes it to point to the next element.

    Quote Originally Posted by raptor88
    What are the actual mechanics involved?
    That depends on the implementation. Of course, since we are dealing with a vector here, you can imagine having a pointer to an element in a dynamic array. Incrementing the pointer would thus cause it to point to the next element.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  12. #12
    Join Date
    May 2012
    Posts
    57

    Re: Vector iterators

    Quote Originally Posted by laserlight View Post
    If you really wanted a vector of 8 MyStruct objects, then it should have been:
    Code:
    vector<MyStruct> myVect(8);
    Totally right. Being new to C++, I used the parenthesis for "myVect(8)" in my actual test code but used the [] in my example here. Thanks for catching that.

    Then how does incrementing the iterator "i" by only +1 each time work when each struct is effectively variable length in size?

    The memory used is for the MyStruct objects with the empty string members. If you change the string members later, more memory might be allocated at that later point.
    My understanding is that a vector is laid out in contiguous memory and not fragmented. So do you mean that the space for one character is allocated for the string in each structure at time of instantiation, and then the entire vector is reallocated each time a string is initialized?

    Then how does incrementing the iterator "i" by only +1 each time work when each struct is effectively variable length in size?

    Each MyStruct object has the same size with respect to sizeof. Anyway, the concept of an (input) iterator abstracts away this consideration, i.e., you just need to know that incrementing the iterator causes it to point to the next element.

    What are the actual mechanics involved?

    That depends on the implementation. Of course, since we are dealing with a vector here, you can imagine having a pointer to an element in a dynamic array. Incrementing the pointer would thus cause it to point to the next element.
    Although the "need to know" is that incrementing the iterator by +1 makes it point to the next element, I wanted to know how that actually works. (Yes, I used to take my toys apart when I was a kid and still have that habit )

    The ways how it works that I can imagine now are:

    1. The compiler finds the longest string that is initialized and allocates that amount of memory for every string in each struct. (Or allocates string space by a factor of 2) Then the iterator knows how much memory to jump each time to get to the next structure. Some how the iterator is multiplying that value like (iterator * jumpValue).

    -or-

    2. The compiler is allocating space for each variable length string as needed. It's storing the address of each struct in the vector in a table. The iterator used to scan the table to get the next address.

    I know it's not necessary to understand the mechanics but was just wondering if anyone knows how incrementing an interator by only +1 allows iterating through the vector with variable length strings.

    Thanks for the discussion,
    Raptor

  13. #13
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Vector iterators

    Quote Originally Posted by raptor88 View Post
    I know it's not necessary to understand the mechanics but was just wondering if anyone knows how incrementing an interator by only +1 allows iterating through the vector with variable length strings.
    It doesn't matter what the struct consists of. The sizeof(MyStruct) is the same, regardless of what the members happen to do at runtime.

    It is the sizeof() that determines how many bytes to increment. This is no different than the way basic arrays and pointers work.

    Regards,

    Paul McKenzie

  14. #14
    Join Date
    May 2012
    Posts
    57

    Re: Vector iterators

    Quote Originally Posted by Paul McKenzie View Post
    It doesn't matter what the struct consists of. The sizeof(MyStruct) is the same, regardless of what the members happen to do at runtime.
    This is what I'm trying to understand. How is the sizeof(MyStruct) the same for every struct when there is a variable length string in the struct? Without a variable length member in the struct it's easy to understand but with a variable length member, it's mind boggling. Especially when the "for" loop uses:

    Code:
    for (vector<MyStruct>::size_type i = 0;  i < myVect.size();  ++i);
    how does the "size_type" know what size each variable length struct will be? Especially if structs with a variable length string are push_back'd on the end of the vector during runtime in response to user input. (Mind boggling)

    (Please realize that this is just a "discussion" question. Just idle curiosity so to speak.)

    Thanks for the discussion,
    Raptor

  15. #15
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Vector iterators

    Quote Originally Posted by raptor88 View Post
    This is what I'm trying to understand. How is the sizeof(MyStruct) the same for every struct when there is a variable length string in the struct? Without a variable length member in the struct it's easy to understand but with a variable length member, it's mind boggling.
    You need to understand the difference between compile-time and runtime with respect to C++ types. This is a basic fundamental of the C++ and 'C' language.
    Code:
    #include <string>
    #include <iostream>
    
    using namespace std;
    int main()
    {
       std::string s;
       cout << sizeof(s) << "\n";
       s = "abc123456789123456789xyz";
       cout << sizeof(s) << "\n";
    }
    What results do you get? You see that sizeof(s) is the same, regardless of what you do at runtime to the string? The sizeof(string) doesn't magically change from 0 to 24 just becase it now contains 24 characters.

    The sizeof() is a compile-time constant -- it isn't a function, and nothing you can do at runtime can change the value. So sizeof(T) never changes and cannot change at runtime, and this is the reason why the iterator knows how many bytes to increment in the case of vector (and the case for simple arrays). The number of bytes that the vector iterator (or pointer) needs to jump by never changes and is set at compile-time.

    The memory that is allocated at runtime is from the free-store. It has absolutely nothing to do with the sizeof() the type involved. Here is another simple example showing this:
    Code:
    #include <iostream>
    using namespace std;
    int main()
    {
       char *ptr;
       cout << sizeof(ptr) << "\n";
       ptr = new char[100];
       cout << sizeof(ptr) << "\n";
       delete [] ptr;
       cout << sizeof(ptr) << "\n";
    }
    I've increased what is being pointed to by 100 bytes. Now I can store 100 characters pointed to by ptr, but what about sizeof(ptr)? Note it hasn't budged one bit. I delete the allocated memory, and still sizeof(ptr) doesn't change. It still remains the same value, regardless of what I do with ptr. Now extend this concept to classes. All a vector does is allocate memory from the free-store. The sizeof(std::vector<int>) doesn't change, regardless of what's done with it at runtime.

    Now a pointer to contiguous memory knows exactly how to go from one item to the next, due to sizeof(item) never changing. The iterator in the case of vector acts just like a pointer, and it knows exactly when a "+1" is issued, how many bytes to skip to get to the next item. Again, it has absolutely nothing to do with what you do with the types at runtime, which I demonstrated above.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; December 2nd, 2012 at 04:42 PM.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center