help for back_inserter and end()

[Jess]

Hello,

The iterator adaptor "back_inserter" takes a container and returns a
iterator so that we can insert elements to the end of the container.
Out of curiosity, I tried to look at what element the returned
iterator refers to. Here is my code:

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

cout << (*(back_inserter(v)));
return 0;
}

The code above couldn't compile. Since "back_inserter" returns an
iterator, then I would think I can dereference it. What's wrong with
it?

I also tried to copy containers using "copy", and instead of
"back_inserter", I used "end()". The code is:

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<int> w;
v.push_back(3);
v.push_back(4);

copy(w.begin(),w.end(),v.end()); //instead of back_inserter, I
used .end()

for(vector<int>::const_iterator i = v.begin(); i != v.end(); i++)
cout << (*i) << endl;

return 0;
}

I was told the code above was wrong, but surprisingly, it compiled and
worked. I'm really puzzled by what "back_inserter" does and when I
can replace back_inserter by copy.

Thanks a lot!

 

[P.J. Plauger]

The iterator adaptor "back_inserter" takes a container and returns a
iterator so that we can insert elements to the end of the container.
Out of curiosity, I tried to look at what element the returned
iterator refers to. Here is my code:

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

cout << (*(back_inserter(v)));
return 0;
}

The code above couldn't compile. Since "back_inserter" returns an
iterator, then I would think I can dereference it. What's wrong with
it?

A back_inserter is an output iterator -- you can't read with it,
only write.

I also tried to copy containers using "copy", and instead of
"back_inserter", I used "end()". The code is:

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<int> w;
v.push_back(3);
v.push_back(4);

copy(w.begin(),w.end(),v.end()); //instead of back_inserter, I
used .end()

for(vector<int>::const_iterator i = v.begin(); i != v.end(); i++)
cout << (*i) << endl;

return 0;
}

I was told the code above was wrong, but surprisingly, it compiled and
worked.

It "worked" only in the sense that the nasty thing you did happened
not to bite -- you overwrote the end of the vector. Depending on
the capacity of the vector, or whatever follows it in memory, the
copy may or may not cause apparent damage. But the vector doesn't
get any bigger, as your display loop should have revealed.

I'm really puzzled by what "back_inserter" does and when I
can replace back_inserter by copy.

Well, back_inserter cooperates with the underlying container in
growing it as needed, while copy doesn't.

HTH,

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Jess]

Thanks for the reply!

It "worked" only in the sense that the nasty thing you did happened
not to bite -- you overwrote the end of the vector. Depending on
the capacity of the vector, or whatever follows it in memory, the
copy may or may not cause apparent damage. But the vector doesn't
get any bigger, as your display loop should have revealed.

I understand for vectors, the "capacity" is different to the "size",
but I'm not sure how "capacity" affects the result. If I used "end()"
for copying and suppose I reached the limit of the capacity, then will
the new elements, which are being added to the vector, be silently
discarded since the vector's capacity is not increased?

 

[P.J. Plauger]

Thanks for the reply!


I understand for vectors, the "capacity" is different to the "size",
but I'm not sure how "capacity" affects the result. If I used "end()"
for copying and suppose I reached the limit of the capacity, then will
the new elements, which are being added to the vector, be silently
discarded since the vector's capacity is not increased?

Let's try again. The copy function does *not* increase the size of
the vector. A back_inserter will, by calling insert for the vector;
but copy just scribbles on memory. If you have sufficient capacity,
you luck out and the copy is just a waste of time (the vector doesn't
get any bigger). But if you don't, then you write into terra incognita,
possibly messing up another important but completely unrelated object.
In no event will copy be smart enough to "silently discard" elements,
and in no event will copy change the size or capacity of the vector.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Mike Wahler]

Thanks for the reply!


I understand for vectors, the "capacity" is different to the "size",
but I'm not sure how "capacity" affects the result.

