On Mon, 11 Dec 2000 17:42:46 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:

>What functions are allowed to decrease a vector's capacity?  I'd guess the
>following:
>  operator=
>  assign
>  swap
>My interest is really in clear, however.

Actually, I submitted a public comment on this issue for the draft
standard, all those years ago..

By my reading there are two guarantees given by the standard-

(1) If one does an explicit call of reserve() on a vector then the
implementation must NEVER reduce the vector's capacity() below that
(except via the next guarantee) .

(2) swap (being constant time) MUST swap capacities and so the
following function is guaranteed to shrink a vector to the minimal
size (i.e. the size a default constructed vector followed by a series
of inserts would be).

template<typename T>
void compact(std::vector<T>& v)
{
 std::vector<T> temp(v.begin(), v.end());
 temp.swap(v);
}

Apart from these two cases, the standard gives no guarantees because,
as you say,  the behaviour of erase(begin(), end()) is not specified,
although by analogy with erase(begin()+1, end()) one would  expect it
NOT to shrink capacity (and the implementations of STL that I have
seen never shrink capacity).

Strictly,  the two guarantees above are all one needs to manually
manage memory when required, so the standard is useable, but for
determinisms sake, I think that the standard in addition-

(1) should specify that clear(), assign() etc do NOT change capacity
i.e. capacity is non-decreasing unless the function compact() is
called.

(2) the function compact(), or the equivalent member function, should
be added to vector, as its implementation is non-obvious (in fact,
it is interesting to note that even Stroustrups's C++ Programming
language 3rd ed 1st printing incorrectly states that one can compact a
vector by assigning to it e.g. v = vector<int>(4, 99), and this was
changed to-
 vector tmp = v; // copy of v with default capacity
 v.swap(tmp); // now v has the default capacity

in later printings.)

..Brian Parker
(brianjparker@ozemail.com.au)


---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Andrei Alexandrescu wrote:
>
> "Christopher Eltschka" <celtschk@physik.tu-muenchen.de> wrote in message
> news:3A38FA09.58F656D1@physik.tu-muenchen.de...
> > Of course, you cannot change reserve() now, since programs may rely on
> > the fact that it never shrinks the vector. But we could add another
> > member function, say adjust_capacity(), which _would_ be allowed to
> > shrink the vector. The specification would be s.th. like the following:
> >
> >   void adjust_capacity(size_type n)
> >
> >   Post condition: v.capacity() >= min (n, size())
>
> Isn't it max(n, size())?

Yes, of course.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Valentin Bonnard wrote:
>
> Dennis Yelle  wrote:
> > Christopher Eltschka wrote:
> > [...]
> >> Of course, you cannot change reserve() now, since programs may rely on
> >> the fact that it never shrinks the vector. But we could add another
> >> member function, say adjust_capacity(), which _would_ be allowed to
> >> shrink the vector. The specification would be s.th. like the following:
> >>
> >>   void adjust_capacity(size_type n)
> >>
> >>   Post condition: v.capacity() >= min (n, size())
> >>
> >>   This function changes the capacity of the vector, but lets it's
> >>   content unchanged. If before the call n == capacity(), the operation
> >>   is a no-op. Otherwise, the capacity is changed to an arbitrary
> >>   value >= n, and all iterators, pointers and references into the
> >>   vector are invalidated.
> >>
> >>   Implementation advice: adjust_capacity(0) should make the vector
> >>   shrink-to-fit (i.e. after the call, v.capacity() == v.size()).
> >>   If before the call n > v.capacity(), the effect of v.reserve(n)
> >>   and v.adjust_capacity(n) should be the same.
> >>
> >> Hmmm... maybe a candidate for a feature request?
> >
> > It sounds like the only call to adjust_capacity() that a
> > programmer can (sort of) rely on is when the parameter is zero.
>
> With the above semantic, adjust_capacity can be implemented
> as follow:
>
> void adjust_capacity (size_type n) {
>   if (capacity () != n)
>     reserve (n);
> }

Yes, and reserve(n) could be defined to allocate the maximum memory
possible. And capacity() isn't required to return the actual memory
allocation, since no conforming program can check that anyway; all
that is guaranteed is that there is _at least_ as much memory
allocated as capacity() reports.
All this is an implementation quality question. The standard
doesn't guarantee an useful implementation. Why should it make
additional guaranteed on a new adjust_capacity, which wouldn't
be a real additional guarantee anyway, due to the "capacity hole"
shown above? The following code would be legal even with an
"capacity()==min(n, size())" post condition:

vector()
{
  __allocate(max_size());
}

void adjust_capacity(size_type n)
{
  if (capacity() != n)
    reserve(n);
  __reported_capacity = max(n, size());
}

size_type capacity()
{
  return __reported_capacity;
}

void reserve(size_type n)
{
  if (n > __reported_capacity)
    __reported_capacity() = n;
}


