From -8577358519208470775 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,c66ceaccc8f25e6b X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 2002-04-08 17:16:02 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!kibo.news.demon.net!news.demon.co.uk!demon!mail2news.demon.co.uk!not-for-mail From: "James Kuyper Jr." Newsgroups: comp.std.c++ Subject: Re: Allocators, standard containers, and assignment Date: Tue, 9 Apr 2002 00:15:48 GMT Organization: Giganews.Com - Premium News Outsourcing Approved: Fergus Henderson , moderator of comp.std.c++ Message-ID: <3CAFB23E.A7A68E71@wizard.net> References: <42aba677.0203291151.ff4f74c@posting.google.com> <3ca4e319$0$20850$724ebb72@reader2.ash.ops.us.uu.net> <42aba677.0204051121.59ee7aca@posting.google.com> <3cae209e$0$19654$4c41069e@reader1.ash.ops.us.uu.net> <3CAE478F.ECDBDB2C@wizard.net> X-Trace: mail2news.demon.co.uk 1018311356 mail2news:19330 mail2news mail2news.demon.co.uk X-Complaints-To: abuse@demon.net X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-Accept-Language: en MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit NNTP-Posting-Date: Sat, 06 Apr 2002 20:32:47 CST X-DMCA-Notifications: http://www.giganews.com/info/dmca.html X-Abuse-Info: Please be sure to forward a copy of ALL headers X-Abuse-Info: Otherwise we will be unable to process your complaint properly Lines: 113 Xref: archiver1.google.com comp.std.c++:10444 xleobx@qmailcomq.com wrote: > > James Kuyper Jr. wrote: > > >> You get to determine what allocation strategy goes with each object. > >> It doesn't change in surprising ways as the result of swaps and > >> assignments. > > > That depends upon what suprises you. I'd be surprised if the allocation > > strategy was NOT swapped or assigned along with the rest of the object. > > int a = 5; // allocation strategy: data segment > void foo() { > int b; // allocation strategy: stack > b = a; > ... > } > > Are you surprized that `b' dies at the end of foo()? I don't think so. > Why should other objects be any different? Allocation strategy is > presumed to be a part of an object's type, not part of an object's state. a and b have the same type, yet different allocation strategies. I think you've chosen a bad example. In any event, you're correct; for the containers defined by the standard, allocation is a part of the object's type. I made a mistake - I normally try to retain the wording of the message I reply to, in order to make it clear what I was referring to. It was Plauger who first said "allocation strategy", and I copied that wording without even thinking about it. However, if swap() were to swap allocator instances along with the rest of the contents of the container, then it would NOT result in a change of allocation strategy. That strategy is determined by the allocator's type, not by the allocator itself. Two containers that use different Allocator types have different container types, and therefore are not required to be able to swap() with each other (that ability could be provided as an extension, with implmentation-defined semantics). Note: it doesn't matter whether containers swaps allocators, if all such instances are equivalent. Therefore, I'm assuming that this discussion is specifically about Allocators with inequivalent instances. It must also be restricted to implementations that choose to implement containers that allow such allocators. Such support is optional, but encouraged, by section 20.1.5p5. That section essentially leaves it entirely up to the implementor what rules apply to such containers, which makes it basically impossible to talk about what is required by the standard. Therefore, I assume we're only talking about what should be requiered, when the standard finally adopts more specific rules for such containers. What does change when swap() exchanges inequivalent allocators along with the rest of the container's contents, is the set of objects that can be deallocated. I think we can safely presume that a container should always be able to deallocate it's own contents. If swap() didn't swap allocators, then whenever two containers had inequivalent allocators, it would have to allocate new memory, and copy over the elements of the other container into that memeory. That would take time proportional to the number of elements, and would invalidate all references, pointers, or iterators to the elements in their old locations. According to table 65, swap() "Should have constant complexity". and and according to 23.1p10, "no swap() function invalidates any references, pointers, or iterators referring to the elements of the containters being swapped." There are ways around this, but the only ones I can thing of require heavy iterators. If swap() does swap allocators, then it can be a constant-time operation, and satisfy 23.1p10, without using heavy pointers. I consider this a very strong argument in favor of swapping the allocators. However, because of 20.1.5p5, I can't actually claim that this is required. As I mentioned earlier, splice() is a different issue - there's no way I can see to meet to complexity requirements on splice() when using inequivalent allocators. But that remains true, whether the allocators are exchanged or kept in place. > > If the allocators were swap()d, along with the rest of the container's > > contents, there'd be no need for reallocation. splice() is the only case > > where reallocation would be needed when using an allocator with > > inequivalent instances. > > Memory management will be a nightmare. Memory pools tend to have limited > lifetime. If the allocators can be swapped or assigned, you hardly can > be sure if there are no references to an allocator whose memory pool > is about to go away, from objects that you have no control over. I'm afraid I don't follow that. I've never seen code that uses allocators with inequivalent instances; support for them is experimental, and I've never seen one of the experiments. When you swap() the contents of two containers, all iterators, pointers, and references to elements of the first container become iterators, pointers, and references to elements of the second container. That's only possible interpretation of the validity requirement - they can't become iterators pointing at the corresponding element of the original container, because the two containers might have different numbers of elements - there might not be a corresponding element, and such iterators/pointers/references could not possibly remain valid. Therefore, any algorithm that uses such iterators, pointers, or references across a swap() between two containers, must either not care about which of the two containers each one points into, or it must keep track of the fact that the container they point into has changed. Therefore, so long as the allocator stored in a given container can deallocate the elements of that container, I don't see why there's be any special problem. --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]