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

Quote:

---

Originally Posted by raptor88

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

Quote:

---

Originally Posted by Paul McKenzie

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?

Quote:

---

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?

Quote:

---

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

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 << ' ';

---

Quote:

---

Originally Posted by raptor88

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

Quote:

---

Originally Posted by OReubens

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?

Quote:

---

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

Quote:

---

Originally Posted by Paul McKenzie

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

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.

Quote:

---

Originally Posted by laserlight

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

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

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.

Quote:

---

Originally Posted by laserlight

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.

Quote:

---

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?

Quote:

---

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

Quote:

---

Originally Posted by raptor88

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

Quote:

---

Originally Posted by Paul McKenzie

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

Quote:

---

Originally Posted by raptor88

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

Quote:

---

Originally Posted by Paul McKenzie

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.

---

AH HA MOMENT!

I can see now that when the vector of structs is instantiated, space for the string is not allocated "within" the struct. Just a pointer to the string is the actual member in the struct itself. The string is actually stored elsewhere in memory. So the size of the struct remains constant and the compiler knows exactly how many bytes make up the struct which is always a constant value.

Then all the compiler has to do is:

++ iterator
interator * jumpValue

to get to the next struct.

You're the man Paul. Thanks for helping me understand it! (Hope that's right anyway :) )
This technique can actually be used in programs I write in the future.

Thanks,
Raptor

in all fairness. the real motivation behind why STL works the way it does and why method 1 is preferred, is because it allows you to change the underlying container without changing the rest of code.

If for some reason you decide tomorrow that you would rather have a list instead of a vector, then the iterator approach will continue to compile and run. This flexibility can be a HUGE benefit. And a benefit that is made manifest among others by the various <algorithms> YOu can build your own library of algoritms and templates that are based of containers, and even containers of your own. if you follow the "stl way of doing things", you get the benefit that all those algoritms and other templates will be interchangable (to a degree ofc, there are limits to how much you can make one container behaviourly identical to another).

breaking down the code into 2 or 3 works ONLY under the assumption that the container has a [] operator that takes an index. That's true for vector, but not for other containers.


Using the containers in the way they were intended means you benefit from the flexibility of changing the underlying container if you need to (within reason). It also means you could benefit from improvements in the library and how the compiler handles the STL code (some compilers have specific optimisations for the STL code). Which you may not get from accessing the container via method 2 or 3.