Officially, it doesn't. The fact that it 'seemed' to is
merely one possible manifestation of undefined behavior.

If I used "end()"
for copying and suppose I reached the limit of the capacity, then will
the new elements, which are being added to the vector, be silently
discarded since the vector's capacity is not increased?

They're not 'discarded', since they don't officially exist.
If you try to write to elements whose indices are >= 'size()',
the result is undefined, and whatever actually happens is in
no way guaranteed (e.g. something else might happen (or not) the
next time you try it)).

Moral: Don't Do That.

-Mike

 

[Jess]

Thanks again to both of you. I'm afraid I'm still a bit confused...

If I have a vector "v", whose size is "s" and capacity is "c", where s
<= c (always?), then if I try to add elements to it, then do I change
"v"'s size, ie. value of "s"? how about "c"?

Why does vectors have both capacity and size anyway?

In addition, even though "copy" doesn't change the size or capacity of
a vector, its copy operation essentially adds elements to the back of
a vector, which seems to be "push_back"'s behaviour. Therefore, I
would have thought the size is automatically increased, or not?

Thanks!

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

Thanks again to both of you. I'm afraid I'm still a bit confused...

If I have a vector "v", whose size is "s" and capacity is "c", where s
<= c (always?)

Yes

then if I try to add elements to it, then do I change

"v"'s size, ie. value of "s"? how about "c"?

As you add elements there will come a time when s == c, the next time
you add an element the capacity will have to increase to accommodate
the new element.

Why does vectors have both capacity and size anyway?

Because a vector is implemented as an array, so when you create a new
vector it will allocate space on the heap. This space is the capacity,
as you add elements it might happen that this allocated space no
longer is enough, then the vector allocated a new, bigger, piece of
memory and copies all the data in the original memory location to the
new (and frees the original memory). These reallocations can be
costly, especially if the copy-constructor of the objects stored takes
a long time to run (since each object is copy-constructed into the new
space), so if you know how many objects you'll use you can use
reserve() to allocate all the space needed before you start inserting.

In addition, even though "copy" doesn't change the size or capacity of
a vector, its copy operation essentially adds elements to the back of
a vector, which seems to be "push_back"'s behaviour. Therefore, I
would have thought the size is automatically increased, or not?

Don't know exactly which copy you refer to but if the elements are
added to the end of another vector then yes, it's size (and perhaps
capacity) will increase.

 

[Jess]

Thanks!

I meant the "std::copy", eg.

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<int> w;
v.push_back(3);
v.push_back(4);

copy(w.begin(),w.end(),back_inserter(v));

// rest ommitted

I think the "copy" operation only copies to elements in "v" if the
elements really exist, is it right?

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

Thanks!

I meant the "std::copy", eg.

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<int> w;
v.push_back(3);
v.push_back(4);

copy(w.begin(),w.end(),back_inserter(v));

// rest ommitted

I think the "copy" operation only copies to elements in "v" if the
elements really exist, is it right?

No, after the call top std::copy() the vector v will be of size 5,
with copies of the elements in w inserted after the already existing
elements in v. While doing this a reallocation may or may not be
necessary.

 

[Jess]

Is this because of "back_inserter"? If I use "v.end()" instead of
"back_inserter", then the result would be wrong.

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

Is this because of "back_inserter"? If I use "v.end()" instead of
"back_inserter", then the result would be wrong.

Yes, the back_inserter is used when inserting items at the end of a
container (hence the name). You can not use v.end() instead, it is of
the wrong type (not an output iterator).

PS: Try to quote the part of the post you are replying to.

 

[Gavin Deane]

Please quote some context. Not necessarily the entirity of the post to
which you are responding, but sufficient to give meaning to your post.
Thanks. I've added it back in here.

[Jess]
#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>

using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<int> w;
v.push_back(3);
v.push_back(4);

copy(w.begin(),w.end(),back_inserter(v));
}

