Topic: std::vector::resize


Author: nesotto@cs.auc.dk ("Thorsten Ottosen")
Date: Mon, 22 Dec 2003 04:56:29 +0000 (UTC)
Raw View
"Ken Alverson" <USENET.Ken@Alverson.net> wrote in message
news:brrfed$q7e$1@eeyore.INS.cwru.edu...
> ""Andrew Koenig"" <ark@acm.org> wrote in message
> news:JM7Eb.476828$0v4.21375551@bgtnsc04-news.ops.worldnet.att.net...
> >
> > What would happen if you did this?
> >
> >     vector<int> v;
> >     v.push_back(42);
> >     v.resize(100, v[0]);
> >
[snip]
> However, wouldn't an implementation that got rid of the old block before
it
> finished filling in the new block be non-exception-safe?

No, exception-safety guarantees comes in easy and hard ones. To provide the
basic guarantee,
simply don't swap state before all old elements have been copied. Then fill
in the rest. This process
might also throw (well, not with an int, but in general if the copy
constructor does), but it still
give you the basic guarantee.

> How would you
> reliably roll back to a good state if the operation failed (granted, int
> assignment can't throw, but in the general sense).

A "good state" simply means that the vector invariant is not broken. But to
be honest, I don't
see why using a second vector in insert would not make it both affordable
and easy to provide
the strong guarantee.

br

Thorsten


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: AlbertoBarbati@libero.it (Alberto Barbati)
Date: Tue, 23 Dec 2003 17:04:48 +0000 (UTC)
Raw View
Dhruv wrote:
> However, I wonder whether the signature for resize for std::list makes
> sense, since there is no lurking danger of the node getting destroyed,
> unless I am mistaken.

Yep! Same for deque. As I notice in another post of mine, I don't
understand why they took such a precaution for resize() when insert()
poses the same problem (on both vector and deque, at least).

Alberto

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: pjp@dinkumware.com ("P.J. Plauger")
Date: Tue, 23 Dec 2003 18:56:44 +0000 (UTC)
Raw View
"Alberto Barbati" <AlbertoBarbati@libero.it> wrote in message
news:V3DFb.206983$e6.7886859@twister2.libero.it...

> Dhruv wrote:
> > However, I wonder whether the signature for resize for std::list makes
> > sense, since there is no lurking danger of the node getting destroyed,
> > unless I am mistaken.
>
> Yep! Same for deque. As I notice in another post of mine, I don't
> understand why they took such a precaution for resize() when insert()
> poses the same problem (on both vector and deque, at least).

Different meetings.

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

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: AlbertoBarbati@libero.it (Alberto Barbati)
Date: Wed, 24 Dec 2003 00:41:09 +0000 (UTC)
Raw View
P.J. Plauger wrote:
> "Alberto Barbati"
>>Dhruv wrote:
 >>
>>>However, I wonder whether the signature for resize for std::list makes
>>>sense, since there is no lurking danger of the node getting destroyed,
>>>unless I am mistaken.
>>
>>Yep! Same for deque. As I notice in another post of mine, I don't
>>understand why they took such a precaution for resize() when insert()
>>poses the same problem (on both vector and deque, at least).
>
> Different meetings.

That may explain it, but makes me want to file a DR to (try to) correct
the issue, once and for all. A possibile wording for such a DR could be:

1) clarify the semantic of insert() so that the result is correct even
in the extreme case insert(v.begin(), v[0])

2) change the prototype of resize() for all containers to take a const
reference

The rationale has been discussed in this thread. In addition to
optimization and coherency issues, let's not forget the original one: on
some platforms there are types that cannot be passed by value (for
example aligned types on x86).

As a library implementor, what problems do you see in such a proposal? I
am really interested in your opinion.

Alberto

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: pjp@dinkumware.com ("P.J. Plauger")
Date: Wed, 24 Dec 2003 06:39:41 +0000 (UTC)
Raw View
"Alberto Barbati" <AlbertoBarbati@libero.it> wrote in message
news:XF4Gb.210224$e6.8020174@twister2.libero.it...

