By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,814 Members | 1,671 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,814 IT Pros & Developers. It's quick & easy.

Query regarding iterators and vector

P: n/a
I am new STL programming.
I have a query regarding vectors. If I am iterating over a vector
using a iterator, but do some operations that modify the size of the
vector. Will the iterator recognize this?

I wrote the following program to test this out.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
vector<inta;

a.push_back(1);
a.push_back(2);
a.push_back(3);
cout<<"Vector test begin"<<endl;
vector<int>::iterator iter0;
for(iter0=a.begin(); iter0!=a.end(); iter0++)
{
cout << "\n value: " << (*iter0)<<endl;
if(*iter0 == 2)
{
a.push_back(4);
a.push_back(5);
}
}
cout<<"Vector test end";
}

I am getting the following output. Could somebody please explain what
is happening in my program. I am thoroughly confused.

---------------------------------------Output------------------
Vector test begin

value: 1

value: 2

value: 3

value: 4

value: 0

value: 41

value: 1

value: 2

value: 3

value: 4

value: 5

value: 4

value: 5
Vector test end

----------------------------------------------End of
Output--------------------------------------
Jul 4 '08 #1
Share this Question
Share on Google+
13 Replies


P: n/a
Sam
pr**********@gmail.com writes:
I am new STL programming.
I have a query regarding vectors. If I am iterating over a vector
using a iterator, but do some operations that modify the size of the
vector. Will the iterator recognize this?
No. An insertion or deletion in a std::vector invalidates all existing
iterators.

Use std::list if you want iterators to remain valid after an insertion (or a
deletion, if the iterator does not point to the std::list member that was
deleted).
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkhuo3oACgkQx9p3GYHlUOLeyACfUNo/pQKJ4Bt8lX36K0KysbUG
5zYAn2o9oKalz38aDj3p69vXn+PLsz/f
=7gEI
-----END PGP SIGNATURE-----

Jul 4 '08 #2

P: n/a
pr**********@gmail.com wrote:
I am new STL programming.
I have a query regarding vectors. If I am iterating over a vector
using a iterator, but do some operations that modify the size of the
vector. Will the iterator recognize this?
No.

A vector's iterators are invalidated when its memory is reallocated.
Additionally, inserting or deleting an element in the middle of a
vector invalidates all iterators that point to elements following the
insertion or deletion point. It follows that you can prevent a
vector's iterators from being invalidated if you use reserve() to
preallocate as much memory as the vector will ever use, and if all
insertions and deletions are at the vector's end.
<http://www.sgi.com/tech/stl/Vector.html>
I wrote the following program to test this out.
Try adding "a.reserve(5);" at any point after 'a' is defined, and before
the loop.
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
vector<inta;

a.push_back(1);
a.push_back(2);
a.push_back(3);
cout<<"Vector test begin"<<endl;
vector<int>::iterator iter0;
for(iter0=a.begin(); iter0!=a.end(); iter0++)
{
cout << "\n value: " << (*iter0)<<endl;
if(*iter0 == 2)
{
a.push_back(4);
a.push_back(5);
}
}
cout<<"Vector test end";
}
Jul 4 '08 #3

P: n/a
Thank you all for the replies. I used a loop variable and
vector.size() instead of the iterator to solve my problem.

On Jul 4, 6:31*pm, "Daniel T." <danie...@earthlink.netwrote:
prasadmpa...@gmail.com wrote:
I am new STL programming.
I have a query regarding vectors. If I am iterating over a vector
using a iterator, but do some operations that modify the size of the
vector. Will the iterator recognize this?

No.

* *A vector's iterators are invalidated when its memory is reallocated.
* *Additionally, inserting or deleting an element in the middle of a
* *vector invalidates all iterators that point to elements following the
* *insertion or deletion point. It follows that you can prevent a
* *vector's iterators from being invalidated if you use reserve() to
* *preallocate as much memory as the vector will ever use, and if all
* *insertions and deletions are at the vector's end.
* *<http://www.sgi.com/tech/stl/Vector.html>
I wrote the following program to test this out.

Try adding "a.reserve(5);" at any point after 'a' is defined, and before
the loop.
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
* *vector<inta;
* *a.push_back(1);
* *a.push_back(2);
* *a.push_back(3);
* *cout<<"Vector test begin"<<endl;
* *vector<int>::iterator iter0;
* *for(iter0=a.begin(); iter0!=a.end(); iter0++)
* *{
* * * * * *cout << "\n value: " << (*iter0)<<endl;
* * * * * *if(*iter0 == 2)
* * * * * *{
* * * * * * * * * *a.push_back(4);
* * * * * * * * * *a.push_back(5);
* * * * * *}
* *}
* *cout<<"Vector test end";
}

