C++ Data Structures Member Functions and Time Complexity

Data Structure Member Function Description

Array (`std::array`) at(index) Access element at the given index O(1)

Array (`std::array`) size() Returns the number of elements O(1)

Array (`std::array`) fill(value) Fill array with a value O(n)

Vector (`std::vector`) push_back(value) Adds an element to the end O(1) a

Vector (`std::vector`) pop_back() Removes the last element O(1)

Vector (`std::vector`) at(index) Accesses element at the given index O(1)

Vector (`std::vector`) insert(iterator, val) Insert element at a given position O(n)

Vector (`std::vector`) erase(iterator) Erase element from a given position O(n)

Vector (`std::vector`) size() Returns the number of elements O(1)

List (`std::list`) push_front(value) Inserts element at the front O(1)

List (`std::list`) push_back(value) Inserts element at the end O(1)

List (`std::list`) pop_front() Removes the first element O(1)

List (`std::list`) pop_back() Removes the last element O(1)

List (`std::list`) insert(iterator, val) Insert element before specified position O(1)

List (`std::list`) erase(iterator) Remove element at the specified position O(1)

List (`std::list`) size() Returns the number of elements O(1)

Multiset (`std::multiset`) insert(value) Inserts element (allows duplicates, sorted) O(log

Multiset (`std::multiset`) erase(iterator) Removes element at specified position O(log

Multiset (`std::multiset`) find(value) Searches for an element O(log

Multiset (`std::multiset`) size() Returns the number of elements O(1)

Multimap (`std::multimap`) insert({key, value}) Inserts key-value pair (allows duplicate keys, sorted)O(log

Multimap (`std::multimap`) erase(iterator) Removes key-value pair at specified position O(log

Multimap (`std::multimap`) find(key) Searches for an element with the given key O(log

Multimap (`std::multimap`) size() Returns the number of elements O(1)

Unordered Set (`std::unordered_set`) insert(value) Inserts element (unique, unordered) O(1) a

Unordered Set (`std::unordered_set`) erase(iterator) Removes element at specified position O(1) a

Unordered Set (`std::unordered_set`) find(value) Searches for an element O(1) a

Unordered Set (`std::unordered_set`) size() Returns the number of elements O(1)

Unordered Multiset (`std::unordered_multiset`)

insert(value) Inserts element (allows duplicates, unordered) O(1) a

Unordered Multiset (`std::unordered_multiset`)

erase(iterator) Removes element at specified position O(1) a

Unordered Multiset (`std::unordered_multiset`)

find(value) Searches for an element O(1) a

Unordered Multiset (`std::unordered_multiset`)

size() Returns the number of elements O(1)

Unordered Map (`std::unordered_map`)insert({key, value}) Inserts key-value pair (unique, unordered) O(1) a

Unordered Map (`std::unordered_map`)erase(iterator) Removes key-value pair at specified position O(1) a

Unordered Map (`std::unordered_map`)find(key) Searches for an element with the given key O(1) a

Unordered Map (`std::unordered_map`)size() Returns the number of elements O(1)

Unordered Multimap (`std::unordered_multimap`)

insert({key, value}) Inserts key-value pair (allows duplicate keys, unordered)
O(1) a

Unordered Multimap (`std::unordered_multimap`)

erase(iterator) Removes key-value pair at specified position O(1) a

Unordered Multimap (`std::unordered_multimap`)

find(key) Searches for an element with the given key O(1) a

Unordered Multimap (`std::unordered_multimap`)

size() Returns the number of elements O(1)

Stack (`std::stack`) push(value) Inserts element at the top O(1)

Stack (`std::stack`) pop() Removes the top element O(1)

Stack (`std::stack`) top() Accesses the top element O(1)

Stack (`std::stack`) size() Returns the number of elements O(1)

Queue (`std::queue`) push(value) Adds an element to the end O(1)

Queue (`std::queue`) pop() Removes the front element O(1)

Queue (`std::queue`) front() Accesses the front element O(1)

Queue (`std::queue`) back() Accesses the last element O(1)

Queue (`std::queue`) size() Returns the number of elements O(1)

Priority Queue (`std::priority_queue`) push(value) Inserts element into the priority queue O(log

Priority Queue (`std::priority_queue`) pop() Removes the element with the highest priority O(log
Priority Queue (`std::priority_queue`) top() Accesses the element with the highest priority O(1)

Priority Queue (`std::priority_queue`) size() Returns the number of elements O(1)