However, looking again at the specification, I see that the *intent*
of allowing the vector to shrink isn't clear in the text. Therefore,
revised specification:

  void adjust_capacity(size_type n)

  Post condition: v.capacity() >= min (n, size())

  This function changes the capacity of the vector, but lets it's
  content unchanged. If before the call n == capacity(), the operation
  is a no-op. Otherwise, the capacity is changed to an arbitrary
  value >= n, which may be less than the capacity the of vector before
  the call, and all iterators, pointers and references into the
  vector are invalidated.

  Implementation advice: adjust_capacity(0) should make the vector
  shrink-to-fit (i.e. after the call, v.capacity() == v.size()).
  If before the call n > v.capacity(), the effect of v.reserve(n)
  and v.adjust_capacity(n) should be the same. adjust_capacity should
  make the capacity as small as possible within the constraints of the
  used memory allocation strategy.

While this revised specification still does not guarantee shrinking,
is makes the intent clear and gives an appropriate implementation
advice.

The non-guarantee is intentional; think f.ex. of a word addressed
machine, 4 bytes per word, which allocates memory in full words
for vector<char>. Now assume size()==14, capacity()==16, and a call
of adjust_capacity(15) is done. Now, should the vector really be
forced to reduce it's capacity to 15?

[...]

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Christopher Eltschka" <celtschk@physik.tu-muenchen.de> wrote in message
news:3A38FA09.58F656D1@physik.tu-muenchen.de...
> Of course, you cannot change reserve() now, since programs may rely on
> the fact that it never shrinks the vector. But we could add another
> member function, say adjust_capacity(), which _would_ be allowed to
> shrink the vector. The specification would be s.th. like the following:
>
>   void adjust_capacity(size_type n)
>
>   Post condition: v.capacity() >= min (n, size())

Isn't it max(n, size())?

Andrei



---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Pete Becker wrote:
>
> Use resize to shrink a vector.
>

Whoops, never mind. resize doesn't affect capacity, just size.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Tue, 12 Dec 2000 17:27:00 GMT, Pete Becker wrote:
> No, clear is not allowed to reduce a vector's capacity. I don't know
> whether the same is true for a string.

How do you come to this conclusion?  I'm not disagreeing with you, but I
would like to know why you believe this.

> Use resize to shrink a vector.

The semantics of both clear and resize (when the new size is smaller than
the current size) are defined by the behavior of the range form of erase.
So I guess the question boils down to this:

  For a vector or string x, can x.erase(x.begin(), x.end()) change x's
  capacity?

My suspicion is that it can, but I could easily have overlooked something.
On a related note, does anybody know of any implementation where clear or
erase(begin, end) DOES change the capacity of a vector or string?

Scott

--
I've scheduled more public seminars.  Check out
http://www.aristeia.com/seminars/ for details.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

scott.ladd@maximal.com (Scott Robert Ladd) wrote (abridged):
> I've been looking into this very issue, and I think the Standard has
> left us high and dry. I can't find *any* way to "shrink" the allocated
> capacity of a vector (of or any container, for that matter).

Agreed. In practice,

    template <typename V>
    void shrink( V &v ) {
        V( v ).swap( v );
        assert( v.capacity() == v.size() );
    }

works for all implementations I know of (including VC++ 6). It creates a
temporary copy of v, which hopefully will only allocate memory for the
items it needs to store. It can do this because it is a new vector and
doesn't have to worry about invalidating iterators, or any other
guarantees on capacity. Then it swaps this minimal vector back into v.

Although I don't think this is guaranteed by the standard, I would use it
in preference to creating my own vector type. I would be surprised if any
thoughtful vendor broke it, as it is a fairly well-known idiom and
because we must have *some* way to reduce capacity.


> A general, "Standard" solution, however, would be a Good Thing.

Absolutely. Do you want to propose a "Feature Request" for it?

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Pete Becker wrote:
>

>
> No, clear is not allowed to reduce a vector's capacity. I don't know
> whether the same is true for a string.
>
> Use resize to shrink a vector.
>
>

