STL vector and reserve

73 views
Skip to first unread message

Matt Blackler

unread,
Sep 20, 2001, 9:46:50 PM9/20/01
to
Hi

I would like to reserve a chunk of memory in a vector, and reuse that
memory each time a function is called. I thought I could do that with
the code below, but while capacity1 == 40, capacity2 == 0. This means
that I need to call reserve() after each call to clear(), with the
accompanying performance hit (from the call to malloc).

Is there any way to clear the contents of the vector without
deallocating the reserved memory?

BTW the implementation of the STL I am using is Microsoft's XBox
implementation.

Thanks

Matt


------------------

void foo()
{
static std::vector <MyVectorClass> positions;
static bool first = true;

if(first)
{
first = false;
positions.reserve(40);
}

int capacity1 = positions.capacity();

positions.clear();

int capacity2 = positions.capacity();
}

------------------

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]

Bruce G. Stewart

unread,
Sep 22, 2001, 11:44:08 PM9/22/01
to
Matt Blackler wrote:
>
> Hi
>
> I would like to reserve a chunk of memory in a vector, and reuse that
> memory each time a function is called. I thought I could do that with
> the code below, but while capacity1 == 40, capacity2 == 0. This means
> that I need to call reserve() after each call to clear(), with the
> accompanying performance hit (from the call to malloc).
>
> Is there any way to clear the contents of the vector without
> deallocating the reserved memory?

