By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,386 Members | 1,860 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,386 IT Pros & Developers. It's quick & easy.

vector iterators ...

P: n/a

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
Share this Question
Share on Google+
2 Replies


P: n/a
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

P: n/a
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.