473,323 Members | 1,550 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,323 software developers and data experts.

help for back_inserter and end()

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<intv;
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<intv;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<intw;
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!

Mar 25 '07 #1
17 4461
"Jess" <wd***@hotmail.comwrote in message
news:11*********************@p15g2000hsd.googlegro ups.com...
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<intv;
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<intv;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<intw;
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
Mar 25 '07 #2
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?

Mar 25 '07 #3
"Jess" <wd***@hotmail.comwrote in message
news:11*********************@n59g2000hsh.googlegro ups.com...
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?
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
Mar 25 '07 #4

"Jess" <wd***@hotmail.comwrote in message
news:11*********************@n59g2000hsh.googlegro ups.com...
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.
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
Mar 25 '07 #5
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!

Mar 26 '07 #6
On 26 Mar, 09:34, "Jess" <w...@hotmail.comwrote:
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.

--
Erik Wikström

Mar 26 '07 #7
Thanks!

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

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

using namespace std;

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

vector<intw;
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?

Mar 26 '07 #8
On 26 Mar, 14:34, "Jess" <w...@hotmail.comwrote:
Thanks!

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

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

using namespace std;

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

vector<intw;
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.

--
Erik Wikström

Mar 26 '07 #9
Is this because of "back_inserter"? If I use "v.end()" instead of
"back_inserter", then the result would be wrong.

Mar 26 '07 #10
On 26 Mar, 14:50, "Jess" <w...@hotmail.comwrote:
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.

--
Erik Wikström

Mar 26 '07 #11
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<intv;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<intw;
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.

On 26 Mar, 13:50, "Jess" <w...@hotmail.comwrote:
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

Mar 26 '07 #12
"Erik Wikström" <er****@student.chalmers.sewrote in message
news:11**********************@o5g2000hsb.googlegro ups.com...

On 26 Mar, 14:50, "Jess" <w...@hotmail.comwrote:
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
Mar 26 '07 #13
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.
Mar 26 '07 #14
On 26 Mar, 15:14, "Jess" <w...@hotmail.comwrote:
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?
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<intv;
v.push_back(0);
v.push_back(1);
v.push_back(2);

vector<intw;
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

Mar 26 '07 #15
Gavin Deane wrote:
On 26 Mar, 15:14, "Jess" <w...@hotmail.comwrote:
>On the other hand, input iterator should only be used
for reading, is this right?

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)
Mar 26 '07 #16
On 26 Mar, 17:44, Pete Becker <p...@versatilecoding.comwrote:
GavinDeanewrote:
On 26 Mar, 15:14, "Jess" <w...@hotmail.comwrote:
On the other hand, input iterator should only be used
for reading, is this right?
Again no.

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

Gavin Deane

Mar 27 '07 #17
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.

Mar 27 '07 #18

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: Mark A. Gibbs | last post by:
I have a string conversion function that looks something like this (apologies, but I cannot post the actual code): whar_t char_to_wchar(char); wstring to_wstring(const string& s) { wstring...
23
by: mrvendetta1 | last post by:
#include <stdio.h> #include <string.h> #include <stdlib.h> #define N 33 void StringToIntArray(const char *s1); void takeinteger(int i); int main() { char string; printf("enter a string of...
36
by: felixnielsen | last post by:
What i really wanna do, is defining my own types, it doesnt really matter why. Anyway, i have run into some problems 1) typedef unsigned short U16; U16 test = 0xffffffff; // There should be a...
3
by: silverburgh.meryl | last post by:
i have the following code, but it does not compile because I pass in back_inserter(b) as the output iterator in the remove_copy_if algorithm. My questions are: 1. why it does not compile? Passing...
1
by: Allerdyce.John | last post by:
Can I use back_inserter as the output iterator? The following code wont't compile, is there a reason for that? How can I achieve what I want? (grow aList if needed) class build { public: A*...
6
by: Daniel T. | last post by:
The line marked (1) below compiles fine and does exactly what I would expect, but the line marked (2) does not compile at all on my system. error: variable or field 'bar' declared void My...
16
by: C++ Hell | last post by:
Hey everyone just designing a quiz for school and managed to write the code for the questions and answers thou i have to add scores and at the end an overall score does anyone have any idea what to...
9
by: Dilip | last post by:
Hi I have a pretty simply task of splitting a std::string that has a comma separated list of names. I know the usual brute force method to do this (with basic_string::find_first_of and...
6
by: StephQ | last post by:
I need to implement an algorithm that takes as input a container and write some output in another container. The containers involved are usually vectors, but I would like not to rule out the...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.