Section: 23.3.5.2 [deque.cons] Status: TC1 Submitter: Herb Sutter Opened: 1999-05-09 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [deque.cons].
View all issues with TC1 status.
Discussion:
In 23.3.5.2 [deque.cons] paragraph 6, the deque ctor that takes an iterator range appears to have complexity requirements which are incorrect, and which contradict the complexity requirements for insert(). I suspect that the text in question, below, was taken from vector:
Complexity: If the iterators first and last are forward iterators, bidirectional iterators, or random access iterators the constructor makes only N calls to the copy constructor, and performs no reallocations, where N is last - first.
The word "reallocations" does not really apply to deque. Further, all of the following appears to be spurious:
It makes at most 2N calls to the copy constructor of T and log N reallocations if they are input iterators.1)
1) The complexity is greater in the case of input iterators because each element must be added individually: it is impossible to determine the distance between first abd last before doing the copying.
This makes perfect sense for vector, but not for deque. Why should deque gain an efficiency advantage from knowing in advance the number of elements to insert?
Proposed resolution:
In 23.3.5.2 [deque.cons] paragraph 6, replace the Complexity description, including the footnote, with the following text (which also corrects the "abd" typo):
Complexity: Makes last - first calls to the copy constructor of T.