Associative containers always store data in sorted fashion. Associative containers are very efficient in searching a value with O( log n ) runtime complexity because of its sorted nature which allows us to perform binary search.
=> How are associative containers implemented ?
Associative containers are implemented through
self balancing binary search trees, more precisely
red black trees.
When we insert an element in the container,
it will be inserted in the tree in it proper location and if we remove an
element from the container, the tree will be rearranged/balanced so that
everything is still in order.
The default sorting criteria for
associative containers is '<'(less than), though a custom criteria
can also be provided.
There are 4 associative containers in C++ STL
:
1. set
2. map
3. multiset
4. multimap
1. set and multiset
|
Set cannot have duplicate items so if you try to insert an already
existing value, it will not be inserted.
set<int> st;
// create a set of integers
=> Inserting an element
st.insert(5); // st
= {5};
st.insert(1);
// st= {1,5};
st.insert(3);
// st= {1,3,5};
After insertion of every element, the data in set is
automatically sorted.
Time complexity :
O(log n) , irrespective of where the value is
inserted (in beginning, in middle or somewhere else) because it takes
logarithmic time to find its correct position in sorted order in a binary
search tree.
This member function returns a pair of values :
pair<set<int>::iterator, bool>
the bool value indicates whether insertion is successful(1) or it
failed(0) because of duplicate value.
If it succeeded, then the
iterator points to this new value, else if it failed it points to the existing
duplicate value corresponding to the value we tried to insert.
=> Searching an element
This is one of the most important feature of associative container. They
provide logarithmic time searching as compared to sequence containers which
provide linear time searching.
set<int>::iterator it = st.find(3);
Time complexity : O(log n)
Note: sequence containers
don't even provide a find function.
=> Erasing an element
a. using iterator
st.erase(it);
Time complexity : O(1)
b. erase by value
st.erase(3);
Time complexity : O(log n)
This member function automatically finds the element in the set
and erases it.
Note : sequence containers don't provide this
kind of erase.
=> Traversing set
We use the universal iterator traversal to traverse the elements(which is in
sorted order).
for(auto it=st.begin();it!=st.end();it++)
cout<<*it;
Now. let's discuss multiset.
As you might be guessing,
multiset is almost similar to set, it just has one difference that
it allows duplicates.
It also stores the values in sorted order
but may have multiple occurrences of the same value(unlike set).
multiset<int> ms;
ms.insert(3);
// ms={3};
ms.insert(5);
// ms = {3,5};
ms.insert(3);
// ms =
{3,3,5};
All the functions provided by set are also provided by
multiset.
Note : A very important point to remember is that
both set and multiset are read-only, i.e values in the container can
not be modified.
auto it=st.find(10);
*it = 10;
// assignment not
allowed.
Why ?
Think about this, if we modify any value inside
a set/multiset, the container may get corrupted as the elements may not be
sorted anymore .The container might lose its most important property due to
which it offered its advantages.
Properties of set/multiset :
1. Fast searching of elements. Time complexity : O(log n)
2.
No random access operator ( like vector/deque)
3. Slow traversal
2. map and multimap
Sometimes we don't want to sort the container by values of elements, but by
some key provided for every value.
They have the same interface as
set/multiset except that instead of directly storing values they
store key-value pairs.
Keys are actually used to position the elements in map/multimap,
the value just corresponds to the key.
map, just like set does not allow
duplicate keys.
Create a map from int(key) to char(value)
map<int,char> mp;
=> Inserting a value
A pair of values is inserted in map/multimap
Different forms :
1.
mp.insert(pair<int,char>(10,'c'));
2. Use make_pair function
mp.insert(make_pair(50,'b'));
3.
pair<int,char> p = make_pair(25,'b');
mp.insert(p);
4. Map also provides random access by key value using random access operator ('[ ]').
mp[15]='c'; // inserts
pair(15,'c') in map if not already present otherwise updates the value
Time Complexity : O(log n), similar to set
=> Searching a key
mp.find(20);
Searches for this
key and gets the key-value pair.
Time Complexity :
O(log n)
=> Traversing map
Use universal iterator traversal to traverse in sorted order. We can access
the key and value using the members of pair: first and second respectively.
for auto it=mp.begin();it!=mp.end();it++)
cout<<(*it).first<<" "<<(*it).second;
(*it).first can also be
written as it->first. Similarly,
(*it).second
can also be written as it->second.
This form is preferred mostly as it's more easier and takes less
time.
multimap is similar to map, just the difference is that
it allows duplicate keys.
Note for multiset and multimap :
find() member function returns an iterator to one of the value(multiset) or
key(multimap) in case of duplicates, which is typically the first
one.
Note for map/multimap : Keys
cannot be modified inside the container but their corresponding values can be
changed.
auto it = mp.find(10);
(*it).first = '20';
// error
(*it).second
= 'f';
// No error
=> Now you might be wondering,
why are all these containers called as "associative" ?
The
term "associative" actually refers to the key-value nature of map which
associates a value with a key. Think of set/multiset as special kind of map
where the key of any element is the same as its value.
=> How to provide custom sorting criteria in associative containers?
We need to use functor (a class/structure that overloads the ()
operator so it can be called like a function).
struct comp {
bool operator() (int x, int y)
{ // this is our custom comparator which
overrides default comparator
return x>y;
//
sort by decreasing order
}
};
Then declare set using this functor
set<int, comp> st;
// this will sort the set in decreasing order
Note : sort in decreasing order can also be written as
set<int, greater<int> > st;
=> Using associative container for user defined data types :
If we wish to stored user defined data types in associative container, we
must provide custom comparison function
otherwise compiler shows error as there is no internal implementation
available.
Consider a structure
struct Person{
int age;
string name;
};
Let's define a set for Person.
We define structure
'comp' as discussed before which provides custom comparison function. We sort
the set by age.
struct comp {
bool operator() (Person x, Person y)
{
return x.age > y.age;
}
};
Now declare set simply as:
set<Person, comp> st;
Other associative containers can also be implemented in similar
way.
=> Finally before the end of the article, let's check out two
important member functions provided by associative containers which are very
commonly used for multiset and multimap :
lower_bound(val) and
upper_bound(val).
lower_bound(val)
: searches for the first position corresponding to the value(or key in
multimap) 'val'.
upper_bound(val) :
searches for the first position corresponding to the first greater value(or
key in multimap) 'val'.
For example :
To get total number of elements with value 10, use :
int total_count = st.upper_bound(10) - st.lower_bound(10);
This completes our discussion of Associative containers. If you have
any doubts. please mention in the comments section.
Also check out other types of C++ STL containers if you missed them out :
1. Sequence Containers
2. Unordered Containers
Thank
you for your patience reading. If you enjoyed this post, I’d be very grateful
if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp
or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.