Depends what you mean by shrink. Your suggestion is (effectively) to
erase the elements at the end of the vector but as Herb Sutter's GotW
#54 (http://www.peerdirect.com/Resources/gotw054a.html) you should use
vector<X>(x).swap(x) to reduce the allocated storage. I believe that
reducing the capacity means just that, so resize doesn't seem to be the
right thing (unless I misunderstood Scott Meyer's question).


Regards, 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Meyers wrote:
>
> On Tue, 12 Dec 2000 17:27:00 GMT, Pete Becker wrote:
> > No, clear is not allowed to reduce a vector's capacity. I don't know
> > whether the same is true for a string.
>
> How do you come to this conclusion?  I'm not disagreeing with you, but I
> would like to know why you believe this.
>

This just isn't my day. clear has the effect of erase(begin(), end()).
Our documentation says that erase doesn't reallocate, which is true, and
which implies that clear cannot shrink a vector. The C++ standard says
less: it requires that erase invalidate iterators from the point of the
erase to the end, which implies that iterators before the point of the
erase remain valid. For erase(begin(), end()) there are no iterators
before the point of the erase, and, more generally, for any erase
beginning at begin(), an implementation could reallocate.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Tue, 12 Dec 2000 22:14:49 GMT, Pete Becker wrote:
> This just isn't my day.

Heck, I've had months like that :-)

> erase remain valid. For erase(begin(), end()) there are no iterators
> before the point of the erase, and, more generally, for any erase
> beginning at begin(), an implementation could reallocate.

Okay, it sounds like we read the standard the same way.  clear can do
whatever it wants to wrt a vector's/string's capacity.  Oh happy day :-|

Scott

--
I've scheduled more public seminars.  Check out
http://www.aristeia.com/seminars/ for details.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <MPG.14a047c4155a35b798975e@news.supernews.com>,
  Scott Meyers <smeyers@aristeia.com> wrote:
> On Tue, 12 Dec 2000 22:14:49 GMT, Pete Becker wrote:
> > This just isn't my day.
>
> Heck, I've had months like that :-)
>
> > erase remain valid. For erase(begin(), end()) there are no iterators
> > before the point of the erase, and, more generally, for any erase
> > beginning at begin(), an implementation could reallocate.
>
> Okay, it sounds like we read the standard the same way.  clear can do
> whatever it wants to wrt a vector's/string's capacity.  Oh happy
day :-|
>

Maybe not quite so happy :(

A call to reserve guarantees that a vector has at least the specified
capacity. I would be really miffed if I called reserve to ensure there
was at least enough space for 20 elements, added 10, deleted all of
them (using clear()), and then inserted 20, only to find that the
vector was now reallocating.

Anthony
--
alink@anthonyw.cjb.net -- Questions relating to ALINK
anthony@anthonyw.cjb.net  -- Non-ALINK questions
anthonyw.cjb.net -- ALINK home page
PGP Key at: i3.yimg.com/3/c7e5ee24/g/68fc2307.asc


Sent via Deja.com
http://www.deja.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Tue, 12 Dec 2000 22:14:49 GMT, Pete Becker <petebecker@acm.org>
wrote:

> Scott Meyers wrote:
> >
> > On Tue, 12 Dec 2000 17:27:00 GMT, Pete Becker wrote:
> > > No, clear is not allowed to reduce a vector's capacity. I don't know
> > > whether the same is true for a string.
> >
> > How do you come to this conclusion?  I'm not disagreeing with you, but I
> > would like to know why you believe this.
> >
>
> This just isn't my day. clear has the effect of erase(begin(), end()).
> Our documentation says that erase doesn't reallocate, which is true, and
> which implies that clear cannot shrink a vector. The C++ standard says
> less: it requires that erase invalidate iterators from the point of the
> erase to the end, which implies that iterators before the point of the
> erase remain valid. For erase(begin(), end()) there are no iterators
> before the point of the erase, and, more generally, for any erase
> beginning at begin(), an implementation could reallocate.

I liked your first answer better.  Maybe a standardez lesson for me.
24.2.4.2/5 states that no insertion after a reserve will reallocate
unless size exceeds the reserve.

   vector<int> v;
   v.reserve(20);
   v.insert(v.begin(), 10, 42);  // No reallocation
   v.clear();

Same vector with new size == 0.

   v.insert(v.begin(), 15, 86);

Still after the reserve.  Size <= 20.  No reallocation.

   v.assign(10, 69);

Same vector with new value.

   v.push_back(13);

Still after the reserve.  Size <= 20.  No reallocation.

   v = vector<int>(3, 7);

Same vector with new value.

   v.insert(v.begin(), 8, 24);

Still after the reserve.  Size <= 20.  No reallocation.

   vector<int>().swap(v);

It can't be the same vector now if swap is constant time.  This must
invalidate the reserve.

The standard gives no way to invalidate the reserve other than
exceeding it.

While we are at it, I have recently seen claims that

   vector<int>(v).swap(v);

will reduce the capacity of v to near the size of v.

   v.reserve(1024);
   vector<int>(v).swap(v);

Is there anything in the standard that says that a copy of a vector will
have a capacity other than that of the copied vector?

I don't see any upper bound on capacity in the standard.

I do find it interesting that assignment does not allow assignment of
elements, but requires destruction and construction of them.

What am I missing?

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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3a36f3da.35211981@news.csrlink.net>,
  jpotter@falcon.lhup.edu (John Potter) wrote:
>
> While we are at it, I have recently seen claims that
>
>    vector<int>(v).swap(v);
>
> will reduce the capacity of v to near the size of v.
>
>    v.reserve(1024);
>    vector<int>(v).swap(v);
>
> Is there anything in the standard that says that a copy of a vector
will
> have a capacity other than that of the copied vector?
>

There isn't, but there isn't anything to say it must have the same
capacity, either. (Actually, I can see an argument that a "true" copy
of an object would have all the same properties as the original, which
would include capacity for a vector)

I expect

vector<int>(v.begin(),v.end()).swap(v);

to work better, allocating the minimum space that the vector
implementation feels is necessary to fit the elements. Of course, an
implementation is free to set the capacity as high as it likes in this
case (perhaps it chooses the first power of two that fits the required
number). It doesn't even have to be repeatable - the capacity may be a
random amount larger than the required size.

I would, however, expect that the capacity of the new vector in this
case would be the same as the capacity of both of the following vectors:

vector<int> v2(v.size());
vector<int> v3;
v3.resize(v.size());

Anthony
--
alink@anthonyw.cjb.net -- Questions relating to ALINK
anthony@anthonyw.cjb.net  -- Non-ALINK questions
anthonyw.cjb.net -- ALINK home page
PGP Key at: i3.yimg.com/3/c7e5ee24/g/68fc2307.asc


Sent via Deja.com
http://www.deja.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Tue, 12 Dec 2000 17:19:15 GMT, "Richard Parkin"
<rparkin@nospam.msi-eu.com> wrote:

>
>"Scott Robert Ladd" <scott.ladd@maximal.com> wrote in message
>news:YvrZ5.123286$vc3.25643023@typhoon.tampabay.rr.com...
>> I've been looking into this very issue, and I think the Standard has left us
>> high and dry. I can't find *any* way to "shrink" the allocated capacity of a
>> vector (of or any container, for that matter).
>
>How about:
>
>std::vector< int > v;
>// populate v
>std::vector< int >( v ).swap( v ); // split into two lines if you like
>// v now contains the smallest capacity it can.

unfortunately, I have not found anything in the standard to guarantee
that the last comment is true... I believe that the implementation may
make the capacity of the copy-constructed vector whatever it likes:
for example the capacity of the one being copied, or even bigger!

Tim

--
Tim Sharrock   (tim@sharrock.org.uk)

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3A3658C2.BB9A15EF@sensor.com>,
  Ron Natalie <ron@sensor.com> wrote:

> Scott Robert Ladd wrote:

> > I've been looking into this very issue, and I think the Standard
> > has left us high and dry. I can't find *any* way to "shrink" the
> > allocated capacity of a vector (of or any container, for that
> > matter).

> The standard doesn't require that implmentations be able to shirnk
> the reserved capacity.  This isn't really any worse than the fact
> that the standard doesn't make any statement as to the reusability
> of the memory returned from delete either.

That's not the problem.  The problem is that I have guarantees
concerning the validity of iterators, pointers and references.  Thus:

    vector<int> v( 10 ) ;       //  v.capacity() >= 10
    v.reserve( 20 ) ;           //  v.capacity() >= 10
    v.clear()                   //  v.capacity() >= 10 !!
    v.push_back( 1 ) ;          //  no allocation.
    int* p = &v[ 0 ] ;
    v.push_back( 2 ) ;          //  no allocation, so p still valid...

Unless someone can show me where after the call to reserve, above, the
standard allows invalidating iterators or pointers, I don't see how
clear can possibly reduce the capacity.

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh   ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627


Sent via Deja.com
http://www.deja.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3A368867.884010C9@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> Scott Meyers wrote:
> > From what I can tell, the standard doesn't have much to say about
> > when a vector's capacity may decrease, but this is important
> > information for programmers who are relying on the duration of the
> > effect of a call to reserve.  May a call to clear reduce a
> > vector's capacity?  What about for string?

> No, clear is not allowed to reduce a vector's capacity. I don't know
> whether the same is true for a string.

> Use resize to shrink a vector.

But resize isn't allowed to invalidate iterators either, unless it has
to increase the size.

BTW: where does it say in the standard that assignment can invalidate
iterators?

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh   ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627


Sent via Deja.com
http://www.deja.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

John Potter wrote:
>
> On Tue, 12 Dec 2000 22:14:49 GMT, Pete Becker <petebecker@acm.org>
> wrote:
>
> > Scott Meyers wrote:
> > >
> > > On Tue, 12 Dec 2000 17:27:00 GMT, Pete Becker wrote:
> > > > No, clear is not allowed to reduce a vector's capacity. I don't know
> > > > whether the same is true for a string.
> > >
> > > How do you come to this conclusion?  I'm not disagreeing with you, but I
> > > would like to know why you believe this.
> > >
> >
> > This just isn't my day. clear has the effect of erase(begin(), end()).
> > Our documentation says that erase doesn't reallocate, which is true, and
> > which implies that clear cannot shrink a vector. The C++ standard says
> > less: it requires that erase invalidate iterators from the point of the
> > erase to the end, which implies that iterators before the point of the
> > erase remain valid. For erase(begin(), end()) there are no iterators
> > before the point of the erase, and, more generally, for any erase
> > beginning at begin(), an implementation could reallocate.
>
> I liked your first answer better.  Maybe a standardez lesson for me.
> 24.2.4.2/5 states that no insertion after a reserve will reallocate
> unless size exceeds the reserve.
>
>    vector<int> v;
>    v.reserve(20);
>    v.insert(v.begin(), 10, 42);  // No reallocation
>    v.clear();
>
> Same vector with new size == 0.
>

I think that that reading of the standard is defensible, but I don't
think that the intention was to make reserve sticky. Rather, it was a
statement of effect: reserve sets aside enough memory for the number of
elements you've requested. Reading it to prohibit any subsequent
reduction in the size of the vector, regardless of any itervening
operations, seems to me to go beyond its intent.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:3a36f3da.35211981@news.csrlink.net...
> On Tue, 12 Dec 2000 22:14:49 GMT, Pete Becker <petebecker@acm.org>
> wrote:
> While we are at it, I have recently seen claims that
>
>    vector<int>(v).swap(v);
>
> will reduce the capacity of v to near the size of v.
>


This was likely to be have been me.

>    v.reserve(1024);
>    vector<int>(v).swap(v);


> Is there anything in the standard that says that a copy of a vector will
> have a capacity other than that of the copied vector?

in other words
vector< int > v2 ( v1 );
what relationship is there guarenteed between the capacities?

I think the answer is, not much:
v2.size() == v1.size();
v1.capacity() >= v1.size();
v2.capacity() >= v2.size();

Anthony mentions the argument that capacity could be viewed as a property of
the container, so is preserved by a copy. I'll just mention a possible
counter-argument: as capacity is just a consequence of how many insertions
and optimization hints (and could even be random), it's not logically part
of the object state, so is shouldn't be copied.

Coming at it another angle, is

vector< int > v2( v );
equivalent to
vector< int > v2( v.begin(), v.end() );

A: Yes, except for the capacity.

> I don't see any upper bound on capacity in the standard.

Drat, me neither. Even the lower bound isn't that useful:

vector< int > v;
cout << v.capacity(); // could be any value if it preallocates (Q: is it
allowed to do such a thing?)

So it's even possible that
vector<int>().swap(v);
could be a waste of time.

Hmm, so that idiom should have the caveat 'it is not guarenteed to do
anything at all, but often will, and is often what you expect'. Not that
comforting.

So
vector< int >( v.begin(), v.end() ).swap( v );

is the 'best' we can do - the initial capacity of the copy will the smallest
allowed by the implementation.

> I do find it interesting that assignment does not allow assignment of
> elements, but requires destruction and construction of them.
>
> What am I missing?

Is that where assign has the effects of erase + insert?  The values must be
Assignable, so it's not to cater for them not being.
I can't see it making it much better in the presence of exceptions either.

Ric






---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Tim Sharrock wrote:
>
> On Tue, 12 Dec 2000 17:19:15 GMT, "Richard Parkin"
> <rparkin@nospam.msi-eu.com> wrote:
...
> >How about:
> >
> >std::vector< int > v;
> >// populate v
> >std::vector< int >( v ).swap( v ); // split into two lines if you like
> >// v now contains the smallest capacity it can.
>
> unfortunately, I have not found anything in the standard to guarantee
> that the last comment is true... I believe that the implementation may
> make the capacity of the copy-constructed vector whatever it likes:
> for example the capacity of the one being copied, or even bigger!

Correct, however -
1. The standard allows the capacity to be shrunk in this context.
2. There's no good reason for a typical implementation to not
allocate-to-fit. By allocate-to-fit I don't necessarily mean
capacity()==size(); a legal implementation might choose to always have
capacity() == "size() rounded up to next power of 2", or "reservation
rounded up to the next power of 2" if there's a reservation currently in
effect.
3. Any competent implementor will seize any reasonably cheap opportunity
to legally perform allocate-to-fit, precisely because there's so many
contexts where it isn't legal.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Pete Becker wrote:
...
> I think that that reading of the standard is defensible, but I don't
> think that the intention was to make reserve sticky. Rather, it was a
> statement of effect: reserve sets aside enough memory for the number of
> elements you've requested. Reading it to prohibit any subsequent
> reduction in the size of the vector, regardless of any itervening
> operations, seems to me to go beyond its intent.

The standard only mentions two operations that are allowed to cancel or
modify a reservation: an insert that exceeds the reservation, and a new
reservation (since it's only the most recent one that imposes a
restriction). I think that operator=() and swap() might be allowed to
change the reservation, but only by arguing that a reservation is one of
the attributes of a vector<> which is subject to being copied by those
operations. What others do you think are exempt, and why?

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Richard Parkin wrote:
>
> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:3a36f3da.35211981@news.csrlink.net...
...
> > I don't see any upper bound on capacity in the standard.
>
> Drat, me neither. Even the lower bound isn't that useful:
>
> vector< int > v;
> cout << v.capacity(); // could be any value if it preallocates (Q: is it
> allowed to do such a thing?)

