470,636 Members | 1,468 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,636 developers. It's quick & easy.

vector iterators ...


typedef std::vector < std::complex < double > > complex_vec_type;

// option1
int main()
{
complex_vec_type cc ( 24000 );
complex_vec_type dd ( &cc[ 0 ], &cc[ 12000 ] );
}

versus

// option 2
int main()
{
complex_vec_type cc ( 24000 );
complex_vec_type dd ( cc.begin(), cc.begin()+12000 );
}

Does reallocation occur during construction of dd for either option?

Now if I interpret the standard, more specifically the statement ..

The constructor template <class InputIterator> vector(InputIterator
first, InputIterator last) makes only N calls to the copy construc-
tor of T (where N is the distance between first and last) and no
reallocations if iterators first and last are of forward, bidirec-
tional, or random access categories. It does at most 2N calls to
the copy constructor of T and logN reallocations if they are just
input iterators, since it is impossible to determine the distance
between first and last and then do copying.
brigns to mind the question of what are vector iterators? If memory
serves, they meet requirements of output / input / forward and
bidirectional iterators. With regards to option 2, I'm assuming no
reallocation occurs since iterators first and last are 'forward' (
correct ? ) iterators.

Things get muddled though with the statement " does at most 2N calls
to
the copy constructor of T and logN reallocations if they are just
input iterators"
Now vector iterators meet the category of input iterators hence, what
is 'cc.begin()'? If cc.begin is an input interator then reallocations
does occur during the construction of dd. I'm a little confused.

Jun 3 '06 #1
2 2152
ma740988 wrote:
typedef std::vector < std::complex < double > > complex_vec_type;

// option1
int main()
{
complex_vec_type cc ( 24000 );
complex_vec_type dd ( &cc[ 0 ], &cc[ 12000 ] );
}

versus

// option 2
int main()
{
complex_vec_type cc ( 24000 );
complex_vec_type dd ( cc.begin(), cc.begin()+12000 );
}

Does reallocation occur during construction of dd for either option?
No.
Now if I interpret the standard, more specifically the statement ..

> The constructor template <class InputIterator> vector(InputIterator
first, InputIterator last) makes only N calls to the copy construc-
tor of T (where N is the distance between first and last) and no
reallocations if iterators first and last are of forward, bidirec-
tional, or random access categories. It does at most 2N calls to
the copy constructor of T and logN reallocations if they are just
input iterators, since it is impossible to determine the distance
between first and last and then do copying.

brigns to mind the question of what are vector iterators? If memory
serves, they meet requirements of output / input / forward and
bidirectional iterators. With regards to option 2, I'm assuming no
reallocation occurs since iterators first and last are 'forward' (
correct ? ) iterators.
They are random access iterators.
Things get muddled though with the statement " does at most 2N calls
to
the copy constructor of T and logN reallocations if they are just
input iterators"
Now vector iterators meet the category of input iterators hence, what
is 'cc.begin()'? If cc.begin is an input interator then reallocations
does occur during the construction of dd. I'm a little confused.


Random access iterators certainly meet the requirements for input
iterators but they most definitely are not "just input iterators". So
this paragraph does not apply.

Jun 3 '06 #2
On Sat, 03 Jun 2006 08:51:23 -0700, ma740988 wrote:
typedef std::vector < std::complex < double > > complex_vec_type;

// option1
int main()
{
complex_vec_type cc ( 24000 );
complex_vec_type dd ( &cc[ 0 ], &cc[ 12000 ] );
}

versus

// option 2
int main()
{
complex_vec_type cc ( 24000 );
complex_vec_type dd ( cc.begin(), cc.begin()+12000 );
}

Does reallocation occur during construction of dd for either option?
No. You get one allocation of sufficient size at the beginning, since the
compiler can know how many elements there will be.

Now if I interpret the standard, more specifically the statement ..

> The constructor template <class InputIterator> vector(InputIterator
first, InputIterator last) makes only N calls to the copy construc- tor
of T (where N is the distance between first and last) and no
reallocations if iterators first and last are of forward, bidirec-
tional, or random access categories. It does at most 2N calls to the
copy constructor of T and logN reallocations if they are just input
iterators, since it is impossible to determine the distance between
first and last and then do copying.

brigns to mind the question of what are vector iterators? If memory
serves, they meet requirements of output / input / forward and
bidirectional iterators. With regards to option 2, I'm assuming no
They're also RandomAccess iterators too.
reallocation occurs since iterators first and last are 'forward' ( correct
? ) iterators.
RandomAccess.

Things get muddled though with the statement " does at most 2N calls to
the copy constructor of T and logN reallocations if they are just input
iterators"
Now vector iterators meet the category of input iterators hence, what is
'cc.begin()'? If cc.begin is an input interator then reallocations does
occur during the construction of dd. I'm a little confused.


Note that it said *just* input iterators. Since vector iterators are
"more" than just input iterators (RandomAccess, to be specific), the
compiler knows how many elements that there will be, and will size the new
vector appropriately.

If we're dealing with only an input iterator (such as istream_iterator),
the compiler cannot determine how many elements there will be before
starting to copy. With forward iterators, the compiler can safely advance
through the range to count how many elements there will be, then start
again at the first iterator. With input iterators, the compiler cannot
"rewind" the range to get back to the beginning, so it must insert the
elements into the new vector as it is going through the range the first
time around.
Jun 3 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

11 posts views Thread by Richard Thompson | last post: by
3 posts views Thread by codefixer | last post: by
13 posts views Thread by zaineb | last post: by
23 posts views Thread by Sanjay Kumar | last post: by
9 posts views Thread by Christian Chrismann | last post: by
2 posts views Thread by ernesto | last post: by
16 posts views Thread by xyz | last post: by
reply views Thread by subramanian100in | last post: by
1 post views Thread by Korara | last post: by
???
reply views Thread by Stoney L | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.