std::vector::_M_insert_aux() code

[digz]

template<typename _Tp, typename _Alloc>
void
vector<_Tp, _Alloc>::
_M_insert_aux(iterator __position, const _Tp& __x)
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
this->_M_impl.construct(this->_M_impl._M_finish,
*(this->_M_impl._M_finish - 1));
++this->_M_impl._M_finish;
_Tp __x_copy = __x;
std::copy_backward(__position,
iterator(this->_M_impl._M_finish-2),
iterator(this->_M_impl._M_finish-1));
*__position = __x_copy;
}
else ...

I had a couple of doubts with regard to code pasted here from
stl_vector.h
a) I was curious why a copy of x is created in the statement:
_Tp __x_copy = __x;
and that is assigned to *position, rather than directly doing
*position = __x ;

b) is it necessary to increment finish ++this->_M_impl._M_finish
before the copy_backward.
operation, is there anything wrong in doing the copy backwards first
like this

std::copy_backward(__position,
iterator(this->_M_impl._M_finish-1),
iterator(this->_M_impl._M_finish));
and then
++this->_M_impl._M_finish;

Thx
Digz

 

[Bo Persson]

digz wrote:
:: template<typename _Tp, typename _Alloc>
:: void
:: vector<_Tp, _Alloc>::
:: _M_insert_aux(iterator __position, const _Tp& __x)
:: {
:: if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
:: {
:: this->_M_impl.construct(this->_M_impl._M_finish,
:: *(this->_M_impl._M_finish - 1));
:: ++this->_M_impl._M_finish;
:: _Tp __x_copy = __x;
:: std::copy_backward(__position,
:: iterator(this->_M_impl._M_finish-2),
:: iterator(this->_M_impl._M_finish-1));
:: *__position = __x_copy;
:: }
:: else ...
::
:: I had a couple of doubts with regard to code pasted here from
:: stl_vector.h
:: a) I was curious why a copy of x is created in the statement:
:: _Tp __x_copy = __x;
:: and that is assigned to *position, rather than directly doing
:: *position = __x ;

It could be that __x is a reference to an element already in the vector. In
that case you have to save the value, before doing the copy_backward().

It must handle code like:

v.insert(v.begin(), v[5]);

::
:: b) is it necessary to increment finish ++this->_M_impl._M_finish
:: before the copy_backward.
:: operation, is there anything wrong in doing the copy backwards first
:: like this
::
:: std::copy_backward(__position,
:: iterator(this->_M_impl._M_finish-1),
:: iterator(this->_M_impl._M_finish));
:: and then
:: ++this->_M_impl._M_finish;
::

Yes. The increment is connected to the construction of a new object:

this->_M_impl.construct(this->_M_impl._M_finish,
*(this->_M_impl._M_finish - 1));
++this->_M_impl._M_finish;

This adds a new object to the vector, so it must also add 1 to the size of
the vector (by incrementing the end pointer).

If it didn't, and something bad happened in copy_backward, the newly created
object could be left created but never destroyed.


Bo Persson

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

template<typename _Tp, typename _Alloc>
void
vector<_Tp, _Alloc>::
_M_insert_aux(iterator __position, const _Tp& __x)
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
this->_M_impl.construct(this->_M_impl._M_finish,
*(this->_M_impl._M_finish - 1));
++this->_M_impl._M_finish;
_Tp __x_copy = __x;
std::copy_backward(__position,
iterator(this->_M_impl._M_finish-2),
iterator(this->_M_impl._M_finish-1));
*__position = __x_copy;
}
else ...

I had a couple of doubts with regard to code pasted here from
stl_vector.h
a) I was curious why a copy of x is created in the statement:
_Tp __x_copy = __x;
and that is assigned to *position, rather than directly doing
*position = __x ;

A copy have to be made before copy_backwards() is called in case the
copy-constructor would throw an exception or we would be left with a
inconsistent vector.

 

[Howard Hinnant]

