Runtime complexity of STL LIST

Runtime complexity of STL LIST

Constructors

list<T> l;	Make an empty list.	O(1)
list<T> l(begin, end);	Make a list and copy the values from begin to end.	O(n)

Accessors

l.size();	Return current number of elements.	O(1)
l.empty();	Return true if list is empty.	O(1)
l.begin();	Return bidirectional iterator to start.	O(1)
l.end();	Return bidirectional iterator to end.	O(1)
l.front();	Return the first element.	O(1)
l.back();	Return the last element.	O(1)

Modifiers

l.push_front(value);	Add value to front.	O(1)
l.push_back(value);	Add value to end.	O(1)
l.insert(iterator, value);	Insert value after position indexed by iterator.	O(1)
l.pop_front();	Remove value from front.	O(1)
l.pop_back();	Remove value from end.	O(1)
l.erase(iterator);	Erase value indexed by iterator.	O(1)
l.erase(begin, end);	Erase the elements from begin to end.	O(1)
l.remove(value);	Remove all occurrences of value.	O(n)
l.remove_if(test);	Remove all element that satisfy test.	O(n)
l.reverse();	Reverse the list.	O(n)
l.sort();	Sort the list.	O(n log n)
l.sort(comparison);	Sort with comparison function.	O(n logn)
l.merge(l2);	Merge sorted lists.	O(n)