C++ has many simplified data structures that we don’t need to write ourselves, and let’s talk about them. At first, I will write about what they do, what their structure is, and then I think I will write the code for all of them myself and how they work.
Array
About Array. An Array can be thought of as a container that can hold many things.
Currently we only store 1 value in 1 variable, so what if we need to store 2000 variables?
Of course, declaring 2000 different variables is a waste of time.
int a[2000] is a container named a and can hold 2000 numbers. Array first element number is 0 and when accessing that element
Access it as a[INDEX].
For example, let’s consider a problem.
Given N and N integers, find the sum of these N numbers. constraint 1 <= N <= 1000.
#include <iostream>
using namespace std;
int main() {
int n;
int i;
int a[2000];
cin >> n;
for(i = 0; i < n; i++) {
cin >> a[i];
}
int sum = 0;
for(int i = 0; i < n; i++) {
sum += a[i];
}
cout << sum << endl;
return 0;
}
Char array
It means an array of characters. In other words, char a[2000] means that an array named a can hold 2000 characters.
Let’s explain it with an example problem. Given 1 word and print all letters in uppercase(ASCII is written about)
#include <iostream>
#include <string.h>
using namespace std;
int main() {
char a[2000];
cin >> a;
int n, i;
n = strlen(a);
for(i = 0; i < n; i++) {
if(a[i] >= 'a' && a[i] <= 'z' ) {
a[i] -= 32;
}
}
cout << a << endl;
return 0;
}
Vector
A vector can be said to be an array that can change its size. In other words, if we say int a[2000], the array a can contain only 2000 elements. but if we have any size like 247143 elements or 247 elements and we don’t know the exact size, we have to declare a simple array as int a[3000000].
But if we only need to store 247 numbers, the rest are just sitting in memory, useless.
But for vector, declare vector<data_type> v; and it will be empty at first, and we can only fill in the elements we will use. Vector also has many functions that make it easier to use, such as deleting elements and adding elements to desired positions.
push_back(elm)- add element to backsize()- number of elements of vectorerase(v.begin() + index)- deletes the element in indexinsert(v.begin() + index, value)- Adds value to position index.clear()- empty the vector
etc. and the example below shows how to use it
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back( 247 );
cout << v[0] << endl;
v.push_back( 1 );
v.push_back( 2 );
int n = v.size(), i;
for(i = 0; i < n; i++) {
cout << v[i] << " ";
}
cout << endl;
v.erase( v.begin()+1 );
n = v.size();
for(i = 0; i < n; i++) {
cout << v[i] << " ";
}
cout << endl;
v.insert( v.begin()+1, 4 );
n = v.size();
for(i = 0; i < n; i++) {
cout << v[i] << " ";
}
cout << endl;
v.clear();
return 0;
}
String
What is a String? it can be said that it is an array that takes character type values that can change its size. char a[2000] can only contain up to 2000 characters. But if string a; it can change its size. We will talk more about memory later.
It’s also easier than char arrays for operations like appending words and checking whether 2 characters are the same.
If we check whether 2 characters are equal with an array of char type, we check whether each letter at each index is equal.
But for string type, String1 == String2 is enough. And when adding elements behind CharacterString = CharacterString + CharacterString1; For example
string a = ""; // make empty
a = "aBg"; // set value
cout << a[0] << endl; // print first element
#include <string>
#include <iostream>
using namespace std;
int main() {
string a, b, c;
cin >> a;
cin >> b;
// cin >> a >> b; you can simply write like that
int n, m;
n = a.size();
m = b.size();
cout << "Length of the strings ->" << n << " " << m << endl;
c = a + b;
cout << "If we concat ->" << c << endl;
if( a == b ) cout << "Same\n";
else cout << "Different\n";
return 0;
}
Queue
A queue is a type of array that operates on a “first in, first out” principle, similar to a queue XD. We can add elements to it, retrieve the frontmost element, and remove it, all in a single operation. While we could achieve this using a vector, removing the first element would require multiple operations, resulting in slower execution time. Using a queue makes the process easier to implement and write. However, it’s important to note that direct access to the second and third elements of the queue is not possible.
push(elm)- adds the last elementfront()- returns the frontmost elementpop()will remove the frontmost elementsize()- returns the number of elements
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue <int> q;
q.push( 12 );
q.push( 23 );
q.push( -2 );
int k = q.front();
cout << k << endl;
q.pop();
k = q.size();
cout << k << endl;
k = q.front();
cout << k << endl;
return 0;
}
Stack
What is stack is the opposite of Queue or first in first out principle. We can add elements to this array and remove the last element in a single action. However, it is important to note that we cannot directly access elements other than the top element of the stack, such as element 3.
push(elm)- add the element to the toptop()- returns the topmost elementpop()- will remove the topmost elementsize()- returns the number of elements
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack <int> s;
s.push( 12 );
s.push( 23 );
s.push( -2 );
s.push( 0 );
int k = s.top();
cout << k << endl;
s.pop();
k = s.size();
cout << k << endl;
k = s.top();
cout << k << endl;
return 0;
}
Set
A set is a data structure in which elements are stored in order, and operations such as adding and deleting elements take O(log N) time. It also ensures that duplicates are not allowed (unlike a multiset).
All these operation can be done O(Log(N)).
- We can determine the presence of an element in the set with the Log(n) operation, regardless of whether it’s a vector or another structure. However, in order to find the element, we still need to iterate through each element.
lower_bound(elm)- returns the first position greater than or equal to elmupper_bound(elm)- returns the first position that is significantly greater than elmerase(elm)- delete from elm.insert(elm)- add elm
Below is an example code
#include <set>
#include <iostream>
using namespace std;
int main() {
set<int> s;
set<int>::iterator it;
s.insert( 222 );
s.insert( 111 );
for( it = s.begin(); it != s.end(); it++) {
cout << *it << " ";
}
cout << "\n----------------------------------\n";
int n = s.size();
cout << n << endl;
cout << "----------------------------------\n";
s.insert( 111 );
n = s.size();
cout << n << endl;
cout << "----------------------------------\n";
s.insert( 22 );
s.insert( 12 );
for( it = s.begin(); it != s.end(); it++) {
cout << *it << " ";
}
cout << "\n----------------------------------\n";
s.erase( 22 );
for( it = s.begin(); it != s.end(); it++) {
cout << *it << " ";
}
cout << "\n----------------------------------\n";
it = s.lower_bound( 12 );
cout << *it << "\n----------------------------------\n";
it = s.upper_bound( 12 );
cout << *it << "\n----------------------------------\n";
s.erase( it );
for( it = s.begin(); it != s.end(); it++) {
cout << *it << " ";
}
cout << "\n----------------------------------\n";
return 0;
}
Priority Queue
A priority queue is a data structure that stores elements with the highest value at the top, and it can be implemented using a set. The advantage of using a priority queue is that when you need to find the maximum element, it can be done in a single operation. It’s important to note that a priority queue is not inherently sorted; it uses a heap data structure.
push(value)- add value. (add element)pop()- remove the maximum number of elements.top()- returns the maximum element value.size()- element size.empty()- returns 1 if empty, 0 otherwise. (True or False)
// priority_queue
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue <int> pq;
pq.push( 3 );
cout << pq.top() << endl;
cout << "-------------------------------------------\n";
pq.push( 4 );
cout << pq.top() << endl;
cout << "-------------------------------------------\n";
pq.push( 2 );
cout << pq.top() << endl;
cout << "-------------------------------------------\n";
pq.pop();
cout << pq.top() << endl;
cout << "-------------------------------------------\n";
pq.pop();
cout << pq.top() << endl;
cout << "-------------------------------------------\n";
cout << pq.size() << endl;
return 0;
}
Map
What is a Map? It is a type of data structure that allows searching and storing data based on keys.
When using an array, we typically look for elements using indexes or natural numbers.
However, with a map, the key becomes crucial as it allows us to assign our desired data type to it.
In the case of map<int,int> m;, a variable named int type will receive an int type value.
But map<string,int> m; will get the value of the variable named string type int. Instead, there is a pointer that points to it, and it is called an iterator.
#include <iostream>
#include <map>
using namespace std;
int main() {
map<string, int> m;
map<string, int>:: iterator it;
m[ "Luuwan" ] = 1;
m[ "Toms" ] = 22;
for( it = m.begin(); it != m.end(); it++) {
cout << it->first << " " << it->second << endl;
}
cout << "----------------------------------------------------\n";
string st = "";
st = "Luuwan";
m[ st ] += 100;
for( it = m.begin(); it != m.end(); it++) {
cout << it->first << " " << it->second << endl;
}
cout << "----------------------------------------------------\n";
st = "Toms";
cout << m[ st ] << endl;
return 0;
}
Summary
I wrote about some data structures in C++. In the future, I will write about how to use them and how they are written in the background.