digz wrote:
:: template<typename _Tp, typename _Alloc>
:: void
:: vector<_Tp, _Alloc>::
:: _M_insert_aux(iterator __position, const _Tp& __x)
:: {
:: if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
:: {
:: this->_M_impl.construct(this->_M_impl._M_finish,
:: *(this->_M_impl._M_finish - 1));
:: ++this->_M_impl._M_finish;
:: _Tp __x_copy = __x;
:: std::copy_backward(__position,
:: iterator(this->_M_impl._M_finish-2),
:: iterator(this->_M_impl._M_finish-1));
:: *__position = __x_copy;
:: }
:: else ...
::
:: I had a couple of doubts with regard to code pasted here from
:: stl_vector.h
:: a) I was curious why a copy of x is created in the statement:
:: _Tp __x_copy = __x;
:: and that is assigned to *position, rather than directly doing
:: *position = __x ;

It could be that __x is a reference to an element already in the vector. In
that case you have to save the value, before doing the copy_backward().

It must handle code like:

v.insert(v.begin(), v[5]);

Yes. But this is a poor (imho) implementation of how to handle that
problem. The copy constructor of _Tp may be arbitrarily expensive and
you want to try and minimize calls to a function of unknown expense.

It is cheap and easy to detect whether __x is self referencing or not.
And if it self referencing, it is also cheap and easy to compute its new
location after shuffling things around.

-Howard

 

[digz]

digz wrote:
:: template<typename _Tp, typename _Alloc>
:: void
:: vector<_Tp, _Alloc>::
:: _M_insert_aux(iterator __position, const _Tp& __x)
:: {
:: if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
:: {
:: this->_M_impl.construct(this->_M_impl._M_finish,
:: *(this->_M_impl._M_finish - 1));
:: ++this->_M_impl._M_finish;
:: _Tp __x_copy = __x;
:: std::copy_backward(__position,
:: iterator(this->_M_impl._M_finish-2),
:: iterator(this->_M_impl._M_finish-1));
:: *__position = __x_copy;
:: }
:: else ...
::
:: I had a couple of doubts with regard to code pasted here from
:: stl_vector.h
:: a) I was curious why a copy of x is created in the statement:
:: _Tp __x_copy = __x;
:: and that is assigned to *position, rather than directly doing
:: *position = __x ;

It could be that __x is a reference to an element already in the vector. In
that case you have to save the value, before doing the copy_backward().

It must handle code like:

v.insert(v.begin(), v[5]);

Yes. But this is a poor (imho) implementation of how to handle that
problem. The copy constructor of _Tp may be arbitrarily expensive and
you want to try and minimize calls to a function of unknown expense.

It is cheap and easy to detect whether __x is self referencing or not.
And if it self referencing, it is also cheap and easy to compute its new
location after shuffling things around.

-Howard

But I copied this block of code from STL shipped with Suse-
Linux-10.0 ,
Are you saying that the std::vector code is not optimal enough.What
could be a better/cheaper implementation
for the problem the block of code above is trying to address ??

--Digz

 

[Howard Hinnant]

digz wrote:
:: template<typename _Tp, typename _Alloc>
:: void
:: vector<_Tp, _Alloc>::
:: _M_insert_aux(iterator __position, const _Tp& __x)
:: {
:: if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
:: {
:: this->_M_impl.construct(this->_M_impl._M_finish,
:: *(this->_M_impl._M_finish - 1));
:: ++this->_M_impl._M_finish;
:: _Tp __x_copy = __x;
:: std::copy_backward(__position,
:: iterator(this->_M_impl._M_finish-2),
:: iterator(this->_M_impl._M_finish-1));
:: *__position = __x_copy;
:: }
:: else ...
::
:: I had a couple of doubts with regard to code pasted here from
:: stl_vector.h
:: a) I was curious why a copy of x is created in the statement:
:: _Tp __x_copy = __x;
:: and that is assigned to *position, rather than directly doing
:: *position = __x ;

It could be that __x is a reference to an element already in the vector.
In
that case you have to save the value, before doing the copy_backward().

It must handle code like:

v.insert(v.begin(), v[5]);

