STL

STL: Standard Template Library(C++ Only)

As you may have seen vectors now in Arrays, you might be wondering about more such amazing pre-defined data structures and methods. So here is a list of all such "magical containers" STL has to offer and when and how to use them.

Introduction to STL: (All misconceptions)

STL: Standard Template Library.

STL is a library that gives us many predefined functions and "containers" to make our life much easier! 

See, many of you now would be wondering: If there are such magical containers, then why learn things like linked lists and all which are quite difficult to understand and implement. Also, is using STL recommended, or is it just a "quick fix". 

First of all, STL is not at all "magic". Every container is made by the creators of this library and we can and should use it to make code look a lot cleaner and easy to both understand and write. Secondly, the theory of linked lists, self-balancing BSTs(which are maps in STL) is really important, not only for interviews but to understand how this magic happens.

Major Containers:

STL has these containers to store data, and they are all straightforward to use and understand. Here we just discuss the syntax and properties and when to use them and who they are in actuality.

But before jumping to the containers, we have to learn about Iterators and how to use them.

Iterators

Iterators are objects which can point to some container and can iterate through them. The most obvious form of an iterator is a pointer and we are gonna use a very similar thing for iterating on the containers. Also please note that containers such as vectors can be iterated with a simple for loop(same way to iterate an array) and iterators as well but containers such as sets and maps can't. We have to use iterators to iterate through them. Also, they reduce the complexity and execution time of the program.  

Syntax of iterator is:

vector<int>::iterator it; 
      OR
auto it=my_vector_name.begin();

Now let's see the difference. First of all, the first syntax is not pointing to anything but the second one is pointing to the vector's beginning.And as the second syntax is far more better, I am gonna use that only from here.

Using Iterators: We would be using iterators mostly iterate through maps, sets, and in some algorithms like sort, erase, etc in vectors. So the use of iterators would be discussed in those sections only.

Okay, there are some things to be kept in mind while dealing with them:

• Never do something like this(this would only work on vectors): iterator_name=iterator_name+5 to shift iterator 5 positions ahead.  Instead use advance() to advance the original iterator, but if you want to make a copy of the advanced iterator to another iterator, use next(). The syntax of both and differences are here(Similarly for decrementing you can use prev()):

  //For advance
  vector<int> my_vec = {1, 2, 3, 4, 5};
  auto it = my_vec.begin();
  advance(it, 3);
  cout << "The changed position of it is: " << *it << endl;//Output is 4 and it is modified
  

  //For next
  vector<int> my_vec = {1, 2, 3, 4, 5};
  auto it = my_vec.begin();
  auto it2 = next(it, 3);
  cout << "The position of it2 is: " << *it2 << endl;//Output is 4 and it is not modified 

• If you want to change the values of a map or vector inside a for loop then use pass by reference as in code below:

for (auto &it : my_vec)//Suppose my_vec is 1,2,3,4,5
{
	it = 4;
}
for (int i = 0; i < my_vec.size(); i++)
{
	cout << my_vec[i] << " ";//Output is 4 4 4 4 4
}

Now let's see the widely used utility library's pair.

Pairs

Pairs, as the name suggests are used to make pairs. Now, these pairs can be of any kind, like pairing chars to chars, or chars to ints, you get the point. 

Here is the syntax of using pairs with vectors and creating a pair also:

vector<pair<char, int> > my_vec = {{'a', 2}, {'b', 3}, {'c', 8}};
pair<char, int> my_pair = make_pair('d', 9);
my_vec.push_back(my_pair);
for (int i = 0; i < my_vec.size(); i++)
{
	cout << my_vec[i].first << ": " << my_vec[i].second << endl;
}

The above code's output is:

a: 2
b: 3
c: 8
d: 9

Now the thing is that how we should use them and when to use them. Here are some questions in which you can use pairs really efficiently:

Questions:

................................................................................................................................................

Finally, now let's explore the containers we would be using most often.

Vectors

I think they have been discussed quite deeply in the arrays section. let's see some functions:

Some commonly used functions:

• sort(): sort function works in O(nlog(n)) in case of vectors and is pretty useful, and it actually works like merge sort under the hood for large arrays and insertion sort for smaller ones but the real fact is that it makes the code a lot cleaner! We use sort in such a way: sort(my_vec.begin(),my_vec.end());
• min and max: Instead of doing those if-else conditions you can directly use min and max functions. Also if you are comparing more than 2 values, use curly braces. For eg. min({1,2,3,4}).

Sets

Sets are associative containers, and by associative containers, I mean the containers in which value is stored in the form of keys, and hence, we can not have duplicates in a set and cannot modify an element but can delete, or insert an element. And it is a lot more useful than vectors or arrays in some problems. As insertion, deletion, and find operation in O(log(n)) which is quite useful in situations where we have to update and find an element repeatedly. But the harsh thing is that you can't just access an element directly like in the case of vector, you have to iterate till the position which makes retrieval operation as O(n). Here are the syntax and the operations:   

set<int> my_set;
for (int i = 0; i < 4; i++)
{
	my_set.insert(i);
}

//now my set is 0,1,2,3

//For printing the whole set

for (auto it : my_set)
{
    cout << (it) << " ";
}
cout << "\n";

//Find operation in sets

