855. capacity() and reserve() for deque?

Section: 23.3.5.3 [deque.capacity] Status: NAD Submitter: Hervé Brönnimann Opened: 2008-06-11 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [deque.capacity].

View all issues with NAD status.

Discussion:

The main point is that capacity can be viewed as a mechanism to guarantee the validity of iterators when only push_back/pop_back operations are used. For vector, this goes with reallocation. For deque, this is a bit more subtle: capacity() of a deque may shrink, whereas that of vector doesn't. In a circular buffer impl. of the map, as Howard did, there is very similar notion of capacity: as long as size() is less than B * (total size of the map - 2), it is guaranteed that no iterator is invalidated after any number of push_front/back and pop_front/back operations. But this does not hold for other implementations.

Still, I believe, capacity() can be defined by size() + how many push_front/back minus pop_front/back that can be performed before terators are invalidated. In a classical impl., capacity() = size() + the min distance to either "physical" end of the deque (i.e., counting the empty space in the last block plus all the blocks until the end of the map of block pointers). In Howard's circular buffer impl., capacity() = B * (total size of the map - 2) still works with this definition, even though the guarantee could be made stronger.

A simple picture of a deque:

A-----|----|-----|---F+|++++|++B--|-----|-----Z

(A,Z mark the beginning/end, | the block boundaries, F=front, B=back, and - are uninitialized, + are initialized) In that picture: capacity = size() + min(dist(A,F),dist(B,Z)) = min (dist(A,B),dist(F,Z)).

Reserve(n) can grow the map of pointers and add possibly a number of empty blocks to it, in order to guarantee that the next n-size() push_back/push_front operations will not invalidate iterators, and also will not allocate (i.e. cannot throw). The second guarantee is not essential and can be left as a QoI. I know well enough existing implementations of deque (sgi/stl, roguewave, stlport, and dinkumware) to know that either can be implemented with no change to the existing class layout and code, and only a few modifications if blocks are pre-allocated (instead of always allocating a new block, check if the next entry in the map of block pointers is not zero).

Due to the difference with vector, wording is crucial. Here's a proposed wording to make things concrete; I tried to be reasonably careful but please double-check me:

[ San Francisco: ]

Hans: should the Returns clause for capacity read "1 Returns: A lower bound..." rather than "1 Returns: An upper bound..."

Howard: maybe what's needed is capacity_front and capacity_back. In fact, I think I implemented a deque that had these members as implementation details.

Proposed resolution:

Add new signatures to synopsis in 23.3.5 [deque]:

size_type capacity() const;
bool reserve(size_type n);

Add new signatures to 23.3.5.3 [deque.capacity]:

size_type capacity() const;

1 Returns: An upper bound on n + max(n_f - m_f, n_b - m_b) such that, for any sequence of n_f push_front, m_f pop_front, n_b push_back, and m_b pop_back operations, interleaved in any order, starting with the current deque of size n, the deque does not invalidate any of its iterators except to the erased elements.

2 Remarks: Unlike a vector's capacity, the capacity of a deque can decrease after a sequence of insertions at both ends, even if none of the operations caused the deque to invalidate any of its iterators except to the erased elements.

bool reserve(size_type n);

2 Effects: A directive that informs a deque of a planned sequence of push_front, pop_front, push_back, and pop_back operations, so that it can manage iterator invalidation accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if this operation returns true; and equal to the previous value of capacity() otherwise. If an exception is thrown, there are no effects.

3 Returns: true if iterators are invalidated as a result of this operation, and false otherwise.

4 Complexity: It does not change the size of the sequence and takes at most linear time in n.

5 Throws: length_error if n > max_size().

6 Remarks: It is guaranteed that no invalidation takes place during a sequence of insert or erase operations at either end that happens after a call to reserve() except to the erased elements, until the time when an insertion would make max(n_f-m_f, n_b-m_b) larger than capacity(), where n_f is the number of push_front, m_f of pop_front, n_b of push_back, and m_b of pop_back operations since the call to reserve().

7 An implementation is free to pre-allocate buffers so as to offer the additional guarantee that no exception will be thrown during such a sequence other than by the element constructors.

And 23.3.5.4 [deque.modifiers] para 1, can be enhanced:

1 Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, unless provisions have been made with reserve, but has no effect on the validity of references to elements of the deque.

Rationale:

Complication outweighs the benefit.