This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++11 status.
Section: 16.4.4.6[allocator.requirements]Status:C++11Submitter: Hans BoehmOpened: 2007-10-11Last modified: 2016-01-28
Priority:Not Prioritized
View otheractive issues in [allocator.requirements].
View all otherissues in [allocator.requirements].
View all issues withC++11 status.
Discussion:
Did LWG recently discuss 16.4.4.6[allocator.requirements]-2, which states that "All the operationson the allocators are expected to be amortized constant time."?
As I think I pointed out earlier, this is currently fiction forallocate() if it has to obtain memory from the OS, and it's unclear tome how to interpret this forconstruct() anddestroy() if they deal withlarge objects. Would it be controversial to officially let these taketime linear in the size of the object, as they already do in real life?
Allocate() more blatantly takes time proportional to the size of theobject if you mix in GC. But it's not really a new problem, and I thinkwe'd be confusing things by leaving the bogus requirements there. Thecurrent requirement onallocate() is generally not important anyway,since it takes O(size) to construct objects in the resulting space.There are real performance issues here, but they're all concerned withthe constants, not the asymptotic complexity.
Proposed resolution:
Change 16.4.4.6[allocator.requirements]/2:
-2- Table 39 describes the requirements on types manipulated throughallocators.
All the operations on the allocators are expected to beamortized constant time.Table 40 describes therequirements on allocator types.