if (my_set.find(1) != my_set.end())
	cout << *(my_set.find(1)) << "\n";

my_set.insert(5);
my_set.erase(3);//erases 3
my_set.erase(my_set.begin());//erases beginning of vector
for (auto it : my_set)
{
    cout << (it) << " ";
}

Questions that require/can be done using sets:

Questions:

...........................................................................................................................................

Some Methods(common in sets and vectors):

• Upper Bound and Lower Bound:

These only work on sorted vectors and sets are already sorted, so, no comments.

• lower_bound(c): It returns an iterator that points to an element that is equal to or just greater than c in O(log(n)). Usage is shown here:

  set<int> my_set;
  my_set.insert(1);
  my_set.insert(2);
  my_set.insert(4);
  my_set.insert(5);
  cout<<*my_set.lower_bound(3)<<endl;

        The use of such a method is when you don't need to find the exact element and the "just greater" element would work fine for you. Also, if they can't find anything, they just point to the end of the vector. You can check that with a.end(). Some questions where it is useful:

Questions:

...........................................................................................................................................

• upper_bound(c): It returns an iterator that points to an element that is just greater than c in O(log(n)). Usage is shown here:

  set<int> my_set;
  my_set.insert(1);
  my_set.insert(2);
  my_set.insert(4);
  my_set.insert(5);
  cout << *(my_set.upper_bound(2)) << endl;
  

The above code gives output 4.

Some related questions:

Questions:

...........................................................................................................................................

• find(): It returns an iterator which points to the element(if present, otherwise points to container.end()). Usage is shown in the sets section. Time complexity is O(n) in the case of vectors and O(log N) in the case of sets. 

• erase(): This can be used in several ways like if you give an iterator as its parameter, it would erase the element the iterator was pointing to, and if you passed a simple data type, it would find the element with the same value and remove it from the container. Complexity is O(n) in vectors and O(log(n)) in sets.

•         set<int> my_set;
  	my_set.insert(1);
  	my_set.insert(2);
  	my_set.insert(4);
  	my_set.insert(5);
  	auto it = my_set.begin();
  	my_set.erase(it);
  	for (auto &it : my_set)
  	{
  		cout << it << " ";
  	}
  	cout << endl;
  	my_set.erase(4);
  	for (auto &it : my_set)
  	{
  		cout << it << " ";
  	}
  	cout << endl;
  

Although there are many other functions like size(), max_size(), insert(), etc but these functions are self-explanatory and have nothing cool or any kind of advisory for them, so I give you the responsibility of exploring them. (You can check them at geeks for geeks)

Maps

Maps are associative containers(as explained in sets) and have these special "key-value pairs" which means you have to map a value to a key and you can't map two or more values on the same key. So you would be thinking what's the difference between a map and a vector of pairs! Well, a huge difference, first of all, maps are actually BSTs through which you can do Insertion, deletion, and searching in O(log(n)) and moreover, it looks pretty sexier than a vector of pairs. Also, the key-value pairs are actual pairs we talked about before.

Syntax to declare, insert and iterate through a map:

string s = "abhinandan sharma";
map<char, int> my_map;
for (int i = 0; i < s.size(); i++)
{
	my_map[s[i]]++;//see this very carefully
}
for (auto it : my_map)
{
	cout << it.first << ": " << it.second << endl;
}

Output

 : 1
a: 5
b: 1
d: 1
h: 2
i: 1
m: 1
n: 3
r: 1
s: 1

Erase, upper_bound, lower_bound, find operations take the key as a parameter and returns the same old iterator. 

Maps are generally used to ..... solve questions! So let's just head to questions where maps are used and see how they are solved:

Questions:

...........................................................................................................................................

unordered_map

These are implemented using hash tables under the hood and have time complexity O(1) for insertion, deletion, and find operation! The difference between maps and unordered_maps is just that maps are sorted and unordered_maps(as the name suggests) are not, because maps are implemented as BSTs. And these containers are very useful if you don't need the pairs to be sorted inside them. The syntax and all is the same as that of the map, so not gonna repeat it.

 

Questions:

...........................................................................................................................................

Queue

 These will be discussed in the deep in queues section.

Stacks

 These will be discussed in the deep in queues section.

MultiSet

So, the name says it all! Sets that can have multiple values! These are also implemented using BSTs under the hood.

Just a small thing: to erase all elements you may use my_multiset.erase(key) and to remove just one occurrence use my_multiset.erase(my_multiset.find(key));

As for the syntax, iterations are the same, we just jump to questions:

Questions:

...........................................................................................................................................

unordered_set

Another useful container. You may have guessed it by now. Unordered sets have much to offer with their O(1) superpower. O(1) time complexity for insertion, deletion, and search which is pretty fast. Also, they are implemented using hash tables. 

Let's jump to questions:

Questions:

...........................................................................................................................................

 

dequeue

Double Ended Queues shorten as dequeue are an implementation of doubly ended queues, in which insertion and deletion are possible on both ends which makes it quite a good replacement for vectors. The functions are same as of vectors with some added ones: push_front(), pop_front().

So, when to use vector and when dequeue?

Simple, when you need to insert elements and delete elements from beginning or end, prefer using dequeue.

Questions:

...........................................................................................................................................