> void foo()
> {
> static std::vector <MyVectorClass> positions;
> static bool first = true;
>
> if(first)
> {
> first = false;
> positions.reserve(40);
> }
>
> int capacity1 = positions.capacity();
>
> positions.clear();

probably better alternative to my previous posting:

positions.resize (0);

Peter Dimov

unread,
Sep 22, 2001, 11:45:04 PM9/22/01
to
themig...@hotmail.com (Matt Blackler) wrote in message
news:<b6b26eec.01092...@posting.google.com>...

> I would like to reserve a chunk of memory in a vector, and reuse that
> memory each time a function is called. I thought I could do that with
> the code below, but while capacity1 == 40, capacity2 == 0. This means
> that I need to call reserve() after each call to clear(), with the
> accompanying performance hit (from the call to malloc).
>
> Is there any way to clear the contents of the vector without
> deallocating the reserved memory?
>
> BTW the implementation of the STL I am using is Microsoft's XBox
> implementation.

v.erase(v.begin(), v.end()) seems to do what you want under Dinkumware
3.0x (which is the XBox STL AFAIK.)

Strictly speaking v.clear() should be equivalent to the above; I don't
know why it deallocates in this implementation (or whether this is
conforming.)

--
Peter Dimov
Multi Media Ltd.

Frank Foerster

unread,
Sep 22, 2001, 11:47:43 PM9/22/01
to
On 20 Sep 2001 21:46:50 -0400, themig...@hotmail.com (Matt

Blackler) wrote:
>I would like to reserve a chunk of memory in a vector, and reuse that
>memory each time a function is called. I thought I could do that with
>the code below, but while capacity1 == 40, capacity2 == 0. This means
>that I need to call reserve() after each call to clear(), with the
>accompanying performance hit (from the call to malloc).
>
>Is there any way to clear the contents of the vector without
>deallocating the reserved memory?
>
>BTW the implementation of the STL I am using is Microsoft's XBox
>implementation.
>
>Thanks
>
>Matt
>
>
>------------------
>
>void foo()
>{
> static std::vector <MyVectorClass> positions;
> static bool first = true;
>
> if(first)
> {
> first = false;
> positions.reserve(40);
> }
>
> int capacity1 = positions.capacity();
>
> positions.clear();
>
> int capacity2 = positions.capacity();
>}

This is strange. On GCC on Linux as well as VC++ the following code :


#include <vector>
#include <iostream>

int main()
{


std::vector<double> dvec( 500 );
std::cout << dvec.capacity() << std::endl;

dvec.resize( 2720 );
std::cout << dvec.capacity() << std::endl;

dvec.clear();
std::cout << dvec.capacity() << std::endl;

dvec.resize( 3450 );
std::cout << dvec.capacity() << std::endl;

dvec.resize( 0 );
std::cout << dvec.capacity() << std::endl;

return 0;

}

yields this:

500
2720
2720
3450
3450


I am not 100% sure, but i think the capacity handling is left to the
implementer of the library and not standards defined. What puzzles me
is, that obviously the compiler you are using handles it differently
from the VC++ compiler. Even if i use a Class instead of a native
type, like this:

class CTestClass
{
public:
virtual ~CTestClass()
{}

int i;
double d;
char c;
};

it works.


Frank

Sean Kelly

unread,
Sep 23, 2001, 12:28:31 AM9/23/01
to
themig...@hotmail.com (Matt Blackler) wrote in message
news:<b6b26eec.01092...@posting.google.com>...
> Hi
>
> I would like to reserve a chunk of memory in a vector, and reuse that
> memory each time a function is called. I thought I could do that with
> the code below, but while capacity1 == 40, capacity2 == 0. This means
> that I need to call reserve() after each call to clear(), with the
> accompanying performance hit (from the call to malloc).
>
> Is there any way to clear the contents of the vector without
> deallocating the reserved memory?

Since the standard doesn't really mention much (if anything) about
memory behavior, this is largely implementation-specific. Indeed, the
clause describing vector::erase states that the destructors for all
the involved objects are invoked but doesn't say anything one way or
the other about underlying memory.

I decided to write a custom allocator to see what the vector
implementation I'm using (Dinkum 3.08) does, and apparently it behaves
the same as yours (in fact, my guess would be that the XBox dev kit
ships with the Dinkum STL also, since it ships with Visual Studio).

The most straightforward solution I can suggest would be to write your
own allocator that manages memory a bit differently. Keep an internal
list of memory blocks and re-use them when possible, destroying them
all in the destructor of your allocator or whenever else you think is
appropriate.

I'm including the allocator test code I wrote as a starting point.
It's basically copied and pasted directly from the Dinkumware STL
documentation with bits filled in from Josuttis' "The Standard C++
Library."

///////////////////////////////////////////////////////////////////////

#include <vector>
#include <limits>
#include <iostream>

template<class T>
class debug_alloc
{
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;

template<class U>
struct rebind
{
typedef debug_alloc<U> other;
};

pointer address( reference val ) const
{
return( &value );
}

const_pointer address( const_reference val ) const
{
return( &value );
}

debug_alloc()
{

}

template<class U>
debug_alloc( const debug_alloc<U>& rhs )
{

}

template<class U>
debug_alloc& operator=( const debug_alloc<U>& rhs )
{

}

size_type max_size() const
{
return( std::numeric_limits<size_type>::max() / sizeof( T ) );
}

template<class U>
pointer allocate( size_type count, const U* hint = 0 )
{
std::cout << "alloc " << count << '\n';
return( static_cast<pointer>( ::operator new( count * sizeof(
T ) ) ) );
}

void deallocate( pointer ptr, size_type count )
{
std::cout << "dealloc " << count << '\n';
::operator delete( static_cast<void*>( ptr ) );
}

void construct( pointer ptr, const T& val )
{
new( static_cast<void*>( ptr ) ) T( val );
}

void destroy( pointer ptr )
{
ptr->~T();
}
};

template<class T1, class T2>
bool operator==( const debug_alloc<T1>&, const debug_alloc<T2>& )
{
return( true );
}

template<class T1, class T2>
bool operator!=( const debug_alloc<T1>&, const debug_alloc<T2>& )
{
return( false );
}

int main( int argc, char **argv )
{
std::vector<int,debug_alloc<int> > vec;

vec.reserve( 5 );
std::cout << "capacity: " << vec.capacity() << '\n';
for( int i = 0; i < 5; ++i )
vec.push_back( i );
vec.clear();
std::cout << "capacity: " << vec.capacity() << '\n';
vec.reserve( 5 );
std::cout << "capacity: " << vec.capacity() << '\n';
return( 0 );

Gabriel Becedillas

unread,
Sep 23, 2001, 5:54:59 AM9/23/01
to
themig...@hotmail.com (Matt Blackler) wrote in message news:<b6b26eec.010920
0529.3...@posting.google.com>...

> Hi
>
> I would like to reserve a chunk of memory in a vector, and reuse that
> memory each time a function is called. I thought I could do that with
> the code below, but while capacity1 == 40, capacity2 == 0. This means
> that I need to call reserve() after each call to clear(), with the
> accompanying performance hit (from the call to malloc).

I've tested your example and I always get capacity1 == capacity2 ==
40.
In the documentation I've read, it says that when you call clear(), no
reallocation ocucurs.

Raoul Gough

unread,
Sep 23, 2001, 6:50:49 AM9/23/01
to
"Matt Blackler" <themig...@hotmail.com> wrote in message
news:b6b26eec.01092...@posting.google.com...

> Hi
>
> I would like to reserve a chunk of memory in a vector, and reuse that
> memory each time a function is called. I thought I could do that with
> the code below, but while capacity1 == 40, capacity2 == 0. This means
> that I need to call reserve() after each call to clear(), with the
> accompanying performance hit (from the call to malloc).
>
> Is there any way to clear the contents of the vector without
> deallocating the reserved memory?
>
> BTW the implementation of the STL I am using is Microsoft's XBox
> implementation.
>
> Thanks
>
> Matt
>
>
> ------------------
>
> void foo()
> {
> static std::vector <MyVectorClass> positions;
> static bool first = true;
>
> if(first)
> {
> first = false;
> positions.reserve(40);
> }
>
> int capacity1 = positions.capacity();
>
> positions.clear();
>
> int capacity2 = positions.capacity();
> }
>
> ------------------

The way I read the standard, the vector is only required to have a size() of
zero after the clear, so the standard does not require the vector to release
it's memory, setting capacity() back to zero. The standard also doesn't seem
to require that the vector *not* release the memory, either. [I'm referring
to sections 23.1.1, 23.2.4.2 and .3]. I don't see why their implementation
deallocates the memory though, because you could always force it to with
swap() if you really wanted this effect.

You could try replacing the v.clear() with v.erase (v.begin(), v.end()), or
v.resize(0) and see if that affects the behaviour. Otherwise, I guess you
can't do much about it. Is the cost of the memory allocation/deallocation
that significant? Have you profiled the code to see how much difference it
makes?

Regards,
Raoul Gough.

--
Don't bother trying the deja return address. You could try the same username
"at" knuut.de or via Hotmail if I've moved home address.

S.K.Mody

unread,
Sep 23, 2001, 7:53:47 AM9/23/01
to
"Matt Blackler" <themig...@hotmail.com> wrote in message
news:b6b26eec.01092...@posting.google.com...
> Hi
>
> I would like to reserve a chunk of memory in a vector, and reuse that
> memory each time a function is called. I thought I could do that with
> the code below, but while capacity1 == 40, capacity2 == 0. This means
> that I need to call reserve() after each call to clear(), with the
> accompanying performance hit (from the call to malloc).
>
[cut]

> void foo()
> {
> static std::vector <MyVectorClass> positions;
> static bool first = true;
>
> if(first)
> {
> first = false;
> positions.reserve(40);
> }
>
> int capacity1 = positions.capacity();
>
> positions.clear();
>
> int capacity2 = positions.capacity();
> }
>

The clear() doesn't do anything since there are no elements
in the vector. clear() simply erases any elements from begin()
to end() and should not change the capacity of the vector.
So there is no reason why capacity1 should not be equal to
capacity2.

Some others have mentioned that the standard says nothing about
this, but the behaviour doesn't seem to make sense. After all the
whole point of reserve() is to ensure that you don't have to reallocate
memory whenever the size changes.

In any case I am guessing that in your case the implementation
only changes the numerical value returned by capacity() and doesn't
actually deallocate the memory. So I don't think that you are losing
any efficiency. Have you stepped through the code in a debugger to
check what happens?

Regards,
S.K.Mody.

Carlos Moreno

unread,
Sep 23, 2001, 9:52:23 PM9/23/01
to

"S.K.Mody" wrote:
>
> but the behaviour doesn't seem to make sense. After all the
> whole point of reserve() is to ensure that you don't have to reallocate
> memory whenever the size changes.

I don't think this argument makes any sense. Yes, the whole point
of reserve is that; but you could argue that the whole point of
clear is to truly clear the state (i.e., as in send the state back
to exactly the same after instantiation with default parameters).
So, if you clear after you called reserve, well, you're choosing
what you need when...

Your argument seems similar to this [exaggerated] example:

int a;

a = 2;

cout << a << endl;

a = -1;

cout << a << endl;


Would you argue that it doesn't make sense that the second cout
prints -1 because the whole point of the statement a = 2 is that
the value of a is 2 afterwards? (yes, it's an exaggerated
example, but your argument is similar to this)

Anyway, I'm not saying that clear should or should not bring
capacity back to zero, because I'm not sure. I'm just auto-
replying to your argument that the behaviour does not make
sense...

Carlos
--

Marc Butler

unread,
Sep 23, 2001, 9:58:13 PM9/23/01
to
On 20 Sep 2001 21:46:50 -0400, themig...@hotmail.com (Matt
Blackler) wrote:

>Hi
[snip]


>BTW the implementation of the STL I am using is Microsoft's XBox
>implementation.

[snip]


>void foo()
>{
> static std::vector <MyVectorClass> positions;
> static bool first = true;
>
> if(first)
> {
> first = false;
> positions.reserve(40);
> }
>
> int capacity1 = positions.capacity();
>
> positions.clear();
>
> int capacity2 = positions.capacity();
>}

Using the STLport STL implemenation (www.stlport.org) and MS VC++ 6.0
I'm seeing the behaviour you desire. Namely: capacity1 == 40 and
capacity2 == 40.

Thus you might want to try using STLport rather than the native
implementation.

Marc

Hendrik Schober

unread,
Sep 24, 2001, 8:04:06 PM9/24/01
to
"Marc Butler" <marcb...@acm.org> wrote:
> [...]

> Thus you might want to try using STLport rather than the native
> implementation.

I second that. There's numerous reasons. It
simplified our daily work considerably.

> Marc

Schobi

--
Spam...@gmx.de is never read
I'm hschober at gmx dot de

John Potter

unread,
Sep 24, 2001, 11:17:38 PM9/24/01
to
On 20 Sep 2001 21:46:50 -0400, themig...@hotmail.com (Matt Blackler)
wrote:

> Hi


>
> I would like to reserve a chunk of memory in a vector, and reuse that
> memory each time a function is called. I thought I could do that with
> the code below, but while capacity1 == 40, capacity2 == 0. This means
> that I need to call reserve() after each call to clear(), with the
> accompanying performance hit (from the call to malloc).

See 23.2.4.2/5. It is guaranteed that no reallocation will take place
during insertions until the size exceeds the value in the reserve call.

It seems that your implementation is non-conforming. It either
reallocates or gives an incorrect value from capacity.

John

Matt Blackler

unread,
Sep 25, 2001, 10:06:07 AM9/25/01
to
pdi...@mmltd.net (Peter Dimov) wrote
> themig...@hotmail.com (Matt Blackler) wrote
> > I would like to reserve a chunk of memory in a vector, and reuse that
> > memory each time a function is called. I thought I could do that with
> > the code below, but while capacity1 == 40, capacity2 == 0. This means
> > that I need to call reserve() after each call to clear(), with the
> > accompanying performance hit (from the call to malloc).
> >
> > Is there any way to clear the contents of the vector without
> > deallocating the reserved memory?
> >
> > BTW the implementation of the STL I am using is Microsoft's XBox
> > implementation.
>
> v.erase(v.begin(), v.end()) seems to do what you want under Dinkumware
> 3.0x (which is the XBox STL AFAIK.)
>
> Strictly speaking v.clear() should be equivalent to the above; I don't
> know why it deallocates in this implementation (or whether this is
> conforming.)


Hi

Thanks for all the replies. I was a little surprised to hear that this
behaviour seems to be conforming (from Raoul Gough), I thought it
would not be.

However, since posting the original problem, I discovered that in the
example below vectorSize comes out at 40, and if I push_back() after
this it adds the new elements starting at the 40th element in the
vector.

So I believe that the implementation of the STL for the XBox is
nonconforming, even if the behaviour in the original example I posted
is not. I'll email the XBox support team about it.

Thanks again

Matt



-----------

std::vector <MyVectorClass> myVector;

myVector.reserve(40);

int vectorSize = myVector.size();

-----------

Carl Daniel

unread,
Sep 25, 2001, 10:24:13 AM9/25/01
to

"Marc Butler" <marcb...@acm.org> wrote in message
news:3bae016f.62900906@news...

> On 20 Sep 2001 21:46:50 -0400, themig...@hotmail.com (Matt
> Blackler) wrote:
[snip]

>
> Using the STLport STL implemenation (www.stlport.org) and MS VC++ 6.0
> I'm seeing the behaviour you desire. Namely: capacity1 == 40 and
> capacity2 == 40.
>
> Thus you might want to try using STLport rather than the native
> implementation.
>

Actually, that'd be a bad idea. 23.1.1 (table 67 - Sequence Requirements)
states the requirements for clear(): erase(begin(),end()); post: size()==0.

Notice that there's no mention of capacity(). That lack of mention means
it's _not_specified_ what clear() does with regard to capacity. An
implementation which sets capacity to 0 is just as conforming as one which
doubles it (or leaves it unchanged).

Rather than choose an STL implementation which happens to implement what you
want, better to re-write the code to depend only on what the standard
guarantees.

-cd

Dave Harris

unread,
Sep 25, 2001, 3:42:59 PM9/25/01
to
themig...@hotmail.com (Matt Blackler) wrote (abridged):

> Is there any way to clear the contents of the vector without
> deallocating the reserved memory?

When this has been discussed before, the consensus was that clear() should
not reduce capacity. This is based on $23.2.4.2:

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

Which does not say anything about clear() or erase() being allowed to make
a difference. It sounds as though Microsoft's XBox implementation is not
conforming.

The only way to reduce capacity is swap(). Even that is not really
specified, but it seems to have emerged as a de facto standard.


> the accompanying performance hit

Just for the record, it matters for correctness as well as performance,
because it affects when iterators may be invalidated. I would regard
non-conformance here as a serious bug.

Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."

Raoul Gough

unread,
Sep 25, 2001, 3:49:59 PM9/25/01
to
"John Potter" <jpo...@falcon.lhup.edu> wrote in message
news:3baef630...@news.csrlink.net...
[cut]

>
> See 23.2.4.2/5. It is guaranteed that no reallocation will take place
> during insertions until the size exceeds the value in the reserve call.
>
> It seems that your implementation is non-conforming. It either
> reallocates or gives an incorrect value from capacity.
>
> John

I don't see how this applies to a call to clear(). If it had said, "no
reallocation will ever take place *except* during insertions and only when
the size exceeds the value in the reserve call" I would see the relevance.
Or is this what the standardese actually translates as?

Josuttis also states that "the capacity of vectors never shrinks" and
provides a work around using swap() to shrink capacity while maintaining the
contents of a vector. I'm not sure what he bases this on.

After thinking about it, I can see an argument for clear() actually
deallocating memory, even though vector<T>().swap (v) would be a work around
if it didn't. Note that erase() is allowed to invalidate all iterators that
refer to the erased or later items, which in this case allows the
implementation to invalidate all iterator references to the entire vector.

Regards,
Raoul Gough.

--
Don't bother trying the deja return address. You could try the same username
"at" knuut.de or via Hotmail if I've moved home address.

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

S.K.Mody

unread,
Sep 25, 2001, 3:50:54 PM9/25/01
to
"Carlos Moreno" <mor...@mochima.com> wrote in message
news:3BADF55F...@mochima.com...

>
> "S.K.Mody" wrote:
> >
> > but the behaviour doesn't seem to make sense. After all the
> > whole point of reserve() is to ensure that you don't have to reallocate
> > memory whenever the size changes.
>
> I don't think this argument makes any sense. Yes, the whole point
> of reserve is that; but you could argue that the whole point of
> clear is to truly clear the state (i.e., as in send the state back
> to exactly the same after instantiation with default parameters).
> So, if you clear after you called reserve, well, you're choosing
> what you need when...

Look at it this way. clear() is supposed to be equivalent to
erase(begin(), end()).

Now erase(begin(), end()) should not do anything fundamentally
different from say erase(begin()+1, end()) or from erase(begin()+5, end())
or even from erase(begin(), begin()+1). But the behaviour reported
by the OP violates this expectation. Would you agree that the latter
calls should not change the capacity? You could have code depending
on a parameter that calls any one of the above depending on the
value of the parameter. Why should one of these calls behave differently
just because the size goes to zero? erase() should do just what it says
-ie : erase _elements_ from the vector, and not make assumptions as
to why the user wanted to erase.

> Your argument seems similar to this [exaggerated] example:
>
> int a;
>
> a = 2;
>
> cout << a << endl;
>
> a = -1;
>
> cout << a << endl;
>

> Would you argue that it doesn't make sense that the second cout
> prints -1 because the whole point of the statement a = 2 is that
> the value of a is 2 afterwards? (yes, it's an exaggerated
> example, but your argument is similar to this)
>

No, what you have done here is analogous to:-

vect.reserve(20);

//use vector.

vect.reserve(40);

which is perfectly reasonable. So your example does little
to justify your critisism.

Regards,
S.K.Mody.

[cut]

Anthony Williams

unread,
Sep 25, 2001, 5:03:52 PM9/25/01
to
"Carl Daniel" <cpda...@nospam.pacbell.net> wrote in message
news:7mHr7.202$Tq4.49...@newssvr13.news.prodigy.com...

>
> "Marc Butler" <marcb...@acm.org> wrote in message
> news:3bae016f.62900906@news...
> > On 20 Sep 2001 21:46:50 -0400, themig...@hotmail.com (Matt
> > Blackler) wrote:
> [snip]
> >
> > Using the STLport STL implemenation (www.stlport.org) and MS VC++ 6.0
> > I'm seeing the behaviour you desire. Namely: capacity1 == 40 and
> > capacity2 == 40.
> >
> > Thus you might want to try using STLport rather than the native
> > implementation.
> >
>
> Actually, that'd be a bad idea. 23.1.1 (table 67 - Sequence Requirements)
> states the requirements for clear(): erase(begin(),end()); post:
size()==0.
>
> Notice that there's no mention of capacity(). That lack of mention means
> it's _not_specified_ what clear() does with regard to capacity. An
> implementation which sets capacity to 0 is just as conforming as one which
> doubles it (or leaves it unchanged).

Capacity is not mentioned because it is unchanged.

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

std::vector<int> v;
v.reserve(40); // capacity is now 40
// no reallocations here
for(unsigned i=0;i<40;++i)
v.push_back(i);

// capacity and size are now 40
v.clear(); // size is zero, capacity is still 40

// the following insertions are guaranteed not to cause reallocations,
// since the size of the vector is still not greater than the size specified
// in the previous call to reserve.
for(unsigned i=0;i<40;++i)
v.push_back(i);

> Rather than choose an STL implementation which happens to implement what
you
> want, better to re-write the code to depend only on what the standard
> guarantees.

Good advice in general, but it doesn't apply in this case - it is better to
choose an STL implementation that provides what the standard guarantees than
one which doesn't :)

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer

Dave Harris

unread,
Sep 25, 2001, 7:04:51 PM9/25/01
to
Raoul...@my-deja.com (Raoul Gough) wrote (abridged):

> Note that erase() is allowed to invalidate all iterators
> that refer to the erased or later items, which in this case allows the
> implementation to invalidate all iterator references to the entire
> vector.

Agreed. However, we can find more complex examples where the MS XBox
implementation would invalidate iterators it shouldn't. Eg:

std::vector<int> vec;
vec.reserve( 100 );
vec.clear();
vec.push_back( 0 );
std::vector<int>::iterator i = vec.begin();
vec.push_back( 0 );
*i = 2;

If clear() is allowed to affect capacity(), then the last line has
undefined behaviour, otherwise it is well-defined.

Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

Carl Daniel

unread,
Sep 25, 2001, 7:09:02 PM9/25/01
to

"Anthony Williams" <ant...@nortelnetworks.com> wrote in message
news:9oq6dg$e8fpb$1...@ID-49767.news.dfncis.de...

> "Carl Daniel" <cpda...@nospam.pacbell.net> wrote in message
> news:7mHr7.202$Tq4.49...@newssvr13.news.prodigy.com...
> >
> > "Marc Butler" <marcb...@acm.org> wrote in message
> > news:3bae016f.62900906@news...
> > > On 20 Sep 2001 21:46:50 -0400, themig...@hotmail.com (Matt
> > > Blackler) wrote:
[snip]
> >
> > Notice that there's no mention of capacity(). That lack of mention
means
> > it's _not_specified_ what clear() does with regard to capacity. An
> > implementation which sets capacity to 0 is just as conforming as one
which
> > doubles it (or leaves it unchanged).
>
> Capacity is not mentioned because it is unchanged.
>
> 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()."
>

I'm not sure about that...

The reallocation in question is occurring during a call to clear(), not an
insertion, and I don't see anything in 23.2.4 which mentions the effect of
clear() on capacity(). It would appear that some STL implementors have
taken 23.2.4.2(5) at its strongest possible meaning: that no sequence of
calls to insert and any other std::vector member functions other than
reserve will cause reallocation unless the insert would cause size() > than
capacity(), while other implementors have taken the more literal meaning: a
sequence of inserts won't cause reallocation, but if other functions (like
clear()) are mixed with the inserts, all bets are off.

Given the way 23.2.4.2(5) is worded, I'd be inclined to side with you -
clear() shouldn't reallocate the memory. I'm not convinced that the
standard forbids clear() from reallocating the memory.

-cd

Raoul Gough

unread,
Sep 25, 2001, 7:12:13 PM9/25/01
to
"Dave Harris" <bran...@cix.co.uk> wrote in message
news:memo.20010924...@brangdon.madasafish.com...

> themig...@hotmail.com (Matt Blackler) wrote (abridged):
> > Is there any way to clear the contents of the vector without
> > deallocating the reserved memory?
>
> When this has been discussed before, the consensus was that clear() should
> not reduce capacity. This is based on $23.2.4.2:
>
> 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().
>
> Which does not say anything about clear() or erase() being allowed to make
> a difference. It sounds as though Microsoft's XBox implementation is not
> conforming.

Finally I get it. I hadn't thought about what happens /after/ the call to
clear()

v.reserve (20);
v.clear(); // Invalidates all references, but...
v.insert (v.begin(), 20, T()); // Must not reallocate

My apologies to John Potter for doubting his word.
Raoul Gough.

>
> The only way to reduce capacity is swap(). Even that is not really
> specified, but it seems to have emerged as a de facto standard.
>
>
> > the accompanying performance hit
>
> Just for the record, it matters for correctness as well as performance,
> because it affects when iterators may be invalidated. I would regard
> non-conformance here as a serious bug.
>

--


Don't bother trying the deja return address. You could try the same username
"at" knuut.de or via Hotmail if I've moved home address.

Carlos Moreno

unread,
Sep 25, 2001, 10:31:55 PM9/25/01
to

"S.K.Mody" wrote:
>
> Look at it this way. clear() is supposed to be equivalent to
> erase(begin(), end()).

Errr... I disagree on this. That is like saying that empty()
is equivalent to size() == 0.

empty() is a very particular thing, as opposed to the more
general size() facility. And even though the "observable"
behaviour of both expressions is equivalent, the internal
details and implementation may be radically different (in
fact, it *should* be radically different at least for the
list container).

Though clear() and erase(begin(), end()) are equivalent
concerning observable behaviour, I've never thought of
capacity() as part of the observable state of a container
(yes, I understand that, being a public member function,
that makes it part of the observable state -- but given
that you have (in general) no complete control over
capacity(), not even with reserve(), I prefer to see
it as an internal implementation detail to which client
code has the privilege of sneakpeeking at).

So, my argument holds: clear() *could* be defined as
a method that brings the internal state of the container
to that of a newly-instantiated and empty container,
and that would still break no rules or requirements.

I repeat that I'm not saying that capacity() *should*
be zero after a call to clear(), because I am (still)
not sure about it -- after reading through this thread,
I'm under the impression that it is not specified, and
that most implementations actually do not bring capacity
back to zero. I'm only arguing that it would be possible
and pretty reasonable that clear() could do it.

> No, what you have done here is analogous to:-
>
> vect.reserve(20);
>
> //use vector.
>
> vect.reserve(40);
>
> which is perfectly reasonable. So your example does little
> to justify your critisism.

I'm sorry that my mesage sounded like criticism... I
didn't intend it that way. I used an exaggerated example
because it was trivial and illustrated the point... It's
probably just the way that you phrased your comment that
made me disagree -- it sounded to me like you were not
acknowledging the possibility that what you do now
(e.g., reserving a certain capacity) may be changed at
a later time.

It's true that the key detail was different: capacity
is in general *never* reduced -- only increased. But I
was trying to argue that since clear() is a *very*
specific, almost drastic, thing to do (as opposed to
the more general resize() or erase() facilities), I
wouldn't be surprised that there was an exception to
the rule that capacity is not decreased...

I apologize for my message sounding too much like
criticism... I'll have to learn to watch my keyboard!
:-)