> P.J. Plauger wrote:
> > "Alberto Barbati"
> >>Dhruv wrote:
>  >>
> >>>However, I wonder whether the signature for resize for std::list makes
> >>>sense, since there is no lurking danger of the node getting destroyed,
> >>>unless I am mistaken.
> >>
> >>Yep! Same for deque. As I notice in another post of mine, I don't
> >>understand why they took such a precaution for resize() when insert()
> >>poses the same problem (on both vector and deque, at least).
> >
> > Different meetings.
>
> That may explain it, but makes me want to file a DR to (try to) correct
> the issue, once and for all. A possibile wording for such a DR could be:
>
> 1) clarify the semantic of insert() so that the result is correct even
> in the extreme case insert(v.begin(), v[0])
>
> 2) change the prototype of resize() for all containers to take a const
> reference
>
> The rationale has been discussed in this thread. In addition to
> optimization and coherency issues, let's not forget the original one: on
> some platforms there are types that cannot be passed by value (for
> example aligned types on x86).

You're still walking on eggs when you ask the Standard C++ library
to traffic in objects that violate the basic rules of C.

> As a library implementor, what problems do you see in such a proposal? I
> am really interested in your opinion.

Given that we have to get self-referential inserts right these days,
I see little additional problem with self-referential fills.

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

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: solosnake@solosnake._remove_this_.fsnet.co.uk ("solosnake")
Date: Wed, 17 Dec 2003 21:48:37 +0000 (UTC)
Raw View
Hello, and merry Christmas!

When trying to compile some code that had specific alignment requirements, I
found that the Visual Studio .NET compiler gave me compile time errors. It
forbids alignment specification of stack variables.

