STL Sundays, Introduction to STL Containers (Part 1)

Introduction

The Standard Template Library (STL) is a software library for the C++ programming language that influenced many parts of the C++ Standard Library . It provides four components called

• algorithms
• container
• iterators
• functions

In the first week of STL Sundays, we will be covering some basic containers( data structures) . Being specific, we will cover

• std::vector
• std::stack
• std::queue
• std::deque
• std::list

Before diving straight into the containers however, we must have knowledge about iterators.

Iterators: Building block of C++ Standard Library

Iterators are an integral part of STL. Pretty much all STL algorithms are designed to work with iterators and you will see them being used extensively in our series as well. Almost every container in C++ standard library have iterators. Iterators are mostly used to specify the range on which an algorithm or operation should be performed on. Only std::stack, std::queue and std::priority_queue(which are naturally not supposed to be iterated on) are the containers that lack iterators.

General working with iterators

• begin() : This will return the beginning iterator of the container. This can be invoked in two ways: std::begin(container) or container.begin()
• end() : This will return the end of the container. This can also be invoked in two ways ,similar to begin(): std::end(container) or container.end()
• cbegin() and cend() : These two are the const version of begin() and end(). These two return an object of const_iterator type which can’t be changed, while begin() and end() return iterator type, whose internal value can be changed.

Note: There are different types of iterators in C++ . They are also not limited to just containers as well. You can see more about them on cppreference.

std::vector

std::vector is a dynamic array data structure provided by C++ standard library. It is a generic container meaning it can hold almost any type, provided they satisfy some constraints. It has the ability to resize itself automatically when inserting or erasing an object.

Common operations on std::vector

• push_back(element) : Appends the given element to the end of the container. There is alsoemplace_back(element)which can do what push_back does and more. This is done in amortized(average) O(1) time
• pop_back() : Removes the last element of the container. Calling this when vector is empty is an undefined behaviour (we don’t know what happens but its not good). O(1) time
• size() : Returns the current size of the vector. O(1) time.
• empty() : Returns true if the size of vector is 0 else returns false. O(1) time.
• clear() : Clears the content of the vector making the vector’s size 0. O(n) time, where n is the size of vector before calling clear().
• Access operations : front() , back() , at(index) and [] operator are used for accessing elements. front() and back() do as their name suggests(return front of the vector and back of the vector respectively and will return garbage when called on empty vector or a segmentation fault happens). at(i) and [i] will both access element at index i but at(i) will do bounds check but [i] won’t. All of these operation are O(1) time.
• reserve(n) : Increase the capacity of the vector to a value that’s greater or equal to n. It will however not change the size of vector. Worst case linear time operation.
• Erasing elements : It has two variants,both taking iterators as parameters (one takes just one iterator , another takes in two iterators. It has worst case linear time complexity. erase(iter) variant will remove the element pointed to by the iter from the vector. erase(first_iter,last_iter) variant will remove all the elements in range [first_iter, last_iter).

std::vector in action

std::stack

The std::stack class is a container that gives us the functionality of a stack - specifically, a LIFO (last-in, first-out) data structure.

Stack Data Structure

Common operations on std::stack

• push(element) : Pushes element to the top of the stack. In dynamic stack such as std::stack , this operation will take O(1) amortized time. There is also emplace(element) which will do the same thing which will construct the element in-place without invoking copy or move constructor.
• pop() : Removes the top element from the stack. O(1) time.
• top() : Returns reference to the top element in the stack. O(1) time.
• size() : Returns the number of elements in the stack. O(1) time.
• empty() : Checks if the stack has no elements, returning true if it does else false. O(1) time.

std::stack in action

std::queue

The std::queue class is a container that gives us the functionality of a queue - specifically, a FIFO (first-in, first-out) data structure.

Queue Data Structure

Common operations on std::queue

• push(element) : Pushes element to the back of the queue. This operation will take O(1) amortized time. There isemplace(element) for queue as well.
• pop() : Removes the front element from the queue. O(1) time.
• front() : Returns reference to the first element in the queue. O(1) time.
• size() : Returns the number of elements in the queue. O(1) time.
• empty() : Checks if the queue has no elements, returning true if it does else false. O(1) time.

std::queue in action

std::deque

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end . As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping. This is pretty useful container capable of giving us random access as well as constant time insertions at the back and the front. You must be thinking why do we even use std::vector or std::queue or std::stack when this container can perform all of their functionalities. This much power does have some cost. std::deque is not as cache friendly as std::vector is due to how its implemented. This is probably its major drawback, but it is unlikely you will notice this in most of the programming challenges you will encounter, so feel free to use std::deque without any worries. As for myself, I barely use it because I never felt like I needed it.

Common operations on std::deque

• push_back(element) : Appends the given element to the end of the container. There is alsoemplace_back(element)which can do what push_back does and more. This is done in constant time.
• pop_back() : Removes the last element of the container. Calling this when vector is empty is an undefined behaviour (we don’t know what happens but its not good). Constant time operation.
• push_front(element) : Inserts element to the beginning of the deque. There is again an emplace variant for this called emplace_front(element) . This is again a constant time operation.
• pop_front() : Removes the first element from the deque. Again a constant time operation.
• size() : Returns the current size of the deque. Constant time operation.
• empty() : Returns true if the size is 0 else returns false. Constant time operation.
• clear() : Clears the content of the container making the it’s size 0. O(n) time, where n is the size before calling clear().
• Access operations : front() , back() , at(index) and [] operator are used for accessing elements. front() and back() do as their name suggests(return front back of the the deque respectively and will return garbage when called on empty deque or it will give segmentation fault). at(i) and [i] will both access element at index i but at(i) will do bounds check but [i] won’t. All of these operation are O(1) time.
• Erasing elements : It has two variants,both taking iterators as parameters (one takes just one iterator , another takes in two iterators. It has worst case linear time complexity. erase(iter) variant will remove the element pointed to by the iter from the vector. erase(first_iter,last_iter) variant will remove all the elements in range [first_iter, last_iter).

std::deque in action

std::list

std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. It doesn’t support constant time random access as with std::vector or std::deque . This is implemented as a doubly linked list. There is also another container in STL std::forward_list which is based on singly linked list but you won’t get bidirectional iteration with it unlike in std::list.

Doubly Linked List

Common operations on std::list

Following are some of the common operations(with same functionality) that std::list has with std::deque :

• push_back(element)
• pop_back()
• push_front()
• pop_front()
• front()
• back()
• size()
• empty()
• clear()

The operations that sets std::list apart from other containers is its ability to do constant time insertion anywhere in the list given that you have iterator to the position you want to insert it at. If you have iterator to 5th element(and its value be 100) in the list and you call lst.insert(it,10) , then 10 will become the 5th element and 100 will become 6th element in that list. You can insert a range of elements as well with lst.insert(it, start_it,end_it) which will basically insert range of elements [start_it,end_it) before it. This operation will take (end_it-start_it) time.

std::list in action

Conclusion

A lot was covered in this article and I hope you learnt something from this. This serves as introduction to some of the STL containers and I only included information that I thought were must knows and some common operations I find myself using from time to time. These containers can do much more than this and with iterators they compose well with different STL algorithms and other containers as well. To know more about these containers and other containers in STL , you can visit cppreference.com.