From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=ham autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,927ae253da8bb547
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-05-31 09:44:52 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!feed2.news.rcn.net!rcn!nntp.abs.net!uunet!dca.uu.net!ash.uu.net!spool0901.news.uu.net!spool0900.news.uu.net!reader0901.news.uu.net!not-for-mail
Message-ID: <3CF7A88D.3080405@mail.com>
Date: Fri, 31 May 2002 12:45:01 -0400
From: Hyman Rosen <hyrosen@mail.com>
User-Agent: Mozilla/5.0 (Windows; U; WinNT4.0; en-US;
 rv:1.0rc3) Gecko/20020523
X-Accept-Language: en-us, en
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: Re: Specialization
References: <ad56du$pp4$1@wanadoo.fr>
 <4519e058.0205300909.5bfb317d@posting.google.com> <ad5nem$fhb$1@wanadoo.fr>
 <uznyha1d3.fsf@gsfc.nasa.gov> <ad5vj4$euo$1@wanadoo.fr>
 <3CF6CF7D.8000704@worldnet.att.net> <ad72e5$e9c$1@ns.felk.cvut.cz>
 <82347202.0205310608.2f7d634d@posting.google.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Organization: KBC Financial Products
Cache-Post-Path: master.nyc.kbcfp.com!unknown@mosquito.nyc.kbcfp.com
X-Cache: nntpcache 3.0.1 (see http://www.nntpcache.org/)
NNTP-Posting-Host: 204.253.250.10
X-Trace: 1022863491 reader1.ash.ops.us.uu.net 16799 204.253.250.10
Xref: archiver1.google.com comp.lang.ada:25098
Date: 2002-05-31T12:45:01-04:00
List-Id: <comp.lang.ada>

Jim Rogers wrote:
> You got me there. My ignorant message assumed you were correct when you claimed
> that the C++ STL did not need to allocate nodes in its container classes.
> 
> I have since done a little research on the web. I see that the STL container
> classes do indeed allocate objects and copy them. This is clearly documented
> in http://www.sgi.com/tech/stl/alloc.html 
> 
> After reading the above reference I see no significant difference between
> the problems you encountered in Ada and the way the C++ STL is currently
> implemented (regarding node allocation).

Note that for vector, there is not "node allocation". Rather, space
for the entire vector is allocated in one allocation, and the objects
of the vector are built in place in the allocated memory. If the
vector needs to be grown beyond its current capacity, twice as much
memory is allocated, so appending takes constant amortized time. The
elements of a vector are contiguous, just as if they were in an array.

Here's a simplified version of how this looks in C++:

template<typename T> T *make_array(size_t n, const T &prototype)
{
	// allocate uninitialized storage for n T objects
	T *array = static_cast<T *>(::operator new(n * sizeof(T)));
	// construct each array object in place from prototype
	for (size_t i = 0; i < n; ++i)
		new (array + i) T(prototype);
	return array;
}

template<typename T> void destroy_array(size_t n, const T *array)
{
	// destruct each array object in place; storage unaffected
	for (size_t i = 0; i < n; ++i)
		array[i].~T();
	// deallocate storage
	::operator delete(array);
}