I see nothing to prohibit it.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3A37B950.9DB94876@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> John Potter wrote:
> >
> > I liked your first answer better.  Maybe a standardez lesson for me.
> > 24.2.4.2/5 states that no insertion after a reserve will reallocate
> > unless size exceeds the reserve.
> >
> >    vector<int> v;
> >    v.reserve(20);
> >    v.insert(v.begin(), 10, 42);  // No reallocation
> >    v.clear();
> >
> > Same vector with new size == 0.
> >
>
> I think that that reading of the standard is defensible, but I don't
> think that the intention was to make reserve sticky. Rather, it was a
> statement of effect: reserve sets aside enough memory for the number
of
> elements you've requested. Reading it to prohibit any subsequent
> reduction in the size of the vector, regardless of any itervening
> operations, seems to me to go beyond its intent.

It might be beyond its intent, but its what it says:

23.2.4.2p5:

"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()."

However, you do get the opt-out:

vector<int> v;
v.reserve(100);
v.reserve(0);

The first call to reserve() will ensure the capacity() is at least 100.
The second call will leave capacity unchanged, but remove any
guarantees we have on the capacity() after subsequent operations. Thus,
if we do:

v.clear();

We now have no requirement on capacity(), and we are permitted to
reallocation for any insert operation that increases the size beyond
that of the most recent reserve(), which is 0, so we can reallocate for
ANY insert operation.

