std::vector<>::clear semantics

[Stefan Höhne]

Hi,

[this is a repost of a simmilar question I asked in
alt.comp.lang.l earn.c-c++ recently]

as I recon, std::vector::cl ear()'s semantics changed from MS VC++ 6.0 to
MS' DOT.NET - compiler.

In the 6.0 version the capacity() of the vector did not change with the
call to clear(), in DOT.NET the capacity() is reduced to 0.

I relied on capacity() not changing when calling clear(). This is because
I do not want any reallocs within the following push_back() calls because
I use iterators that should keep valid. I've got an example below.

As I dicovered, some people claim that clear() is not required to keep
capacity() unchanged (as I thought it was). So I probably can not
blame M$ (but I do, nevertheless, because they changed semantics
silently and because of tradition) and need a workaround.

I know that I can use clear() in combination with reserve(). But this
would add some overhead with allocating and deallocating huge amounts
of memory and I want to avoid that.

I also want to avoid to give the elements of the std::vector a default
constructor. In the moment, I use resize(0) instead of clear(), but this
needs an default constructor in MS VC++'s lib.

Is there a (guaranteed to work-) way to do shrink a std::vector's size
without
- reducing its capacity()
- requiring the vectors elements to be default - constructable
?

Anybody a clue?

Stefan.


Example:
---
std::vector<int > v;
v.reserve(...);
while (...) {
v.clear();
//fill vector:
for (...)
v.push_back(... );

for(std::vector <int>::iterat or i=v.begin(); i!=v.end();/*nothing*/) {
if(...)
v.push_back(... ); // i should survive this because of reserve()
if(...)
++i;
else
i=v.erase(i);
}

/* some further use of v */
}
---

[David B. Held]

Re: std::vector&lt; &gt;::clear semantics

"Stefan Höhne" <do_not_use_thi s_adress@127.0. 0.1> wrote in message
news:bmlh6e$3o8 $1@news1.wdf.sa p-ag.de...[color=blue]
> [...]
> Is there a (guaranteed to work-) way to do shrink a std::vector's
> size without
> - reducing its capacity()
> - requiring the vectors elements to be default - constructable
> [...][/color]

An extreme solution would be to write a custom allocator that
pre-allocates a large chunk and never frees it until you make
an explicit call to a function of the allocator. That is, it would
honor deallocate() calls, but wouldn't deallocate the actual
storage it reserved.

Dave



---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.521 / Virus Database: 319 - Release Date: 9/23/2003

[grejdanospam@pacbell.net]

Re: std::vector&lt; &gt;::clear semantics

On Thu, 16 Oct 2003 09:24:56 +0200, Stefan Höhne
<do_not_use_thi s_adress@127.0. 0.1> wrote:
[color=blue]
> Hi,
>
> [this is a repost of a simmilar question I asked in
> alt.comp.lang.l earn.c-c++ recently]
>
> as I recon, std::vector::cl ear()'s semantics changed from MS VC++ 6.0 to
> MS' DOT.NET - compiler.[/color]

This is of topic here, I mean this is not a place for MS documentation.
[color=blue]
>
> In the 6.0 version the capacity() of the vector did not change with the
> call to clear(), in DOT.NET the capacity() is reduced to 0.[/color]

that's kind of funny.
[color=blue]
>
> I relied on capacity() not changing when calling clear(). This is because
> I do not want any reallocs within the following push_back() calls because
> I use iterators that should keep valid. I've got an example below.[/color]

Trying to keep iterators valid through clear was another nifty trick,
nice.
[color=blue]
>
> As I dicovered, some people claim that clear() is not required to keep
> capacity() unchanged (as I thought it was). So I probably can not
> blame M$ (but I do, nevertheless, because they changed semantics
> silently and because of tradition) and need a workaround.
>
> I know that I can use clear() in combination with reserve(). But this
> would add some overhead with allocating and deallocating huge amounts
> of memory and I want to avoid that.[/color]

why ?
[color=blue]
>
> I also want to avoid to give the elements of the std::vector a default
> constructor. In the moment, I use resize(0) instead of clear(), but this
> needs an default constructor in MS VC++'s lib.[/color]

