24 Containers library [containers]

24.2 Requirements [container.requirements]

24.2.1 Preamble [container.requirements.pre]

Containers are objects that store other objects.
They control allocation and deallocation of these objects through constructors, destructors, insert and erase operations.
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.
[Example 1:
The copy constructor of type vector<vector<int>> has linear complexity, even though the complexity of copying each contained vector<int> is itself linear.
— end example]
Allocator-aware containers ([container.alloc.reqmts]) other than basic_­string construct elements using the function allocator_­traits<allocator_­type>​::​rebind_­traits<U>​::​​construct and destroy elements using the function allocator_­traits<allocator_­type>​::​rebind_­traits<U>​::​​destroy ([allocator.traits.members]), where U is either allocator_­type​::​value_­type or an internal type used by the container.
These functions are called only for the container's element type, not for internal types used by the container.
[Note 1:
This means, for example, that a node-based container would need to construct nodes containing aligned buffers and call construct to place the element into the buffer.
— end note]