STL Complexity

str.md

vector/string

insert

• push_back: O(1)
• emplace_back: O(n)

acess: O(1)

erase

• back: O(1)
• other: O(n)

find

• sorted: O(log n)
• other: O(n)

deque

insert

• back/front: O(1)
• other: O(n)

access: O(1)

erase

• back/front: O(1)
• other: O(n)

find

• sorted: O(log n)
• other: O(n)

priority_queue:

insert: O(log n)

access: O(1)

erase: O(log n)

find:

list/forward_list

insert

• back/front: O(1)
• with iterator: O(1)
• index: O(n)

access:

• back/front: O(1)
• with iterator: O(1)
• index: O(n)

erase

• back/front: O(1)
• other: O(n)

find: O(n)

set/map

insert: O(log n)

access:

erase: O(log n)

find: O(log n)

unordered_set/unordered_map

insert: O(1) or O(n)

access: O(1) or O(n)

erase: O(1) or O(n)

find: O(1) or O(n)

string

find_first_of: O(nm)