Data Structures using C++ STL

Published in

ACM-W Manipal

11 min readMar 28, 2019

Picture courtesy: The Photography Club, Manipal

ACM-W Manipal Chapter recently organised a workshop on the basics of data structures and C++ Standard Template Libraries which was conducted by Harshita Binani and myself. The workshop received an overwhelming 120+ registrations!

C++ Standard Template Library is a relatively simple yet a very powerful tool in the field of competitive coding and we wanted to ensure that everyone in our college made the best use out of it. Keeping the upcoming placement season in mind and to simply help the students improve their coding game for contests like ACM ICPC, we covered data structures like stacks, queues, deques, priority queues, lists, hash maps, sets, heaps and vectors. It helped the attendees gain a better understanding of the C++ language as a whole. Their usage with C++ STL was demonstrated with code as well. A guide containing the basics of data structures was already sent out to the registered participants. Here is an overview of the workshop and all the necessary resources to get started with data structures using STL stacked up in one place!

What is C++ STL?

The C++ Standard Template Library (STL) is a set of classes that implement many popular and commonly used algorithms and data structures. These features help you create more efficient, performant, and reusable code. A template is used to define functions and classes for generic data types, ie, a generic blueprint of the function/class that will work for any data type and class objects.

Components of C++ STL

Containers: Like the name suggests, these are certain data structures that contain or hold the data. Ex: Stacks, vectors, arrays, queues.
Iterators: Pointer like objects for traversal of containers.
Algorithms: Use header file algorithm.h — it contains a collection of algorithm implementations such as sort. Alternatively check out the new header file: bits/stdc++.h. (Make sure you know when it is useful and when it isn’t!)
Functors: (not required for our usage) Function objects that can be parameterised in their constructors — functional.h

Types of Containers

Sequence : Stores data elements in a sequence. Ex: Vectors, lists, deques, stacks, queues.
Associative : Stores associated pairs. Ex: Sets, maps, multisets, multimaps. These are internally implemented as a tree.
Unordered Associative : Similar to associated containers, but stored in an unordered manner. Even faster because these are implemented as hash tables.
Functors: Function objects that can be parameterised in their constructors. (functional.h)

Iterators

Iterators are objects through which we can access the containers. Pointers are a type of iterators. Ex: The name of an array is actually a pointer to the first element in the array, which helps us access all the elements of an array. They help us to traverse containers in some order either for reading or writing.

Types of iterators(not necessary to know for coding purposes, but helps to wrap your head around the language’s concepts) are: input(suitable for input streams like keyboard buffers/read only files), output(suitable for output streams like screen text), forward(singly linked lists, unordered sets, maps, multi sets/maps), bidirectional(doubly linked lists, multisets/maps) and random access(arrays, dequeue and vectors).

Important iterator functions (common to many STLs)

begin() : returns iterator to the beginning of the container.
end() : returns iterator to the end. If begin == end container is empty.
empty() : returns true if container is empty, otherwise false.
rbegin(), rend() : same as begin and end but for reverse containers.
size(): returns size of the container.

Arrays and Vectors

Arrays, in layman terms, are fixed size containers that hold data of a particular datatype. Important thing to note here is that elements in an array are stored contiguously in memory. Arrays support random access for insertion and deletion of elements.

Vectors are similar to arrays except that we don’t need to specify the size of the array before hand — as we add elements to the vector, the size adjusts accordingly. They are similar to ArrayLists in Java. Hence, they are much easier to use when we don’t know what the size of the array is going to be.

Inserting and deleting at the end of vectors is easy and efficient, however inserting in the beginning or in the middle of vectors is an expensive process. (Think why?) Lists are a better choice for the latter case.

Pro tip: You can use auto as the datatype of any iterator while declaring it and it will automatically assign itself to any type of STL.

Here is the code demonstrating the use of vectors using STL. Try it out for yourself!

Try out the following questions on vectors/arrays:

An easy one:

2. Medium difficulty:

Stacks

A stack is defined as a collection of items in which the insertion of new item and deletion of items already in the stack are made at one end only. This end is called as top of stack. If an item is inserted onto a stack, the top value increases or moves upwards from its present position and if an item is removed the top value decreases or moves downwards. Important points to remember: it is a linear data structure, data is stored on top of one another, last in first out strategy is employed, insertion and deletion happens at one end which is called the top, implementation of stack is done using 1D array.

A small snippet on how to go about using stacks with STL is given here. We encourage you to use the same basic concepts of vectors and explore the STL yourself.

Pro tip: You cannot traverse a stack from the beginning to end like vectors. (Try and find out why!)

Try to solve the following question in the most efficient way possible. (Hint: It can be solved in O(1) time complexity!)

Queues

Ever waited at a bus stop to board a bus in the queue? A new person can only join at the end of the queue, whereas the first person to board the bus (and hence leave the queue) is the person at the front of the queue. That’s exactly how this data structure works. It follows the first in first out strategy.

