WikiGalaxy
C++ Data Structures & STL: Introduction
Overview:
C++ Standard Template Library (STL) is a powerful set of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures like vectors, lists, queues, and stacks.
Importance:
STL allows developers to use common data structures and algorithms without having to implement them from scratch. This leads to faster development times and more reliable code.
Vectors in C++
Definition:
Vectors are sequence containers representing arrays that can change in size. They use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements.
Usage:
Vectors are preferred over arrays when the size of the data is not known in advance or when the data may need to grow or shrink dynamically.
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers;
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
for (int i = 0; i < numbers.size(); ++i) {
std::cout << numbers[i] << " ";
}
return 0;
}
Console Output:
10 20 30
Lists in C++
Definition:
A list is a sequence container that allows non-contiguous memory allocation. As compared to vectors, lists allow fast insertions and deletions from anywhere in the sequence.
Usage:
Lists are preferred when frequent insertion and deletion of elements are required, especially in the middle of the sequence.
#include <iostream>
#include <list>
int main() {
std::list<int> numbers;
numbers.push_back(10);
numbers.push_back(20);
numbers.push_front(5);
for (auto it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}
Console Output:
5 10 20
Queues in C++
Definition:
A queue is a data structure that follows the FIFO (First In First Out) principle. Elements are inserted at the back and removed from the front.
Usage:
Queues are used in scenarios where order needs to be preserved, such as task scheduling and handling requests in a server.
#include <iostream>
#include <queue>
int main() {
std::queue<int> q;
q.push(5);
q.push(10);
q.push(15);
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
return 0;
}
Console Output:
5 10 15
Stacks in C++
Definition:
A stack is a data structure that follows the LIFO (Last In First Out) principle. Elements are added and removed from the top of the stack.
Usage:
Stacks are used in scenarios such as expression evaluation, backtracking algorithms, and function call management.
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
std::cout << s.top() << " ";
s.pop();
}
return 0;
}
Console Output:
3 2 1
Sets in C++
Definition:
A set is a container that contains unique elements following a specific order. In C++, sets are implemented using binary search trees.
Usage:
Sets are used when you need to store unique elements and frequently check for the presence of an element.
#include <iostream>
#include <set>
int main() {
std::set<int> s;
s.insert(10);
s.insert(20);
s.insert(10); // duplicate, will not be added
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}
Console Output:
10 20
Maps in C++
Definition:
A map is an associative container that stores elements in key-value pairs. Keys are unique, and each key is associated with exactly one value.
Usage:
Maps are used when you need to associate values with keys and retrieve values efficiently based on their keys.
#include <iostream>
#include <map>
int main() {
std::map<std::string, int> ageMap;
ageMap["Alice"] = 25;
ageMap["Bob"] = 30;
for (const auto &pair : ageMap) {
std::cout << pair.first << ": " << pair.second << " ";
}
return 0;
}
Console Output:
Alice: 25 Bob: 30
Unordered Maps in C++
Definition:
Unordered maps are associative containers that store elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys.
Usage:
Unordered maps are used when you need fast access to elements based on keys and do not require elements to be sorted.
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> ageMap;
ageMap["Charlie"] = 35;
ageMap["Dave"] = 40;
for (const auto &pair : ageMap) {
std::cout << pair.first << ": " << pair.second << " ";
}
return 0;
}
Console Output:
Charlie: 35 Dave: 40
Priority Queues in C++
Definition:
A priority queue is a type of container adaptors, specifically designed such that the first element of the queue is the greatest of all elements in the queue and elements are in non-increasing order.
Usage:
Priority queues are used in scenarios where you need to process elements in order of priority, such as in scheduling algorithms.
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
return 0;
}
Console Output:
30 20 10