how about using resize(0,const value&)
[color=blue]
>
> Is there a (guaranteed to work-) way to do shrink a std::vector's size
> without
> - reducing its capacity()[/color]

maybe erase or pop_back ?
[color=blue]
> - requiring the vectors elements to be default - constructable
> ?
>
> Anybody a clue?
>
> Stefan.
>
>
> Example:
> ---
> std::vector<int > v;[/color]

empty vector
[color=blue]
> v.reserve(...);[/color]

still empty
[color=blue]
> while (...) {
> v.clear();[/color]

clearing empty vector ?
[color=blue]
> //fill vector:
> for (...)
> v.push_back(... );
>
> for(std::vector <int>::iterat or i=v.begin(); i!=v.end();/*nothing*/) {
> if(...)
> v.push_back(... ); // i should survive this because of reserve()[/color]

push_back will call reserve if needed
[color=blue]
> if(...)
> ++i;
> else
> i=v.erase(i);
> }
>
> /* some further use of v */
> }
> ---
>
>
>
>[/color]

Good luck.

--
grzegorz

[Stefan Höhne]

Re: std::vector&lt; &gt;::clear semantics

Hi,

<grejdanospam@p acbell.net> wrote in message
news:oprw4li7mi 6u0rcr@news.sf. sbcglobal.net.. .[color=blue]
> On Thu, 16 Oct 2003 09:24:56 +0200, Stefan Höhne
> <do_not_use_thi s_adress@127.0. 0.1> wrote:
>[color=green]
> > Hi,
> >
> > [this is a repost of a simmilar question I asked in
> > alt.comp.lang.l earn.c-c++ recently]
> >
> > as I recon, std::vector::cl ear()'s semantics changed from MS VC++ 6.0[/color][/color]
to[color=blue][color=green]
> > MS' DOT.NET - compiler.[/color]
>
> This is of topic here, I mean this is not a place for MS documentation.[/color]

my actual question is not about some MS - specific stuff, its a pure
C++ - specific question. I thought it could be good to give some
background information. Its not an academic thought which I have,
its a real problem.
[color=blue][color=green]
> > In the 6.0 version the capacity() of the vector did not change with[/color][/color]
the[color=blue][color=green]
> > call to clear(), in DOT.NET the capacity() is reduced to 0.[/color]
>
> that's kind of funny.[/color]

It is whats happening.
[color=blue][color=green]
> > I relied on capacity() not changing when calling clear(). This is[/color][/color]
because[color=blue][color=green]
> > I do not want any reallocs within the following push_back() calls[/color][/color]
because[color=blue][color=green]
> > I use iterators that should keep valid. I've got an example below.[/color]
>
> Trying to keep iterators valid through clear was another nifty trick,
> nice.[/color]

Im not sure wether my explaination above is clear enough or not, but
Im pretty sure that the example below should be.

I want an iterator to keep valid through subsequent push_back() calls.
For this, its nessesary that capacity() does not change.
[color=blue][color=green]
> > As I dicovered, some people claim that clear() is not required to keep
> > capacity() unchanged (as I thought it was). So I probably can not
> > blame M$ (but I do, nevertheless, because they changed semantics
> > silently and because of tradition) and need a workaround.
> >
> > I know that I can use clear() in combination with reserve(). But this
> > would add some overhead with allocating and deallocating huge amounts
> > of memory and I want to avoid that.[/color]
>
> why ?[/color]

I suppose that if capacity() shrinks to zero, this is a clear indicator
for memory beeing freed (depending on the behaviour of the default
allocator of std::vector) during the clear(). A subsequent call to
reserve() would clearly allocate memory. Is this the explanation you
wanted?
[color=blue][color=green]
> > I also want to avoid to give the elements of the std::vector a default
> > constructor. In the moment, I use resize(0) instead of clear(), but[/color][/color]
this[color=blue][color=green]
> > needs an default constructor in MS VC++'s lib.[/color]
>
> how about using resize(0,const value&)[/color]

