Basics containers - C++
Welcome in last material before first program!
This topic will be about containers. Of course the simplest container the most simply is array can be one or more dimensional. I will talk just for a while, I know it will be just a begging and it is totally basics containers not all standard containers.
Containers can be one or more dimensional - simple example:
one dimensional (1x5) [1,2,3,4,5]
two dimensional (3x5)
[1,2,3,4,5]
[6,7,8,9,10]
[11,12,13,14,0]
Static array - is the most basic container without many function implemented.
int foo [5]; // declaration
or
int foo [5] = { 6, 2, 8, 32, 16}; // declaration and initialization in one line
Dynamic array looks similar, but you can change size of table and you need remember to release memory. Why dynamic arrays are better sometimes? Because of growing, casual table you have to destroy, allocate new memory and create table in dynamic tables you add elements to end, that mean it is all time the same table but bigger. Dynamic table can be table for tables, which can be different sizes. Which one you should use? It depend. Answer one question: this array will be constant size or no? If yes use static table, if no use dynamic. Every container is the best for his own destination. :D
int * foo= new int[5];
delete [] foo; // after all release memory to not making memory leaks
every containers can be iterated by loops. If you want to get or set variable you can use name in last example print(foo[4]) give you 16. Why almost because everything in programming is counted from 0, so print(foo[0]) give us 6. You can still set new value like now:
foo[0] = 4; // set 4 and table looks now [ 4, 2, 8, 32, 16]
cout << *foo; // display value foo[0] - now 4
cout << foo; // address of first elements
Lenght of arrays in C++
int lenght = sizeof(foo)/sizeof(int); // you have to get lengths in bits and divide by length of single element. For example 20 bits / 4 bits = 5 elements.
Other structures I will describe shortly. I have hope that you understand why we are using it and which container you need to your projects. So I will fast describe it bellow.
Array - from C++11 static size table like - simple container.
String - it is that obvious that we don't think it can be container, but it is. This container is just for char elements, because his destination is to being word or sentences container. In C++ string is dynamic structure (C# and JAVA is known size - different implementation).
Vector - the most used container. Similar to table, it have known size that mean searching is quite fast on it, but adding and removing elements can be time problematic, because you need to allocate memory, fix values and free memory if necessary. So if you want to take known element or search for element it is container for your problem, but if you need to often add and remove object maybe you will use a list? (If you know lists from JAVA or C# vector is that list, but C++ got own different list implementation).
List - next most popular container from stl is list. List can be one or bi-directional etc. One directional list is then if element got pointer to next element, if element got two pointer to previous and next element we call it bi-directional. Lists are perfect to fast removing or add elements, you can search on them element one after one - it is quite fast. Like every container in STL list got own iterator.
Queue - this is more specific container we have 2 main queues:
FIFO - first in first out - When you are in shop and you wait to pay for products, first customer which stay will pay as first and then go home for example.
LIFO - is more about books. Did you remember how to do tower from books? First is on bottom, next is second etc. When you want to take book, you will took from top of that turret, so last book which was thrown is first which you took. That mean first book which you throw is on bottom and it will be last on the table.
We got also priority_queue that mean first taken element is this with the biggest prioritize. Like you got task queue, some of them are more important and this will be done as first.
In other words:
FIFO – queue
LIFO - stack
Priority - priority_queue
Deque - is kind of mix bi-directional list and vector, that mean you can have fast access by number of element, if you add something on begin or at end it is fast operation, problem is when you try add something inside - then time is equal number of elements, so can be big is some situations.
Set/Unordered_set - Set is sorted collections of keys, which have tree representation - some has bigger key, second think has lower index. Set need a lot of time during adding because everything need to be rebuilded - sorted again. So if you have known size table of key and you need to search it often set is right collection. When you add/remove element you have to rebuild set. From C++11 you can use unsorted kind of sets, which is unsorted.
Map/Unordered_map - Map is similar to set collection, but it has key and value. Key can not be changed, but value can be. Key also need to be unique, so you can have access to object by key. We are using maps, when we want to sort something which have value or name like index of children in class. When you add/remove element you have to rebuild map. From C++11 you can use unsorted kind of map, which is unsorted.
Of course you have more containers in STL, but this you can use at the beginning of your programming journey. The most important containers are here, so try to use them in yours applications.
