This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD status.

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

Section: 24.3.8.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 24.3.8 [deque]:

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

Add new signatures to 24.3.8.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 24.3.8.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.