stlab.adobe.com Adobe Systems Incorporated

BackInsertionSequence
[Concepts]

Detailed Description

A Back Insertion Sequence is a Sequence where it is possible to append an element to the end, or to access the last element, in amortized constant time. Back Insertion Sequences have special member functions as a shorthand for those operations.

Refinement Of:
Sequence
Associated Types:
None, except for those of Sequence.
Notation:
X A type that is a model of Back Insertion Sequence
a Object of type X
T The value type of X
t Object of type T
Definitions:
Valid Expressions:
In addition to the expressions defined in Sequence, the following expressions must be valid.
Name Expression Type requirements Return type
Back a.back()   reference if a is mutable, otherwise const_reference.
Push back a.push_back(t) a is mutable. void
Pop back a.pop_back() a is mutable. void
Expression Semantics:
Name Expression Precondition Semantics Postcondition
Back a.back() !a.empty() Equivalent to *(--a.end()).  
Push back a.push_back(t)   Equivalent to a.insert(a.end(), t) a.size is incremented by 1. a.back() is a copy of t.
Pop back a.pop_back() !a.empty() Equivalent to a.erase(--a.end()) a.size() is decremented by 1.
Complexity Guarantees:
Back, push back, and pop back are amortized constant time. [1]
Invariants:
Symmetry of push and pop push_back() followed by pop_back() is a null operation.
Type(s) Modeling this Concept:
  • Vector
  • List
  • Deque
Notes:

[1] This complexity guarantee is the only reason that back(), push_back(), and pop_back() are defined: they provide no additional functionality. Not every sequence must define these operations, but it is guaranteed that they are efficient if they exist at all.

See Also:
Container, Sequence, FrontInsertionSequence, Vector, Deque, List

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google