Anthony
--
alink@anthonyw.cjb.net -- Questions relating to ALINK
anthony@anthonyw.cjb.net  -- Non-ALINK questions
anthonyw.cjb.net -- ALINK home page
PGP Key at: i3.yimg.com/3/c7e5ee24/g/68fc2307.asc


Sent via Deja.com
http://www.deja.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

James.Kanze@dresdner-bank.com wrote:
>
> In article <3A3658C2.BB9A15EF@sensor.com>,
>   Ron Natalie <ron@sensor.com> wrote:
>
> > Scott Robert Ladd wrote:
>
> > > I've been looking into this very issue, and I think the Standard
> > > has left us high and dry. I can't find *any* way to "shrink" the
> > > allocated capacity of a vector (of or any container, for that
> > > matter).
>
> > The standard doesn't require that implmentations be able to shirnk
> > the reserved capacity.  This isn't really any worse than the fact
> > that the standard doesn't make any statement as to the reusability
> > of the memory returned from delete either.
>
> That's not the problem.  The problem is that I have guarantees
> concerning the validity of iterators, pointers and references.  Thus:
>
>     vector<int> v( 10 ) ;       //  v.capacity() >= 10
>     v.reserve( 20 ) ;           //  v.capacity() >= 10

You wanted to say:                    v.capacity() >= 20