I won’t be providing any code snippet for queues here because I want you guys to go ahead and try to implement it yourselves! Queue has a similar push and pop function as stacks and if you didn’t already guess it, the header file to be imported at the beginning of the code is called queue.

Food for thought: Do you think you can traverse a queue stl like vectors?

(Harshita and I in the flow of the talk :P) Picture courtesy: The Photography Club, Manipal

Deques

Similar to queues, deques have the added advantage of allowing push and pop operations at both the ends of the queue, ie, elements can be pushed not only at the rear but also at the front end and elements can be deleted from both the ends as well. Further, the deque data structure allows you to traverse the queue from the start to end, even though it isn’t really necessary.

Priority queues

It is important to not be mislead by the name here. Priority queues are internally heap data structures (max heap by default). Heaps are complete binary trees in which the parent node is always greater than its 2 children nodes in the case of a max heap, and the reverse in case of a min heap. This implies that the root of a max heap is the maximum element of the given values which can be accessed in O(1) time. This is the internal working of a priority queue. Priority queue can be understood as a data structure that assigns a priority to every value and stores every element according to the priority, and not in the order in which it arrives, and is time efficient.

Food for thought: Do you think this data structure can be used to solve the max element question given under stacks subsection? If yes, how?

Here is a small code snippet demonstrating the use of priority queue. Remember that it comes under the queue header file itself. Also find out how you would use a priority queue that stores elements in the form of a min heap.

Linked Lists

A linked list is a data structure that consists of a sequence of nodes such that in each node there is a field that contains a data item and another field that stores the link to the next node in the sequence. Linked lists are used as a major component in graphs. A linked list:

does not have contiguous memory storage- whichever random memory is available, data is stored there
does not provide random access
insertion, deletion is much cheaper than arrays

Here is a code snippet demonstrating the use of lists. It has a large number of functions(only a few of them mentioned here) so make sure to check it out.

Sets and Hashmaps

You can say these are the most important and extremely extremely extremely useful data structures. This bit from HackerEarth should prove useful in understanding the concept:

Consider the scenario: You are given a very large array with large numbers (which can have duplicate elements). You are then given a number and simply asked to check whether the given number exists in the array or not. Hashing can be used here instead of performing linear search to improve time complexity. Use a bool array where indices would be the elements in the array if the array elements are small (If the array elements are big, say in millions, then we cannot make an array of that big size). So we use a hash function and then hash elements of array and then use our bool array to store mapped values. Sets make this very simple for us. All we have to do is throw in the values of the array into a set and then simply check in O(1) time whether the given element exists in the set or not. Set will internally store all elements as a hash table only, so we need not go through the trouble of implementing the hash function and related code.

Suppose we extend this problem to find not just whether the element occurs in the array or not, but also to find the number of occurrences of the given element. An efficient way to do this would be to store the counts of all values as well. We can make a key-value pair for each element in the array. The key would be every unique element and its value would indicate its count in the array. We then store this pair in a hash map and we can access the count of any element in O(1) time. A simple way to visualise a hash map would be to think of a huge line of n buckets labelled from 1 to n each, all containing certain number of items in them. To find out the number of items in any bucket b, all we have to do is go to that bucket and look inside.

Hash maps and sets increase the space complexity but significantly improve the time complexity in most scenarios.

Note: This is one of the most important data structures asked in placement interviews.

Here are the code snippets for sets and hash maps in C++:

Note: Keys in a hash map should be unique. For duplicate keys, use a multimap.

Here are a few interesting questions, try to find the most efficient solutions to these problems (Hint: Use hash maps or sets!):

Heaps

I am sure after going through this incredibly long article, you have now wrapped your head around the use of STLs. Let me assure you though, heaps are used in a very different way. Check out this link on GeeksForGeeks for a very great explanation: https://www.geeksforgeeks.org/heap-using-stl-c/

In fact, check out GeeksForGeeks for a lot of resources on every other C++ STL and very elaborate codes along with a list of functions to use for each one.

Sorting

Check out this really short article on how to sort arrays and vectors in a single statement and not even worry about using the right type of sorting algorithm in the right scenario (yes I really did say one line sort!)

https://www.geeksforgeeks.org/sort-c-stl/

Conclusion

It is important to understand that this article (and the workshop) only aims to provide a basic introduction to help you get an idea about what kind of data structures exist and how to get started with STLs in C++. Knowing a language well can have a plenty of benefits. For example, in a coding test, while your other peers not having knowledge about STLs would waste a lot of time defining each data structure, you can utilise these predefined set of classes and finish up your code before the other peers even reach int main(). Not only do these STLs save your time, they also make your code efficient and neat. With practice, it becomes very easy and convenient to use these STLs. I hope you could take away something useful from all of this!

References

#acmw #manipal #data structures #stl #workshop #womenwhocode #empowerment