Back Access Container LOGN

Category: containers
Component type: concept


A Back Access Container LOGN is a Forward Container where it is possible to access, pop or destroy the last element in amortized logarithmic time. Back Access Containers LOGN have special member functions as a shorthand for those operations.

A Back Access Container LOGN is the same as a Back Access Container except that the performance requirements have changed to logn time.

Refinement of

Forward Container

Associated types

None, except for those of Forward Container.


X A type that is a model of Back Access Container LOGN
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 Forward Container, the following expressions must be valid.

Name Expression Type requirements Return type
Back a.back()   reference if a is mutable, otherwise const_reference.
Pop back a.pop_back() a is mutable. void
Destroy back a.destroy_back() a is mutable. void

Expression semantics

Name Expression Precondition Semantics Postcondition
Back a.back() !a.empty() Equivalent to *(--a.end()).  
Pop back a.pop_back() !a.empty() Equivalent to a.erase(--a.end()) a.size() is decremented by 1.
Destroy back a.destroy_back() !a.empty() Equivalent to delete *(--a.end()); a.erase(--a.end()); a.size() is decremented by 1.

Complexity guarantees

Back, pop back and destroy back are amortized logn time. [1]



[1] This complexity guarantee is the only reason that back(), pop_back(), and destroy_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, Forward Container, Front Access Container, Front Access Container LOGN, Back Access Container.

 All Classes Files Functions Variables Typedefs