Cheers,

Carlos
--

Carlos Moreno

unread,
Sep 26, 2001, 12:24:16 AM9/26/01
to

Anthony Williams wrote:
>
> Capacity is not mentioned because it is unchanged.
>
> 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()."

I don't see how the quoted text says or even suggests that the
capacity is unchanged after a call to clear. That the capacity
is not changed after a call to insert does not tell me anything
about what happens to capacity after a call to clear.

That it seems to be standard practice that capacity never
shrinks (except after a call to container::swap), that's a
different issue, and maybe the one thing that would support
your argument. If you quote from the standard something that
explicitly say that the capacity of a vector *never* shrinks,
then that would be a completely different story...

Carlos
--

James Dennett

unread,
Sep 26, 2001, 7:51:50 AM9/26/01
to
Carl Daniel wrote:
> "Anthony Williams" <ant...@nortelnetworks.com> wrote in message
> news:9oq6dg$e8fpb$1...@ID-49767.news.dfncis.de...
>
>>"Carl Daniel" <cpda...@nospam.pacbell.net> wrote in message
>>news:7mHr7.202$Tq4.49...@newssvr13.news.prodigy.com...
>>
>>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()."
>>
>
> I'm not sure about that...
>
> The reallocation in question is occurring during a call to clear(),
> not an insertion, and I don't see anything in 23.2.4 which mentions
> the effect of clear() on capacity(). It would appear that some STL
> implementors have taken 23.2.4.2(5) at its strongest possible meaning: >
that no sequence of
> calls to insert and any other std::vector member functions other than
> reserve will cause reallocation unless the insert would cause size() > than
> capacity(), while other implementors have taken the more literal meaning: a
> sequence of inserts won't cause reallocation, but if other functions (like
> clear()) are mixed with the inserts, all bets are off.

