Data structures which are commonly used in algorithm functions and natively supported in C++
November 21, 2024
1
minutes
What’s on your mind when it comes to data structures provided by C++? Which are high frequently used in algorithm functions?
In this blog, I’d like to summarize those data structures(stack, queue, hash map and priority queue) one-by-one, and how to use them in different scenarios will be talked about in the subsequent blogs.
This table lists the commonly used data structures natively supported by C++. To effectively tackle LeetCode algorithm problems in C++, it’s essential to have a thorough understanding of them.
| Data structures |
C++ Objects |
Common methods |
| string |
std::string |
string str
substr(int startId, int length)
push_back(char)
char pop_back()
char front()
char back()
int size()
int compare(int id1, int id2, string)
————————————–
sort: sort(str.begin(), str.end())
reverse: reverse(str.begin(), str.end())
————————————–
string to int: atoi
int to string: std::to_string(int)
char tolower(char)
char toupper(char)
if a char is a number(0~9):
int isDigit(unsigned char c) |
| vector |
std::vector<T> |
push_back(T)
emplace_back(T)
T front()
T back()
insert(int pos, T val)
operator[]
erase(iterator begin, iterator end)
erase(iterator begin)
reset(int size, T val)
bool empty()
int size() |
| stack |
std::stack<T> |
push(T)
pop()
T top()
bool empty()
int size() |
| queue |
std::queue<T> |
push(T)
pop()
T front()
T back()
bool empty()
int size() |
| |
std::dequeue<T> |
push_back(T)
emplace_back(T)
pop_back()
push_front(T)
pop_front()
T front()
T back()
bool empty()
int size() |
| set |
std::set<T> O(logN) |
insert(T)
int count()
bool empty()
int size()
clear()
erase(T)
Iterator find(T)
Iterator std::next(Iterator)
Iterator std::prev(Iterator) |
| hash map |
std::unordered_map<T1, T2> |
insert({T1 ,T2 })
int count()
operator[]
bool empty()
int size()
clear()
erase(T1) |
| |
std::unordered_set<T> |
insert(T)
int count()
operator[]
bool empty()
int size()
clear()
erase(T) |
| priority queue |
std::priority_queue<T> |
push(T)
pop()
T top()
bool empty()
int size()
—————————————–
Constructor of a max priority queue
auto cmp = [](int x, int y){ return x < y; }
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp)
or
struct cmp{
bool operator()(const int x, const int y) const{
return x < y;
}
}
priority_queue<int, vector<int>, cmp> pq
|
References
cppreference
| Algorithms |