Yes. But this is a poor (imho) implementation of how to handle that
problem. The copy constructor of _Tp may be arbitrarily expensive and
you want to try and minimize calls to a function of unknown expense.

It is cheap and easy to detect whether __x is self referencing or not.
And if it self referencing, it is also cheap and easy to compute its new
location after shuffling things around.

-Howard

But I copied this block of code from STL shipped with Suse-
Linux-10.0 ,
Are you saying that the std::vector code is not optimal enough.

I'm saying *this* implementation of std::vector is not optimal. I've
seen better (I've written better).

What
could be a better/cheaper implementation
for the problem the block of code above is trying to address ??

It would be better to detect the self reference by comparing the address
of __x with the address of the insertion point and the address of the
end of the buffer. If the address of __x lies within that range, it is
self referencing. And in this case, the address of __x is going to
change during the reshuffling to make room for the new copy of __x.
Computing the final address of __x after the reshuffle is trivial: it
is going to move in the buffer by one position.

-Howard

 

[digz]

digz wrote:
:: template<typename _Tp, typename _Alloc>
:: void
:: vector<_Tp, _Alloc>::
:: _M_insert_aux(iterator __position, const _Tp& __x)
:: {
:: if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
:: {
:: this->_M_impl.construct(this->_M_impl._M_finish,
:: *(this->_M_impl._M_finish - 1));
:: ++this->_M_impl._M_finish;
:: _Tp __x_copy = __x;
:: std::copy_backward(__position,
:: iterator(this->_M_impl._M_finish-2),
:: iterator(this->_M_impl._M_finish-1));
:: *__position = __x_copy;
:: }
:: else ...
::
:: I had a couple of doubts with regard to code pasted here from
:: stl_vector.h
:: a) I was curious why a copy of x is created in the statement:
:: _Tp __x_copy = __x;
:: and that is assigned to *position, rather than directly doing
:: *position = __x ;
It could be that __x is a reference to an element already in the vector.
In
that case you have to save the value, before doing the copy_backward().
It must handle code like:
v.insert(v.begin(), v[5]);
Yes. But this is a poor (imho) implementation of how to handle that
problem. The copy constructor of _Tp may be arbitrarily expensive and
you want to try and minimize calls to a function of unknown expense.
It is cheap and easy to detect whether __x is self referencing or not.
And if it self referencing, it is also cheap and easy to compute its new
location after shuffling things around.
-Howard

But I copied this block of code from STL shipped with Suse-
Linux-10.0 ,
Are you saying that the std::vector code is not optimal enough.

I'm saying *this* implementation of std::vector is not optimal. I've
seen better (I've written better).

What
could be a better/cheaper implementation
for the problem the block of code above is trying to address ??

It would be better to detect the self reference by comparing the address
of __x with the address of the insertion point and the address of the
end of the buffer. If the address of __x lies within that range, it is
self referencing. And in this case, the address of __x is going to
change during the reshuffling to make room for the new copy of __x.
Computing the final address of __x after the reshuffle is trivial: it
is going to move in the buffer by one position.

-Howard

Thanks a lot for clarifying this.

This is libstdc++-3.3 , g++-4.0.1 on x86_64-pc-linux-gnu
Is gcc-help the right mailing list to follow up on opensource libstdc+
+ implementations ??
coz after your explanation I cannot imagine how g++ developers are
producing this code and shipping
it with RedHat, Debian, Suse..etc..all Linux Vendors have the same
STL, and on a bad day
a super slow copy constructor can make std::vector really suffer !!

--Digz

 

[Howard Hinnant]

This is libstdc++-3.3 , g++-4.0.1 on x86_64-pc-linux-gnu
Is gcc-help the right mailing list to follow up on opensource libstdc+
+ implementations ??
coz after your explanation I cannot imagine how g++ developers are
producing this code and shipping
it with RedHat, Debian, Suse..etc..all Linux Vendors have the same
STL, and on a bad day
a super slow copy constructor can make std::vector really suffer !!

Sorry for the slow response. Yes, gcc-help or libstdc++ would be good
followup lists.

-Howard