I don't see how the second interpretation is consistent with
the wording.

std::vector<int> x;
x.reserve(1);
x.clear();
x.push_back(1);

The wording says that no reallocation will take place during
the last insertion after the call to reserve(1) until the


time when an insertion would make the size of the vector

greater than 1. In other words, rellocation is not
allowed, as the x.size()==1 after the insertion.

If you don't think the wording bans reallocation in this
case, I'd be interested to hear where you believe this
argument falls down.

-- James Dennett


>
> Given the way 23.2.4.2(5) is worded, I'd be inclined to side with you -
> clear() shouldn't reallocate the memory. I'm not convinced that the
> standard forbids clear() from reallocating the memory.

Anthony Williams

unread,
Sep 26, 2001, 7:52:13 AM9/26/01
to
"Carlos Moreno" <mor...@mochima.com> wrote in message
news:3BB118FE...@mochima.com...

>
> Anthony Williams wrote:
> >
> > Capacity is not mentioned because it is unchanged.
> >
> > 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()."
>
> I don't see how the quoted text says or even suggests that the
> capacity is unchanged after a call to clear. That the capacity
> is not changed after a call to insert does not tell me anything
> about what happens to capacity after a call to clear.

The point is, it doesn't mention clear. Insertions after a reserve() do not
cause reallocations, _irrespective_ of intervening calls (except to
reserve). Thus clear() cannot reduce capacity in case it lies between a
reserve() and an insertion.

> That it seems to be standard practice that capacity never
> shrinks (except after a call to container::swap), that's a
> different issue, and maybe the one thing that would support
> your argument. If you quote from the standard something that
> explicitly say that the capacity of a vector *never* shrinks,
> then that would be a completely different story...

There is plenty of wording that allows the capacity to grow, and none that
allows it to shrink. The only places it could shrink is at clear() and
erase(). erase() preserves iterators _before_ the start of the range erased
=> no shrinkage unless the start of the range is begin(). clear() is
equivalent to erase(begin(),end()).

Thus there is the _possibility_ of shrinkage on vec.clear() and
vec.erase(vec.begin(),someIterator).

However, no reallocation can be done if there is a previous call to reserve
still in effect.

Calls to reserve() lose their effect when inserts are done beyond the
current capacity. Thus the following is permitted to shrink the vector:

std::vector<int> v;

v.reserve(100); // reserve some space

v.resize(v.capacity()+1); // causes reallocation, cancelling the reserve()
v.clear(); // invalidates all iterators, no reserve()d capacity to worry
about, can shrink vector
v.erase(v.begin(),v.begin()); // same applies here, even though no elements
erased.

Thus a shrink-to-fit algorithm can be

unsigned currentSize=v.size();
v.resize(v.capacity()+1); // Cancel effect of reserve()
v.erase(v.begin()+currentSize,v.end()); // remove excess elements
v.erase(v.begin(),v.begin()); // shrink

Obviously, it is implementation-defined whether or not it works, and it may
make things worse (by forcing a reallocation to a larger size initially).

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer

S.K.Mody

unread,
Sep 26, 2001, 6:06:46 PM9/26/01
to
"Carlos Moreno" <mor...@mochima.com> wrote in message
news:3BB0E56F...@mochima.com...

I agree that it would have been reasonable, perhaps even
preferable, for the standard to have defined it that way. ie: if it
had been required that clear() should erase() and then deallocate.
As it stands though, as far as I can comprehend, the standard
implies that it should _not_ deallocate. The following statements
are taken from it:-

1. After reserve(), capacity() is greater or equal to the argument of
reserve if reallocation happens; and equal to the previous value
of capacity().

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

3. clear() - behaves like the function calls erase(begin(), end()).

I interpret the first two to mean that the capacity can only increase.

However, I see your point. It might have been better to let clear()
deallocate the vector as there seems to be no other clean way of
doing so.

[cut]

> I'm sorry that my mesage sounded like criticism... I
> didn't intend it that way. I used an exaggerated example
> because it was trivial and illustrated the point...

[cut]


>
> I apologize for my message sounding too much like
> criticism... I'll have to learn to watch my keyboard!
> :-)
>

On the other hand, it does liven up the newsgroup a bit ;-)
I can't say that I don't enjoy some of the occasional skirmishes
between posters that you get here and on the unmoderated group.
I've never been particularly good at them though (at least not
without a long warm up :->).

Regards,
S.K.Mody.

James Kanze

unread,
Sep 27, 2001, 5:47:56 AM9/27/01
to
Carlos Moreno <mor...@mochima.com> wrote in message
news:<3BB0E56F...@mochima.com>...
> "S.K.Mody" wrote:

> > Look at it this way. clear() is supposed to be equivalent to
> > erase(begin(), end()).

> Errr... I disagree on this. That is like saying that empty() is
> equivalent to size() == 0.

It is, never the less, what the standard says: in table 67, the
semantics of clear() are defined to be erase(begin(), end()).

> empty() is a very particular thing, as opposed to the more general
> size() facility. And even though the "observable" behaviour of both
> expressions is equivalent, the internal details and implementation
> may be radically different (in fact, it *should* be radically
> different at least for the list container).

> Though clear() and erase(begin(), end()) are equivalent concerning
> observable behaviour, I've never thought of capacity() as part of
> the observable state of a container (yes, I understand that, being a
> public member function, that makes it part of the observable state
> -- but given that you have (in general) no complete control over
> capacity(), not even with reserve(), I prefer to see it as an
> internal implementation detail to which client code has the
> privilege of sneakpeeking at).

When an allocation is allowed to take place is a very important part
of the observable behavior of std::vector, since an allocation
invalidates all iterators and references into the vector. IMHO, the
most frequent use of reserve isn't optimization, but to ensure that
iterators and references remain valid.

> So, my argument holds: clear() *could* be defined as a method that
> brings the internal state of the container to that of a
> newly-instantiated and empty container, and that would still break
> no rules or requirements.

It would break the requirement (in the standard) that it have the same
behavior as erase(begin(), end()). The question is, could erase treat
this as a special case, and do something radically different? I'm not
sure myself what the answer is -- erase invalidates all iterators and
references to elements after the point of erase, so erase(begin(),
end()) effectively invalidates all iterators and references.

> I repeat that I'm not saying that capacity() *should* be zero after
> a call to clear(), because I am (still) not sure about it -- after
> reading through this thread, I'm under the impression that it is not
> specified, and that most implementations actually do not bring
> capacity back to zero. I'm only arguing that it would be possible
> and pretty reasonable that clear() could do it.

I think that there is some doubt as to whether clear() is allowed to
change the capacity. Off hand, I think it is illegal, because of the
words "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()." (23.2.4.2/5). I
think that there is an error report concerning this, however, since
taken literally, it and the requirement that swap have constant time
make a conforming implementation impossible. (In all of the
implementations I know, swap may reduce the capacity, and it is
traditionally the mechanism used to ensure that the resulting capacity
is reduced.)

--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique oriente objet
Ziegelhttenweg 17a, 60598 Frankfurt, Germany, Tl.: +49 (0)69 19 86 27

James Kanze

unread,
Sep 27, 2001, 5:51:17 AM9/27/01
to
James Dennett <jden...@acm.org> wrote in message
news:<3BB11C71...@acm.org>...

