shrink_to_fit and invalidation (C++0x)

[Scott Meyers]

Draft C++0x specifies that vector, string, and deque offer a shrink_to_fit
member function. They all have more or less the same specification; this is
for vector:

shrink_to_fit is a non-binding request to reduce capacity() to size().

What are the effects, if any, on iterators, pointers, and references into a
container on which shrink_to_fit is invoked? I can't find any information on
this point in the draft.

Thanks,

Scott

 

[Balog Pal]

Draft C++0x specifies that vector, string, and deque offer a shrink_to_fit
member function. They all have more or less the same specification; this
is for vector:


What are the effects, if any, on iterators, pointers, and references into
a container on which shrink_to_fit is invoked? I can't find any
information on this point in the draft.

As I see the text, it explicitly states invalidation wherever it applies
(following the chain if a function is defined in terms of others). This
function stays silent so it will not invalidate anything.

From the logical view I don't see any reason for invalidation either, with
the non-binding nature it seem clear the intent is just realloc/shrink the
memory block obtained if the implementation thinks it is possible and
feasible, leaving it alone otherwise.

If the function allowed moving the content to a new block, it would be
mandatory to tate the time complexity and invalidation effect in the text.

 

[Saeed Amrollahi]

Draft C++0x specifies that vector, string, and deque offer a shrink_to_fit
member function.  They all have more or less the same specification;  this is
for vector:


What are the effects, if any, on iterators, pointers, and references into a
container on which shrink_to_fit is invoked?  I can't find any information on
this point in the draft.

Thanks,

