#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;
}