Книга: Standard Template Library Programmer
Front Insertion Sequence
Разделы на этой странице:
Front Insertion Sequence
Category: containers
Component type: concept
Description
A Front Insertion Sequence is a Sequence where it is possible to insert an element at the beginning, or to access the first element, in amortized constant time. Front 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 Front Insertion Sequence
a Object of type X
T The value type of X
t Object of type T
Valid expressions
In addition to the expressions defined in Sequence, the following expressions must be valid.
| Name | Expression | Type requirements | Return type |
|---|---|---|---|
| Front | a.front() [1] |
reference if a is mutable, otherwise const_reference. | |
| Push front | a.push_front(t) |
a is mutable. | void |
| Pop front | a.pop_front() |
a is mutable. | void |
Expression semantics
| Name | Expression | Precondition | Semantics | Postcondition |
|---|---|---|---|---|
| Front | a.front() [1] |
!a.empty() | Equivalent to *(a.begin()). | |
| Push front | a.push_front(t) | Equivalent to a.insert(a.begin(), t) a.size is incremented by 1. | a.front() is a copy of t. | |
| Pop front | a.pop_front() |
!a.empty() |
Equivalent to a.erase(a.begin()) | a.size() is decremented by 1. |
Complexity guarantees
Front, push front, and pop front are amortized constant time. [2]
Invariants
| Symmetry of push and pop | push_front() followed by pop_front() is a null operation. |
Models
• list
• deque
Notes
[1] Front is actually defined in Sequence, since it is always possible to implement it in amortized constant time. Its definition is repeated here, along with push front and pop front, in the interest of clarity.
[2] This complexity guarantee is the only reason that front(), push_front(), and pop_front() 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, Back Insertion Sequence, deque, list, slist
Оглавление книги
- Sequence
- Sequences
- Back Insertion Sequence
- front_insert_iterator
- Sequence number
- Escape Sequences
- 3.1.9 Escape Sequences
- Be Paranoid: Call Sequence Checks
- 3.4 Target System Software Initialization Sequence
- Пример применения технологий УДОП, front-end, cross-sell
- Vectors As Sequences
- Sequence Iterating Functions