Sets and Maps
std::set
std::set is an associative container and header that need to be include for it is,
#include<set>
Benefits and Features of std::set:
It’s doesn’t allow duplicate elements i.e. it only contains unique elements.
Std::set can contain element of any specified type in template argument i.e.
std::set internally store elements in balanced binary tree.
By default std::set uses the operator < for comparing two elements and but if user passes the external sorting criteria i.e. comparator then it uses that instead of default operator <.
std::set will keep the inserted elements in sorted order based on the assigned sorting criteria i.e. either by default criteria operator < or by passed comparator (if passed).
Basic Example:
setOfNumbers.size()
in above example returns 3 because std::set only contains unique elements, so string “first” was added in the set only once and call to again insert “first” string was rejected.
It uses the operator < for comparison and keeps the all the elements in sorted order, in output above you can check that all strings are in sorted order.
How to iterate through std::set:
You can use iterators i.e.
But you cannot modify the elements using iterators because if you modify the element value then internal data structure of std::set
will get corrupt and it will not remain balanced binary search tree. Hence further additions and find operations will not work properly.
How to search an element in std::set:
Using find member function,
iterator find (const value_type& val) const;
It Searches the container for an element equivalent to val and returns an iterator to it if found, otherwise it returns an iterator to set::end
std::set
find example
Why should we use std::set::find member method instead of std::find standard generic algorithm?
Because find member function knows its internal data structure is balance binary search tree and hence designed to operate on that only therefore it will take much lesser time then standard algorithm std::find
How std::set verifies while insertion if element is already added or not:
By default std::set
uses the operator <
It internally maintains a binary balanced tree and during insertion it compares the new element with already present nodes and finds the right position of new element in tree. If that element is already present then it doesn’t insert the new element.
But wait a minute, if it uses the operator < for comparison of two elements then how it checks if two elements are equal or not with operator < ?
It uses the following logic to check if two elements like a and b are equal or not,
If a < b
is false and b
< a
is false
Then it means a and b are equal.
Example to verify insertion in std::set
How to remove an element in std::set :
Using member function erase i.e.
There are three overloaded versions of erase member function
Let’s see an example to erase element in std::set
std::map
Maps are used to replicate associative arrays. Maps contain sorted key-value pair, in which each key is unique and cannot be changed, and it can be inserted or deleted but cannot be altered. Value associated with keys can be altered. We can search, remove and insert in a map within O(n)
time complexity.
Benefits of using std::map :
It stores only unique keys and that too in sorted order based on its assigned sorting criteria.
As keys are in sorted order therefore searching element in map through key is very fast i.e. it takes logarithmic time.
In
std::map
there will be only one value attached with the every key.std::map
can be used as associative arrays.It might be implemented using balanced binary trees.
Lets see an example
Creating std::map objects
Creating a std::map
of words i.e.
Key = Word (std::string
)
Value = Word’s frequency count (int
)
As no external sorting criteria for key(std::string
) is specified in above std::map
, therefore it will use default key sorting criteria i.e operator < and all elements will be arranged inside std::map in alphabetical sorted order of keys.
Inserting data in std::map :
Inserting data using insert member function,
We can also insert data in std::map using operator [] i.e.
Different between operator [] and insert function:
If specified key already existed in map then operator [] will silently change its value where as insert will not replace already added key instead it returns the information i.e. if element is added or not. e.g.
Where as for insert member function,
will return false.
Iterating through all std::map elements:
Each entry in std::map<std::string, int>
is std::pair<std::string, int>
therefore through iterator, key can be accessed by it->first and value by it->second
Searching element in std::map by key
find member function of std::map
can be used to search element in std::map
by key. If specified key is not present then it returns the std::map::end
else an iterator to the searched element.
Searching element in std::map by Value
To search element in std::map
by value we need to iterate through all of the elements and check for the passed value and return i.e.
Deleting data from std::map
std::map
’s erase member function is used to delete the element in std::map
Code example
begin
, end
and find
begin
, end
and find
begin, end and find returns an iterator. begin()
returns the iterator to the starting entry of the map, end()
returns the iterator next to the last entry in the map and find()
returns the iterator to the entry having key equal to given key (passed as parameter).
Last updated