Query regarding iterators and vector

Discussion in 'C++' started by prasadmpatil@gmail.com, Jul 4, 2008.

  1. Guest

    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<int> a;

    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, 2008
    #1
    1. Advertising

  2. Guest

    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." <> wrote:
    > 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<int> a;

    >
    > >    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, 2008
    #2
    1. Advertising

  3. Jerry Coffin Guest

    In article <1ce7647b-4099-41b0-be32-
    >,
    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<int> a;
    >
    > 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.

    However, directly using an iterator in a loop is a sign that you're not
    really using algorithms as intended. In this case you're adding the
    sequence '4,5' each time you find a '2' in the input. I'd do that
    something like this:

    int n = std::count(a.begin(), a.end(), 2);
    for (int i=0;i<n;i++) {
    a.push_back(4);
    a.push_back(5);
    }

    It's also possible that you only really intended to add the '4,5' once,
    regardless of how many times '2' was found in the input. In that case,
    I'd do something like:

    if (std::binary_search(a.begin(), a.end(), 2)) {
    a.push_back(4);
    a.push_back(5);
    }

    or, if the fact that the input was sorted was really just an accident,
    and it could be in random order:

    if (std::find(a.begin(), a.end(), 2)!=a.end()) {
    a.push_back(4);
    a.push_back(5);
    }

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Jul 5, 2008
    #3
  4. Jerry Coffin Guest

    In article <-
    sjc.supernews.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.
     
    Jerry Coffin, Jul 5, 2008
    #4
  5. Prasad Patil Guest

    On Jul 5, 9:52 am, "Daniel T." <> wrote:
    > Jerry Coffin <> wrote:
    > > 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?
     
    Prasad Patil, Jul 5, 2008
    #5
  6. Prasad Patil Guest

    On Jul 5, 6:31 pm, "Daniel T." <> wrote:
    > Prasad Patil <> wrote:
    > > On Jul 5, 9:52 am, "Daniel T." <> wrote:
    > > > Jerry Coffin <> wrote:
    > > > > 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<b> vals)
    {
    objB= vals;
    }

    vector<b> objB;
    };


    int main()
    {
    vector<a> vec_of_a;

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

    vector<b> temp2;
    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.
     
    Prasad Patil, Jul 7, 2008
    #6
  7. Jerry Coffin Guest

    In article <62d91254-dff3-4359-90f8-5da22195d8c6
    @d45g2000hsc.googlegroups.com>, says...
    > On Jul 5, 6:31 pm, "Daniel T." <> wrote:
    > > Prasad Patil <> wrote:
    > > > On Jul 5, 9:52 am, "Daniel T." <> wrote:
    > > > > Jerry Coffin <> wrote:
    > > > > > 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<b> vals)
    > {
    > objB= vals;
    > }
    >
    > vector<b> objB;
    > };
    >
    >
    > int main()
    > {
    > vector<a> vec_of_a;
    >
    > vector<b> temp1;
    > temp1.push_back(b(1));
    > temp1.push_back(b(2));
    > temp1.push_back(b(3));
    >
    > vector<b> temp2;
    > 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<b> objB;
    public:
    a(vector<B> const &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<a> vec_of_a;
    vector<b> temp1;

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

    vector<b> temp2;
    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.
     
    Jerry Coffin, Jul 7, 2008
    #7
  8. Prasad Patil Guest

    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." <> wrote:
    > Prasad Patil <> wrote:
    > > 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<b> vals)
    > >  {
    > >     objB= vals;
    > >  }

    >
    > >     vector<b> objB;
    > > };

    >
    > > int main()
    > > {
    > >  vector<a> vec_of_a;

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

    >
    > >  vector<b> temp2;
    > >  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<b> objB;
    > 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, Jul 11, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    24,135
  2. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    524
    Kai-Uwe Bux
    May 8, 2005
  3. David Crawford

    Question on vector of vector iterators

    David Crawford, Dec 15, 2005, in forum: C++
    Replies:
    3
    Views:
    517
  4. Replies:
    8
    Views:
    2,007
    Csaba
    Feb 18, 2006
  5. , India
    Replies:
    10
    Views:
    1,106
    James Kanze
    Aug 8, 2009
Loading...

Share This Page