Runtime complexity of STL Deque

Runtime complexity of STL Deque

Constructors

deque<T> d;	Make an empty deque.	O(1)
deque<T> d(n);	Make a deque with N elements.	O(n)
deque<T> d(n, value);	Make a deque with N elements, initialized to value.	O(n)
deque<T> d(begin, end);	Make a deque and copy the values from begin to end.	O(n)

Accessors

d[i];	Return (or set) the I'th element.	O(1)
d.at(i);	Return (or set) the I'th element, with bounds checking.	O(1)
d.size();	Return current number of elements.	O(1)
d.empty();	Return true if deque is empty.	O(1)
d.begin();	Return random access iterator to start.	O(1)
d.end();	Return random access iterator to end.	O(1)
d.front();	Return the first element.	O(1)
d.back();	Return the last element.	O(1)

Modifiers

d.push_front(value);	Add value to front.	O(1) (amortized)
d.push_back(value);	Add value to end.	O(1) (amortized)
d.insert(iterator, value);	Insert value at the position indexed by iterator.	O(n)
d.pop_front();	Remove value from front.	O(1)
d.pop_back();	Remove value from end.	O(1)
d.erase(iterator);	Erase value indexed by iterator.	O(n)
d.erase(begin, end);	Erase the elements from begin to end.	O(n)