How ro Iterate a portion of a container

Discussion in 'C++' started by toton, Sep 11, 2006.

  1. toton

    toton Guest

    Hi,
    I have a container class, and I want to iterate over a portion of the
    container class while I insert/remove item from it. Noting down the
    present location & constructing iterator from there is working, however
    storing a copy of the iterator itself do not work.
    For example,
    If I have a vector of int.
    vector<int> v;
    v.push_back(5);
    v.push_back(10);
    I pushed back two element into it.
    Iterate over the vector from begin to end.
    typedef vector<int>::iterator VecIterator;
    for(VecIterator it = v.begin() ; it!= v.end(); ++it){
    cout<<*it <<" ";
    }
    mark the current end as beginning of my range.
    VecIterator beg1 = v.end();
    Insert few more elements
    v.push_back(12);
    v.push_back(15);
    now marke the end.
    VecIterator end1 = v.end();
    Iterate over the range.
    for(VecIterator it = beg1 ; it!= end1; ++it){
    cout<<*it <<" ";
    }
    This code do not work. I need to return a range (a pair of iterator for
    a big container) for processing only, and a class stores the pair of
    iterators for operation.
    However changing the code to
    int size = v.size();
    v.push_back(12);
    v.push_back(15);
    VecIterator beg1 = v.begin()+size;
    VecIterator end1 = v.end();
    works.
    However if the container class is not a vector, size may not give the
    current location in the container. As in my case I have a custom
    circular_buffer container, which can write over a fully occupied vector
    also. In that case size may be different from the present location.
    In general case how to mark such range. In my program, one large vector
    contains the data, and different class are supposed to hold different
    view of the data (i.e different range for operation). Also as the range
    contains two iterator, and the iterator do not have a default ctor, it
    is not possible to store them as class member (I store them as pointer
    ), as the range is not known at the construct time, but assigned later.
    Is it a good way to store the range? or will I need to store raw
    position in terms of size_t and return an newly constructed range every
    time it is called from the position?
    In that case the code may be little complex, as in my container the
    positions are relative, and wrapped one rather than linear in case of
    vector.

    Any help is appreciated.
    toton, Sep 11, 2006
    #1
    1. Advertising

  2. toton

    Jens Theisen Guest

    "toton" <> writes:

    > v.push_back(12);
    > v.push_back(15);
    > now marke the end.
    > VecIterator end1 = v.end();
    > Iterate over the range.
    > for(VecIterator it = beg1 ; it!= end1; ++it){
    > cout<<*it <<" ";
    > }
    > This code do not work.


    Pushing back beyond the current capacity in the vector invalidates
    iterators. Try reserving enough capacity first (with the reserve
    member function). Another way is to use std::list, as its iterators
    stay valid under insertion and removal (except removal of the element
    your iterator points to).

    Cheers,

    Jens
    Jens Theisen, Sep 11, 2006
    #2
    1. Advertising

  3. toton

    toton Guest

    Jens Theisen wrote:
    > "toton" <> writes:
    >
    > > v.push_back(12);
    > > v.push_back(15);
    > > now marke the end.
    > > VecIterator end1 = v.end();
    > > Iterate over the range.
    > > for(VecIterator it = beg1 ; it!= end1; ++it){
    > > cout<<*it <<" ";
    > > }
    > > This code do not work.

    >
    > Pushing back beyond the current capacity in the vector invalidates
    > iterators. Try reserving enough capacity first (with the reserve
    > member function). Another way is to use std::list, as its iterators
    > stay valid under insertion and removal (except removal of the element
    > your iterator points to).
    >
    > Cheers,
    >
    > Jens

    Thanks for the reply. with reserve it works fine. However the main
    reason is that iterator do not keep the present index in the vector.
    rather it keeps a pointer to the present location. Thus when capacity
    increases it fails to work. Is it a standard behavior?

    I do not use vector in my implementation I use a circular buffer, which
    is something like deque but with a reserve facility. It can remove or
    insert from front & back easily (const time). and can work as circular
    buffer also. in that case it removes from tail automatically when
    memory gets exhosted (a cyclic kind of structure). It has the facility
    like one can ensure additional capacity for the cyclic buffer
    temporarily before a series of push_back. Or one can simply use it as a
    deque with an reserve memory and increment factor.
    here the code to use it as deque
    CircularBuffer<int> cb(2,2);//size 2, increment 2
    cb.use_as_circular_buffer(false);
    cb.push_back(0);
    cb.push_back(1);

    cout<<"size "<<cb.size() << " cap " <<cb.capacity()<<endl;
    typedef CircularBuffer<int>::iterator VecIterator;
    for(VecIterator it = cb.begin() ; it!= cb.end(); ++it){
    cout<<*it <<" ";
    }
    cout<<endl;
    cb.push_back(2);
    cout<<"size "<<cb.size() << " cap " <<cb.capacity()<<endl;
    for(VecIterator it = cb.begin() ; it!= cb.end(); ++it){
    cout<<*it <<" ";
    }
    cout<<endl;
    cb.push_back(3);
    cout<<"size "<<cb.size() << " cap " <<cb.capacity()<<endl;
    for(VecIterator it = cb.begin() ; it!= cb.end(); ++it){
    cout<<*it <<" ";
    }
    size 2 cap 2
    0 1
    size 3 cap 4
    0 1 2
    size 4 cap 4
    0 1 2 3
    The use as circular buffer,
    comment the line, cb.use_as_circular_buffer(false);
    The output is like,
    size 2 cap 2
    0 1
    size 2 cap 2
    1 2
    size 2 cap 2
    2 3
    Press ENTER to continue.
    And marking works as usual for circular buffer.
    Thus the code gives the output,
    CircularBuffer<int> cb(3,2);
    //cb.use_as_circular_buffer(false);
    cb.push_back(0);
    cb.push_back(1);

    cout<<"size "<<cb.size() << " cap " <<cb.capacity()<<endl;
    typedef CircularBuffer<int>::iterator VecIterator;
    for(VecIterator it = cb.begin() ; it!= cb.end(); ++it){
    cout<<*it <<" ";
    }
    cout<<endl;
    VecIterator beg = cb.end()-1;//marked one past. end ponts one more
    cb.push_back(2);
    cb.push_back(3);
    VecIterator end = cb.end();

    cout<<"size "<<cb.size() << " cap " <<cb.capacity()<<endl;
    for(VecIterator it = beg ; it!= end; ++it){
    cout<<*it <<" ";
    }
    cout<<endl;

    cout<<"size "<<cb.size() << " cap " <<cb.capacity()<<endl;
    for(VecIterator it = cb.begin() ; it!= cb.end(); ++it){
    cout<<*it <<" ";
    }
    size 2 cap 3
    0 1
    size 3 cap 3
    2 3 => marked data!
    size 3 cap 3
    1 2 3 =>all data.

    Ofcourse, here also if the buffer gets recycled, the marked data will
    give new data within that region (as the old data may get partially or
    fully removed).
    toton, Sep 11, 2006
    #3
  4. toton

    Jens Theisen Guest

    "toton" <> writes:

    > Thanks for the reply. with reserve it works fine. However the main
    > reason is that iterator do not keep the present index in the vector.
    > rather it keeps a pointer to the present location. Thus when capacity
    > increases it fails to work. Is it a standard behavior?


    Yes. Each container has it's own iterator invalidation
    semantics. std::list almost never invalidates, std::vector is quite
    fragile. std::string sometimes even invalidates iterators on non-const
    calls to begin/end, operator[], etc. due to copy on write.

    If you have a nonstandard container it's up to this container to
    define the semantics. So I can't tell you what these semantics are.

    Jens
    Jens Theisen, Sep 11, 2006
    #4
    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. Gogo
    Replies:
    1
    Views:
    2,096
    Sudsy
    Sep 4, 2003
  2. runescience
    Replies:
    0
    Views:
    1,451
    runescience
    Feb 9, 2006
  3. John
    Replies:
    4
    Views:
    907
    RedGrittyBrick
    Apr 1, 2008
  4. Luqman
    Replies:
    2
    Views:
    907
    Luqman
    Apr 27, 2008
  5. Mike Copeland

    Accessing Portion(s) of STL Container

    Mike Copeland, Oct 30, 2010, in forum: C++
    Replies:
    4
    Views:
    256
    RaZiel
    Oct 30, 2010
Loading...

Share This Page