Advanced Data Structures
Advanced data structures provide powerful abstractions for solving complex problems efficiently. Understanding iterators, ranges, and specialized data structures is crucial for advanced programming.
STL Iterators
Iterators are objects that point to elements in containers and provide a way to traverse them:
#include <vector>
#include <list>
#include <iterator>
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
// Different iterator types
vector<int>::iterator it = vec.begin();
vector<int>::const_iterator cit = vec.cbegin();
vector<int>::reverse_iterator rit = vec.rbegin();
// Using auto (C++11+)
auto it2 = vec.begin();
// Iterator operations
cout << *it << endl; // Dereference
++it; // Move to next
it += 2; // Advance by 2 (random access)
// Iterator categories
// 1. Input Iterator - read once, forward only
// 2. Output Iterator - write once, forward only
// 3. Forward Iterator - read/write, forward only
// 4. Bidirectional Iterator - read/write, forward and backward
// 5. Random Access Iterator - all operations, jump to any position
return 0;
}
Priority Queues and Heaps
Priority queues maintain elements in order of priority, with the highest priority element at the top:
#include <queue>
#include <vector>
#include <functional>
int main() {
// Max heap (default)
priority_queue<int> maxHeap;
maxHeap.push(10);
maxHeap.push(30);
maxHeap.push(20);
cout << "Max element: " << maxHeap.top() << endl; // 30
maxHeap.pop(); // Remove max element
// Min heap
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
cout << "Min element: " << minHeap.top() << endl; // 10
// Custom comparator for pairs
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first > b.first; // Min heap by first element
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
pq.push({5, 100});
pq.push({1, 200});
pq.push({3, 150});
return 0;
}
Deque (Double-Ended Queue)
Deque allows efficient insertion and deletion at both ends:
#include <deque>
int main() {
deque<int> dq;
// Add elements at both ends
dq.push_back(10); // Add to rear
dq.push_front(5); // Add to front
dq.push_back(15);
dq.push_front(1);
// Current deque: [1, 5, 10, 15]
// Access elements
cout << "Front: " << dq.front() << endl; // 1
cout << "Back: " << dq.back() << endl; // 15
cout << "At index 2: " << dq[2] << endl; // 10
// Remove from both ends
dq.pop_front(); // Remove front
dq.pop_back(); // Remove back
// Iterate
for (int x : dq) {
cout << x << " "; // Output: 5 10
}
return 0;
}
Stack and Queue
Basic LIFO and FIFO data structures:
#include <stack>
#include <queue>
int main() {
// Stack (LIFO - Last In, First Out)
stack<int> st;
st.push(10);
st.push(20);
st.push(30);
cout << "Stack top: " << st.top() << endl; // 30
st.pop();
cout << "After pop: " << st.top() << endl; // 20
cout << "Stack size: " << st.size() << endl; // 2
// Queue (FIFO - First In, First Out)
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
cout << "Queue front: " << q.front() << endl; // 10
cout << "Queue back: " << q.back() << endl; // 30
q.pop();
cout << "After pop: " << q.front() << endl; // 20
return 0;
}
STL Algorithms
Powerful algorithms that work with iterators:
#include <algorithm>
#include <numeric>
#include <vector>
int main() {
vector<int> nums = {5, 2, 8, 1, 9, 3, 7};
// Sorting and searching
sort(nums.begin(), nums.end());
bool found = binary_search(nums.begin(), nums.end(), 5);
// Find operations
auto it = find(nums.begin(), nums.end(), 8);
auto it2 = find_if(nums.begin(), nums.end(),
[](int x) { return x > 5; });
// Counting
int count = count_if(nums.begin(), nums.end(),
[](int x) { return x % 2 == 0; });
// Transformations
vector<int> squares(nums.size());
transform(nums.begin(), nums.end(), squares.begin(),
[](int x) { return x * x; });
// Accumulate and reduce
int sum = accumulate(nums.begin(), nums.end(), 0);
int product = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());
// Min/Max operations
auto minIt = min_element(nums.begin(), nums.end());
auto maxIt = max_element(nums.begin(), nums.end());
auto [minIt2, maxIt2] = minmax_element(nums.begin(), nums.end());
// Partition operations
auto pivot = partition(nums.begin(), nums.end(),
[](int x) { return x % 2 == 0; });
return 0;
}
Custom Data Structure: Trie
Example of implementing a custom data structure:
class TrieNode {
public:
TrieNode* children[26];
bool isEndOfWord;
TrieNode() {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
isEndOfWord = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (node->children[index] == nullptr) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
bool search(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (node->children[index] == nullptr) {
return false;
}
node = node->children[index];
}
return node->isEndOfWord;
}
bool startsWith(const string& prefix) {
TrieNode* node = root;
for (char c : prefix) {
int index = c - 'a';
if (node->children[index] == nullptr) {
return false;
}
node = node->children[index];
}
return true;
}
};
Memory-Efficient Techniques
Memory Optimization
- Object pooling: Reuse objects instead of creating new ones
- Bit manipulation: Use bits to store boolean flags
- Structure packing: Arrange struct members by size
- Smart pointers: Use unique_ptr, shared_ptr for automatic memory management
// Bit manipulation for flags
class Flags {
unsigned int flags;
public:
void setFlag(int bit) { flags |= (1 << bit); }
void clearFlag(int bit) { flags &= ~(1 << bit); }
bool isSet(int bit) { return flags & (1 << bit); }
};
// Smart pointer usage
#include <memory>
class Resource {
public:
Resource() { cout << "Resource created" << endl; }
~Resource() { cout << "Resource destroyed" << endl; }
};
int main() {
auto ptr = make_unique<Resource>(); // Automatic cleanup
shared_ptr<Resource> shared = make_shared<Resource>();
return 0; // Automatic destruction
}