Query regarding iterators and vector

[prasadmpatil@gmail.com]

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>::it erator iter0;
for(iter0=a.beg in(); 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--------------------------------------

[Sam]

Re: Query regarding iterators and vector

prasadmpatil@gm ail.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)

iEYEABECAAYFAkh uo3oACgkQx9p3GY HlUOLeyACfUNo/pQKJ4Bt8lX36K0K ysbUG
5zYAn2o9oKalz38 aDj3p69vXn+PLsz/f
=7gEI
-----END PGP SIGNATURE-----

[Daniel T.]

Re: Query regarding iterators and vector

prasadmpatil@gm ail.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>::it erator iter0;
for(iter0=a.beg in(); iter0!=a.end(); iter0++)
{
cout << "\n value: " << (*iter0)<<endl;
if(*iter0 == 2)
{
a.push_back(4);
a.push_back(5);
}
}
cout<<"Vector test end";
}

[prasadmpatil@gmail.com]

Re: Query regarding iterators and vector

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...@earth link.netwrote:

prasadmpa...@gm ail.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>::it erator iter0;
   for(iter0=a.beg in(); iter0!=a.end(); iter0++)
   {
           cout << "\n value: " << (*iter0)<<endl;
           if(*iter0 == 2)
           {
                   a.push_back(4);
                   a.push_back(5);
           }
   }
   cout<<"Vector test end";
}

>
>

[Daniel T.]

Re: Query regarding iterators and vector

Jerry Coffin <jcoffin@taeus. comwrote:

prasadmpatil@gm ail.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>::it erator iter0;
for(iter0=a.beg in(); 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.

[Jerry Coffin]

Re: Query regarding iterators and vector

In article <daniel_t-C8B00E.10104205 072008@earthlin k.vsrv-
sjc.supernews.n et>, daniel_t@earthl ink.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.siz e()+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.

[Daniel T.]

Re: Query regarding iterators and vector

Jerry Coffin <jcoffin@taeus. comwrote:

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

Agreed.

[Prasad Patil]

Re: Query regarding iterators and vector

On Jul 5, 9:52 am, "Daniel T." <danie...@earth link.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?

[Daniel T.]

Re: Query regarding iterators and vector

Prasad Patil <prasadmpatil@g mail.comwrote:

On Jul 5, 9:52 am, "Daniel T." <danie...@earth link.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.

[Prasad Patil]

Re: Query regarding iterators and vector

On Jul 5, 6:31 pm, "Daniel T." <danie...@earth link.netwrote:

Prasad Patil <prasadmpa...@g mail.comwrote:

On Jul 5, 9:52 am, "Daniel T." <danie...@earth link.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_b ack(a(temp1));
vec_of_a.push_b ack(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.

[Jerry Coffin]

Re: Query regarding iterators and vector

In article <62d91254-dff3-4359-90f8-5da22195d8c6
@d45g2000hsc.go oglegroups.com> , prasadmpatil@gm ail.com says...

On Jul 5, 6:31 pm, "Daniel T." <danie...@earth link.netwrote:

Prasad Patil <prasadmpa...@g mail.comwrote:

On Jul 5, 9:52 am, "Daniel T." <danie...@earth link.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_b ack(a(temp1));
vec_of_a.push_b ack(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_ite rator, 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_b ack(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_b ack(temp1);
vec_of_a.push_b ack(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.

[Daniel T.]

Re: Query regarding iterators and vector

Prasad Patil <prasadmpatil@g mail.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_b ack(a(temp1));
vec_of_a.push_b ack(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.

[Prasad Patil]

Re: Query regarding iterators and vector

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_vec tor
2. Generate states based on transition rules and store them
in a temporary_vecto r.
3. Insert newly generated states from temporary vector into
state_space_vec tor after checking if they already exist in the
state_space_vec tor.
4. Increment the curentPosition.
} while(currentPo sition < state_space_vec tor.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...@earth link.netwrote:

Prasad Patil <prasadmpa...@g mail.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_b ack(a(temp1));
 vec_of_a.push_b ack(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.

[Daniel T.]

Re: Query regarding iterators and vector

Prasad Patil <prasadmpatil@g mail.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.