Yep, that would do it, because the objects I collect in the vector are
assignable. But I'm not sure anymore wether it would be
guaranteed that this will not affect capacity().
[color=blue][color=green]
> > Is there a (guaranteed to work-) way to do shrink a std::vector's size
> > without
> > - reducing its capacity()[/color]
>
> maybe erase or pop_back ?[/color]

erase() is just another possible workaround. People in
alt.comp.lang.l earn.c-c++ believe the behaviour of erase(begin(), end())
should be the same as of clear().

pop_back() is no alternative: it takes linear time. The object within the
vector is a POD, therefore clear() should take no time. Yes, this will
matter, its a huge vector.
[color=blue][color=green]
> > Example:
> > ---
> > std::vector<int > v;[/color]
>
> empty vector
>[color=green]
> > v.reserve(...);[/color]
>
> still empty
>[color=green]
> > while (...) {
> > v.clear();[/color]
>
> clearing empty vector ?[/color]

is no harm in such an example. It will not be empty
in the second iteration.

Im not sure why your quote is unindented. Reading
my own post in google groups I can see the
indentation. Where is the problem?


[color=blue]
>[color=green]
> > //fill vector:
> > for (...)
> > v.push_back(... );
> >
> > for(std::vector <int>::iterat or i=v.begin(); i!=v.end();/*nothing*/) {
> > if(...)
> > v.push_back(... ); // i should survive this because of reserve()[/color]
>
> push_back will call reserve if needed[/color]

And this will make i invalid. So I dont want clear() or whatever I'll use
to shrink the vectors capacity(). Im sure that the vector will never grow
bigger than the amount I'm initially passing to reserve().
[color=blue]
>[color=green]
> > if(...)
> > ++i;
> > else
> > i=v.erase(i);
> > }
> >
> > /* some further use of v */
> > }
> > ---
> >
> >
> >
> >[/color]
>
> Good luck.[/color]

Thanks,
Stefan.

[David B. Held]

Re: std::vector&lt; &gt;::clear semantics

"Stefan Höhne" <do_not_use_thi s_adress@127.0. 0.1> wrote in message
news:bmmbkr$1f9 $1@news1.wdf.sa p-ag.de...[color=blue]
> [...]
> erase() is just another possible workaround. People in
> alt.comp.lang.l earn.c-c++ believe the behaviour of
> erase(begin(), end()) should be the same as of clear().[/color]

Clearly that's wrong (pun intended).
[color=blue]
> pop_back() is no alternative: it takes linear time.
> [...][/color]

Really??? I can believe that erase() takes linear time,
but would you like to explain how pop_back() takes
linear time?

Maybe what you want to do is look at the reverse iterators,
and use std::erase() with them instead.

Dave



---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.521 / Virus Database: 319 - Release Date: 9/23/2003

[tom_usenet]

Re: std::vector&lt; &gt;::clear semantics

On Thu, 16 Oct 2003 15:55:50 +0200, "Stefan Höhne"
<do_not_use_thi s_adress@127.0. 0.1> wrote:
[color=blue]
>erase() is just another possible workaround. People in
>alt.comp.lang. learn.c-c++ believe the behaviour of erase(begin(), end())
>should be the same as of clear().[/color]

That isn't quite true. What is true is that a clear() implementation
must behave according to the semantics of erase(begin(), end()) in the
standard. That doesn't mean it has to behave the same as the
implementation of erase(begin(), end()) on the same platform.

In fact, erase(begin(), end()) leaves the capacity unchanged on
MSVC.NET, whereas clear() sets it to 0. So, for your particular
platform dependent problem, erase(begin(), end()) is a platform
dependent solution.

The only standard solution is not to let the size of the vector hit 0,
because, as soon as it does, the memory can be deallocated (according
to some, anyway).

Personally, I think any implementation that frees storage on a call to
clear() (and without documenting the fact!) is poor, since most users
expect capacity to be "sticky". I can only assume that it is an
accidental change to Dinkumware's std::vector.

Tom

[Howard Hinnant]

Re: std::vector&lt; &gt;::clear semantics