I think the real key is the validity of iterators and pointers. In
many ways, reallocation is an implementation detail, which happens
behind the back of the user. There is no real way to determine when
it occurs. On the other hand, think that the following code is
guaranteed to work:

std::vector<int> v ;
v.reserve( 100 ) ;
v.clear() ;
v.push_back( 1 ) ;
std::vector<int>::iterator i = v.begin() ;
v.push_back( 2 ) ;
*i = 0 ;

This guarantee pretty much means that clear cannot free up the memory.

(On the other hand, I'm not convinced that anyone was really aware of
this restriction when the actual text was voted.)

--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique oriente objet
Ziegelhttenweg 17a, 60598 Frankfurt, Germany, Tl.: +49 (0)69 19 86 27

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

James Kanze

unread,
Sep 27, 2001, 5:51:57 AM9/27/01
to
bran...@cix.co.uk (Dave Harris) wrote in message
news:<memo.20010924...@brangdon.madasafish.com>...

> themig...@hotmail.com (Matt Blackler) wrote (abridged):
> > Is there any way to clear the contents of the vector without
> > deallocating the reserved memory?

> When this has been discussed before, the consensus was that clear()
> should not reduce capacity. This is based on $23.2.4.2:

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

Which also applies to swap.

> Which does not say anything about clear() or erase() being allowed
> to make a difference. It sounds as though Microsoft's XBox
> implementation is not conforming.

Given that the above passage doesn't make an exception for swap
either, can you show me a conforming implementation. (Remember, to be
conforming, swap also has to execute in constant time.)

> The only way to reduce capacity is swap(). Even that is not really
> specified, but it seems to have emerged as a de facto standard.

Correct. It *seems* *to* *have* *emerged* as a *de* *facto*
standard. It isn't what the standard actually says, it isn't really
written anywhere, and it has only emerged recently, long after the
standard (and probably some actual libraries) were written.

> > the accompanying performance hit

> Just for the record, it matters for correctness as well as
> performance, because it affects when iterators may be invalidated. I
> would regard non-conformance here as a serious bug.

As a practical matter, I would hesitate counting on a de facto
standard which has emerged after some of the major libraries were
written in my code.

If the standards committee actually votes a correction that this is
what was meant, and Microsoft refuses to correct it in a future
release, we might be able to speak of a bug. Until then, I don't
think so.

--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique oriente objet
Ziegelhttenweg 17a, 60598 Frankfurt, Germany, Tl.: +49 (0)69 19 86 27

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

James Kanze

unread,
Sep 27, 2001, 5:52:38 AM9/27/01
to
"Anthony Williams" <ant...@nortelnetworks.com> wrote in message
news:<9os26r$et0du$1...@ID-49767.news.dfncis.de>...

> > Anthony Williams wrote:

I don't think so. Consider:

std::vector< int > v ;
v.reserve( 100 ) ;

I am now guaranteed that *no* insert will invalidate any iterators
unless the capacity exceeds 100, by the quoted passage. So I can now
safely write:

v.clear() ;
v.push_back( 1 ) ;
std::vector< int >::iterator i = v.begin() ;

for ( i = 2 ; i < 100 ; ++ i ) {
v.push_back( i ) ;
}
*i = 0 ;

That seems, in fact, cristal clear, and not open to interpretation.
Except that it is equally clear that what I have just said holds if I
replace the call to clear with :

std::vector<int> empty ;
v.swap( empty ) ;

Except that this makes it impossible to implement swap in constant
time.

So we must consider that there is a contradiction in the standard, and
wait for the committee to resolve it, before we really know what is
required.

> However, no reallocation can be done if there is a previous call to
> reserve still in effect.

> Calls to reserve() lose their effect when inserts are done beyond
> the current capacity.

And *only* when inserts are done beyond the current capacity.
Intervening calls to clear or swap do not affect this guarantee.

--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique oriente objet
Ziegelhttenweg 17a, 60598 Frankfurt, Germany, Tl.: +49 (0)69 19 86 27

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

Carl Daniel

unread,
Sep 27, 2001, 12:44:13 PM9/27/01
to

"James Dennett" <jden...@acm.org> wrote in message
news:3BB11C71...@acm.org...
> Carl Daniel wrote:
> > "Anthony Williams" <ant...@nortelnetworks.com> wrote in message
> > news:9oq6dg$e8fpb$1...@ID-49767.news.dfncis.de...
> >
> >>"Carl Daniel" <cpda...@nospam.pacbell.net> wrote in message
> >>news:7mHr7.202$Tq4.49...@newssvr13.news.prodigy.com...
>
> If you don't think the wording bans reallocation in this
> case, I'd be interested to hear where you believe this
> argument falls down.
>

It depends on what the meaning of is is... ;-) Well, more on what the
meaning of "after" is. Does after mean "after a call to reserve() with no
intervening calls to clear(), erase(), swap(), ..." or does after mean
"after a call to reserve() no matter what intervening calls are made".

Your interpretation would seem to require that swap() also not cause
reallocation on subsequent insert()'s, but that seems incorrect (and
would defeat a common idiom). Note that 23.2.4.2(5) makes no more mention
of swap() than it does of clear().

I'd just like the standard to be a bit more explicit: exactly which
functions can "reset" the guarantee that 23.2.4.2(5) provides? Most
implementations say that only swap() and reserve() have this power. The OPs
implementation adds clear() to that list.

-cd

PS- I notice now that James Kanze has weighed in on this matter - and feels
that swap cannot cause subsequent reallocation, yet this is a common idiom,
is it not?

Carlos Moreno

unread,
Sep 27, 2001, 1:22:50 PM9/27/01
to

"S.K.Mody" wrote:
>
> As it stands though, as far as I can comprehend, the standard
> implies that it should _not_ deallocate. The following statements
> are taken from it:-

I insist that you are drawing conclusions on very shaky grounds.
At least considering the fragments from the standard I've seen
so far in this thread:

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

This seems to imply that the size can not be reduced in any way,
since it mentions the size specified in the most recent call to
reserve. However, swap does indeed reduce the size, and that
*does* contradict the above:

vec.reserve (10);
vec.swap (vector<int>());
vec.push_back (1);
// this insertion does cause a reallocation, even though the
// size does not exceed the size specified in the most recent
// call to reserve -- two lines above

It should be mentioned explicitly that there is an exception, or
else, the paragraph sounds to me like ill-phrased :-)

> 3. clear() - behaves like the function calls erase(begin(), end()).

Does the standard say exactly this?? That would certainly be
*extremely* close to say that clear does not reduce the size
(though I still think it's not very clear -- pun not intended)

> I interpret the first two to mean that the capacity can only increase.

swap decreases the capacity, and though swap is a very special
function, so is operator=, and... well, so is clear!!! (well,
at least it sounds to me that it could be)

> However, I see your point. It might have been better to let clear()
> deallocate the vector as there seems to be no other clean way of
> doing so.

I wasn't exactly proposing that clear() should reduce the
capacity; though now that you mention it yes, if it were up
to me, I would probably include the *requirement* that clear
must reduce capacity to zero -- after all, the most logical
interpretation I can come up with for the behaviour of
clear() is that it should leave the object in the exact
same state as a default newly created object -- erase (beg,
end) sounds like one possible way in which that goal *could*
be achieved.

> [... talking about discussions and criticism ...]


>
> On the other hand, it does liven up the newsgroup a bit ;-)

:-)

Cheers,

Carlos
--

Raoul Gough

unread,
Sep 27, 2001, 2:24:05 PM9/27/01
to
"James Kanze" <ka...@gabi-soft.de> wrote in message
news:d6651fb6.01092...@posting.google.com...

> "Anthony Williams" <ant...@nortelnetworks.com> wrote in message
> news:<9os26r$et0du$1...@ID-49767.news.dfncis.de>...

