Szerkesztő:LinguisticMystic/cpp/AdvancedDataStructures

🔑 1. Maps: Associative Key-Value Storage

Overview

• A std::map is an associative container that stores elements formed by key-value pairs.
• Keys are unique, and elements are automatically sorted by key using the < operator by default.
• Backed by self-balancing binary search trees (usually Red-Black trees).

Syntax

std::map<KeyType, ValueType> mapName;

Example

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> studentAges;
    studentAges["Maria"] = 29;
    studentAges["Adam"] = 25;
    studentAges["David"] = 27;

    std::cout << "David's age: " << studentAges["David"];
    return 0;
}

Output

David's age: 27

Operations

Operation	Description
[]	Insert or access by key (creates default if absent)
.at(key)	Access by key, throws exception if key doesn’t exist
.find(key)	Returns iterator to key or .end() if not found
.insert({k, v})	Adds new key-value pair (if key doesn’t exist)
.erase(key)	Removes entry by key

Use When:

• You need fast lookup by unique keys (O(log n) complexity).
• You need sorted keys.
• You want to associate data with labels or IDs.

---

📚 2. Stacks: Last-In-First-Out (LIFO)

Overview

• A std::stack is a container adaptor that allows elements to be accessed in LIFO order.
• Useful for scenarios like function call tracking, backtracking, or undo mechanisms.

Syntax

std::stack<DataType> stackName;

Example

std::stack<int> myStack;
myStack.push(10);
myStack.push(20);
int top = myStack.top();  // returns 20
myStack.pop();            // removes 20

Key Operations

Operation	Description
push(val)	Add to the top of the stack
pop()	Remove from the top
top()	Access the top element
empty()	Check if stack is empty
size()	Number of elements

Use When:

• You need reversibility or last-added tracking.
• Great for DFS, recursion simulations, etc.

---

📨 3. Queues: First-In-First-Out (FIFO)

Overview

• A std::queue is a container adaptor for FIFO operations.
• Useful in task scheduling, breadth-first search (BFS), and job queues.

Syntax

std::queue<DataType> queueName;

Example

std::queue<std::string> myQueue;
myQueue.push("apple");
myQueue.push("banana");
std::string front = myQueue.front(); // "apple"
myQueue.pop();                       // removes "apple"

Key Operations

Operation	Description
push(val)	Add to the back of the queue
pop()	Remove from the front
front()	Access front element
back()	Access rear element
empty()	Check if queue is empty

Use When:

• Tasks must be processed in order.
• Suitable for producer-consumer problems, BFS, etc.

---

🔢 4. Sets: Unique, Sorted Collections

Overview

• A std::set stores unique elements in sorted order.
• Like a std::map with only keys and no values.
• Internally implemented as a balanced binary search tree.

Syntax

std::set<DataType> setName;

Example

#include <iostream>
#include <set>

int main() {
    std::set<int> uniqueNumbers;
    uniqueNumbers.insert(1);
    uniqueNumbers.insert(5);
    uniqueNumbers.insert(1); // duplicate, ignored

    for (int num : uniqueNumbers)
        std::cout << num << " ";
}

Output

1 5

Key Operations

Operation	Description
insert(val)	Adds a new element
erase(val)	Removes element
find(val)	Returns iterator to element or .end()
count(val)	Returns 0 or 1 (since all elements are unique)
size()	Number of elements

Use When:

• You need to store unique elements.
• You want automatic sorting.
• Useful in mathematical set operations (union, intersection).

---

📊 Time Complexity Summary

Container	Insert/Delete	Search	Access by Index
map	O(log n)	O(log n)	Not supported
set	O(log n)	O(log n)	Not supported
stack	O(1)	N/A	O(1) to top
queue	O(1)	N/A	O(1) to front

---

🧠 When to Use What?

Problem Type	Best STL Container
Need to map IDs to values	std::map
Track undo/redo, backtracking	std::stack
Schedule tasks in arrival order	std::queue
Maintain a sorted set of values	std::set
Ensure uniqueness automatically	std::set
Fast key-value lookups	std::map

---

✅ Conclusion

Understanding and using these STL containers properly will:

• Improve code performance.
• Increase clarity and readability.
• Save development time by using robust, tested implementations.

STL containers like map, stack, queue, and set are not only building blocks but also powerful tools to solve real-world problems efficiently.