Created
July 14, 2020 01:25
-
-
Save wilderfield/3ce12fdc59c749b86922e6ce53a7d78c to your computer and use it in GitHub Desktop.
All Cpp STL Data Structures in One Go!
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> // cout | |
#include <vector> // Dynamic Array | |
#include <list> // Doubly Linked List | |
#include <deque> // Double Ended Queue (Circular Buffer) | |
#include <queue> // FIFO Queue, and Max Heap (Priority Queue) | |
#include <stack> // LIFO Stack | |
#include <set> // Ordered Set (BST - Red/Black) | |
#include <map> // Ordered Map (BST - Red/Black) | |
#include <unordered_set> // Hash Set | |
#include <unordered_map> // Hash Map | |
#include <multiset> // Ordered Set allow duplicate keys (BST) | |
#include <multimap> // Ordered map allow duplicate keys (BST) | |
#include <unordered_multiset> // UnOrdered Set allow duplicate keys (BST) | |
#include <unordered_multimap> // UnOrdered map allow duplicate keys (BST) | |
#include <utility> // pair, make_pair | |
#include <algorithm> // Sort, Binary Search, Shuffle | |
#include <random> | |
using namespace std; | |
auto r = default_random_engine {}; | |
int main () | |
{ | |
///////////// | |
// Array //// | |
///////////// | |
vector<int> A(5,0); // 5 elements, all 0 | |
vector<int> B = {1,3,5,7,9}; // 5 elements, initialized here | |
vector<int> array; // Empty | |
// Update A to be all Even numbers (0,2,4,6,8) | |
for (int a=0;a<A.size();++a) | |
A[a] = 2*a; // O(1) access | |
// Merge A and B into array | |
for (int a=0,b=0,i=0;i<10;++i) | |
if (i % 2) | |
array.push_back(B[b++]); // O(1) insertion at tail | |
else | |
array.push_back(A[a++]); | |
for (auto& el : array) cout << el << " "; cout << endl; // Print array | |
shuffle(array.begin(),array.end(),r); // Randomize elements | |
for (auto& el : array) cout << el << " "; cout << endl; // Print array | |
sort(array.begin(),array.end()); // Sort array from smallest to biggest | |
for (auto& el : array) cout << el << " "; cout << endl; // Print array | |
bool z = binary_search(array.begin(),array.end(),4); // Does array contain 4? | |
/////////////////// | |
// Linked List //// | |
/////////////////// | |
list<int> linkedList; | |
for (int i=0;i<array.size();++i) | |
if (i % 2) | |
linkedList.push_back(array[i]); // O(1) insertion at tail | |
else | |
linkedList.push_front(array[i]); // O(1) insertion at head | |
for (auto& el : linkedList) cout << el << " "; cout << endl; // Print linkedList | |
linkedList.pop_front(); // O(1) deletion at head | |
linkedList.pop_back(); // O(1) deletion at tail | |
for (auto& el : linkedList) cout << el << " "; cout << endl; // Print linkedList | |
// Key drawback is that you don't have random access to any offset | |
////////////////////////// | |
// Double Ended Queue //// | |
////////////////////////// | |
deque<int> dequeue; | |
// Get remaining elements from LinkedList | |
while (!linkedList.empty()) | |
{ | |
dequeue.push_back(linkedList.front()); // O(1) insertion at tail | |
dequeue.push_front(linkedList.back()); // O(1) insertion at tail | |
linkedList.pop_front(); | |
linkedList.pop_back(); | |
} | |
for (auto& el : dequeue) cout << el << " "; cout << endl; // Print dequeue | |
cout << dequeue[3] << endl; // Random access to dequeue, because its an array underneath | |
cout << dequeue.front() << endl; // Access front | |
cout << dequeue.back() << endl; // Access back | |
sort(dequeue.begin(),dequeue.end()); | |
///////////// | |
// Queue //// | |
///////////// | |
queue<int> fifo; | |
while (!dequeue.empty()) | |
{ | |
fifo.push(dequeue.front()); | |
dequeue.pop_front(); | |
} | |
while (!fifo.empty()) | |
{ | |
cout << "Popping: " << fifo.front() << endl; | |
fifo.pop(); | |
} | |
//////////////// | |
// Max Heap //// | |
//////////////// | |
priority_queue<int> maxHeap; | |
for (int i=0;i<10;++i) | |
{ | |
maxHeap.push(i); // O(log(n)) insertion, such that max element is always at top | |
cout << "Max Element: " << maxHeap.top() << endl; | |
} | |
//while (!maxHeap.empty()) | |
//{ | |
// cout << "Max Element: " << maxHeap.top() << endl; // O(1) access to max element | |
// maxHeap.pop(); // O(log(n)) deletion (re-heapify) | |
//} | |
///////////// | |
// Stack //// | |
///////////// | |
stack<int> lifo; | |
while (!maxHeap.empty()) | |
{ | |
lifo.push(maxHeap.top()); | |
maxHeap.pop(); | |
} | |
while (!lifo.empty()) | |
{ | |
cout << "Popping: " << lifo.top() << endl; | |
lifo.pop(); | |
} | |
/////////// | |
// Set //// | |
/////////// | |
set<int> bst; | |
// Make BST contain only even numbers | |
for (int i=0;i<5;++i) | |
bst.insert(2*i); // O(log(n)) insertion | |
for (auto it=bst.begin();it!=bst.end();++it) | |
cout << *it << " "; | |
cout << endl; | |
if (bst.find(4) != bst.end()) // O(log(n)) search | |
cout << "Found 4!" << endl; | |
if (bst.find(3) == bst.end()) // O(log(n)) search | |
cout << "Can't find 3!" << endl; | |
/////////// | |
// Map //// | |
/////////// | |
map<int,char> bstMap {{1,'a'},{3,'b'},{5,'c'}}; | |
bstMap[5] = 'z'; // O(log(n)) access | |
for (auto it=bstMap.begin();it!=bstMap.end();++it) | |
cout << "Key: " << it->first << " Val: " << it->second << endl; | |
bstMap.erase(5); // O(log(n)) delete // Delete by key | |
bstMap.erase(bstMap.begin()); // Delete via iterator | |
for (auto it=bstMap.begin();it!=bstMap.end();++it) | |
cout << "Key: " << it->first << " Val: " << it->second << endl; | |
//////////////// | |
// Hash Set //// | |
//////////////// | |
unordered_set<int> hashSet; | |
// Make hashSet contain only even numbers | |
for (int i=0;i<5;++i) | |
hashSet.insert(2*i); // O(1) insertion | |
for (auto it=hashSet.begin();it!=hashSet.end();++it) | |
cout << *it << " "; | |
cout << endl; | |
if (hashSet.find(4) != hashSet.end()) // O(1) search | |
cout << "Found 4!" << endl; | |
if (hashSet.find(3) == hashSet.end()) // O(1) search | |
cout << "Can't find 3!" << endl; | |
//////////////// | |
// Hash Map //// | |
//////////////// | |
map<int,char> hashMap {{1,'a'},{3,'b'},{5,'c'}}; | |
hashMap[5] = 'z'; // O(1) access | |
hashMap[100] = 'k'; // O(1) insertion | |
hashMap.insert(make_pair(55,'h')); // O(1) insertion | |
for (auto it=hashMap.begin();it!=hashMap.end();++it) | |
cout << "Key: " << it->first << " Val: " << it->second << endl; | |
hashMap.erase(5); // O(1) delete // Delete by key | |
hashMap.erase(hashMap.begin()); // Delete via iterator | |
for (auto it=hashMap.begin();it!=hashMap.end();++it) | |
cout << "Key: " << it->first << " Val: " << it->second << endl; | |
if (hashMap.find(55) != hashMap.end()) // O(1) search | |
cout << "Found key 55: " << hashMap[55] << endl; | |
// TODO | |
// - multiset | |
// - multimap | |
// - unordered_multiset | |
// - unordered_multimap | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment