std::string			-- array based
std::array			-- array based
std::vector			-- array based
std::deque			-- double ended queue
std::forward_list	-- single linked list
std::list			-- double linked list



set   - unique element -- BST
unordered set -	hash key based storage


//------------------------------------------------------------------------------------------------
Array Based containers
Arrays provide random access, with the index operator or with pointer arithmatic you can access or mutate
any value in the array

A search of unsorted data would take O(N)
If the array was sorted you could implement a binary search O(log N)


require a single contiguous piece of memory, 
resizing the array can take a bit of time.




//------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------
Stack
ArrayBased

push operation O(1)
pop operation O(1)
top operation O(1)
search operations are not supported in a stack

add or remove from anywhere other than top is NOT possible in a stack
provides random access: no

NOTE:
If we are actually using an array to store our data, yes you technically do 
have random access to any element in the array and you could technically insert or delete 
from positions other than the top of the stack. But then it would NOT be a stack.
A "stack" is by defenition a LIFO container that does not have random access.


//------------------------------------------------------------------------------------------------
Node based containers

no random access
each addition requires memory allocation for a new node
there is no resize needed memory used is in individual small pieces




//------------------------------------------------------------------------------------------------
Single Linked List,
has head pointer

insert front O(1)
insert back  O(N)
delete specific value O(N)
search for specific value O(N)


provides random access: no

NOTE: In this class and our implementation we did not have a tail pointer
we ONLY had a head pointer. By defenition a SLL only has next pointers in each node
and you can ONLY traverse the list from head to tail. A tail pointer would allow inserts to back with O(1)
but you could ONLY insert at the end with a tail pointer, it would not speed up any other operations


//------------------------------------------------------------------------------------------------
Single Linked List,
has head pointer

insert front O(1)
insert back  O(N)
delete specific value O(N)
search for specific value O(N)


provides random access: no

NOTE: In this class and our implementation we did not have a tail pointer
we ONLY had a head pointer. By defenition a SLL only has next pointers in each node
and you can ONLY traverse the list from head to tail. A tail pointer would allow inserts to back with O(1)
but you could ONLY insert at the end with a tail pointer, it would not speed up any other operations

//------------------------------------------------------------------------------------------------

Binary Search Tree

Insert  O ( log N )   up to O(N)
Search  O ( log N )   up to O(N)
Delete  O ( log N )   up to O(N)







//------------------------------------------------------------------------------------------------

AVL Tree

Insert  O ( log N )
Search  O ( log N )   
Delete  O ( log N )   
//------------------------------------------------------------------------------------------------
Hashtable

Insert  O ( 1 )   to O(N)
Search  O ( 1 )   to O(N)
Delete  O ( 1 )   to 0(N)

//------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------