>     v.clear()                   //  v.capacity() >= 10 !!

Same here.

>     v.push_back( 1 ) ;          //  no allocation.
>     int* p = &v[ 0 ] ;
>     v.push_back( 2 ) ;          //  no allocation, so p still valid...
>
> Unless someone can show me where after the call to reserve, above, the
> standard allows invalidating iterators or pointers, I don't see how
> clear can possibly reduce the capacity.

IMHO the problem is that reserve() itself cannot shrink the vector.
IMHO the correct choice would have been to allow reserve() to shrink
it, as long as capacity remains larger than size:

vector<int> v(10);    // v.capacity() >= 10
v.reserve(20);        // v.capacity() >= 20
v.clear();            // v.capacity() >= 20
v.reserve(0);         // wanted: v.capacity() >= 0
v.push_back(1);       // follows: v.capacity() >= 1
v.push_back(2);       // follows: v.capacity() >= 2
v.reserve(20);        // v.capacity() >= 20
v.reserve(1);         // wanted: v.capacity() >= 2
                      // (because v.size() == 2)

Of course, you cannot change reserve() now, since programs may rely on
the fact that it never shrinks the vector. But we could add another
member function, say adjust_capacity(), which _would_ be allowed to
shrink the vector. The specification would be s.th. like the following:

  void adjust_capacity(size_type n)

  Post condition: v.capacity() >= min (n, size())

  This function changes the capacity of the vector, but lets it's
  content unchanged. If before the call n == capacity(), the operation
  is a no-op. Otherwise, the capacity is changed to an arbitrary
  value >= n, and all iterators, pointers and references into the
  vector are invalidated.

  Implementation advice: adjust_capacity(0) should make the vector
  shrink-to-fit (i.e. after the call, v.capacity() == v.size()).
  If before the call n > v.capacity(), the effect of v.reserve(n)
  and v.adjust_capacity(n) should be the same.

Hmmm... maybe a candidate for a feature request?

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3A37B950.9DB94876@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> John Potter wrote:

> > I liked your first answer better.  Maybe a standardez lesson for me.
> > 24.2.4.2/5 states that no insertion after a reserve will reallocate
> > unless size exceeds the reserve.

> >    vector<int> v;
> >    v.reserve(20);
> >    v.insert(v.begin(), 10, 42);  // No reallocation
> >    v.clear();

> > Same vector with new size == 0.

> I think that that reading of the standard is defensible, but I don't
> think that the intention was to make reserve sticky. Rather, it was
> a statement of effect: reserve sets aside enough memory for the
> number of elements you've requested. Reading it to prohibit any
> subsequent reduction in the size of the vector, regardless of any
> itervening operations, seems to me to go beyond its intent.

You were there, so you presumably know more about the intent than we
do.  However, in this case, what the standard says seems rather clear,
intent or not.  And I can think of cases where it is useful; if code
depends on it, then there may be a problem changing it.

The obvious case where it is useful is where you are reading sets of
known length, then processing them, and reading the next set, e.g.:

    vector<T> v ;
    v.reserve( 100 ) ;
    while ( whatever() ) {
        v.clear() ;
        for ( int i = 0 ; i < 100 ; ++ i ) {
            v.push_back( getData() ) ;
        }
        //  Process data.
    }

According to the standard, there will be no reallocation of v after
the call to reserve.  Of course, in this case, it is just an
optimization issue, but if I looked at the data when pushing it in,
and saved an iterator or a reference to certain data, it would be a do
or die issue for the program.

Can you give some premordial reason why this code should be illegal
(supposing a saved iterator)?

A second question is whether it actually works with current
implementations.  You apparently think (or thought) that clear could
reduce the capacity.  Does your implementation actually do so?  Do
others?

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh   ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627


Sent via Deja.com
http://www.deja.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

