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)
|
No comments:
Post a Comment