Jul 5 '08 #4

P: n/a
Jerry Coffin <jc*****@taeus.comwrote:
pr**********@gmail.com says...
I am new STL programming.
I have a query regarding vectors. If I am iterating over a vector
using a iterator, but do some operations that modify the size of the
vector. Will the iterator recognize this?

I wrote the following program to test this out.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
vector<inta;

a.push_back(1);
a.push_back(2);
a.push_back(3);
cout<<"Vector test begin"<<endl;
vector<int>::iterator iter0;
for(iter0=a.begin(); iter0!=a.end(); iter0++)
{
cout << "\n value: " << (*iter0)<<endl;
if(*iter0 == 2)
{
a.push_back(4);
a.push_back(5);
}
}
cout<<"Vector test end";
}

A push_back on a vector invalidates all iterators into that vector.
Not quite true. push_back only invalidates the iterators if size() <
capacity() before the push_back occurs. If the OP had done a reserve(5)
before entering the loop, all would have been well.
Jul 5 '08 #5

P: n/a
In article <da****************************@earthlink.vsrv-
sjc.supernews.net>, da******@earthlink.net says...

[ ... ]
A push_back on a vector invalidates all iterators into that vector.

Not quite true. push_back only invalidates the iterators if size() <
capacity() before the push_back occurs. If the OP had done a reserve(5)
before entering the loop, all would have been well.
True -- better than 'reserve(5)' would have been something like:
a.reserve(a.size()+2)

I still think it's better to directly express what you're doing with an
algorithm though.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 5 '08 #6

P: n/a
Jerry Coffin <jc*****@taeus.comwrote:
I still think it's better to directly express what you're doing with an
algorithm though.
Agreed.
Jul 5 '08 #7

P: n/a
On Jul 5, 9:52*am, "Daniel T." <danie...@earthlink.netwrote:
Jerry Coffin <jcof...@taeus.comwrote:
I still think it's better to directly express what you're doing with an
algorithm though.

Agreed.
Thank you all for the suggestions.
What I am actually trying to do is generate a state space. I start
with a initial state and then based on rule matches generate
additional states. I continue doing this until no new states are
generated. I am storing these states in a vector. Is this a good idea?
Based on all the above replies there are multiple ways of doing this
namely

1. using vector.reserve()
2. using list
3. using a loop variable.

Which is the best way to implement this?

Jul 5 '08 #8

P: n/a
Prasad Patil <pr**********@gmail.comwrote:
On Jul 5, 9:52*am, "Daniel T." <danie...@earthlink.netwrote:
Jerry Coffin <jcof...@taeus.comwrote:
I still think it's better to directly express what you're doing with an
algorithm though.
Agreed.

Thank you all for the suggestions.
What I am actually trying to do is generate a state space. I start
with a initial state and then based on rule matches generate
additional states. I continue doing this until no new states are
generated. I am storing these states in a vector. Is this a good idea?
Based on all the above replies there are multiple ways of doing this
namely

1. using vector.reserve()
2. using list
3. using a loop variable.

Which is the best way to implement this?
Jerry pointed the way to the best solution. For any particular "state
space" there is a query, how many new states should be generated, and a
command, generate X states.

The loop you presented tried to both determine the number of new states
and generate them at the same time, and I think that is doing too much.
Better would be to have two separate functions, one that determines the
new states to generate, and another that actually does it.
Jul 5 '08 #9

P: n/a
On Jul 5, 6:31*pm, "Daniel T." <danie...@earthlink.netwrote:
Prasad Patil <prasadmpa...@gmail.comwrote:
On Jul 5, 9:52*am, "Daniel T." <danie...@earthlink.netwrote:
Jerry Coffin <jcof...@taeus.comwrote:
I still think it's better to directly express what you're doing with an
algorithm though.
Agreed.
Thank you all for the suggestions.
What I am actually trying to do is generate a state space. I start
with a initial state and then based on rule matches generate
additional states. I continue doing this until no new states are
generated. I am storing these states in a vector. Is this a good idea?
Based on all the above replies there are multiple ways of doing this
namely
1. using vector.reserve()
2. using list
3. using a loop variable.
Which is the best way to implement this?

Jerry pointed the way to the best solution. For any particular "state
space" there is a query, how many new states should be generated, and a
command, generate X states.

