Runtime complexity of STL Set and Multiset

Runtime complexity of STL Set and Multiset

Set and Multiset

Sets store objects and automatically keep them sorted and quick to find. In a set, there is only one copy of each objects. multisets are declared and used the same as sets but allow duplicate elements.
Anything stored in a set has to have a comparison predicate. This will default to whatever operator<() has been defined for the item you're storing. Alternatively, you can specify a predicate to use when constructing the set.

Header

#include <set>

Constructors

set< type, compare > s;	Make an empty set. compare should be a binary predicate for ordering the set. It's optional and will default to a function that uses operator<.	O(1)
set< type, compare > s(begin, end);	Make a set and copy the values from begin to end.	O(n log n)

Accessors

s.find(key)	Return an iterator pointing to an occurrence of key in s, or s.end() if key is not in s.	O(log n)
s.lower_bound(key)	Return an iterator pointing to the first occurrence of an item in s not less than key, or s.end() if no such item is found.	O(log n)
s.upper_bound(key)	Return an iterator pointing to the first occurrence of an item greater than key in s, or s.end() if no such item is found.	O(log n)
s.equal_range(key)	Returns pair<lower_bound(key), upper_bound(key)>.	O(log n)
s.count(key)	Returns the number of items equal to key in s.	O(log n)
s.size();	Return current number of elements.	O(1)
s.empty();	Return true if set is empty.	O(1)
s.begin()	Return an iterator pointing to the first element.	O(1)
s.end()	Return an iterator pointing one past the last element.	O(1)

Modifiers

s.insert(iterator, key)	Inserts key into s. iterator is taken as a "hint" but key will go in the correct position no matter what. Returns an iterator pointing to where key went.	O(log n)
s.insert(key)	Inserts key into s and returns a pair<iterator, bool>, where iterator is where key went and bool is true if key was actually inserted, i.e., was not already in the set.	O(log n)