[cut discussion on why clear() can't change capacity]

> That seems, in fact, cristal clear, and not open to interpretation.
> Except that it is equally clear that what I have just said holds if I
> replace the call to clear with :
>
> std::vector<int> empty ;
> v.swap( empty ) ;
>
> Except that this makes it impossible to implement swap in constant
> time.
>
> So we must consider that there is a contradiction in the standard, and
> wait for the committee to resolve it, before we really know what is
> required.

I just looked at http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-index.html
to see if this is already listed as a library issue. I think the most
relevant issue is (was) number 101, regarding the alleged lack of a means to
reduce the capacity of a deque or vector. It is listed as "Not a defect"
with the following rationale:
"This is not a defect in the Standard. The LWG has considered this issue in
the past and sees no need to change the Standard. Deque has no reserve()
member function. For vector, shrink-to-fit can be expressed in a single line
of code (where v is vector<T>):

vector<T>(v).swap(v); // shrink-to-fit v"


(!)

Well, I guess that must be right. On the other hand, seeing as I wasn't the
only one who didn't understand the full impliciations of 23.2.4.2, point 5,
maybe it would help to have some kind of footnote to explain the effects.

Regards,
Raoul Gough.

P.S. I kept wanting to write "make this clear" and such like, but managed
to restrain myself (until now :-)
[excess quoting deleted -- mod]


--
Don't bother trying the deja return address. You could try the same username
"at" knuut.de or via Hotmail if I've moved home address.

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

Anthony Williams

unread,
Sep 27, 2001, 2:24:48 PM9/27/01
to
"James Kanze" <ka...@gabi-soft.de> wrote in message
news:d6651fb6.01092...@posting.google.com...
> > There is plenty of wording that allows the capacity to grow, and
> > none that allows it to shrink. The only places it could shrink is at
> > clear() and erase(). erase() preserves iterators _before_ the start
> > of the range erased => no shrinkage unless the start of the range is
> > begin(). clear() is equivalent to erase(begin(),end()).
>
> > Thus there is the _possibility_ of shrinkage on vec.clear() and
> > vec.erase(vec.begin(),someIterator).
>
> I don't think so.

As I said, the possibility exists _only_ when the effects of reserve() are
invalidated - i.e. once the size has exceeded the reserved capacity.

> it is equally clear that what I have just said holds if I
> replace the call to clear with :
>
> std::vector<int> empty ;
> v.swap( empty ) ;
>
> Except that this makes it impossible to implement swap in constant
> time.

I always assumed (without checking) that there was wording about swap and
capacity somewhere. I was wrong.

> So we must consider that there is a contradiction in the standard, and
> wait for the committee to resolve it, before we really know what is
> required.

True. There isn't a current issue wrt swap, so I'll raise one. It's related
to issue #329, though

> > However, no reallocation can be done if there is a previous call to
> > reserve still in effect.
>
> > Calls to reserve() lose their effect when inserts are done beyond
> > the current capacity.
>
> And *only* when inserts are done beyond the current capacity.
> Intervening calls to clear or swap do not affect this guarantee.

Agreed.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer

Carlos Moreno

unread,
Sep 27, 2001, 7:29:17 PM9/27/01
to

James Kanze wrote:
>
> Carlos Moreno <mor...@mochima.com> wrote in message
> news:<3BB0E56F...@mochima.com>...
> > "S.K.Mody" wrote:
>
> > > Look at it this way. clear() is supposed to be equivalent to
> > > erase(begin(), end()).
>
> > Errr... I disagree on this. That is like saying that empty() is
> > equivalent to size() == 0.
>
> It is

What is? empty is equivalent to size == 0?? If that's what
you meant, I keep disagreeing -- the observable result of
both operations is the same, but that does not mean that
the operations are equivalent... size() == 0 may take
linear time to compute, whereas empty() always takes
constant time.

> never the less, what the standard says: in table 67, the
> semantics of clear() are defined to be erase(begin(), end()).

A-ha!! That's what I wanted to see. An explicit reference
to the standard saying this... I hadn't seen it in this
thread (only claims to it, but without explicitly saying
that it is taken from the standard)

> > Though clear() and erase(begin(), end()) are equivalent concerning
> > observable behaviour, I've never thought of capacity() as part of
> > the observable state of a container (yes, I understand that, being a
> > public member function, that makes it part of the observable state
> > -- but given that you have (in general) no complete control over
> > capacity(), not even with reserve(), I prefer to see it as an
> > internal implementation detail to which client code has the
> > privilege of sneakpeeking at).
>
> When an allocation is allowed to take place is a very important part
> of the observable behavior of std::vector, since an allocation
> invalidates all iterators and references into the vector. IMHO, the
> most frequent use of reserve isn't optimization, but to ensure that
> iterators and references remain valid.

Agreed. But notice that this argument is irrelevant with clear(),
which does invalidate *every* possible iterator to the container...

> It would break the requirement (in the standard) that it have the same
> behavior as erase(begin(), end()). The question is, could erase treat
> this as a special case, and do something radically different?

*This* was precisely my point. I kind of see clear() as a *very*
special function; it kind of pops-up to my eyes as something
that should truly "reset" the container -- kind of like pressing
the reset button of a computer (as opposed to powering off and
on -- that would be the equivalent to swapping with a newly-
created object :-))

> I'm not
> sure myself what the answer is

There! That was *exactly* my feeling about this topic. I think
we are indeed in complete agreement... Well, not necessarily;
after this discussion, I kind of am inclined to think that
the behaviour of clear *should* indeed be *exactly equivalent*
to vec.swap (vector<T>()). You may or may not share that
opinion with me...

> I think that there is some doubt as to whether clear() is allowed to
> change the capacity. Off hand, I think it is illegal, because of the
> words "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()."

> [...]


> I think that there is an error report concerning this, however, since
> taken literally, it and the requirement that swap have constant time
> make a conforming implementation impossible.

My argument exactly (I'm not sure if my other reply to this already
got to the newsgroup). In any case, as I said in my other message,
swap *is* a very special function... Well, so is operator=, and,
well... so is (might be) clear()!!!

I'll add this to the famous list of inconsistencies for the committe's
people to consider (as per Francis' request :-)).

I find it a horrible hack that to do something so simple and so
straightforward as reducing the capacity to zero (i.s., resetting
the state of the container back to its initial state if it were
instantiated with default parameters), you have to swap with an
on-the-fly-instantiated new container. It's simply horrible
(besides a little bit more inefficient than a hypothetical
clear() that reallocates). An action so simple ought do be
done with a method that describes such simple action. clear()
sounds to me like that perfect candidate (yes, reset() would
also be an appropriate name; but since clear() is already there,
and there would be no severe code breaking -- only efficiency
might potentially be affected, if some already-written code has
been relying on the fact that clear() does not reallocate --,
then I find it a better alternative...)

Any thoughts on this? Notice that I'm no longer arguing about
the current behaviour, or what the current behaviour should be
as specified by the standard -- I'm now looking for what are
your comments and opinions on this potential [slight] change
in the standard...

Cheers,

Carlos
--

Raoul Gough

unread,
Sep 27, 2001, 7:49:50 PM9/27/01
to
"Matt Blackler" <themig...@hotmail.com> wrote in message
news:b6b26eec.01092...@posting.google.com...
[bulk of message cut]

> Is there any way to clear the contents of the vector without
> deallocating the reserved memory?

A trickier question seems to be if it is possible to do anything to a vector
which *does* deallocate the reserved memory (short of destructing the object
:-)

I just tried the assignment operator and was surprised to see that it
doesn't assign the capacity to the target vector (using gcc 2.95.3-4 with
g++, same result with STLport 4.0)

e.g.

vector<int> v1, v2;
v2.reserve (500);
v1 = v2;
assert (v1 == v2); // OK
assert (v1.capacity() == v2.capacity()); // Uh oh...

Now, table 65 of the standard only requires that, after the assignment,
(v1==v2) holds. This makes the first assertion safe, but says nothing about
the second.

On the other hand, swap requires that it's arguments are "assignable", which
means (according to section 23.1, table 64) that t = u makes t "equivalent"
to u. Now, I would have thought that the vector's capacity was part of it's
observable state and should also be assigned, in order to make the vectors
"equivalent":

assert (v2.empty());
v2.reserve (500);
v1 = v2;
v2.insert (v1.begin(), 500, 1); // Must not reallocate
v1.insert (v1.begin(), 500, 1); // May reallocate ?

It also means, of course, that the following code is not functionally the
same as swap (v1, v2):

{
vector<int> temp;
temp = v1;
v1 = v2;
v2 = temp;
}

But when it comes down to it, what does the standard actually say about
swap? I'll quote 25.2.2:

" template<class T> void swap (T& a, T& b);

Requires: Type T is Assignable (23.1)
Effects: Exchanges values stored in two locations."

So that's not so much help in this situation. The only addition to this
requirement made for containers (table 65) is that it should have constant
complexity.

Would it be fair to say that whatever the observable state of a was before
the swap, that b now exhibits this behaviour and vice-versa? I think this
clarifies the issue of swapping capacities, since the requirement of not
reallocating in insert() after a call to reserve() did not disappear, it was
simply relocated to a different variable.

By the way, could we please redefine clear() to be equivalent to the
following?

v.~vector();
new (&v) vector<T>();

Thanks :-)


Regards,
Raoul Gough.

--
Don't bother trying the deja return address. You could try the same username
"at" knuut.de or via Hotmail if I've moved home address.

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

Dave Harris

unread,
Sep 27, 2001, 8:00:10 PM9/27/01
to
ka...@gabi-soft.de (James Kanze) wrote (abridged):

> Correct. It *seems* *to* *have* *emerged* as a *de* *facto*
> standard. It isn't what the standard actually says, it isn't really
> written anywhere, and it has only emerged recently, long after the
> standard (and probably some actual libraries) were written.

We seem to be in complete agreement. I was choosing my words carefully.

Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

John Potter

unread,
Sep 28, 2001, 10:39:45 AM9/28/01
to
On 27 Sep 2001 05:52:38 -0400, ka...@gabi-soft.de (James Kanze) wrote:

> std::vector< int > v ;
> v.reserve( 100 ) ;
>
> I am now guaranteed that *no* insert will invalidate any iterators
> unless the capacity exceeds 100, by the quoted passage. So I can now
> safely write:
>
> v.clear() ;
> v.push_back( 1 ) ;
> std::vector< int >::iterator i = v.begin() ;
> for ( i = 2 ; i < 100 ; ++ i ) {
> v.push_back( i ) ;
> }
> *i = 0 ;
>
> That seems, in fact, cristal clear, and not open to interpretation.
> Except that it is equally clear that what I have just said holds if I
> replace the call to clear with :
>
> std::vector<int> empty ;
> v.swap( empty ) ;
>
> Except that this makes it impossible to implement swap in constant
> time.

I wondered how long it would take to bring the swap nonsense into this.

Vector specializes the algorithm swap(x, y) to x.swap(y). The member
swap is not mentioned because it is covered by container requirements.
Container requirements state that x.swap(y) is swap(x, y). Isn't that
nice? :)

Of course, note A only says that x.swap(y) should (not shall) be
constant time; so, is not a requirement anyway.

> So we must consider that there is a contradiction in the standard, and
> wait for the committee to resolve it, before we really know what is
> required.

Since this is clc++m, lets try common sense. x.swap(y) exchanges
everything about x and y including the reserve guarantees. All
iterators, pointers and references remain valid (23.1.10) (like
list.splice), they just are valid in the other vector. Nobody expects

