How ro Iterate a portion of a container

[toton]

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.

 

[Jens Theisen]

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

 

[toton]

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).

 

[Jens Theisen]

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