I think the "copy" operation only copies to elements in "v" if the
elements really exist, is it right?

[Erik Wikström]
No, after the call top std::copy() the vector v will be of size 5,
with copies of the elements in w inserted after the already existing
elements in v. While doing this a reallocation may or may not be
necessary.

Is this because of "back_inserter"? If I use "v.end()" instead of
"back_inserter", then the result would be wrong.

Yes. This is exactly the sort of thing back_inserter was designed for.
If you had used v.end() instead of back_inserter(v), the behaviour
would be undefined.

Gavin Deane

 

[P.J. Plauger]

Is this because of "back_inserter"? If I use "v.end()" instead of
"back_inserter", then the result would be wrong.

Yes, the back_inserter is used when inserting items at the end of a
container (hence the name). You can not use v.end() instead, it is of
the wrong type (not an output iterator).

[pjp] Uh, no. v.end() works altogether too well as an output iterator.
The problem is that writing to *v.end() is an undefined operation
that does *not* grow the vector and doesn't always do something
clearly wrong enough to reveal how wrong it is.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Jess]

Please quote some context. Not necessarily the entirity of the post to

which you are responding, but sufficient to give meaning to your post.
Thanks. I've added it back in here.

Thanks for adding it back.

Yes, the back_inserter is used when inserting items at the end of a
container (hence the name). You can not use v.end() instead, it is of
the wrong type (not an output iterator).

Can I generalize this to say if we use an output iterator to copy/
assign/add elements, then the size of the container will be increased
automatically? On the other hand, input iterator should only be used
for reading, is this right?

Thanks.

 

[Gavin Deane]

Can I generalize this to say if we use an output iterator to copy/
assign/add elements, then the size of the container will be increased
automatically?

Nearly. If you use an *insert* iterator then the size of the container
will be increased automatically. An insert iterator is just one kind
of output iterator.

On the other hand, input iterator should only be used
for reading, is this right?

Again no. That statement is unnecessarily restrictive. Here's a
variation of your program. You originally passed back_inserter(v) to
copy as the third argument. You've already seen that changing that to
v.end() gives undefined behaviour. But here I have changed it to
v.begin() (which is an input iterator)

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

int main(){
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<int> w;
w.push_back(3);
w.push_back(4);

copy(w.begin(),w.end(),v.begin());
}

After the call to copy, v contains the sequence [3, 4, 2]. The first
two elements have been copied from the vector w and overwritten what
was there before. The third element is untouched by the copy. This
behaviour is well defined and standard, and if you want to copy into
some existing space and overwrite the pre-existing data, this is a
perfectly acceptable way of doing so.

Note that it only works if the size of w <= the size of v. If w had
more elements than v, the call to copy would attempt to write past the
end of v - undefined behaviour again.

Have you got this book? It lives up to its title as both a tutorial
and reference extremely well.
http://www.josuttis.com/libbook/

Gavin Deane

 

[Pete Becker]

Again no.

On the contrary: exactly right. The only operations supported by an
input iterator are reading, incrementing, and comparing.

That statement is unnecessarily restrictive. Here's a
variation of your program. You originally passed back_inserter(v) to
copy as the third argument. You've already seen that changing that to
v.end() gives undefined behaviour. But here I have changed it to
v.begin() (which is an input iterator)

v.begin() returns a random access iterator. One of the requirements for
a random access iterator is that it support all the operations of an
input iterator. But when you write through it you're using it as an
output iterator.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Gavin Deane]

GavinDeanewrote:


On the contrary: exactly right. The only operations supported by an
input iterator are reading, incrementing, and comparing.

Thanks for the correction.

Gavin Deane

 

[Jess]

Thanks for your replies!

Have you got this book? It lives up to its title as both a tutorial
and reference extremely well.
http://www.josuttis.com/libbook/

No, I haven't. I'm reading Accelerated C++, as I need to have quick
start for my work. I should read a more comprehensive reference book
soon.

Thanks.