James.Kanze@dresdner-bank.com wrote:
>
> > I think that that reading of the standard is defensible, but I don't
> > think that the intention was to make reserve sticky. Rather, it was
> > a statement of effect: reserve sets aside enough memory for the
> > number of elements you've requested. Reading it to prohibit any
> > subsequent reduction in the size of the vector, regardless of any
> > itervening operations, seems to me to go beyond its intent.
>
> You were there, so you presumably know more about the intent than we
> do.

I was giving my opinion. I don't recall any particular discussion about
this issue, so I have no more standing here than anyone else.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <91as9d$vcn$1@nnrp1.deja.com>, James.Kanze@dresdner-bank.com wrote:

| A second question is whether it actually works with current
| implementations.  You apparently think (or thought) that clear could
| reduce the capacity.  Does your implementation actually do so?  Do
| others?

The Metrowerks implementation of vector never shrinks the capacity except
possibly via a swap.  The copy constructor sets the capacity at the
vector's size() so that the swap trick shown by other posters is indeed a
shrink to fit operation.

Note that the Metrowerks string reserve, by contrast, does do a shrink to
fit provided that there is enough memory to allocate another buffer.  If
there is not enough memory, and the reserve's argument indicated an intent
to shrink capacity (as opposed to grow it), then the exception from the
failed allocation does not propagate out of the reserve method.  In any
event, if the allocation failed reserve has no effect.

>From 21.3.3/11:

| Calling reserve() with a res_arg argument less than capacity() is in
| effect a non-binding shrink request. A call with res_arg <= size() is in
| effect a non-binding shrink-to-fit request.

-Howard

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Christopher Eltschka wrote:
[...]
> Of course, you cannot change reserve() now, since programs may rely on
> the fact that it never shrinks the vector. But we could add another
> member function, say adjust_capacity(), which _would_ be allowed to
> shrink the vector. The specification would be s.th. like the following:
>
>   void adjust_capacity(size_type n)
>
>   Post condition: v.capacity() >= min (n, size())
>
>   This function changes the capacity of the vector, but lets it's
>   content unchanged. If before the call n == capacity(), the operation
>   is a no-op. Otherwise, the capacity is changed to an arbitrary
>   value >= n, and all iterators, pointers and references into the
>   vector are invalidated.
>
>   Implementation advice: adjust_capacity(0) should make the vector
>   shrink-to-fit (i.e. after the call, v.capacity() == v.size()).
>   If before the call n > v.capacity(), the effect of v.reserve(n)
>   and v.adjust_capacity(n) should be the same.
>
> Hmmm... maybe a candidate for a feature request?

It sounds like the only call to adjust_capacity() that a
programmer can (sort of) rely on is when the parameter is zero.
Perhaps a shrink_to_fit(/*void*/) call would be a better fit
for this case.  Would it make sense to _require_ that
v.capacity() and v.size() be equal after a call to v.shrink_to_fit() ?

Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Dennis Yelle  wrote:
> Christopher Eltschka wrote:
> [...]
>> Of course, you cannot change reserve() now, since programs may rely on
>> the fact that it never shrinks the vector. But we could add another
>> member function, say adjust_capacity(), which _would_ be allowed to
>> shrink the vector. The specification would be s.th. like the following:
>>
>>   void adjust_capacity(size_type n)
>>
>>   Post condition: v.capacity() >= min (n, size())
>>
>>   This function changes the capacity of the vector, but lets it's
>>   content unchanged. If before the call n == capacity(), the operation
>>   is a no-op. Otherwise, the capacity is changed to an arbitrary
>>   value >= n, and all iterators, pointers and references into the
>>   vector are invalidated.
>>
>>   Implementation advice: adjust_capacity(0) should make the vector
>>   shrink-to-fit (i.e. after the call, v.capacity() == v.size()).
>>   If before the call n > v.capacity(), the effect of v.reserve(n)
>>   and v.adjust_capacity(n) should be the same.
>>
>> Hmmm... maybe a candidate for a feature request?
>
> It sounds like the only call to adjust_capacity() that a
> programmer can (sort of) rely on is when the parameter is zero.

With the above semantic, adjust_capacity can be implemented
as follow:

void adjust_capacity (size_type n) {
  if (capacity () != n)
    reserve (n);
}

so you cannot ever rely on adjust_capacity to do anything
reserve cannot do.

> Would it make sense to _require_ that
> v.capacity() and v.size() be equal after a call to v.shrink_to_fit() ?

No.

--

Valentin Bonnard

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

What functions are allowed to decrease a vector's capacity?  I'd guess the
following:
  operator=
  assign
  swap
My interest is really in clear, however.  May clear decrease the capacity
of a vector?  Since clear's semantics are defined in terms of the range
form of erase, I think the question boils down to whether erase(it1, it2)
may decrease a vector's capacity.  In general, I think the answer is no,
because erase isn't allowed to invalidate iterators/pointers/references to
elements that precede the range being erased, but if the range being erased
is the entire container, invalidation isn't a concern.

>From what I can tell, the standard doesn't have much to say about when a
vector's capacity may decrease, but this is important information for
programmers who are relying on the duration of the effect of a call to
reserve.  May a call to clear reduce a vector's capacity?  What about for
string?