The loop you presented tried to both determine the number of new states
and generate them at the same time, and I think that is doing too much.
Better would be to have two separate functions, one that determines the
new states to generate, and another that actually does it.
Thanks Daniel and Jerry for the advice. I did implement the algorithm
the way you suggested.

I have another newbie question.
-----------------------------

class b{

public: b(int val)
{
var = val;
}
int var;

};

class a{
public:
a(vector<bvals)
{
objB= vals;
}

vector<bobjB;
};
int main()
{
vector<avec_of_a;

vector<btemp1;
temp1.push_back(b(1));
temp1.push_back(b(2));
temp1.push_back(b(3));

vector<btemp2;
temp2.push_back(b(1));
temp2.push_back(b(2));
temp2.push_back(b(3));

vec_of_a.push_back(a(temp1));
vec_of_a.push_back(a(temp2));

}

//If I need to add another element to temp2 after it has been pushed
to vec_of_a, how do I do it? because as I understand iterators don't
allow me to modify the elements of the vector.

Jul 7 '08 #10

P: n/a
In article <62d91254-dff3-4359-90f8-5da22195d8c6
@d45g2000hsc.googlegroups.com>, pr**********@gmail.com says...
On Jul 5, 6:31*pm, "Daniel T." <danie...@earthlink.netwrote:
Prasad Patil <prasadmpa...@gmail.comwrote:
On Jul 5, 9:52*am, "Daniel T." <danie...@earthlink.netwrote:
Jerry Coffin <jcof...@taeus.comwrote:
I still think it's better to directly express what you're doing with an
algorithm though.
Agreed.
Thank you all for the suggestions.
What I am actually trying to do is generate a state space. I start
with a initial state and then based on rule matches generate
additional states. I continue doing this until no new states are
generated. I am storing these states in a vector. Is this a good idea?
Based on all the above replies there are multiple ways of doing this
namely
1. using vector.reserve()
2. using list
3. using a loop variable.
Which is the best way to implement this?
Jerry pointed the way to the best solution. For any particular "state
space" there is a query, how many new states should be generated, and a
command, generate X states.

The loop you presented tried to both determine the number of new states
and generate them at the same time, and I think that is doing too much.
Better would be to have two separate functions, one that determines the
new states to generate, and another that actually does it.
Thanks Daniel and Jerry for the advice. I did implement the algorithm
the way you suggested.

I have another newbie question.
-----------------------------

class b{

public: b(int val)
{
var = val;
}
int var;

};

class a{
public:
a(vector<bvals)
{
objB= vals;
}

vector<bobjB;
};
int main()
{
vector<avec_of_a;

vector<btemp1;
temp1.push_back(b(1));
temp1.push_back(b(2));
temp1.push_back(b(3));

vector<btemp2;
temp2.push_back(b(1));
temp2.push_back(b(2));
temp2.push_back(b(3));

vec_of_a.push_back(a(temp1));
vec_of_a.push_back(a(temp2));

}

//If I need to add another element to temp2 after it has been pushed
to vec_of_a, how do I do it? because as I understand iterators don't
allow me to modify the elements of the vector.
Yes and no. Iterators allow you to modify the individual elements --
i.e. an iterator gives you access to an element, and you can modify that
element by writing to it.

A normal iterator does NOT give you access to the container that holds
the element. If you want to add an item to the container, you need some
access to the container, such as using the container's push_back member,
or creating some sort of insert iterator for the container (e.g.
insert_iterator, back_insert_iterator, etc.)

As you've defined things right now, the objB member of class a is
public, so you can do something like this:

vec_of_a.push_back(a(temp2));

// add element to vec_of_a[0]
vec_of_a[0].objB.push_back(b(4));

That's probably not a good idea though -- generally speaking, a class
shouldn't give direct access to its internal data. If you want class a
to act like a vector, you could provide a vector-like interface to do
so.

class a {
vector<bobjB;
public:
a(vector<Bconst &vals) : objB(vals) {}

void push_back(b newB) { objB.push_back(newB); }
};

Note that passing a vector by value is (at least potentially) quite
expensive, so for this situation I've passed it by reference (to const)
instead.

Also note that since the ctors for neither a nor b is explicit, all the
conversions can be done implicitly:

int main() {
vector<avec_of_a;
vector<btemp1;

temp1.push_back(1);
temp1.push_back(2);
temp1.push_back(3);

vector<btemp2;
temp2.push_back(1);
temp2.push_back(2);
temp2.push_back(3);

vec_of_a.push_back(temp1);
vec_of_a.push_back(temp2);

return 0;
}