std::vector<int> x(5, 42);
std::vector<int>::iterator xi(x.begin() + 2);
std::vector<int> y;
swap(x, y);
x.erase(xi);

to do anything other than crash.

Swap is a red herring here.

John

S.K.Mody

unread,
Sep 28, 2001, 10:51:02 AM9/28/01
to
"Carlos Moreno" <mor...@mochima.com> wrote in message
news:3BB265E4...@mochima.com...
>
> "S.K.Mody" wrote:
> >
[cut]

> > 2. 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().
>
> This seems to imply that the size can not be reduced in any way,
> since it mentions the size specified in the most recent call to
> reserve. However, swap does indeed reduce the size, and that
> *does* contradict the above:

> vec.reserve (10);
> vec.swap (vector<int>());
> vec.push_back (1);
> // this insertion does cause a reallocation, even though the
> // size does not exceed the size specified in the most recent
> // call to reserve -- two lines above
>
> It should be mentioned explicitly that there is an exception, or
> else, the paragraph sounds to me like ill-phrased :-)

I does seem like an oversight. It would have worked consistently
if not for the requirement that the implementations be optimized
to give constant time. The optimized implementation swaps the
actual vectors rather than the elements but swap is required to
behave as though the _contents_ have been swapped.

Since it doesn't seem like there is a way to do a constant time
swap of the actual elements, perhaps it would have been more
consistent to define swap simply as swapping the two vectors.

> > 3. clear() - behaves like the function calls erase(begin(), end()).
>
> Does the standard say exactly this?? That would certainly be
> *extremely* close to say that clear does not reduce the size
> (though I still think it's not very clear -- pun not intended)

Actually it is phrased this way in the section on strings, but there
is a table (68) under "sequences" where this equivalence is specified.

[cut]

Regards,
S.K.Mody.

Dave Harris

unread,
Sep 28, 2001, 11:09:56 AM9/28/01
to
mor...@mochima.com (Carlos Moreno) wrote (abridged):

> I find it a horrible hack that to do something so simple and so
> straightforward as reducing the capacity to zero (i.s., resetting
> the state of the container back to its initial state if it were
> instantiated with default parameters), you have to swap with an
> on-the-fly-instantiated new container. It's simply horrible
> (besides a little bit more inefficient than a hypothetical
> clear() that reallocates). An action so simple ought do be
> done with a method that describes such simple action. clear()
> sounds to me like that perfect candidate (yes, reset() would
> also be an appropriate name; but since clear() is already there,
> and there would be no severe code breaking -- only efficiency
> might potentially be affected, if some already-written code has
> been relying on the fact that clear() does not reallocate --,
> then I find it a better alternative...)

It is not just efficiency. Several people (including me) have posted
examples of code that would break if clear() deallocates. The problem
comes with iterators that are created *after* the clear(), which may be
invalidated by subsequent insertions.

That said, I think such code will be very rare in practice. Also, as James
Kanze argues, the reasons for thinking the code is valid are a bit
dubious. The committee apparently did not consciously intend that code to
be valid. So perhaps it is OK to break that code.

Then again, I would see this as a change to the standard which goes beyond
the minimum necessary to resolve its inconsistency. I would suggest
instead:

(1) swap() swaps the capacities.

(2) erase( begin(), end() ) may not reduce capacity.

(3) clear() may not reduce capacity. It remains identical in
semantics to erase( begin(), end() ).

I believe these fix the contradictions in the current standard in the
smallest and safest way. (1) is the only actual change, which is necessary
to make swap() implementable in constant time. All three formalise what I
believe is the de facto practice of most implementations. Something like
this is necessary urgently to correct a defect in the standard.

And then we should consider:

(4) A new function be added to help avoid memory waste.

This is obviously adding a new feature, which makes a different kind of
animal politically, one which cannot be adopted so quickly. It is actually
redundant because (given (1)) we can use swap(). Also it is purely for
optimisation. So it is controversial whether such a new feature should be
added at all. But I agree with you, it should.

Reset() would be a candidate for (4). However, I would prefer a more
general function, perhaps called minimise_capacity(), which can be called
when the vector is not empty and which has no formal effect other than to
invalidate iterators. In other words, more general and purer. It could be
implemented as a no-op, or as:

template <typename T, typename A>
void minimise_capacity( vector<T,A> &v ) {
vector<T,A>( v ).swap( v );
}

Of course I can add this to my personal library today, but I think it is
important and bizarre and unobvious enough to be part of some future
version of the standard.

Also, there can be more efficient implementations if it is part of the
standard. For example, if the allocator uses fixed-sized chunks we may
have v.capacity() > v.size() and yet no way to reduce capacity further. In
that case it would be a waste of time to copy the elements.

Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

S.K.Mody

unread,
Sep 28, 2001, 3:03:37 PM9/28/01
to
> mor...@mochima.com (Carlos Moreno) wrote (abridged):
[cut]

> >clear()
> > sounds to me like that perfect candidate (yes, reset() would
> > also be an appropriate name; but since clear() is already there,
> > and there would be no severe code breaking -- only efficiency
> > might potentially be affected, if some already-written code has
> > been relying on the fact that clear() does not reallocate --,
> > then I find it a better alternative...)

"Dave Harris" <bran...@cix.co.uk> wrote in message
news:memo.20010928...@brangdon.madasafish.com...
[cut]

> (4) A new function be added to help avoid memory waste.
>
> This is obviously adding a new feature, which makes a different kind of
> animal politically, one which cannot be adopted so quickly. It is actually
> redundant because (given (1)) we can use swap(). Also it is purely for
> optimisation. So it is controversial whether such a new feature should be
> added at all. But I agree with you, it should.
>
> Reset() would be a candidate for (4). However, I would prefer a more
> general function, perhaps called minimise_capacity(), which can be called
> when the vector is not empty and which has no formal effect other than to
> invalidate iterators. In other words, more general and purer. It could be
> implemented as a no-op, or as:
>
> template <typename T, typename A>
> void minimise_capacity( vector<T,A> &v ) {
> vector<T,A>( v ).swap( v );
> }
>

A shorter name would be "unreserve()", no arguments (no pun intended),
which suggests reducing capacity to the extent possible without
invalidating existing iterators. So to "reset" a vector one would write:

v.clear(); //erase(v.begin(), v.end())
v.unreserve(); //deallocates because there are no outstanding iterators.

If the meaning of clear() is changed, it would have to be done for
all containers.

Regards,
S.K.Mody.

Carlos Moreno

unread,
Sep 28, 2001, 3:04:43 PM9/28/01
to

Dave Harris wrote:
>
> And then we should consider:
>
> (4) A new function be added to help avoid memory waste.

Yeah, that would be also great. Avoid any possibility of breaking
existing code, but eliminate the need for a horrible hack whenever
we need to shrink the capacity of a vector.

> This is obviously adding a new feature, which makes a different kind of
> animal politically, one which cannot be adopted so quickly. It is actually
> redundant because (given (1)) we can use swap(). Also it is purely for
> optimisation. So it is controversial whether such a new feature should be
> added at all.

This reasoning is more or less why I thought that modifying the
behaviour of clear() would be a better alternative -- I still think
it is a better alternative, although your argument is also solid.
(the reason being that relying on clear() not to reduce the
capacity really is thin ice, so it should be a harmless change)

> But I agree with you, it should.

Exactly. One thing is that a language encourage people to
worry less and less about efficiency and premature optimizations,
and another thing is that the language almost prohibits you
from optimizing or making things efficiently (or that it makes
you go to outrageous lengths to achieve some optimization, for
that matter). It's true that I'm exaggerating a little bit,
in the sense that swapping in the (rare?) occasions where
you need to reduce the capacity is not *that* outrageous...
But still...

> Reset() would be a candidate for (4).

It's true that reset() would sound confusing, given the
presence of clear -- two different methods identified by words
that are almost synonims is not good -- well, not that it hasn't
happened before (list::remove and list::erase).

Carlos
--

Carlos Moreno

unread,
Sep 28, 2001, 4:19:40 PM9/28/01
to

"S.K.Mody" wrote:
>
> A shorter name would be "unreserve()", no arguments (no pun intended)

Intended or not, very subtle, very brilliant! :-)

Carlos
--

Carlos Moreno

unread,
Sep 28, 2001, 6:22:32 PM9/28/01
to

"S.K.Mody" wrote:
>
> A shorter name would be "unreserve()", no arguments (no pun intended),
> which suggests reducing capacity to the extent possible without
> invalidating existing iterators.

There is no way that the container could know about what
iterators are or may be pointing to it. The only thing
that could be known for sure is that no iterators are
valid a a certain time (e.g., right after a clear() or
a reallocation).

If an unreserve() is provided, it would have to invalidate
iterators (i.e., it would have to reallocate); I don't
see any other way to implement it, other than only
working after a clear() or equivalent, or a reallocation
(is that what you meant?)

> If the meaning of clear() is changed, it would have to be done for
> all containers.

At least for the list, that's not a problem -- list::clear
will have the exact same effect (there is no reallocation
notion for the list as a whole)

Carlos
--

Dave Harris

unread,
Sep 28, 2001, 10:10:54 PM9/28/01
to
jpo...@falcon.lhup.edu (John Potter) wrote (abridged):

> Since this is clc++m, lets try common sense. x.swap(y) exchanges
> everything about x and y including the reserve guarantees. All
> iterators, pointers and references remain valid (23.1.10) (like
> list.splice), they just are valid in the other vector.

This would discourage iterators which contain pointers to their
containers, which are one way to implement checked iterators.


> Nobody expects
>
> std::vector<int> x(5, 42);
> std::vector<int>::iterator xi(x.begin() + 2);
> std::vector<int> y;
> swap(x, y);
> x.erase(xi);
>
> to do anything other than crash.