Upon examing the source of the error, it was due to the signatures of the
std::vector::resize being as follows:

    template<class _Ty, class _Ax = allocator<_Ty> >
    class vector : public _Vector_val<_Ty, _Ax>
    {
    public:

    ....

    void resize(size_type _Newsize)
    {
       // determine new length, padding with _Ty() elements as needed
        resize(_Newsize, _Ty());
    }

     void resize(size_type _Newsize, _Ty _Val)
    {
        // determine new length, padding with _Val elements as needed
        if (size() < _Newsize)
            _Insert_n(end(), _Newsize - size(), _Val);
      else if (_Newsize < size())
           erase(begin() + _Newsize, end());
    }

The second version is passing the "_Val" object by copy, instead of what I
would have assumed to be a more conventional method of by const referance.
This to me appears unnecessary, as the recipient of the "_Val" object in the
call, the "_Insert_n" method, actually takes as a parameter a const
reference.

I have changed the signature of "resize" to as follows:

     void resize(size_type _Newsize, const _Ty& _Val)


...and everything works as I hoped and expected. The compilers alignment
requirements are not breached, and I have also saved a potentially expensive
and unnecessary copy.

Can anyone tell me if there was a good reason why the original version
passed by copy instead of by const reference?
Have I broken anything serious by doing so (other then possible portability
issues)?
Does the standard specify passing by copy, and if so why?

Thanks in advance for all replies!

- solosnake








---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: ark@acm.org ("Andrew Koenig")
Date: Thu, 18 Dec 2003 04:02:25 +0000 (UTC)
Raw View
> I have changed the signature of "resize" to as follows:
>
>      void resize(size_type _Newsize, const _Ty& _Val)
>
>
> ...and everything works as I hoped and expected. The compilers alignment
> requirements are not breached, and I have also saved a potentially
expensive
> and unnecessary copy.
>
> Can anyone tell me if there was a good reason why the original version
> passed by copy instead of by const reference?
> Have I broken anything serious by doing so (other then possible
portability
> issues)?

What would happen if you did this?

    vector<int> v;
    v.push_back(42);
    v.resize(100, v[0]);

Are you sure that it won't free the old memory, allocate new memory, then
try to initialize the new memory by repeatedly copying an element from the
memory it has just freed?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: USENET.Ken@Alverson.net (Ken Alverson)
Date: Thu, 18 Dec 2003 06:58:33 +0000 (UTC)
Raw View
""Andrew Koenig"" <ark@acm.org> wrote in message
news:JM7Eb.476828$0v4.21375551@bgtnsc04-news.ops.worldnet.att.net...
>
> What would happen if you did this?
>
>     vector<int> v;
>     v.push_back(42);
>     v.resize(100, v[0]);
>
> Are you sure that it won't free the old memory, allocate new memory, then
> try to initialize the new memory by repeatedly copying an element from the
> memory it has just freed?

Both blocks of memory have to exist simultaneously at least long enough to
copy the old elements into the new memory.  While that doesn't guarantee the
old block is around while the rest of the new elements are initialized, it
does preclude the exact scenario you described.

However, wouldn't an implementation that got rid of the old block before it
finished filling in the new block be non-exception-safe?  How would you
reliably roll back to a good state if the operation failed (granted, int
assignment can't throw, but in the general sense).

Ken


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: jeffplus@comcast.net (Jeff Schwab)
Date: Thu, 18 Dec 2003 17:49:36 +0000 (UTC)
Raw View
Andrew Koenig wrote:
>>I have changed the signature of "resize" to as follows:
>>
>>     void resize(size_type _Newsize, const _Ty& _Val)
>>
>>
>>...and everything works as I hoped and expected. The compilers alignment
>>requirements are not breached, and I have also saved a potentially
>
> expensive
>
>>and unnecessary copy.
>>
>>Can anyone tell me if there was a good reason why the original version
>>passed by copy instead of by const reference?
>>Have I broken anything serious by doing so (other then possible
>
> portability
>
>>issues)?
>
>
> What would happen if you did this?
>
>     vector<int> v;
>     v.push_back(42);
>     v.resize(100, v[0]);
>
> Are you sure that it won't free the old memory, allocate new memory, then
> try to initialize the new memory by repeatedly copying an element from the
> memory it has just freed?


Whatever elements already exist in the vector need to be copied on
resize.  Doesn't this imply that the memory containing those elements
can't be freed before it has been copied into the new memory?  I think
the new memory must be allocated (and the first elements initialized)
before the old is deleted.  Of course, your point is still completely
valid, and the initializer needs to be passed by value, since the old
memory could be freed before the new elements are initialized.

>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]
>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: AlbertoBarbati@libero.it (Alberto Barbati)
Date: Fri, 19 Dec 2003 23:46:37 +0000 (UTC)
Raw View
solosnake wrote:
> Does the standard specify passing by copy, and if so why?

The standard specify passing by copy (23.2.4.2). By the way, the
resize() method should only have one signature, i.e.:

 void resize(size_type n, T value = T());

having two distinct signatures (one with one argument and another with
two arguments) makes the implementation non-conforming as it requires
the type T to be default-constructible in case you explicitly
instantiate the template. This is a case where 17.4.4.4 para 2 does
*not* apply, IMHO.

Back to the original issue, I am surprised as you are about passing by
value, because the "sizing" constructor has the following signature:

 vector(size_type n, const T& value = T(), const Allocator& = Allocator());

thus passing the parameter by reference.

Alberto

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: AlbertoBarbati@libero.it (Alberto Barbati)
Date: Sat, 20 Dec 2003 07:46:49 +0000 (UTC)
Raw View
Ken Alverson wrote:

> ""Andrew Koenig"" <ark@acm.org> wrote in message
> news:JM7Eb.476828$0v4.21375551@bgtnsc04-news.ops.worldnet.att.net...
>
>>What would happen if you did this?
>>
>>    vector<int> v;
>>    v.push_back(42);
>>    v.resize(100, v[0]);
>>
>>Are you sure that it won't free the old memory, allocate new memory, then
>>try to initialize the new memory by repeatedly copying an element from the
>>memory it has just freed?
>
> Both blocks of memory have to exist simultaneously at least long enough to
> copy the old elements into the new memory.  While that doesn't guarantee the
> old block is around while the rest of the new elements are initialized, it
> does preclude the exact scenario you described.
>
> However, wouldn't an implementation that got rid of the old block before it
> finished filling in the new block be non-exception-safe?  How would you
> reliably roll back to a good state if the operation failed (granted, int
> assignment can't throw, but in the general sense).

I have a question for the gurus on exception-safety, here. Consider this
(very naive) implementation of resize():

// this->p_ = current pointer to data block
// this->n_ = current size of the vector
// this->c_ = current capacity of the vector
// this->a_ = allocator

// scoped_block = helper class similar to boost::scoped_array that calls
// allocate() on ctor and deallocate() on dtor

void resize(size_type n, T t)
{
   // case where n <= n_ omitted for clarity

   // allocate new block
   scoped_block<T, Allocator> p(n, this->a_);

   // copy existing elements (assume uninitialized_copy exception-safe)
   uninitialized_copy(this->p_, this->p_ + this->n_, p.get());

   T* oldp = this->p_;
   this->p_ = p.release(); // doesn't throw
   this->c_ = n;   // update capacity() but not size()!

   // now the vector is using the new block, the old one
   // is no longer necessary

   destroy(oldp, oldp + this->n_);
   this->a_.deallocate(oldp);    // old elements deallocated here!!!

   // fill the remaining elements
   // (assume uninitialized_fill exception-safe)
   uninitialized_fill(this->p_ + this->n_, this->p_ + this->c_, t);

   // update size() and finish
   this->n_ = n;
}

Is it exception-safe?

The main issue is if a copy ctor in uninitialized_fill() throws. In that
case, reallocation has already occurred but size() hasn't been updated
yet, so:

1) size() hasn't changed
2) the values of the elements haven't changed

