I'm using the special GCC that Apple supplies with Mac OS X 10.4.7 (PowerPC) and XCode 2.4. I just ran a test case with code like: std::deque<int> d; assert( d.max_size() <= d.get_allocator().max_size() ); And it failed. I looked at the definition of deque::max_size and saw that it blindly return size_type(-1). This is actually greater than what the allocator itself returns (hence the error). Then I looked again and saw that std::allocator does the same thing, except that it divides the max value by sizeof(value_type). Is there a legitimate reason for a deque to return a larger max_size than its allocator? Even if so, did you guys consider that, or did you just blindly put in the maximum value? Does the max_size for the standard allocator have the same issues? Can there be some thought put into what std::allocator::max_size() should return? Maybe it can be based on how much memory the program can actually access. Even if you don't do that, all the standard container types/tempates should base their max_size() method on their this->get_allocator().max_size() return value.
And what does the C++ standard say about this case?
(In reply to comment #1) > And what does the C++ standard say about this case? As far as I can see, the standard is very vague about the relationship between the two max_size. About allocator::max_size, it says "the largest value that can meaningfully be passed to X::allocate" and, given that way allocate forwards to the underlying memory allocation facilities, size_type(-1) / sizeof(T) seems certainly conforming. As regards container::max_size, we have the same value for vector - the only one which always allocates a single chunk of memory at a time - and simply size_type(-1) for the other containers. Again, I don't see how those values could be non-conforming to the text in the standard, which only says "size() of the largest possible container". Maybe, as a matter of QoI something more accurate could be returned, basing on non-trivial interactions with the underlying OS, but I don't think we have any hard bug here.
Actually, I think deque could do with a better max_size. Some tests: vector<int> v; v.resize(v.max_size()); Throws bad_alloc. deque<int> v; v.resize(v.max_size()); Bus errors. This is on i686-apple-darwin8, 4.0.1 Apple's build, so might not be the same behaviour as mainline. Still seems like it shouldn't bus error however?
(In reply to comment #3) > Actually, I think deque could do with a better max_size. It's not at all clear to me what we can possibly do in the general case of discontiguous containers. Certainly, we don't want Segmentation faults or bus errors, but that is a largely unrelated issue (I suggest filing a separate PR), which, I bet, in general has to do mostly with proper arithmetic in each individual container. As a matter of fact, the problem with deque is an arithmetic overflow in _M_new_elements_at_front.
The reason I bought this up here, is because I thought (and I could be wrong, sorry) that the overflow was being caused by the fact that we allow the container size to get too big, and if we pull max_size() down to a proper level, then the container should never have to deal with arithmetic overflow. Of course as a QoI issue, we might want good behaviour even if someone tries to resize a container larger than max_size.
(In reply to comment #5) > The reason I bought this up here, is because I thought (and I could be wrong, > sorry) that the overflow was being caused by the fact that we allow the > container size to get too big, and if we pull max_size() down to a proper > level, then the container should never have to deal with arithmetic overflow. In principle, very in principle. Because we are talking here about *discontiguous* memory containers, not about vector. I'm not even sure the semantics of max_size allows (of course doesn't requires) that each time we go down to the machine and interact with the OS in order to try to figure out how much memory it's actually overall available. The last time I discussed a bit this issue with LWG people I seem to remember that the assumed user general expectation was that of *constant* numbers, meaning overall max "time independent" numbers (+ appropriate case-by-case, exceptions, of course). You may want to brought up the issue again...
... and in fact, even for vector, I think we can only reasonably provide a time-independent upper-bound, because in general we cannot know how much memory each element' constructor is going to allocate... No, I'm more and more convinced that we cannot do much for the issue as originally presented, of course the arithmetic in deque must be robustified, it will.
I agree also we can't do any better. On 64 bit systems it will be even harder to give anything sensible.
(In reply to comment #8) > I agree also we can't do any better. On 64 bit systems it will be even harder > to give anything sensible. I'm only wondering whether it would make sense to divide by sizeof(T) also in the other containers beside vector: the upper bound would be somewhat tighter and still correct, AFAICS. What do you think?
(In reply to comment #9) > I'm only wondering whether it would make sense to divide by sizeof(T) also in > the other containers beside vector: the upper bound would be somewhat tighter > and still correct, AFAICS. What do you think? Even better, it can be used the max_size of an allocator of value_type. That seems a very safe upper bound and probably the consistency with allocator will make submitter happy ;)
Subject: Bug 29134 Author: paolo Date: Thu Sep 21 00:11:52 2006 New Revision: 117099 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117099 Log: 2006-09-20 Paolo Carlini <pcarlini@suse.de> PR libstdc++/29134 * include/bits/stl_list.h (list<>::max_size): Forward to allocator' max_size. * include/bits/stl_vector.h (vector<>::max_size): Likewise. * include/bits/stl_deque.h (deque<>::max_size): Likewise. * include/bits/stl_tree.h (_Rb_tree<>::max_size): Likewise. * include/tr1/hashtable (_Hashtable<>::max_size): Likewise. * testsuite/23_containers/vector/capacity/29134.cc: Add. * testsuite/23_containers/deque/capacity/29134.cc: Likewise. * testsuite/23_containers/list/capacity/29134.cc: Likewise. * testsuite/23_containers/set/capacity/29134.cc: Likewise. * testsuite/23_containers/map/capacity/29134.cc: Likewise. * testsuite/23_containers/multiset/capacity/29134.cc: Likewise. * testsuite/23_containers/multimap/capacity/29134.cc: Likewise. * testsuite/tr1/6_containers/unordered/capacity/29134-set.cc: Likewise. * testsuite/tr1/6_containers/unordered/capacity/29134-map.cc: Likewise. * testsuite/tr1/6_containers/unordered/capacity/29134-multiset.cc: Likewise. * testsuite/tr1/6_containers/unordered/capacity/29134-multimap.cc: Likewise. * include/bits/deque.tcc (deque<>::_M_new_elements_at_front, deque<>::_M_new_elements_at_back): Check for length errors. * testsuite/23_containers/deque/capacity/29134-2.cc: New. * testsuite/23_containers/vector/capacity/29134-2.cc: Likewise. * include/tr1/hashtable (_Hashtable<>::_M_get_Value_allocator): Add. (_Hashtable<>::_M_allocate_node, _M_deallocate_node): Use it. * testsuite/tr1/6_containers/unordered/instantiate/set.cc: Add test. * testsuite/tr1/6_containers/unordered/instantiate/map.cc: Likewise. * testsuite/tr1/6_containers/unordered/instantiate/multiset.cc: Likewise. * testsuite/tr1/6_containers/unordered/instantiate/multimap.cc: Likewise. Added: trunk/libstdc++-v3/testsuite/23_containers/deque/capacity/ trunk/libstdc++-v3/testsuite/23_containers/deque/capacity/29134-2.cc trunk/libstdc++-v3/testsuite/23_containers/deque/capacity/29134.cc trunk/libstdc++-v3/testsuite/23_containers/list/capacity/29134.cc trunk/libstdc++-v3/testsuite/23_containers/map/capacity/ trunk/libstdc++-v3/testsuite/23_containers/map/capacity/29134.cc trunk/libstdc++-v3/testsuite/23_containers/multimap/capacity/ trunk/libstdc++-v3/testsuite/23_containers/multimap/capacity/29134.cc trunk/libstdc++-v3/testsuite/23_containers/multiset/capacity/ trunk/libstdc++-v3/testsuite/23_containers/multiset/capacity/29134.cc trunk/libstdc++-v3/testsuite/23_containers/set/capacity/ trunk/libstdc++-v3/testsuite/23_containers/set/capacity/29134.cc trunk/libstdc++-v3/testsuite/23_containers/vector/capacity/29134-2.cc trunk/libstdc++-v3/testsuite/23_containers/vector/capacity/29134.cc trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/capacity/ trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/capacity/29134-map.cc trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/capacity/29134-multimap.cc trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/capacity/29134-multiset.cc trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/capacity/29134-set.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/deque.tcc trunk/libstdc++-v3/include/bits/stl_deque.h trunk/libstdc++-v3/include/bits/stl_list.h trunk/libstdc++-v3/include/bits/stl_tree.h trunk/libstdc++-v3/include/bits/stl_vector.h trunk/libstdc++-v3/include/tr1/hashtable trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/map.cc trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multimap.cc trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multiset.cc trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/set.cc
Fixed for 4.2.0.
I like this solution a lot. NICE! It seems as if everything is now consistent except for std::string. Any thoughts on that one? -benjamin
(In reply to comment #13) > I like this solution a lot. NICE! > > It seems as if everything is now consistent except for std::string. Any > thoughts on that one? basic_string is delicate, from many different points of view, as we know well, and, at minimum, the current design cannot use the entire the full allocator' max_size. Let's not fiddle with it. I will think about ext/vstring...
Ok, seems sane enough. Just curious about the omission.
(In reply to comment #15) > Ok, seems sane enough. Just curious about the omission. I'm going to adjust vstring first. Hopefully we can back port something to basic_string, but really seems tricky (_S_max_size is static, exported, blah...)
Subject: Bug 29134 Author: paolo Date: Thu Sep 21 10:34:48 2006 New Revision: 117109 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117109 Log: 2006-09-21 Paolo Carlini <pcarlini@suse.de> PR libstdc++/29134 (ext/vstring bits) * include/ext/sso_string_base.h (__sso_string_base<>::_S_max_size): Remove. (__sso_string_base<>::_M_max_size): Use allocator' max_size. (__sso_string_base<>::_M_create): Adjust. * include/ext/vstring.h: Minor comment tweak. * testsuite/ext/vstring/capacity/29134.cc: New. Added: trunk/libstdc++-v3/testsuite/ext/vstring/capacity/ trunk/libstdc++-v3/testsuite/ext/vstring/capacity/29134.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/ext/sso_string_base.h trunk/libstdc++-v3/include/ext/vstring.h
Subject: Bug 29134 Author: paolo Date: Fri Sep 22 17:51:01 2006 New Revision: 117148 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117148 Log: 2006-09-22 Paolo Carlini <pcarlini@suse.de> PR libstdc++/29134 (vector<bool> bits) * include/bits/stl_bvector.h (vector<bool>::max_size): Use allocator' max_size. * testsuite/23_containers/vector/bool/capacity/29134.cc: New. * testsuite/23_containers/deque/capacity/29134-2.cc: Minor tweak. * testsuite/23_containers/vector/capacity/29134-2.cc: Likewise. Added: trunk/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/stl_bvector.h trunk/libstdc++-v3/testsuite/23_containers/deque/capacity/29134-2.cc trunk/libstdc++-v3/testsuite/23_containers/vector/capacity/29134-2.cc