In article <o4ftov83l75frl o4ijb8p0nmnqh5k 7d08v@4ax.com>,
tom_usenet <tom_usenet@hot mail.com> wrote:
[color=blue]
> The only standard solution is not to let the size of the vector hit 0,
> because, as soon as it does, the memory can be deallocated (according
> to some, anyway).[/color]

Imho, the standard solution is to use clear().

23.2.4.2/5:
[color=blue]
> It is guaranteed that no reallocation takes place during insertions that
> happen after a call to reserve() until the time when an insertion would make
> the size of the vector greater than the size specified in the most recent
> call to reserve().[/color]

So:

vector<int> v;
v.reserve(2);
v.clear();
v.push_back(1);
int& i = v.front();
v.push_back(2);

After the second push_back, 23.2.4.2/5 guarantees that the reference "i"
will still be valid sense the most recent call to reserve specified that
there be room for at least two ints.

To be fair, 23.2.4.2/5 is being changed by DR 329:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#329

to read:
[color=blue]
> Reallocation invalidates all the references, pointers, and iterators
> referring to the elements in the sequence. It is guaranteed that no
> reallocation takes place during insertions that happen after a call to
> reserve() until the time when an insertion would make the size of the vector
> greater than the value of capacity().[/color]

But I do not believe this new wording provides any flexibility for
clear() to reduce capacity. It merely clarifies the situation described
in the DR:

vec.reserve(23) ;
vec.reserve(0);

// capacity() still >= 23 here

-Howard

[tom_usenet]

Re: std::vector&lt; &gt;::clear semantics

On Thu, 16 Oct 2003 16:33:57 GMT, Howard Hinnant
<hinnant@metrow erks.com> wrote:
[color=blue]
>In article <o4ftov83l75frl o4ijb8p0nmnqh5k 7d08v@4ax.com>,
> tom_usenet <tom_usenet@hot mail.com> wrote:
>[color=green]
>> The only standard solution is not to let the size of the vector hit 0,
>> because, as soon as it does, the memory can be deallocated (according
>> to some, anyway).[/color]
>
>Imho, the standard solution is to use clear().
>
>23.2.4.2/5:
>[color=green]
>> It is guaranteed that no reallocation takes place during insertions that
>> happen after a call to reserve() until the time when an insertion would make
>> the size of the vector greater than the size specified in the most recent
>> call to reserve().[/color]
>
>So:
>
>vector<int> v;
>v.reserve(2) ;
>v.clear();
>v.push_back(1) ;
>int& i = v.front();
>v.push_back(2) ;
>
>After the second push_back, 23.2.4.2/5 guarantees that the reference "i"
>will still be valid sense the most recent call to reserve specified that
>there be room for at least two ints.[/color]

How about:

vector<int> v(2); //obviously capacity() >= 2
v.clear();
v.push_back(1);
int& i = v.front();
v.push_back(2);

The standard is underspecified here in a way that makes it hard to
write efficient (or even correct) code.
[color=blue]
>To be fair, 23.2.4.2/5 is being changed by DR 329:
>
>http://anubis.dkuug.dk/jtc1/sc22/wg2...fects.html#329
>
>to read:
>[color=green]
>> Reallocation invalidates all the references, pointers, and iterators
>> referring to the elements in the sequence. It is guaranteed that no
>> reallocation takes place during insertions that happen after a call to
>> reserve() until the time when an insertion would make the size of the vector
>> greater than the value of capacity().[/color]
>
>But I do not believe this new wording provides any flexibility for
>clear() to reduce capacity. It merely clarifies the situation described
>in the DR:
>
>vec.reserve(23 );
>vec.reserve(0) ;
>
>// capacity() still >= 23 here[/color]

I have roughly the same reasoning (I'd studied the defect reports a
couple of days ago, along with old threads in std.c++), but Dinkumware
seem to disagree. But I think it must be a bug/oversight in their
implementation.

In any case, the standard is ridiculously unclear at the moment. It
needs to say that capacity will never decrease except during a call to
swap. I have no idea why it doesn't say that, and why none of the
defect reports have suggested that.