but:

3) the elements have been moved to a different memory address, thus
invalidating all iterators and references
4) capacity() has changed

I see 4) as the only real issue against non-exception safety. Is it
really an issue?

If the answer is yes, then we could move the line "this->c_ = n;" at the
end of the function. The value returned capacity() will be less
reliable, in that case, but still conforming.

If the example is exception-safe, we would have an example of the
implementation hinted by Andrew, where pass-by-reference cannot be used.

Alberto

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: kanze@alex.gabi-soft.fr (James Kanze)
Date: Sun, 21 Dec 2003 05:11:46 +0000 (UTC)
Raw View
ark@acm.org ("Andrew Koenig") writes:

|>  > I have changed the signature of "resize" to as follows:

|>  >      void resize(size_type _Newsize, const _Ty& _Val)

|>  > ...and everything works as I hoped and expected. The compilers
|>  > alignment requirements are not breached, and I have also saved a
|>  > potentially expensive and unnecessary copy.

|>  > Can anyone tell me if there was a good reason why the original
|>  > version passed by copy instead of by const reference? Have I
|>  > broken anything serious by doing so (other then possible
|>  > portability issues)?

|>  What would happen if you did this?

|>      vector<int> v;
|>      v.push_back(42);
|>      v.resize(100, v[0]);

|>  Are you sure that it won't free the old memory, allocate new memory,
|>  then try to initialize the new memory by repeatedly copying an
|>  element from the memory it has just freed?

That's the implementation's problem, not mine.  What if I write
something like:

    v.insert( v.end(), v.begin(), v.end() ) ;

?

There are a lot of functions which have this sort of problem.

--=20
James Kanze                             mailto:kanze@gabi-soft.fr
Conseils en informatique orient=E9e objet/
                 Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France  +33 1 41 89 80 93

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: jpotter@falcon.lhup.edu (John Potter)
Date: Sun, 21 Dec 2003 12:58:22 +0000 (UTC)
Raw View
On Sun, 21 Dec 2003 05:11:46 +0000 (UTC), kanze@alex.gabi-soft.fr (James
Kanze) wrote:

> What if I write something like:

>     v.insert( v.end(), v.begin(), v.end() ) ;

> ?

You violate the preconditions of table 67.  I think that is called
undefined behavior.

> There are a lot of functions which have this sort of problem.

They seem to be handled in one way or another.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: nesotto@cs.auc.dk ("Thorsten Ottosen")
Date: Mon, 22 Dec 2003 01:45:33 +0000 (UTC)
Raw View
"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:i35buvg56966u7ell1laofdpa6bp550lt7@4ax.com...
> On Sun, 21 Dec 2003 05:11:46 +0000 (UTC), kanze@alex.gabi-soft.fr (James
> Kanze) wrote:
>
> > What if I write something like:
>
> >     v.insert( v.end(), v.begin(), v.end() ) ;
>
> > ?
> You violate the preconditions of table 67.  I think that is called
> undefined behavior.
> > There are a lot of functions which have this sort of problem.
>

yep, it is a bit strange.

> They seem to be handled in one way or another.

what do you mean?

-Thorsten


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: dhruvbird@gmx.net ("Dhruv")
Date: Mon, 22 Dec 2003 04:55:55 +0000 (UTC)
Raw View
On Fri, 19 Dec 2003 23:46:37 +0000, Alberto Barbati wrote:

[...]

> Back to the original issue, I am surprised as you are about passing by
> value, because the "sizing" constructor has the following signature:
>
>  vector(size_type n, const T& value = T(), const Allocator& = Allocator());
>
> thus passing the parameter by reference.

Here, there is no danger of the current object being the source of the
reference parameter, since it is being constructed.

However, I wonder whether the signature for resize for std::list makes
sense, since there is no lurking danger of the node getting destroyed,
unless I am mistaken.


Regards,
-Dhruv.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]