Scott
--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Oct. 24-27 near Seattle
(http://cppandbeyond.com/)
* License my training materials for commercial (http://tinyurl.com/yfzvkp9) or
personal use (http://tinyurl.com/yl5ka5p).

Hi Scott
I tested the shrink_to_fit function in g++ 4.5.0. I think
there is no uniform behavior about iterators or pointers to
the elements which are shrunk:
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

int main()

{
using namespace std;
vector<int> v(10, 0);
v.reserve(20);
cout << "the size of v is " << v.size() << '\n';
cout << "the capacity of v is " << v.capacity() << '\n';
vector<int>::iterator cit = v.begin() + 10; // points to element 11
*cit = -1;
v[11] = -2;
v.data()[12] = -3;
copy(v.begin(), v.end(), ostream_iterator<int>(cout, "\t"));
v.shrink_to_fit();
cout << "\nthe size of v is " << v.size() << '\n';
cout << "the capacity of v is " << v.capacity() << '\n';
cout << *cit << '\n';
cout << v[10] << '\n';
cout << v[11] << '\n';
cout << v.data()[12] << '\n';
return 0;
}

Output:
the size of v is 10
the capacity of v is 20
0 0 0 0 0 0 0 0 0 0
the size of v is 10
the capacity of v is 10
-1
0
135121
0

My two cents
-- Saeed Amrollahi

 

[Marc]

As I see the text, it explicitly states invalidation wherever it applies
(following the chain if a function is defined in terms of others). This
function stays silent so it will not invalidate anything.

From the logical view I don't see any reason for invalidation either, with
the non-binding nature it seem clear the intent is just realloc/shrink the
memory block obtained if the implementation thinks it is possible and
feasible, leaving it alone otherwise.

If the function allowed moving the content to a new block, it would be
mandatory to tate the time complexity and invalidation effect in the text.

This seems to make shrink_to_fit rather useless. The allocator interface
doesn't allow you to give back part of the memory block, so the only way
to shrink is to reallocate and copy/move, which invalidates iterators in
all implementations I know.

shrink_to_fit was introduced as a nicer syntax than swapping a vector
with a copy of itself, so it doesn't sound like the goal ever was to
preserve pointers.

 

[Juha Nieminen]

From the logical view I don't see any reason for invalidation either, with
the non-binding nature it seem clear the intent is just realloc/shrink the
memory block obtained if the implementation thinks it is possible and
feasible, leaving it alone otherwise.

I would say on the contrary: From the logical point of view iterators
should be considered invalid after that operation.

If eg. a vector has currently a capacity of 1 million elements and its
size is only 10, there's a great benefit in reducing the capacity to 10
even if it means that iterators will be invalidated.

 

[Scott Meyers]

I agree with Marc's interpretation.

I don't think Marc offered an interpretation (of the draft standard). I think
he offered an opinion about what might be the case. I'm interested in something
stemming from the standard.

There are implementations of shrink_to_fit by various vendors, so it's easy for
me to look at what they've done, but that's not what I'm interested in. I'm
interested in what C++0x has to say about this question.

Thanks,

Scott

 

[Scott Meyers]

Put it the other way around: the standard doesn't require any heroics, so the
best you can count on is something analogous to the copy-swap idiom. The
standard doesn't prohibit more sophisticated memory managers, and if you know
that your implementation uses one that can chop off the end of a block and
return it to the free store, you may be able to count on iterators not being
invalidated. But that's implementation-specific, and not portable.

These comments, and in fact most of the comments in this thread, seem to refer
exclusively to vector (and, by analogy, to string) and to iterators thereof.
But what about deque, and what about pointers and references? My original
question was

What are the effects, if any, on iterators, pointers, and references into a container on which shrink_to_fit is invoked?

Certainly it would be surprising if deque::shrink_to_fit invalidated pointers
and references, but what about iterators?

Scott

 

[Scott Meyers]

I found it surprising that shrink_to_fit was even applied to deque. Does
the new standard also add reserve and capacity to deque? Because it
seems to me that without at least capacity, shrink_to_fit has no
measurable effect on the container.

It allows the internal array of buffer pointers to be shrunk. Google around for
the document that led to this change in deque, and you'll find a complete
rationale. I don't have number or a link at hand right now, sorry.

Scott

 

[Miles Bader]

This seems to make shrink_to_fit rather useless. The allocator interface
doesn't allow you to give back part of the memory block, so the only way
to shrink is to reallocate and copy/move, which invalidates iterators in
all implementations I know.

shrink_to_fit was introduced as a nicer syntax than swapping a vector
with a copy of itself, so it doesn't sound like the goal ever was to
preserve pointers.

OTOH, even if shrink_to_fit currently is mainly just a nice way of
writing copy+swap, it does make it easier to slot in more clever
implementations (through implementation-specific hackery, or future
standards with an extended allocator interface, or whatever).

[and generally it seems not a bad idea to give a nice name to what's
currently a very common but not-entirely-obvious-to-the-uninitiated code
pattern...]

-Miles

 

[Joshua Maurice]

It make sense to me. I think reserve() and capacity() should be added to deque.

But I also think shrink_to_fit() should be added to all the other containers.

A std::list could easily have a pointer to deleted nodes for a list object, waiting to be recycled in the event of an insert().
shrink_to_fit() would make the number of deleted nodes 0.

I would think such an implementation of a basic standard-library
doubly linked list would be rather perverse. Sure, it's not illegal by
standard, but I still think that's definitely not what a coder wants
or intends when he uses a std::list. "Caching", if I may use the term,
for vector and deque makes sense. That makes push_back amortized
constant time work. Caching nodes inside of a specific list object
doesn't make much sense to me as a general purpose container. It seems
to be a rare use case which requires that, and it seems a job better
suited to the template argument allocator of the list.

 

[James Kanze]

I would think such an implementation of a basic standard-library
doubly linked list would be rather perverse. Sure, it's not illegal by
standard, but I still think that's definitely not what a coder wants
or intends when he uses a std::list. "Caching", if I may use the term,
for vector and deque makes sense. That makes push_back amortized
constant time work. Caching nodes inside of a specific list object
doesn't make much sense to me as a general purpose container. It seems
to be a rare use case which requires that, and it seems a job better
suited to the template argument allocator of the list.

"Caching" doesn't make sense, but most implementations of node
based containers I've seen do use a pool allocator for their
nodes, only going to the system for larger blocks. A reserve()
function could make sense in such cases (not that I'm arguing
for something that specialized in the standard).

 

[Joshua Maurice]

"Caching" doesn't make sense, but most implementations of node
based containers I've seen do use a pool allocator for their
nodes, only going to the system for larger blocks.  A reserve()
function could make sense in such cases (not that I'm arguing
for something that specialized in the standard).

Yes, but that pool allocator tends to be a global, yes? I was arguing
against the sensibility of pooling nodes at the "scope" of a single
doubly-linked list object. It makes perfect sense when we're talking
about groups of list objects, which I tried to explain in my earlier
post. That "reserve" function belongs more on the allocator template
object / type than it does on the list object itself. This is in
contrast with vector where it makes very much sense to "reserve" for a
specific single vector object.