Of course it may be open to question whether 1) the explicit cases are
clearer, and/or 2) you might want to make the ctors explicit, so these
conversions won't happen by accident.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 7 '08 #11

P: n/a
Prasad Patil <pr**********@gmail.comwrote:
Thanks Daniel and Jerry for the advice. I did implement the algorithm
the way you suggested.

I have another newbie question.
-----------------------------

class b{

public: b(int val)
{
var = val;
}
int var;

};

class a{
public:
a(vector<bvals)
{
objB= vals;
}

vector<bobjB;
};
int main()
{
vector<avec_of_a;

vector<btemp1;
temp1.push_back(b(1));
temp1.push_back(b(2));
temp1.push_back(b(3));

vector<btemp2;
temp2.push_back(b(1));
temp2.push_back(b(2));
temp2.push_back(b(3));

vec_of_a.push_back(a(temp1));
vec_of_a.push_back(a(temp2));

}

If I need to add another element to temp2 after it has been pushed
to vec_of_a, how do I do it?
First, temp2 has not been pushed into vec_of_a. A *copy* of temp2 has
been made by the object vec_of_a[1].

I suspect that what you are really asking is how to add a 'b' to the 'a'
object that occupies that position in vec_of_a. The answer is that you
provide a member-function in 'a' that lets you do it.

class a {
vector<bobjB;
public:
a( const vector<b>& vals ): objB( vals ) { }

void push_back( const B& b ) {
objB.push_back( b );
}
};

in main:

vec_of_a[0].push_back( b(5) );
because as I understand iterators don't allow me to modify the
elements of the vector.
Iterators allow you to modify the elements in the vector, they *don't*
allow you to modify the vector itself. Understanding this distinction
will go a long way toward understanding iterators.
Jul 7 '08 #12

P: n/a
Thanks Dan and Jerry for the replies :) Really appreciate the help .
I was able to implement the state space and this how I did it..
Slightly different from what you guys suggested, but works for me.

currentPosition = 0;
do{

1. Get state at currentPosition in the state_space_vector
2. Generate states based on transition rules and store them
in a temporary_vector.
3. Insert newly generated states from temporary vector into
state_space_vector after checking if they already exist in the
state_space_vector.
4. Increment the curentPosition.
} while(currentPosition < state_space_vector.size());

A final newbie question. Can you point me to some resources regarding
copy constructor, return using reference/copy. I regularly get
confused by these. (I am mainly a java programmer so everything is
return by reference which is not always the case in c++).

On Jul 7, 6:56*am, "Daniel T." <danie...@earthlink.netwrote:
Prasad Patil <prasadmpa...@gmail.comwrote:
Thanks Daniel and Jerry for the advice. I did implement the algorithm
the way you suggested.
I have another newbie question.
-----------------------------
class b{
public: * b(int val)
*{
* * var = val;
*}
*int var;
};
class a{
*public:
* * a(vector<bvals)
*{
* * objB= vals;
*}
* * vector<bobjB;
};
int main()
{
*vector<avec_of_a;
*vector<btemp1;
*temp1.push_back(b(1));
*temp1.push_back(b(2));
*temp1.push_back(b(3));
*vector<btemp2;
*temp2.push_back(b(1));
*temp2.push_back(b(2));
*temp2.push_back(b(3));
*vec_of_a.push_back(a(temp1));
*vec_of_a.push_back(a(temp2));
}
If I need to add another element to temp2 after it has been pushed
to vec_of_a, how do I do it?

First, temp2 has not been pushed into vec_of_a. A *copy* of temp2 has
been made by the object vec_of_a[1].

I suspect that what you are really asking is how to add a 'b' to the 'a'
object that occupies that position in vec_of_a. The answer is that you
provide a member-function in 'a' that lets you do it.

class a {
* *vector<bobjB;
public:
* *a( const vector<b>& vals ): objB( vals ) { }

* *void push_back( const B& b ) {
* * * objB.push_back( b );
* *}

};

in main:

vec_of_a[0].push_back( b(5) );
because as I understand iterators don't allow me to modify the
elements of the vector.

Iterators allow you to modify the elements in the vector, they *don't*
allow you to modify the vector itself. Understanding this distinction
will go a long way toward understanding iterators.
Jul 11 '08 #13

P: n/a
Prasad Patil <pr**********@gmail.comwrote:
A final newbie question. Can you point me to some resources regarding
copy constructor, return using reference/copy.
The copy constructor "Type(const Type&);" doesn't return anything.
Jul 11 '08 #14

This discussion thread is closed

Replies have been disabled for this discussion.