Tom

[Howard Hinnant]

Re: std::vector&lt; &gt;::clear semantics

In article <28ltov47hdaqle f56s21ctagjeltb nmn4s@4ax.com>,
tom_usenet <tom_usenet@hot mail.com> wrote:
[color=blue][color=green]
> >So:
> >
> >vector<int> v;
> >v.reserve(2) ;
> >v.clear();
> >v.push_back(1) ;
> >int& i = v.front();
> >v.push_back(2) ;
> >
> >After the second push_back, 23.2.4.2/5 guarantees that the reference "i"
> >will still be valid sense the most recent call to reserve specified that
> >there be room for at least two ints.[/color]
>
> How about:
>
> vector<int> v(2); //obviously capacity() >= 2
> v.clear();
> v.push_back(1);
> int& i = v.front();
> v.push_back(2);[/color]

I think the standard may allow this, but I'm not positive. However the
vendor would have to go to extra expense (both storage and speed) to
pull it off. The vendor would not only need to store capacity, but also
how it was set (by an explicit call to reserve or not). So as long as
the previous semantics are respected (with reserve), this latter concern
might be academic as I can not see any motivation for a vendor to add
such an expense.
[color=blue]
> I have roughly the same reasoning (I'd studied the defect reports a
> couple of days ago, along with old threads in std.c++), but Dinkumware
> seem to disagree. But I think it must be a bug/oversight in their
> implementation.
>
> In any case, the standard is ridiculously unclear at the moment. It
> needs to say that capacity will never decrease except during a call to
> swap. I have no idea why it doesn't say that, and why none of the
> defect reports have suggested that.[/color]

Sounds like you're the guy to write the next defect report! :-)

-Howard

[P.J. Plauger]

Re: std::vector&lt; &gt;::clear semantics

"tom_usenet " <tom_usenet@hot mail.com> wrote in message
news:28ltov47hd aqlef56s21ctagj eltbnmn4s@4ax.c om...
[color=blue][color=green]
> >But I do not believe this new wording provides any flexibility for
> >clear() to reduce capacity. It merely clarifies the situation described
> >in the DR:
> >
> >vec.reserve(23 );
> >vec.reserve(0) ;
> >
> >// capacity() still >= 23 here[/color]
>
> I have roughly the same reasoning (I'd studied the defect reports a
> couple of days ago, along with old threads in std.c++), but Dinkumware
> seem to disagree. But I think it must be a bug/oversight in their
> implementation.
>
> In any case, the standard is ridiculously unclear at the moment. It
> needs to say that capacity will never decrease except during a call to
> swap. I have no idea why it doesn't say that, and why none of the
> defect reports have suggested that.[/color]

At the time we prepared that particular version, the C++ Standard was
at least as unclear. We intentionally made clear reduce capacity, in
response to customer demands for some mechanism to do so. Consensus
seems to be building against that approach, however, so future versions
will no longer reduce capacity.

P.J. Plauger
Dinkumware, Ltd.

http://www.dinkumware.com

[tom_usenet]

Re: std::vector&lt; &gt;::clear semantics

On Thu, 16 Oct 2003 18:13:46 GMT, "P.J. Plauger" <pjp@dinkumware .com>
wrote:
[color=blue][color=green]
>> In any case, the standard is ridiculously unclear at the moment. It
>> needs to say that capacity will never decrease except during a call to
>> swap. I have no idea why it doesn't say that, and why none of the
>> defect reports have suggested that.[/color]
>
>At the time we prepared that particular version, the C++ Standard was
>at least as unclear. We intentionally made clear reduce capacity, in
>response to customer demands for some mechanism to do so.[/color]

You could just have in the documentation for the clear function:

clear() will not reduce the capacity of a vector. To reduce the
capacity call vector<T>().swa p(v);

or similar.

Consensus[color=blue]
>seems to be building against that approach, however, so future versions
>will no longer reduce capacity.[/color]

It's the silent (and undocumented as far as I could find) change in
the meaning of code between versions that's the main problem...

Tom