Agreed. But surely we don't expect:

y.erase(xi);

to be well-defined either.

Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

S.K.Mody

unread,
Sep 29, 2001, 6:44:22 AM9/29/01
to
"Carlos Moreno" <mor...@mochima.com> wrote in message
news:3BB4CF70...@mochima.com...

>
> "S.K.Mody" wrote:
> >
> > A shorter name would be "unreserve()", no arguments (no pun intended)
>
> Intended or not, very subtle, very brilliant! :-)

: = )

> > which suggests reducing capacity to the extent possible without
> > invalidating existing iterators.
>
> There is no way that the container could know about what
> iterators are or may be pointing to it. The only thing
> that could be known for sure is that no iterators are
> valid a a certain time (e.g., right after a clear() or
> a reallocation).

> If an unreserve() is provided, it would have to invalidate
> iterators (i.e., it would have to reallocate); I don't
> see any other way to implement it, other than only
> working after a clear() or equivalent, or a reallocation
> (is that what you meant?)

The size is known. What I mean is that unreserve() would be
free to deallocate any memory reserved beyond 'size' for
containers/implementations for which that is meaningful.
For containers for which it is not meaningful or inconvenient
it could just do nothing except when the size is 0. When
the size is 0 this means that it should (be free to) deallocate
all the memory reserved and capacity() should return 0.

Breaking it down into two functions is a more flexible approach,
which also maintains the current semantics and syntactic convenience
of clear(). The only apparent disadvantage is that you have to write
two statements clear() + unreserve(), but you can argue that it is
also less confusing that way.

In any case I think we are more or less saying the same thing,
and this is mainly splitting hairs. Plus my opinions are beginning to
feel distinctly flatulent and underqualified. Let's leave the dirty
work to the standards committee, shall we. >;->

Regards,
S.K.Mody.

Carlos Moreno

unread,
Sep 29, 2001, 6:44:58 AM9/29/01
to

Dave Harris wrote:
>
> jpo...@falcon.lhup.edu (John Potter) wrote (abridged):
> > Since this is clc++m, lets try common sense. x.swap(y) exchanges
> > everything about x and y including the reserve guarantees. All
> > iterators, pointers and references remain valid (23.1.10) (like
> > list.splice), they just are valid in the other vector.
>
> This would discourage iterators which contain pointers to their
> containers

Huh?? How??

Swap exchanges the internal pointers (the pointer to data),
but the pointer *to the vector object* itself can not be
modified -- not by a.swap(b), not by swap(a,b).

I may have misunderstood what you meant? If so, please
explain?

Thanks,

Carlos
--

John Potter

unread,
Sep 29, 2001, 5:03:21 PM9/29/01
to
On 29 Sep 2001 06:44:58 -0400, Carlos Moreno <mor...@mochima.com> wrote:

> Dave Harris wrote:

> > jpo...@falcon.lhup.edu (John Potter) wrote (abridged):
> > > Since this is clc++m, lets try common sense. x.swap(y) exchanges
> > > everything about x and y including the reserve guarantees. All
> > > iterators, pointers and references remain valid (23.1.10) (like
> > > list.splice), they just are valid in the other vector.

> > This would discourage iterators which contain pointers to their
> > containers

> Huh?? How??

> Swap exchanges the internal pointers (the pointer to data),
> but the pointer *to the vector object* itself can not be
> modified -- not by a.swap(b), not by swap(a,b).

In the example which followed, a smart iterator xi would contain a
pointer to x. After the swap(x, y), the smart iterator into a dumb
container would now contain a pointer to x and point into the data
of y. The standard says that xi is still valid after the swap but
this dumb smart iterator doesn't know what happened. If the
container were also smart, the swap member would have updated all of
the iterators into x to be iterators into y. This should discourage
doing half of a job and producing dumb smart iterators.

John

John Potter

unread,
Sep 29, 2001, 5:04:04 PM9/29/01
to
On 28 Sep 2001 22:10:54 -0400, bran...@cix.co.uk (Dave Harris) wrote:

> jpo...@falcon.lhup.edu (John Potter) wrote (abridged):
> > Since this is clc++m, lets try common sense. x.swap(y) exchanges
> > everything about x and y including the reserve guarantees. All
> > iterators, pointers and references remain valid (23.1.10) (like
> > list.splice), they just are valid in the other vector.
>
> This would discourage iterators which contain pointers to their
> containers, which are one way to implement checked iterators.

No, it would encourage doing it right. Smart iterators require smart
containers which know about their iterators. The standard requirements
do not allow doing half of the job.

> > Nobody expects
> >
> > std::vector<int> x(5, 42);
> > std::vector<int>::iterator xi(x.begin() + 2);
> > std::vector<int> y;
> > swap(x, y);
> > x.erase(xi);
> >
> > to do anything other than crash.
>
> Agreed. But surely we don't expect:
>
> y.erase(xi);
>
> to be well-defined either.

Why not? It seems that the standard requires it.

John

Carlos Moreno

unread,
Sep 30, 2001, 4:35:27 AM9/30/01
to

John Potter wrote:
>
> In the example which followed, a smart iterator xi would contain a
> pointer to x. After the swap(x, y), the smart iterator into a dumb
> container would now contain a pointer to x and point into the data
> of y.

Hmmm, I may be being dense, but... How is that iterator smart? :-)

I thought the whole pointer of a smart vector iterator was to *only*
keep a pointer to the container, and an offset with respect to the
first element -- of course, this would only work for random access
iterators, which is fine -- a list doesn't really need smart
iterators (well, at least not as badly as vectors do)

Carlos
--

John Potter

unread,
Sep 30, 2001, 9:07:29 AM9/30/01
to
On 30 Sep 2001 04:35:27 -0400, Carlos Moreno <mor...@mochima.com> wrote:

>
> John Potter wrote:
> >
> > In the example which followed, a smart iterator xi would contain a
> > pointer to x. After the swap(x, y), the smart iterator into a dumb
> > container would now contain a pointer to x and point into the data
> > of y.

> Hmmm, I may be being dense, but... How is that iterator smart? :-)

Beats me. Dumb iterators are smart enough for me. :)

> I thought the whole pointer of a smart vector iterator was to *only*
> keep a pointer to the container, and an offset with respect to the
> first element

Makes no difference, the smart iterator points into y after the swap.
If it contains the address of x, it can't find its iteratee.

How about an example?

void f () {
vector<int> x(5, 42), y;


vector<int>::iterator xi(x.begin() + 2);

int* pi(&*xi);
swap(x, y); // invalidates no pointers, references, or iterators
assert(&*xi == pi);
assert(xi == y.begin() + 2);
}

The asserts pass for dumb iterators. Do they pass for any smart
iterator that you have or are thinking about?

John

Dave Harris

unread,
Sep 30, 2001, 9:08:47 AM9/30/01
to
mor...@mochima.com (Carlos Moreno) wrote (abridged):
> > jpo...@falcon.lhup.edu (John Potter) wrote (abridged):
> > > All iterators [...] remain valid [...], they just are valid in

> > > the other vector.
> >
> > This would discourage iterators which contain pointers to their
> > containers
>
> Huh?? How??
>
> Swap exchanges the internal pointers (the pointer to data),
> but the pointer *to the vector object* itself can not be
> modified -- not by a.swap(b), not by swap(a,b).

Yes - that is my point. So if we have a checked vector iterator
implemented as:

template <typename T>
class vector {
public:
class iterator {
private:
vector<T> *vec;
int index;
public:
iterator<T> &operator++() {
assert( index < vec->size() );
++index;
return *this;
}
T &operator *() {
return vec->at( index );
}
//...
};
//...
};

it is very hard for vector::swap() to make this a valid iterator into
the second container. Eg given:

std::vector<int> x(5, 42);
std::vector<int>::iterator xi(x.begin() + 2);
std::vector<int> y;
swap(x, y);

y.erase( xi ); // Valid?

I read John Potter as suggesting that the last line be valid; that an
iterator for x becomes an iterator for y after x and y are swapped. I am
saying this is expensive to arrange if the iterator keeps a private,
internal pointer to its original container.

I think checked iterators are a good idea. We should try to avoid
defining swap() in a way which makes them harder to write. In my view,
swap() should invalidate all iterators of both vectors.

Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

Carlos Moreno

unread,
Sep 30, 2001, 1:54:08 PM9/30/01
to

John Potter wrote:
>
> > Hmmm, I may be being dense, but... How is that iterator smart? :-)
>
> Beats me. Dumb iterators are smart enough for me. :)

:-)

> > I thought the whole pointer of a smart vector iterator was to *only*
> > keep a pointer to the container, and an offset with respect to the
> > first element
>
> Makes no difference, the smart iterator points into y after the swap.

No it doesn't (you probably misunderstood my "concept" of smart
iterators -- i.e., what I understood as smart iterators).

This is an example of a smart iterator to vector<T> (just off the
top of my head -- plenty of bugs, omissions, oversights, should be
expected):

template <typename T>
class vector
{

// ...

class iterator
{
vector<T> & container;
size_t offset;
public:
iterator (vector<T> & cont, size_t offs)
: container(cont), offset(offs)
{}

T & operator* ()
{
return container[offset];
}

iterator & operator++ ()
{
offset++;
return *this;
}

// ...
};

iterator begin()
{
return iterator (*this, 0);
}

iterator end()
{
return iterator (*this, size());
}

// ...
};


So, when you swap two containers, there is absolutely no problem,
because the iterator points to the container (which hasn't changed
its identity, only its contents), and the iteratee is found by
going through the container first.

Does this clarify? Am I still misunderstanding your message?
Or did you misunderstand mine?

Carlos
--