STL Sundays Part 2 (C++ STL Containers Continued)
Introduction
Hey everyone!! In this week’s article, we shall continue to explore some more C++ STL containers that are as follows:
- Priority queue
- Map
- Set
- Unordered map
- Unordered set
Under each of the above STL container, I shall give an insight about the data structure itself initially and then list down its methods, explaining them all briefly so that all of the basics are covered. I have also mentioned the time complexities of all the methods so that you will be aware of how your code will respond to enlarging data. Now that the intro is complete, we shall start with priority queues.
std::priority_queue
Let’s just get one thing straight from the very beginning — priority queues are very different from normal queues. Yes, you can retrieve only one element at a time like in normal queues, but priority queues store data in a specific order and do not follow the FIFO rule as normal queues do. By default they store numbers in descending order and strings are stored in descending order of their corresponding ASCII value (compared letter by letter). Nevertheless, we can also store numbers in ascending order and strings in lexicographical order if we use priority_queue<int, vector<int>, greater<int>> and priority _queue<string, vector<string>, greater<string>> while declaring the priority queues respectively. All these features make priority queue a perfect candidate for problems that require repeated optimization like in Dijkstra’s algorithm, etc.
Commonly used methods
Access methods
top() — It’s used to get the most prior element from the priority queue. In case you created a default priority queue, it will return the element with largest value and in case it was changed to ascending/lexicographical order while declaration, it would return the element with lowest value. If the priority queue is empty, this method exhibits undefined behavior. Time complexity of this method is O(1).
Capacity related methods
empty() — It’s used to check if a priority queue has no elements or not. It returns 1 (true value) if the priority queue is empty, else it returns 0 (false value). Time complexity of this method is O(1).
size() — It’s used to find how many elements are present in the priority queue. It returns X if there are X elements in the priority where X is a whole number. Time complexity of this method is O(1).
Modify methods
push(input) — It’s used to add elements into the priority queue. It takes 1 argument — the element to be added, and that specified element will be added to the priority queue based on priority. Time complexity of this method is O(logn).
pop() — It’s used remove the most prior element from the priority queue but it doesn’t return anything. If the priority queue was empty, this method results in undefined behavior. Time complexity of this method is O(logn).
std::map
If you want to store data as pairs that are linked together, maps are a perfect choice. Maps store data in the form of key-value pairs. Given the ‘key’, you will be able to find it’s ‘value’ because the ‘key’ and the ‘value’ are linked together. It’s highly important to note that the keys must be unique and must connect to one and only one value. However, two different keys can map to the same value. They are pretty much like functions that we learnt in our math classes. One more point about normal maps is that their keys are in sorted order (ascending/lexicographical by default which could be altered just like we discussed in priority queues).
Commonly used methods
Access methods
at(key) — It gives the value associated with the given ‘key’ input. However, if the given input ‘key’ doesn’t exists it throws an “out of range error”. Time complexity of this method is O(logn).
name_of_map[key] — The square bracket operator can be used just like in case of arrays. The ‘value’ of the ‘key’ put inside the square brackets will given. This operator can also be used for inserting elements by assigning the new key with its value like this name_of_map[new_key] = value Time complexity of this operation is O(logn).
Capacity related methods
empty() — It returns 1 if the map is empty (has no elements) or returns 0 if the map isn’t empty. Time complexity of this method is O(1).
size() — It returns the number of key-value pairs in the map. Time complexity of this method is O(1).
Modify methods
insert() — It’s used to add key-value pairs to the map. There are two ways to use it:
name_of_map.insert({key, value})name_of_map.insert(std::make_pair(key, value))
Worst case time complexity of this method is O(logn).
erase(key) / erase(iterator) / erase(iterator1, iterator2) — As you may have noticed, there are 3 ways to use the erase method. erase(key) removes the key-value pair of the input ‘key’. erase(iterator) removes the key-value pair pointed by the iterator given as input. erase(iterator1, iterator2) is used to remove a range of key-value pairs by giving two iterators as its input — the starting iterator(included) and the ending iterator(excluded). Worst case time complexity of this method is O(logn).
clear() — It is used to delete all key-value pairs from the map. Time complexity of this method is O(n).
Search methods
find(key) — It takes a ’key’ as its input. If the ‘key’ exists, it returns an iterator to that ‘key’ in the map. If the ‘key’ doesn’t exists it returns a constant iterator which refers to end() iterator. Time complexity of this method is O(logn).
count(key) — It takes a ‘key’ as its input and returns 1 if the ‘key’ exists in the map, else it returns 0. Time complexity of this method is O(logn).
lower_bound(key) — This method returns an iterator pointing to the key (input) in the map container. In case the key isn’t present in the map, the function returns an iterator pointing to the immediate next element which is just greater than key. If the key passed in the parameter exceeds the maximum key in the container, then the returned iterator points to the number of elements in the map as key and element could be any element. The time complexity of this method is O(logn).
upper_bound(key) — The function returns an iterator pointing to the immediate next element which is just greater than key (input). If the key passed in the parameter exceeds the maximum key in the container, then returned iterator refers to name_of_map.end(). The time complexity of this method is O(logn).
Largest and smallest key
Incase you want to find the smallest key in the map, there is a witty way to do so. You can use name_of_map.begin() which will return an iterator to the first key of the map but by default elements are arranged in ascending order in maps, hence the first key is also the smallest key. Similarly if you want to find the largest key, you can use name_of_map.rbegin() which will return an iterator referring to the last key of the map. You can increment these iterators to obtain subsequent smaller/larger keys as well. The time complexity of incrementing these iterators is O(logn).
Key and value from iterator
Suppose you have an iterator pointing to a key in your map, and you want to know the key and its associated value, you can use name_of_iterator->first to obtain the key and name_of_iterator->second to obtain the value. You can also use *(name_of_iterator).first and *(name_of_iterator).second to obtain the key and value respectively.
std::set
You can think of sets as just storing a collection of data which must be unique (not repeated). Hence you can think of sets as maps with just the ‘key’ part. Also similar to maps, the numbers stored in sets are automatically arranged in ascending order, and string are arranged in lexicographical order.
Common methods
Access methods
There are no explicit access methods for sets. However, you can use find() method to get an iterator to refer to an element (if it exists).
find(parameter) — If you want to access an element, you can use this method which returns an iterator to the element passed in as the parameter. If the element doesn’t exist, it returns end() iterator. Time complexity of this method is O(logn).
Capacity related methods
size() — It’s used to get the number of elements in the set. Time complexity of this method is O(1).
empty() — This method returns 1 if the set has no elements else it returns 0. Time complexity of this method is O(1).
Modify methods
insert(parameter) — This method is used to add elements to the sets. The element to be added needs to be passed as the parameter. Worst case time complexity of this method is O(logn).
erase(parameter) — It’s used for erasing an element from the set. The element to be deleted needs to be passed as the parameter. In case the element you passed in was not present in the set it doesn’t throw any error. Worst case time complexity of this method is O(logn).
clear() — It deletes all the elements stored in the set. Time complexity of this method is O(n).
Search Methods
count(parameter) — helps you to get the count of an element in the set. Since elements are unique in sets, it can be used to check if an element exists or not in the set. Time complexity of this method is O(logn).
find(parameter) — if you want to access an element, you can use this method which returns an iterator to the element passed in as the parameter. If the element doesn’t exist, it returns end() iterator. Time complexity of this method is O(logn).
lower_bound(entry) — This method returns an iterator pointing to the entry (input) in the map container. In case the entry isn’t present in the map, the function returns an iterator pointing to the immediate next element which is just greater than entry. If the entry passed in the parameter exceeds the maximum value in the container, then the iterator returned refers to name_of_set.end(). The time complexity of this method is O(logn).
upper_bound(entry) — The function returns an iterator pointing to the immediate next element which is just greater than entry (input). If the entry passed in the parameter exceeds the maximum entry in the container, then returned iterator refers to name_of_set.end(). The time complexity of this method is O(logn).
Largest and smallest entry
Just like in maps, in sets too you can find the smallest entry and largest entry using name_of_set.begin() and name_of_set.rbegin() respectively. You can increment these iterators to obtain subsequent smaller/larger entries. The time complexity of incrementing remains O(logn) for sets too.
std::unordered_map
An unordered map differs from an ordered map in 4 main areas:
- Inbuilt implementation: An unordered map, under the hood, is built based on hash maps whereas ordered maps are built based on red-black trees (self balancing binary trees). This fundamental difference gives rise to all the differences that exist between an unordered and an ordered map. For now, it’s not necessary to dwell deep into what hash maps or red-black trees are. Just focus on the differences and how you can benefit from it.
- Order in which data is stored: This difference is name deductive. Unordered maps have no order when it comes to storing data while ordered maps have a sorted order.
- Time complexity of certain operations: As you will see soon in the methods, unordered maps are faster compared to ordered maps. Time complexity of certain operations of ordered maps is improved compared to unordered maps.
- Limitation on data types of the key: Any data structure whose hash value can’t be found can’t be used as keys in unordered maps. To put it in simple words, primitive data types like int, char, strings are all fine but complex ones like vectors, pairs are a no no. However, no such problem is faced with ordered maps because they are based on trees (where comparison of the data is enough). This limitation can still be solved if we make the data type hashable by writing your own std::hash<> for the class. More info here
Commonly used methods
Methods are of unordered are the same as the ones under ordered maps but their time complexities differ.
Access methods
at(key) — It gives the value associated with the given key input. However, if the given input key doesn’t exists it throws an “out of range error”. Average time complexity is O(1) while worst case time complexity is O(n).
Now you may ask — “How come a worst case complexity of O(n) be better than a consistent O(logn) time complexity as in ordered maps?”. The answer relies on hashing because the worst case scenario occurs when the hashing produces collisions, i.e. more than one ‘key’ starts giving the same ‘value’ after hashing. But this is a rare case and hence most of the time this method operates at O(1). You will need to keep a note of this because all the access, insertion, deletion and search methods here and in unordered sets have the same justification for their time complexity.
name_of_map[key] — This square bracket operator can be used just like in case of arrays. The value of the key put inside the square brackets will given. This operator can also be used for inserting elements by assigning the new key with its value like this name_of_map[new_key] = value Average time complexity is O(1) while worst case time complexity is O(n).
Capacity related methods
empty() — It returns 1 if the map is empty (has no elements) or returns 0 if the map isn’t empty. Time complexity of this method is O(1).
size() — It returns the number of key-value pairs in the map. Time complexity of this method is O(1).
Modify methods
insert() — It’s used to add key-value pairs to the map. There are two ways to use it:
name_of_map.insert({key, value})name_of_map.insert(std::make_pair(key, value))
Average time complexity is O(1) while worst case time complexity is O(n).
erase(key) / erase(iterator) / erase(iterator1, iterator2) — As you may have noticed, there are 3 ways to use the erase method. erase(key) removes the key-value pair of the input key. erase(iterator) removes the key-value pair pointed by the iterator given as input. erase(iterator1, iterator2) is used to remove a range of key-value pairs by giving two iterators as its input — the starting iterator(included) and the ending iterator(excluded). Average time complexity is O(1) while worst case time complexity is O(n).
clear() — It is used to delete all key-value pairs from the map. Time complexity of this method is O(n).
Search Methods
find(key) — It takes a ‘key’ as its input. If the ‘key’ exists, it returns an iterator to that ‘key’ in the map. If the ‘key’ doesn’t exists it returns a constant iterator which refers to end() iterator. Average time complexity is O(1) while worst case time complexity is O(n).
count(key) — It takes a ‘key’ as its input and returns 1 if the ’key’ exists in the map, else it returns 0. Average time complexity is O(1) while worst case time complexity is O(n).
Key and value from iterator
Suppose you have an iterator pointing to a key in your unordered map, and you want to know the key and its associated value, you can use name_of_iterator->first to obtain the key and name_of_iterator->second to obtain the value. You can also use *(name_of_iterator).first and *(name_of_iterator).second to obtain the key and value respectively.
std::unordered_set
Just like how sets are similar to map with just keys, unordered sets are similar to unordered maps with just keys. The elements stored in unordered set are not stored in any specific order. The time complexities of some operations are improved over normal sets.
Common Methods
Access methods
There are no explicit access methods. However, you can use find() method to get an iterator to refer to an element (if it exists).
find(parameter) — if you want to access an element, you can use this method which returns an iterator to the element passed in as the parameter. If the element doesn’t exist, it returns end() iterator. Average time complexity is O(1) while worst case time complexity is O(n).
Capacity related methods
size() — used to get the number of elements in the set. Time complexity of this method is O(1).
empty() — returns 1 if the set has no elements else it returns 0. Time complexity of this method is O(1).
Modify methods
insert(parameter) — This method is used to add elements to the sets. The element to be added needs to be passed as the parameter. Average time complexity is O(1) while worst case time complexity is O(n).
erase(parameter) — It’s used for erasing an element from the set. The element to be deleted needs to be passed as the parameter. In case the element you passed in was not present in the set it doesn’t throw any error. Average time complexity is O(1) while worst case time complexity is O(n).
clear() — It deletes all the elements stored in the set. Time complexity of the method is O(n).
Search methods
count(parameter) — helps you to get the count of an element in the set. Since elements are unique in sets, it can be used to check if an element exists or not in the set. Average time complexity is O(1) while worst case time complexity is O(n).
find(parameter) — if you want to access an element, you can use this method which returns an iterator to the element passed in as the parameter. If the element doesn’t exist, it returns end() iterator. Average time complexity is O(1) while worst case time complexity is O(n).
Conclusion
I tried my best to cover all the basics of this week’s C++ STL containers. I hope you got something useful out from this article and enjoyed it as much. I again emphasize that these are just the basics and you will learn more as you you code and face problems while using these containers. To know more about these containers and other containers in STL , you can visit cppreference.com.