Thanks,

Scott

--
I've scheduled more public seminars.  Check out
http://www.aristeia.com/seminars/ for details.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Scott Meyers" <smeyers@aristeia.com> wrote...
> My interest is really in clear, however.  May clear decrease the capacity
> of a vector?  Since clear's semantics are defined in terms of the range
> form of erase, I think the question boils down to whether erase(it1, it2)
> may decrease a vector's capacity.  In general, I think the answer is no,
> because erase isn't allowed to invalidate iterators/pointers/references to
> elements that precede the range being erased, but if the range being
erased
> is the entire container, invalidation isn't a concern.


Hi,

I've been looking into this very issue, and I think the Standard has left us
high and dry. I can't find *any* way to "shrink" the allocated capacity of a
vector (of or any container, for that matter).

Under Visual C++ 6 (the only compiler this company uses, alas!), the
capacity of a vector increases exponentially -- as you insert elements, the
capacity increases in the series 1, 2, 4, 8, 16... etc. Erasing elements did
*not* cause the vector to decrease its capacity.

Nor does clear()...

The chosen allocator defines how a Standard container changes capacity; I
suppose one could write a "smarter" allocator to adjust capacity
dynamically. However, that seemed like more effort than I needed for my
current application, so I wrote my own "vector" type. A general, "Standard"
solution, however, would be a Good Thing.

--
Scott Robert Ladd  http://coyotegulch.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Robert Ladd wrote:
>
> I've been looking into this very issue, and I think the Standard has left us
> high and dry. I can't find *any* way to "shrink" the allocated capacity of a
> vector (of or any container, for that matter).

The standard doesn't require that implmentations be able to shirnk the reserved
capacity.  This isn't really any worse than the fact that the standard doesn't
make any statement as to the reusability of the memory returned from delete
either.

> Under Visual C++ 6 (the only compiler this company uses, alas!), the
> capacity of a vector increases exponentially -- as you insert elements, the
> capacity increases in the series 1, 2, 4, 8, 16... etc.

To a point, this is what you want.  It's horrendously inefficient to bump
the allocation of what's effectively an array internally as you add elements.

You can probably twart your problem by just "reserve()"-ing the memory in
advance, rather than letting it grow as you push elements into it (if your
issue is the exponential allocator size).  No reallocation happens if the
new size of the vector is less than the reserved capacity.

> The chosen allocator defines how a Standard container changes capacity; I
> suppose one could write a "smarter" allocator to adjust capacity
> dynamically

I'm not sure you could do it then.  I don't think that the dealloate
is necessarily called (it certainly insn't in the VC++ case) on reducing
the size of the vector.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Robert Ladd wrote:
>
> The chosen allocator defines how a Standard container changes capacity;

The allocator allocates memory at the request of the container. The
strategy of allowing for additional space for elements is implemented by
the container itself. Otherwise you couldn't use the same allocator for
a list and a vector.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Scott Robert Ladd" <scott.ladd@maximal.com> wrote in message
news:YvrZ5.123286$vc3.25643023@typhoon.tampabay.rr.com...
> "Scott Meyers" <smeyers@aristeia.com> wrote...
> > My interest is really in clear, however.  May clear decrease the
capacity
> > of a vector?  Since clear's semantics are defined in terms of the range
> > form of erase, I think the question boils down to whether erase(it1,
it2)
> > may decrease a vector's capacity.  In general, I think the answer is no,
> > because erase isn't allowed to invalidate iterators/pointers/references
to
> > elements that precede the range being erased, but if the range being
> erased
> > is the entire container, invalidation isn't a concern.
>
> I've been looking into this very issue, and I think the Standard has left
us
> high and dry. I can't find *any* way to "shrink" the allocated capacity of
a
> vector (of or any container, for that matter).

How about:

std::vector< int > v;
// populate v
std::vector< int >( v ).swap( v ); // split into two lines if you like
// v now contains the smallest capacity it can.

> Under Visual C++ 6 (the only compiler this company uses, alas!), the
> capacity of a vector increases exponentially -- as you insert elements,
the
> capacity increases in the series 1, 2, 4, 8, 16... etc. Erasing elements
did
> *not* cause the vector to decrease its capacity.
>
> Nor does clear()...

I think this is as required.

As far as Scott's original question goes, I think he's right about the only
things that reduce the capacity, but haven't found enough proof to post.

> The chosen allocator defines how a Standard container changes capacity; I
> suppose one could write a "smarter" allocator to adjust capacity
> dynamically. However, that seemed like more effort than I needed for my
> current application, so I wrote my own "vector" type. A general,
"Standard"
> solution, however, would be a Good Thing.

I don't think an allocator could do this - it just responds to general
requests to allocate/deallocate memory, not when those requests occur.

Ric



---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Meyers wrote:
>
> >From what I can tell, the standard doesn't have much to say about when a
> vector's capacity may decrease, but this is important information for
> programmers who are relying on the duration of the effect of a call to
> reserve.  May a call to clear reduce a vector's capacity?  What about for
> string?
>

No, clear is not allowed to reduce a vector's capacity. I don't know
whether the same is true for a string.

Use resize to shrink a vector.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]